Drobouchevitch, Inna G. and Strusevich, Vitaly A. (2001) Two-stage open shop scheduling with a bottleneck machine. European Journal of Operational Research, 128 (1). pp. 159-174. ISSN 0377-2217 (doi:https://doi.org/10.1016/S0377-2217(99)00356-2)

Full text not available from this repository.

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 P6≠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 m⩾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.

Item Type:	Article
Additional Information:	[1] First published online: 20 December 2000. [2] Published in print: 1 January 2001.
Uncontrolled Keywords:	open shop scheduling, approximation algorithm, worst-case analysis
Subjects:	Q Science > QA Mathematics > QA76 Computer software
Pre-2014 Departments:	School of Computing & Mathematical Sciences School of Computing & Mathematical Sciences > Department of Mathematical Sciences School of Computing & Mathematical Sciences > Statistics & Operational Research Group
Related URLs:	Publisher Organisation
Last Modified:	14 Oct 2016 09:01
URI:	http://gala.gre.ac.uk/id/eprint/580

Actions (login required)

View Item