by Tautenhahn, T., Willenius, P..

**Series:** 2000-14, Preprints

- MSC:
- 90B35 Scheduling theory, deterministic

**Abstract:**

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.

**Keywords:**

open shop