(356b) Time Representations and Mathematical Models for Process Scheduling Problems

A classical strategy to process scheduling problems in the chemical industry is to develop a mathematical formulations and use commercial or academic solvers to obtain a good feasible solution. In the area of scheduling, the relationship between problem description and mathematical model is not always well understood. In particular, many different MILP models have proposed, corresponding to different types of representation of time.

In this work, we study four important time representations (Floudas and Lin 2004, Mouret et al. 2009) which are denoted by Multi-Operations Sequencing (MOS), MOS with Synchronized Start Times (MOS-SST), MOS with Fixed Start Times (MOS-FST), and Single-Operations Sequencing (SOS). Each of these representation is decribed using the common concept of priority-slots, which can be seen as a generalization of time-points, time-slots, or event-points. A solution to the scheduling problem is represented by a set of operations which are assigned to priority-slots in order to determine their scheduling priority. Each selected operation is to be executed as many times as it is assigned to a priority-slot. The assignments of operations to priority-slots defines a sequence of operations which contains the following informations: the set of operations to be executed, the number of executions of each operation, and the order of execution of these operations.

The MOS time representation is the most general: multiple operations may be assigned to each priority-slot and the sequencing of operations depends on their assigned priority. The MOS-SST time representation is a special case of MOS: all operations assigned to a given priority-slot must start at the same time. Therefore, a variable time point is associated to each priority-slot, thus defining the start time of all operations assigned to it. The MOS-FST time representation is a special case of MOS-SST in which the time points are fixed a priori, thus leading to a discrete-time formulation (as in Kondili et al., 1993). The SOS time representation is a special case of MOS in which exactly one operation must be assigned to each priority-slot.

Although multiple MILP models can make use of the same time representation, thus leading to solutions with identical objective value, a unique mathematical formulation is derived for each time representation. In order to outline the common features and main differences between these time representations, the same sets, parameters and variables are used in all models. Only a few constraints vary from one model to the other.

Additionality, we present automatic strengthening techniques based on the structure of the scheduling constraints of the problems to be solved. In particular, the notion of non-overlapping graph is introduced and used in order to generate strengthening constraints that can lead to tighter and more compact formulations leading to smaller CPU times.

To solve these models and obtain the optimal number of priority-slots, three solution algorithms are presented. The additive approach consists of iteratively increasing the number of priority-slots by 1 until a given stopping criterion is satisfied. This basic approach can be improved by using cutoff and introducing a new constraint in order to force all priority-slots to be used in the solution at each iteration. It is used to solve models based on the MOS and MOS-SST time representations. The multiplicative approach consists of iteratively multiplying the number of priority-slots by 2 until a given stopping criterion is satisfied. This approach is used to solve models based on the MOS-FST time representation. The direct approach simply consists of selecting a specific number of priority-slot and solve the corresponding model. It is used for the SOS time representation when the number of priority-slot can be determined a priori (see Mouret et al., 2009).

These approaches are applied to different problems ranging from single-stage and multi-stage batch scheduling problem (Pinto and Grossmann, 1995) to crude-oil operations scheduling problems (Lee et al., 1996). The results show that the same mathematical formulations can be efficiently applied to solve each of these types of scheduling problems. Theoretical results on the relationship between the different time representations are also demonstrated.

This work can be helpful for modelers who intend to better understand the various time representations that have been developed and efficiently test and select the most adequate model for a given scheduling problem.

References:

1) Floudas, C. A. and Lin, X. (2004). Continuous-time versus discrete-time approaches for scheduling of chemical processes: a review. Computers and Chemical Engineering, 28:2109?2129.

2) Mouret, S., Grossmann, I. E. and Pestiaux, P. (2009). A novel priority-slot based continuous-time formulation for crude-oil scheduling problems. Industrial and Engineering Chemistry Research, 48(18):8515?8528.

3) Kondili, E., Pantelides, C. C., and Sargent, R. W. H. (1993). A general algorithm for short-term scheduling of batch operations. i: Milp formulation. Computers and Chemical Engineering, 17(2):211?227.

4) Pinto, J. M. and Grossmann, I.E. (1995). A continuous time mixed integer linear programming model for short term scheduling of multistage batch plants. Industrial and Engineering Chemistry Research, 34(9):3037? 3051.

5) Lee, H., Pinto, J. M., Grossmann, I. E., and Park, S. (1996). Mixed-integer linear programming model for refinery short-term scheduling of crude oil unloading with inventory management. Industrial and Engineering Chemistry Research, 35(5):1630?1641.