97-23
On the Hardness of the Classical Job Shop Problem
by Braesel, H.; Harborth, M.; Tautenhahn, T.; Willenius, P.
Preprint series: 97-23, Preprints
The paper is published: Ann. Oper. Res. (to appear)
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 orders, 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 schedule 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
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.