On the set of solutions of the open shop problem

In the classical open shop problem, n jobs have to be processed on m machines, 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 a set of sequences which are structurally optimal in the sense that there is at least one optimal sequence in this set for each instance of processing times. Such sequences are called irreducible. Investigations about irreducible sequences are believed to provide a powerful tool to improve 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.