New MILP models for the permutation flowshop problem

Abstract

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.

Keywords:

• computational analysis
• integer programming
• scheduling
• sequencing

^†Sadly, Ted Stafford passed away on 9 June 2007. This paper is dedicated to his memory.

^†Sadly, Ted Stafford passed away on 9 June 2007. This paper is dedicated to his memory.

Acknowledgements

The authors appreciated the useful comments from anonymous referees. Any remaining errors are the authors’ responsibility. Further, this research was partially supported by the awarding of a C. David Billings Faculty Fellowship, University of Alabama in Huntsville to each of the authors: Stafford (2003–2004), and Tseng (2004–2005).