2022 Annual Meeting

(658d) Strengthening Production Scheduling Formulations By Incorporating Record Keeping Variables

Authors

Maravelias, C. T., Princeton University
Production scheduling is a necessary component of decision making in almost every industry and, as such, much work has been done in order to develop specialized modeling techniques and optimization methods that account for the various process characteristics present in each application within each industry (Harjunkoski et al. 2014, Georgiadis, Elekidis, and Georgiadis 2019). However, the development of sophisticated optimization models capable of aiding one in making complicated decisions related to production scheduling often results in extremely large, complex models that are difficult to solve in reasonable time. For this reason, we focus this work on techniques that allow one to significantly reduce the computational overhead of solving general production scheduling problems. Our motivation is that, by improving the quality of the formulation used to represent the general production scheduling problem that serves as the foundation for more complex variants of this problem, we may achieve improved performance for a wide variety of classes of challenging production scheduling problems.

The current work is highly motivated by that of Velez and Maravelias (Velez and Maravelias 2013) who showed that the incorporation of a relatively small number of additional integer variables and associated constraints into the formulation of a production scheduling problem can significantly reduce the CPU time required to solve instances of that problem. We extend this work by considering additional integer variables and associated constraints that can be incorporated alongside those proposed by Velez and Maravelias in order to achieve further reductions in the computational resources required to solve problem instances. Each of the variables that we add to the problem's formulation serves to keep record of a quantity of interest and, as such, we refer to these variables as record keeping variables. Examples of quantities that one way wish to keep record of using a record keeping variable include the number of times a particular task will be executed during the scheduling horizon, the total number of tasks that will be executed by a particular unit during the scheduling horizon, etc.

We demonstrate the utility of including record keeping variables in a problem's formulation by presenting the results of four computational tests. In the first, we compare the performance of a standard branch-and-bound solution procedure when applied to problem formulations including carefully chosen subsets of our proposed record keeping variables. In the second test, we explore whether or not additional reductions in solution time can be obtained by imposing a hierarchical set of branching priorities on the various binary and integer variables present in a problem's formulation, including the proposed record keeping variables. In the third test, we study the ways in which the inclusion of record keeping variables in a problem's formulation impact the presolve, cut generation, heuristic, and branching phases of the branch-and-bound procedure. Finally, in test four, we assess the utility of problem formulations involving record keeping variables when additional process characteristics such as limits on utility consumption or variable processing times are accounted for in the base model. The results of our tests indicate that the inclusion of record keeping variables in the formulation of a production scheduling problem can significantly reduce the total solution time.

References:

I. Harjunkoski, C. T. Maravelias, P. Bongers, P. M. Castro, S. Engell, I. E. Grossmann, J. Hooker, C. Méndez, G. Sand, J. Wassick, “Scope for industrial applications of production scheduling models and solution methods.” Computers & Chemical Engineering 62 (2014) 161–193.

G. P. Georgiadis, A. P. Elekidis, M. C. Georgiadis, “Optimization-based scheduling for the process industries: from theory to real-life industrial applications.” Processes 7 (2019) 438.

S. Velez, C. T. Maravelias, “Reformulations and branching methods for mixed-integer programming chemical production scheduling models.” Industrial & Engineering Chemistry Research 52 (2013) 3832–3841.