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