New MILP models for the permutation flowshop problem

Two new mixed-integer linear programming (MILP) models for the regular permutation flowshop problem, called TBA and TS3, are derived using a combination of JAML (job-adjacency, machine-linkage) diagrams and variable substitution techniques. These new models are then compared to the incumbent best MILP models (Wilson, WST2, and TS2) for this problem found in the flowshop sequencing literature. We define the term best to mean that a particular model or set of models can solve a common set of test flowshop problems in significantly less time than other competing models. In other words, the two new MILP models (TBA and TS3) become the challengers to the current incumbent best models (Wilson, WST2, TS2.). Both new models are shown to require less time, on average, than the current best models for solving this set of problems; and the TS3 model is shown to solve these problems in statistically significantly less time than the other four models combined.