Reduction of permutation flowshop problems to single machine problems using machine dominance relations

Our hypothesis is that, under certain conditions of machine availability, or correlated processing times, the performance of a given sequence in a flowshop is largely determined by only one stage, thus effectively transforming the flowshop layout into a single machine. Since the single machine scheduling problem with makespan objective is a trivial problem where all feasible sequences are optimal, it would follow that, under these conditions, the equivalent PFSP-M is almost trivial. To address this working hypothesis from a general perspective, we investigate some conditions that allow reducing a permutation flowshop scheduling problem to a single machine scheduling problem, focusing on the two most common objectives in the literature, namely makespan and flowtime. Our work is a combination of theoretical and computational analysis, therefore several properties are derived to prove the conditions for an exact (theoretical) equivalence, together with an extensive computational evaluation to establish an empirical equivalence.