ALCOMFT-TR-02-82

Marjan van den Akker, Han Hoogeveen and Gerhard J. Woeginger
The two-machine open shop problem: to fit, or not to fit, that was the question
Utrecht. Work package 3. May 2002.

Abstract: We consider an open shop scheduling problem with two machines. Here each job consists of two operations, and it is prescribed that the first (second) operation has to be excuted by the first (second) machine. The order in which the two operations have to be scheduled is not fixed, but their execution intervals cannot overlap. The question that we are interested in is whether, given values D₁ and D₂, there exists a feasible schedule such that the first and second machine can process all jobs in the intervals [0,D₁] and [0,D₂], respectively. We present four necessary conditions for D₁ and D₂, which can be computed in O(n) time, and show that these conditions are sufficient as well by specifying an algorithm that constructs a feasible schedule if D₁ and D₂ satisfy these conditions. We further show that there are at most two nondominated points (D₁,D₂) for which there exists a schedule that fits.

\medskip\noindent Keywords. Scheduling, sequencing, open shop scheduling, flow shop scheduling, bicriterion optimization.

Postscript file: ALCOMFT-TR-02-82.ps.gz (82 kb).