(425f) Solution Methods for Discrete-Time Formulations for Scheduling in Multi-Stage Facilities

Solution Methods for Discrete-time Formulations for

Scheduling in Multi-stage Facilities

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

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

1415 Engineering Dr., Madison, WI 53706, USA

Most research on scheduling in multi-stage facilities focuses on models based on continuous representation of time¹. However, discrete-time mixed-integer programming (MIP) models have some distinct advantages, such as their extendibility. For example, they can be readily used to accommodate shared renewable resources (e.g. utilities, manpower), time-varying resource cost and availability, and linear modeling of inventories and resource utilization costs². At the same time, discrete-time scheduling formulations have some disadvantages as well. Since the decision variables are defined at each time point, the length of the time horizon and/or irregular time related data (e.g. processing times, release/due dates) have a high impact on the model size. Also, a predefined coarse time grid may lead to poor solution quality in some cases³. Thus, studies on solution methods for discrete-time formulations for scheduling in sequential environments is necessary.

In this work, we propose four different solution methods for discrete-time models for scheduling in multi-stage facilities. First, we develop tightening constraints based on fixed time windows. Using the earliest start and latest finish times of a unit, we develop a tightening constraint which enforces that the total processing time of all the batches assigned to that unit does not exceed its time window. Second, we propose a different tightening method based on variable time windows. Here, earliest start time and shortest tail of each batch are treated as variables, and are used to formulate constraints which limit the total time for a batch to be completed by its available time window. Then, we propose a simple reformulation by introducing a new discrete variable that denotes the total number of batches assigned to a unit. This reformulation leads to efficient bound improvements in the branch-and-bound algorithm, since branching on these variables facilitates pruning of multiple assignments at once. Finally, inspired by the fact that production schedules in sequential environment are highly influenced by the schedule of the bottleneck stage, we develop a priority-based branching method that enables us to put higher importance on the decision variables related to these stages and/or the corresponding units.

Furthermore, we develop a solution refinement method which refines an approximate solution obtained by a coarse discretization by resolving for the correct timing of process events. The main idea behind this method is that realistic timing of events can be recalculated using a continuous-time model⁴ by just solving a Linear Program (LP) with fixed assignments and sequencing obtained from the discrete-time models. To increase the probability of obtaining the optimal solution, we automatically generate a pool of solutions while solving the discrete-time model, in order to collect multiple candidates for the refinement process.

Finally, we perform an extensive computational study with more than 3000 runs to show the effectiveness of the solution methods proposed. We test the solution methods on different discrete-time models and different objective functions and we study various combinations of the proposed solution methods for each model and objectives. We show that our solution methods lead up to three order of magnitude improvement in the computational time thus allowing us to solve problems that were thought to be intractable.

1. Harjunkoski I, Maravelias CT, Bongers P, et al. Scope for industrial applications of production scheduling models and solution methods. Computers & Chemical Engineering. Mar 2014;62:161-193.

2. Velez S, Maravelias CT. Advances in Mixed-Integer Programming Methods for Chemical Production Scheduling. In: Prausnitz JM, Doherty MF, Segalman RA, eds. Annual Review of Chemical and Biomolecular Engineering, Vol 5. Vol 5. Palo Alto: Annual Reviews; 2014:97-121.

3. Floudas CA, Lin XX. Continuous-time versus discrete-time approaches for scheduling of chemical processes: a review. Computers & Chemical Engineering. Oct 2004;28(11):2109-2129.

4. Mendez CA, Henning GP, Cerda J. An MILP continuous-time approach to short-term scheduling of resource-constrained multistage flowshop batch facilities. Computers & Chemical Engineering. May 2001;25(4-6):701-711.