Two mixed integer linear programming models for the N × M sequence dependent set-up times flowshop sequencing problem

This paper presents the derivation and evaluation of two new MILP models for the SDST flowshop sequencing problem. The first model, TS1, was derived directly from the assignment-problem-based MILP model for the regular flow-shop that Stafford modified from the original Wagner three-machine all-integer model. The second model, TS2, combined the properties of model TS1 with the looser constraints approach of Srikar and Ghosh, as modified by Stafford and Tseng (model SG*). Three experiments were used to compare both new models to the SG* model. Both new models were found to use significantly less computation time than the SG* model, especially for problem sizes of 6 or more jobs and 5 or more machines. The TS1 model used significantly less computation time than the TS2 model, making it the current best MILP model in the SDST flowshop literature.