Mathematical formulations and an enhanced column generation for the hybrid flow shop scheduling problem

Abstract This study addresses a hybrid flow shop scheduling problem with multiple production stages, where at least one stage includes parallel machines with sequence- and machine-dependent setup times. The objective is to minimize the total completion time. Our approach enables seamless reconfiguration by simply adjusting input parameters, making it suitable for industries that face frequent changes in machine availability and workforce allocation. Two mathematical formulations are proposed: a flow-based model and a set-partitioning model using positional variables. The main novelty of this work lies in these two new formulations that avoid the use of “Big M” constants in disjunctive constraints by introducing dummy jobs. This strategy leads to stronger linear relaxations and more accurate lower bounds. Additionally, an Enhanced Column Generation ( ECG ) approach is introduced to solve the set-partitioning model, generating variables on demand. An iterated local search provides an initial set of columns and an upper bound. Computational experiments demonstrate that ECG reduces the GAP by 9.76% and the relative deviation of the lower bound by 8.96%, compared to the flow-based model, though at a higher computational cost. Performance Profiles confirm that ECG finds more best-known solutions but struggles with larger instances. Both formulations outperform existing models in the literature, reducing the relative deviation of the lower bound by at least 14.19 p.p (16.77% - 2.58%). Furthermore, they improve the GAP by 26.88 p.p. (46.66% - 19.78%) for FB and 36.64 p.p. (46.66% - 10.02 %) for ECG on average, confirming their effectiveness. These results highlight the superiority of the proposed models for solving hybrid flow shop scheduling problems.