On the set of solutions of the open shop problem

In the classical open shop problem, n jobs have to be processedon 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 iscalled a (multi‐) sequence. We investigatea set of sequences which are structurally optimal in the sense that there is at least oneoptimal sequence in this set for each instance of processing times. Such sequences arecalled irreducible. Investigations about irreducible sequences are believed to provide apowerful tool to improve exact and heuristic algorithms. Furthermore, structural propertiesof sequences are important for problems with uncertain processing times.We prove necessary and sufficient conditions for the irreducibility of a sequence. Forseveral values of n and m, we give the numbers of allsequences, of the sequences satisfying each of these conditions and of the irreduciblesequences, respectively. It turns out that only a very small fraction of all sequences isirreducible. Thus, algorithms which work only on the set of irreducible sequences insteadof the set of all sequences can potentially perform much better than conventional algorithms. Copyright Kluwer Academic Publishers 1999