Article ID: | iaor19991211 |
Country: | United States |
Volume: | 45 |
Issue: | 7 |
Start Page Number: | 705 |
End Page Number: | 731 |
Publication Date: | Oct 1998 |
Journal: | Naval Research Logistics |
Authors: | Strusevich V.A., Shafransky Yakov M. |
Keywords: | programming: dynamic |
The paper considers the open shop scheduling problem to minimize the makespan, 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