Shafransky, Y.M. and Strusevich, V.A. (1998) The open shop scheduling problem with a given sequence of jobs on one machine. Naval Research Logistics (NRL), 45 (7). pp. 705-731. ISSN 0894-069X (Print), 1520-6750 (Online) (doi:10.1002/(SICI)1520-6750(199810)45:7<705::AID-NAV4>3.0.CO;2-F)

Full text not available from this repository.

Abstract

The paper considers the open shop scheduling problem to minimize the make-span, provided that one of the machines has to process the jobs according to a given sequence. We show that in the preemptive case the problem is polynomially solvable for an arbitrary number of machines. If preemption is not allowed, the problem is NP-hard in the strong sense if the number of machines is variable, and is NP-hard in the ordinary sense in the case of two machines. For the latter case we give a heuristic algorithm that runs in linear time and produces a schedule with the makespan that is at most 5/4 times the optimal value. We also show that the two-machine problem in the nonpreemptive case is solvable in pseudopolynomial time by a dynamic programming algorithm, and that the algorithm can be converted into a fully polynomial approximation scheme. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 705–731, 1998

Item Type:	Article
Uncontrolled Keywords:	open shop,complexity, approximation
Subjects:	Q Science > QA Mathematics
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
Last Modified:	14 Oct 2016 08:59
URI:	http://gala.gre.ac.uk/id/eprint/124

Actions (login required)

View Item