(701f) Changeover Formulations for Discrete-Time Mixed-Integer Programming Scheduling Models

Scheduling problems can be addressed using a wide range of methods, including heuristics and metaheuristics, special-purpose scheduling algorithms, constraint programming, and mixed-integer programming (MIP). Mixed-integer programming methods can be used to model a range of problems under a number of different types of processing constraints, and multiple objective functions; while other methods are limited in the types of problems they can solve effectively. One limitation of MIP methods, especially discrete-time, however is the solution of problems with sequence-dependent changeover times, a feature that can have a significant effect on the scheduling of chemical processes. Accordingly, the goal of this work is to develop new methods for problems with sequence-dependent changeover times. We choose to study discrete-time models because they can be readily extended to account for a number of features (e.g., linear modeling of inventory and utility costs, intermediate release and due times, etc.).

We propose five new formulations to model sequence-dependent changeovers, which can be added to any discrete-time scheduling model to address problems with different objective functions and in various production environments. The new formulations are different from each other in terms of the number of tasks that are included in each constraint, and the number of time points that each type of constraint is written for. We also propose a valid inequality for makespan minimization problems, which significantly improves the computational performance. The new formulations are compared with literature models [1, 2, 3] in terms of tightness and computational performance.

Regarding the tightness of the models, we compare the relative strength of the formulations. Specifically, we develop nine propositions regarding the strength of pairs of formulations. When neither formulation is tighter, we find points that satisfy either one but not the other. It turns out that some of the new formulations are strictly tighter than the previously proposed ones. Furthermore, we prove that one of the proposed formulations is actually facet-defining for the problem that includes unit assignment constraints and changeover constraints; e.g., for a max profit problem where a task can be executed multiple times.

In terms of computation, we study different problems (single unit, parallel units, or parallel units with unequal capacities) and different objective functions (makespan, tardiness or cost minimization), using instances of various difficulty levels. Interestingly, we find that tighter formulations do not always lead to faster solution times. Finally, we show that some of the new formulations perform better than the previously proposed ones.

[1] Kondili, E.; Pantelides, C. C.; Sargent, R. W. H. A General Algorithm for Short-Term Scheduling of Batch-Operations .1. Milp Formulation. Comput Chem Eng 1993, 17 (2), 211-227.
[2] Shah, N.; Pantelides, C. C.; Sargent, R. W. H. A General Algorithm for Short-Term Scheduling of Batch-Operations .2. Computational Issues. Comput Chem Eng 1993, 17 (2), 229-244.
[3] Wolsey, L. A. MIP modelling of changeovers in production planning and scheduling problems. Eur J Oper Res 1997, 99 (1), 154-165.