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

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

0.00 Avg rating0 Votes
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: ,
Keywords: programming: dynamic
Abstract:

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 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 polynominal approximation scheme.

Reviews

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