Novel MILP Models for Scheduling Permutation Flowshops

摘要

Flowshop scheduling via mixed integer linear programming (MILP) has received considerablenattention in the past four decades. However, alternate models are limited; most numerical studiesnhave used small problem sizes. A need for good model evaluation methodology exists; and limitednwork exists on flowshops with no intermediate storage. This paper presents a classification ofnflowshops and MILP scheduling models, and addresses some of these issues. It develops a host ofnnew MILP formulations for minimizing makespan in a permutation flowshop with no storage andnwith or without unit setups. It presents some useful insights into model building by employing anvariety of new and old binary variables and coupling them creatively. In contrast to previous work,nit evaluates a range of new and existing MILP models using many larger test problems with no ornunlimited intermediate storage, and presents a reliable procedure to rank various models based onnproblems with varying data and sizes. It shows that the top models for the two flowshops indeednshow slightly different computational performance.