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)