Zurück zu den Preprints des Jahres 2000


Irreducible sequences on tree-like operation sets

by Tautenhahn, T..

Series: 2000-33, Preprints

90B35 Scheduling theory, deterministic

We consider the classical open shop problem to minimize
For this problem, a semi-active schedule can easily be
from the processing times and a sequence, i.e., a feasible
combination of job orders and machine orders. A sequence is
irreducible if there exists no other sequence such that
this other sequence leads to
a smaller or equal makespan for any choice of processing
The question how to decide in polynomial time wheter a given
sequence is irreducible is open up to now. We answer this
question in the case that the underlying operation set has
tree structure. For this case in which the open shop problem
itself remains unary NP-hard we can test irreducibility of a
sequence in linear time. Furthermore, we consider unavoidable
sequences, i.e., sequences which are uniquely optimal for
some instance of processing times. Unavoidable sequences
are essential for the search of minimal sequence sets with the
property that for each instance of processing times this set
contains an optimal sequence. We give a necessary condition for
unavoidability of a sequence which is conjectured to be
sufficient too.

open shop