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 ‘⪰’ on the set of sequences, i.e., feasible combinations of job orders and machine orders, with the property that A ⪰ B implies that the makespan of the semiactive schedule corresponding to sequence B is less than 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 ⪰ 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.
