Zurück zu den Preprints des Jahres 2000


2000-33

Irreducible sequences on tree-like operation sets

by Tautenhahn, T..


Series: 2000-33, Preprints

MSC:
90B35 Scheduling theory, deterministic

Abstract:
We consider the classical open shop problem to minimize
makespan.
For this problem, a semi-active schedule can easily be
computed
from the processing times and a sequence, i.e., a feasible
combination of job orders and machine orders. A sequence is
called
irreducible if there exists no other sequence such that
this other sequence leads to
a smaller or equal makespan for any choice of processing
times.
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.

Keywords:
open shop