by Braesel, H., Harborth, M., Tautenhahn, T., Willenius, P..

**Series:** 1997-23, Preprints

- MSC:
- 90B35 Scheduling theory, deterministic
- 90C27 Combinatorial optimization

**Abstract:**

In a classical job shop problem n jobs have to be processed on m machines where

the machine orders of the jobs are given. Computational experiments show that

there are huge differences in the hardness of the job shop problem to minimize

makespan depending on the given machine orders. We study a partial order ` 4'

on the set of sequences, i.e., feasible combinations of job orders and machine or-

ders, with the property that A 4 B implies that the makespan of the semiactive

schedule corresponding to sequence B is less or equal to the makespan of any sched-

ule corresponding to A. The minimal sequences according to this partial order are

called irreducible. We present a polynomial algorithm to decide whether A 4 B

holds and we develop a new enumeration algorithm for irreducible sequences. To

explain the differences in the hardness of job shop problems, we study the relation

between the hardness of a job shop problem and the number of irreducible sequences

corresponding to the given machine orders.

**Keywords:**

open shop, job shop, irreducible sequences, enumeration

**This paper was published in:**

Ann. Oper. Res. (to appear)