97-15
On the Set of Solutions of an Open Shop Problem
by Bräsel, H.; Harborth, M.; Tautenhahn, T.; Willenius, P.
Preprint series: 97-15, Preprints
The paper is published: Ann. Oper. Res. (to appear)
- MSC:
- 90B35 Scheduling theory, See also {68M20}
- 90C27 Combinatorial optimization
- 05A15 Exact enumeration problems, generating functions, See Also {33Cxx, 33Dxx}
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 iscalled a (multi-)sequence. We investigate sequences which are structurallyoptimal in the sense that there exists no structurally different sequencewhich leads to a schedule with smaller or equal makespan for each setof processing times. Such sequences are called irreducible. Investigationsabout irreducible sequences are believed to provide a powerful tool to im-prove 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 ofa sequence. For several values of n and m we give the numbers of allsequences, of the sequences satisfying each of these conditions and of theirreducible sequences, respectively. It turns out that only a very smallfraction of all sequences is irreducible. Thus, algorithms which work onlyon the set of irreducible sequences instead of the set of all sequences canpotentially perform much better than conventional algorithms.
Keywords: open shop, irreducible sequence, number results, enumeration
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.