Zurück zu den Preprints des Jahres 2000


How Many Sequences Solve an Open Shop Problem?

by Tautenhahn, T., Willenius, P..

Series: 2000-14, Preprints

90B35 Scheduling theory, deterministic

We consider the classical open shop problem to
minimize makespan. For this problem, a feasible combination
of all job ordes and machine orders is called a sequence.
Structural investigations lead to a dominance relation
between sequences in the sense that if a sequence A
dominates a sequence B then the makespan of A is smaller than
or equal to the makespan of B independently of the given
processing times. In this paper we generalize this concept
by examination a dominance relation between sets of sequences.
We give several necessary and sufficient conditions for a
sequence to be dominated by a set of other sequences.
Moreover, we show that this relation can be formulated as a
mixed integer program. Using these results, for some small
formats we are able to compute a minimal set of sequences with
the property that for any choise of processing times this
set contains at least one optimal sequence.

open shop