Heuristics for short route job shop scheduling problems

Heuristics for short route job shop scheduling problems

0.00 Avg rating0 Votes
Article ID: iaor2000178
Country: Germany
Volume: 48
Issue: 3
Start Page Number: 359
End Page Number: 375
Publication Date: Jan 1998
Journal: Mathematical Methods of Operations Research (Heidelberg)
Authors: ,
Keywords: job shop
Abstract:

We consider two ‘minimum’ NP-hard job shop scheduling problems to minimize the makespan. In one of the problems every job has to be processed on at most two out of three available machines. In the other problem there are two machines, and a job may visit one of the machines twice. For each problem, we define a class of heuristic schedules in which certain subsets of operations are kept as blocks on the corresponding machines. We show that for each problem the value of the makespan of the best schedule in that class cannot be less than 3/2 times the optimal value, and present algorithms that guarantee a worst-case ratio of 3/2.

Reviews

Required fields are marked *. Your email address will not be published.