Zurück zu den Preprints des Jahres 1997


1997-15

On the Set of Solutions of an Open Shop Problem

by Bräsel, H., Harborth, M., Tautenhahn, T., Willenius, P..


Series: 1997-15, Preprints

MSC:
90B35 Scheduling theory, deterministic
90C27 Combinatorial optimization
05A15 Exact enumeration problems, generating functions

Abstract:
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.

Keywords:
open shop, irreducible sequence, number results, enumeration

This paper was published in:
Ann. Oper. Res. (to appear)