A combinatorial analysis of the permutation and non-permutation flow shop scheduling problems

Abstract

In this paper we introduce a novel approach to the combinatorial analysis of flow shop scheduling problems for the case of two jobs, assuming that processing times are unknown. The goal is to determine the dominance properties between permutation flow shop (PFS) and non-permutation flow shop (NPFS) schedules. In order to address this issue we develop a graph-theoretical approach to describe the sets of operations that define the makespan of feasible PFS and NPFS schedules (critical paths). The cardinality of these sets is related to the number of switching machines at which the sequence of the previous operations of the two jobs becomes reversed. This, in turn, allows us to uncover structural and dominance properties between the PFS and NPFS versions of the scheduling problem. We also study the case in which the ratio between the shortest and longest processing times, denoted ρ, is the only information known about those processing times. A combinatorial argument based on ρ leads to the identification of the NPFS schedules that are dominated by PFS ones, restricting the space of feasible solutions to the NPFS problem. We also extend our analysis to the comparison of NPFS schedules (with different number of switching machines). Again, based on the value of ρ, we are able to identify NPFS schedules dominated by other NPFS schedules.