Zurück zu den Preprints des Jahres 1997


On the Hardness of the Classical Job Shop Problem

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

Series: 1997-23, Preprints

90B35 Scheduling theory, deterministic
90C27 Combinatorial optimization

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.

open shop, job shop, irreducible sequences, enumeration

This paper was published in:
Ann. Oper. Res. (to appear)