(701h) Preprocessing and Tightening Methods for Time-Indexed Mixed-Integer Programming Chemical Production Scheduling Models

Over the last three decades, several research efforts have been made in order to incorporate different features that appear in scheduling problems. To this end, many Mixed-Integer Programming (MIP) models have been proposed to account for storage, utilities, limited resources, changeovers, maintenance, rescheduling, among other features, in addition to the basic assignment, sizing and timing of products in processing units. However, the main drawback of most of these models is that they can only handle small- to mid-scale instances. The challenge of solving large-scale industrial instances using MIP models has remained for the most part intractable.

Recently, Maravelias and coworkers have concentrated their efforts in enhancing the solution process for existing time-indexed, discrete and continuous, MIP scheduling models for problems in network production environments. They have shown that reformulations^1,2 and tightening methods^3,4 are particularly effective in reducing computational time and improving optimality gap of existing models, even when large-scale instances are considered⁵.

In this work⁶, we propose a series of preprocessing algorithms for the generation of strong valid inequalities (i.e. tightening) for MIP scheduling models, based on time- and inventory-related data. In particular, we use constraint propagation techniques to calculate different parameters that are then used to bound the number of times a subset of tasks can be executed in a feasible solution. We also extend some of the propagation ideas to generate three classes of new tightening constraints.

The first algorithm we propose calculates the effective time window available for a given task to be processed in a particular unit. To this end we divide the algorithm into two steps: (1) calculation of the earliest start time (EST) of a task in a given unit, using not only time-related information but also inventory data; and (2) calculation of the shortest tail(ST) to the end of the horizon of every task in its compatible units. The time window is then calculated by subtracting the EST and ST from the time horizon.

Next, a forward-propagation algorithm calculates the maximum feasible amount that every task can produce within its time window and the correspondent maximum amounts of each material that can be produced within the given horizon. The propagation reveals if a task is limited either by inventory (i.e. they have excess time in their window, but no additional input materials can be produced) or time (i.e. there is enough material to continue a task execution, but the time window is exceeded).

A new algorithm is then introduced to identify subsets of dependent tasks, whose number of batches are interrelated and their production is limited by one another. We define three main types of dependent groups: (I) tasks that share a processing unit, (II) tasks that share an input material, and (III) tasks that consume material produced by the same upstream unit. The first two types define explicit limitations due to the time window for the shared unit and the cumulative production of the common input material respectively. The third type defines an implicit relation between tasks based on the effect of limited material produced by dependent tasks in the upstream unit.

Finally, a fourth algorithm is used to determine the valid inequalities associated with the three types of dependent groups, based on the calculation of the convex hull for the feasible region defined by the number of batches of dependent tasks. These inequalities limit the number of times a subset of dependent tasks can be executed in a feasible solution.

The proposed methods result in tightening constraints expressed in terms of assignment binary variables (X_ijt=1 if task i is assigned to start on unit j at time point t) which are present in all time-indexed MIP models, therefore they are applicable to all time-indexed models accounting for a wide range of processing features.

We also propose an extension of the ideas introduced by the time window algorithm to the case where variable EST and ST are considered. Specifically, we develop tightening constraints expressed in terms of these new variables for (1) subsequent tasks, (2) tasks consuming a common material, and (3) tasks sharing the same unit. Nonetheless, we show that the constraints derived from the sequence of preprocessing algorithms produce the best results for both discrete- and continuous-time models.

We finally present an extensive computational study that includes 27 instances of three different networks commonly studied in the literature. Our methods are applied to one discrete-time (Shah et al.⁷) and two continuous-time (Sundaramoorthy and Karimi⁸, Gimenez et al.⁹). We show that significant reductions in computational time and optimality gap are achieved; in many cases, up to two orders of magnitude decrease in computational time is achieved when these constraints are applied to the discrete-time model.  We also apply these methods to solve to optimality a large-scale industrial instance that could not be solved by the original discrete-time formulation.

References

1. Velez, S.; Maravelias, C.T. Reformulations and Branching Methods for Mixed-Integer Programming Chemical Production Scheduling Models. Ind. Eng. Chem. Res. 2013, 52: 3832-3841.
2. Merchan, A.F.; Maravelias, C.T. Reformulations of Mixed-Integer Programming Continuous-Time Models for Chemical Production Scheduling. Ind. Eng. Chem. Res. 2014, 53: 10155-10165
3. Velez, S.; Sundaramoorthy, A.; Maravelias, C.T., Valid Inequalities Based on Demand Propagation for Chemical Production Scheduling MIP Models. AIChE J. 2013, 59: 872-887.
4. Merchan, A.F.; Velez, S.; Maravelias, C.T. Tightening Methods for Continuous-Time Mixed-Integer Programming Models for Chemical Production Scheduling. AIChE J. 2013, 59: 4461-4467
5. Velez, S.; Merchan, A.F.; and Maravelias, C.T. On the Solution of Large-Scale MIP Scheduling Models. Chem. Eng. Sci. 2015, Submitted.
6. Merchan, A.F.; Maravelias, C.T. Preprocessing and Tightening Methods for Time-Indexed MIP Chemical Production Scheduling Models. Comp. Chem. Eng. 2015, Submitted.
7. Shah, N.; Pantelides, C.C.; Sargent, R.W.H.. A General Algorithm for Short-Term Scheduling of Batch-Operations .2. Computational Issues. Comp. Chem. Eng. 1993, 17: 229-244
8. Sundaramoorthy, A.; Karimi, I.A. A simpler better slot-based continuous-time formulation for short-term scheduling in multipurpose batch plants. Comp. Chem. Eng. 2005, 60: 2679-2702
9. Gimenez, D.M.; Henning, G.P.; Maravelias, C.T. A novel network-based continuous-time representation for process scheduling: Part I. Main concepts and mathematical formulation. Comp. Chem. Eng. 2009, 33: 1511-1528