Mixed integer programming (MIP) modelling 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 reformulation, or by the addition of valid inequalities. The main topic examined is the handling of changeovers, both sequence-independent and -dependent, in production planning and machine sequencing, with in the background the question of how to model time. We first present results for lot-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 of Karmarkar and Schrage that is effective in modelling changeovers. Then we present various extensions and an application to machine sequencing with the unit flow formulation. We terminate with brief sections on the use of dynamic programming and of time-indexed formulations, which provide two alternative approaches for the treatment of time.