by Bräsel, H., Harborth, M., Tautenhahn, T., Willenius, P..
Series: 1997-15, Preprints
In a classical open shop problem n jobs have to be processed on m ma-
chines where both job orders and machine orders can be chosen arbitrarily.
A feasible (i.e., acyclic) combination of all job orders and machine orders is
called a (multi-)sequence. We investigate sequences which are structurally
optimal in the sense that there exists no structurally different sequence
which leads to a schedule with smaller or equal makespan for each set
of processing times. Such sequences are called irreducible. Investigations
about irreducible sequences are believed to provide a powerful tool to im-
prove exact and heuristic algorithms. Furthermore, structural properties
of sequences are important for problems with uncertain processing times.
We prove necessary and sufficient conditions for the irreducibility of
a sequence. For several values of n and m we give the numbers of all
sequences, of the sequences satisfying each of these conditions and of the
irreducible sequences, respectively. It turns out that only a very small
fraction of all sequences is irreducible. Thus, algorithms which work only
on the set of irreducible sequences instead of the set of all sequences can
potentially perform much better than conventional algorithms.
open shop, irreducible sequence, number results, enumeration
This paper was published in:
Ann. Oper. Res. (to appear)