The Open Shop Scheduling Problem with a Non-Bottleneck Machine

Vitaly A.Strusevich and Leslie A. Hall

This paper considers the problem of processing n jobs in a two-machine non-preemptive open shop to minimize the makespan, i.e., the maximum completion time. One of the machines is assumed to be non-bottleneck. It is shown that, unlike its flow shop counterpart, the problem is NP-hard in the ordinary sense. On the other hand, the problem is shown to be solvable by a dynamic programming algorithm that requires pseudopolynomial time. The latter algorithm can be converted into a fully polynomial approximation scheme that runs in O(n^2/epsilon) time. An O(n log n) approximation algorithm is also designed which finds a schedule with makespan at most 5/4 times the optimal value, and this bound is tight.

Keywords: open shop, complexity, dynamic programming, fully polynomial approximation scheme, worst-case analysis, approximation.