MIP MODELING OF CHANGEOVERS IN PRODUCTION PLANNING AND SCHEDULING PROBLEMS

The goal here is to survey some recent and not so recent work that can be used to improve problem formulations either by a priori reformulat ion, or by the addition of valid inequalities. The main topic examined is the handling of changeovers, both sequence-independent and -depend ent, in production planning and machine sequencing, with in the backgr ound the question of how to model time. We first present results for l ot-sizing problems, in particular the interval submodular inequalities of Constantino that provide insight into the structure of single item problems with capacities and start-ups, and a unit flow formulation o f Karmarkar and Schrage that is effective in modelling changeovers. Th en we present various extensions and an application to machine sequenc ing with the unit flow formulation. We terminate with brief sections o n the use of dynamic programming and of time-indexed formulations, whi ch provide two alternative approaches for the treatment of time. (C) 1 997 Elsevier Science B.V.