Novel MILP models for scheduling permutation flowshops

Abstract

Flowshop scheduling via mixed integer linear programming (MILP) has received considerable attention in the past four decades. However, alternate models are limited; most numerical studies have used small problem sizes. A need for good model evaluation methodology exists; and limited work exists on flowshops with no intermediate storage. This paper presents a classification of flowshops and MILP scheduling models, and addresses some of these issues. It develops a host of new MILP formulations for minimizing makespan in a permutation flowshop with no storage and with or without unit setups. It presents some useful insights into model building by employing a variety of new and old binary variables and coupling them creatively. In contrast to previous work, it evaluates a range of new and existing MILP models using many larger test problems with no or unlimited intermediate storage, and presents a reliable procedure to rank various models based on problems with varying data and sizes. It shows that the top models for the two flowshops indeed show slightly different computational performance. © 2008 Berkeley Electronic Press. All rights reserved.