In this paper the authors consider classical shop problems: n jobs have to be processed on m machines. The processing time piÅ,j of job i on machine j is given for all operations (i,j). Each machine can process at most one job at a time and each job can be processed at most on one machine at a given time. The machine orders are fixed (job-shop) or arbitrary (open-shop). The authors have to determine a feasible combination of machine and job orders, a so-called sequence, which minimizes the makespan. They introduce a partial order on the set of sequences with the property that there exists at least one optimal sequence in the set of minimal elements of this partial order independent of the given processing times. The set of minimal elements (set of irreducible sequences) can be in detail described in the case of the two machine open-shop problem. The cardinality is calculated. The authors will show which sequences are generated by the well-known polynomial algorithms for the construction of optimal schedules. Furthermore, they investigate the problem O||CÅmax on an operation set with spanning tree structure.
