Open‐shop dense schedules: properties and worst‐case performance ratio

Open‐shop dense schedules: properties and worst‐case performance ratio

0.00 Avg rating0 Votes
Article ID: iaor2012921
Volume: 15
Issue: 1
Start Page Number: 3
End Page Number: 11
Publication Date: Feb 2012
Journal: Journal of Scheduling
Authors: , , ,
Keywords: manufacturing industries, heuristics, combinatorial optimization
Abstract:

Dense schedules are easy to construct and can be used as heuristic solutions for open‐shop problems. It is conjectured that in the worst‐case a dense schedule will result in a makespan no more than ( 2 1 m ) equ1 times of the makespan of the optimal schedule, where m is the number of machines. Different approaches have been used in proofs for different number of machines. The conjecture has been proved for the number of machines m≤6, and for some special types of dense schedules. In this paper, we first summarize some useful properties of dense schedules, and then provide some special types of dense schedules that make the conjecture hold. Finally, we give complete proofs of the conjecture for m=7 and 8.

Reviews

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