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.

Recommended Citation

Pitty, Suresh S. and Karimi, Iftekhar A. (2008) "Novel MILP Models for Scheduling Permutation Flowshops," Chemical Product and Process Modeling: Vol. 3 : Iss. 1, Article 22.
Available at: http://www.bepress.com/cppm/vol3/iss1/22