Two-stage open shop scheduling with a bottleneck machine

Two-stage open shop scheduling with a bottleneck machine

0.00 Avg rating0 Votes
Article ID: iaor20013909
Country: Netherlands
Volume: 128
Issue: 1
Start Page Number: 159
End Page Number: 174
Publication Date: Jan 2001
Journal: European Journal of Operational Research
Authors: ,
Keywords: computational analysis
Abstract:

It is known that for the open shop scheduling problem to minimize the makespan there exists no polynomial-time heuristic algorithm that guarantees a worst-case performance ratio better than 5/4, unless P=NP. However, this result holds only if the instance of the problem contains jobs consisting of at least three operations. This paper considers the open shop scheduling problem, provided that each job consists of at most two operations, one of which is to be processed on one of the 2 machines, while the other operation must be performed on the bottleneck machine, the same for all jobs. For this NP-hard problem we present a heuristic algorithm and show that its worst-case performance ratio is 5/4.

Reviews

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