(425c) Discrete-Time Mixed-Integer Programming Models for Scheduling in Sequential Environments

Discrete-time Mixed-Integer Programming Models for

Scheduling in Sequential Environments

Hojae Lee, Andres F. Merchan, and Christos T. Maravelias

Department of Chemical and Biological Engineering, University of Wisconsin-Madison

1415 Engineering Dr., Madison, WI 53706, USA

Most mixed-integer programming (MIP) models that have been developed to address problems in sequential production environments (e.g., multi-stage processes) adopt a continuous modeling of time. The major disadvantage of these models is that accommodating common process features such as shared renewable resources and time-varying resources leads to nonlinearities in the model or introduction of additional variables and constraints. On the other hand, discrete-time representation offers a natural framework to model such type of features without significant increase in the complexity of the model. Moreover, a previous study has shown that discrete-time formulations are not only more effective in terms of computational time, but also in finding better solutions¹.

In this work, we study four discrete-time MIP models for short-term scheduling in multi-stage facilities with non-uniform parallel units. First, we revisit the Resource-Task Network (RTN) based model originally proposed by Castro and Grossmann², where resource balance constraints are enforced for both batches and units. Then, we develop a State-Task Network (STN) based model, in which clique constraints are used to enforce unit utilization, in place of the unit balance constraints in the previous model. Next, we propose two models inspired from the time-aggregated and disaggregated formulations for the Resource-Constrained Project Scheduling Problem (RCPSP)^3,4. The batch precedence constraints in these models are inspired from the precedence constraints written for activities and their successors in the RCPSP formulations.

Furthermore, we propose modeling extensions to account for a more complicated production environment, namely multi-purpose facilities. In the multi-purpose facilities, each product goes through a series of product-specific stages, which consist of multi-purpose units that may belong to different stages for different products⁵. To explicitly model product-specific routing and the multi-purpose units, we introduce new sets to denote product-specific stages for each batch and units that belong to a specific stage of a batch, respectively.

We also propose extensions to model intermediate batch storage for both production environments. Since we model the storage of each intact batch, we only consider vessel compatibility, neglecting vessel capacity. For RTN- and STN-based models, we implicitly model the storage of intermediate batches through vessel and batch balance constraints. In the RCPSP inspired models, additional flow variables are introduced to explicitly model batch flow in and out of the vessels.

We provide illustrative examples to showcase the advantages of the proposed discrete-time formulations in modeling limited and time-varying resources. Furthermore, through computational study, we compare the four models with continuous-time models to show the effectiveness of the proposed formulation in terms of computational efficiency.

Reference

1. Sundaramoorthy A, Maravelias CT. Computational Study of Network-Based Mixed-Integer Programming Approaches for Chemical Production Scheduling. Industrial & Engineering Chemistry Research. May 4 2011;50(9):5023-5040.

2. Castro PM, Grossmann IE. New continuous-time MILP model for the short-term scheduling of multistage batch plants. Industrial & Engineering Chemistry Research. Nov 2005;44(24):9175-9190.

3. Pritsker AAB, Waiters LJ, Wolfe PM. Multiproject Scheduling with Limited Resources: A Zero-One Programming Approach. Management Science. 1969;16(1):93-108.

4. Christofides N, Alvarez-Valdes R, Tamarit JM. Project Scheduling with Resource Constraints â?? A Branch and Bound Approach. European Journal of Operational Research. Jun 1987;29(3):262-273.

5. Maravelias CT. General framework and modeling approach classification for chemical production scheduling. Aiche Journal. Jun 2012;58(6):1812-1828.