# The open shop scheduling problem with a given sequence of jobs on one machine

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)

## 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: | |

Last Modified: | 14 Oct 2016 08:59 |

URI: | http://gala.gre.ac.uk/id/eprint/124 |

### Actions (login required)

View Item |