(530a) Scheduling with Preemption

The most well-known scheduling formulations from the Process Systems Engineering (PSE) community do not account for the possibility of processing tasks to be interrupted. Yet, preemption is often encountered in daily practice, with the ISA-95 standard, which can act as a data-exchange platform for production scheduling [1], including planned break periods (e.g., due to preventive maintenance, weekends), number of stops allowed per task, minimum duration of each partial task, and possible penalties for interrupting a task.

Models allowing for preemption exist in the context of project scheduling. In [2], an activity with discrete duration dcan be interrupted up to dtimes, with the time(s) of interruption being determined by a genetic algorithm. In this paper, we consider a more constrained form of preemption, where tasks can be interrupted at a given point in time, provided that they continue immediately after the break. Long tasks may be interrupted multiple times.

We will show how to handle preemption in discrete- and continuous-time formulations. On the one hand, we focus on the Resource-Task Network (RTN) discrete-time formulation [3], which is known to be very tight and better at handling events such as time-dependent electricity pricing [4]. The required changes occur at the level of the structural parameters and excess resource balance constraints, with the model variables remaining the same (it is straightforward to extend a State-Task Network based discrete-time formulation, such as the one in [5-6], to handle preemption in a similar way). On the other hand, we use Generalized Disjunctive Programming (GDP) [7-9] and a compact convex hull reformulation to derive the complex timing constraints of the continuous-time formulation. These are incorporated into a model for multistage batch plants that relies on the general precedence concept [10-11].

The performance of the proposed formulations is evaluated on an industrial problem featuring 24 orders and 4 stages (96 tasks) [4] considering the objective of makespan minimization. The results show a better performance for the discrete-time formulation (DT), which is able to solve the problem to optimality in less than one hour, whereas the continuous-time model (CT) can only handle 14 orders in the same computational time. This, despite DT having a worse relaxation and generating MILPs that are one order of magnitude larger in size. Preemption allows to reduce the makespan without bringing too much complexity into the model. In fact, CT can actually be solved faster compared to the non-preemptive case, probably due to the lower integrality gap.

Future work will deal with single stage batch plants with parallel units, to see if the ranking is altered when using a tighter continuous-time formulation, one with multiple time grids [9] and without super big-M constraints.

Acknowledgments: Financial support from Fundação para a Ciência e Tecnologia (FCT) through projects IF/00781/2013 andUID/MAT/04561/2013.

References:

[1] I. Harjunkoski, R. Bauer, 2014, Sharing Data for Production Scheduling using the ISA-95 Standard, Frontiers in Energy Research, doi: 10.3389/fenrg.2014.00044.

[2] V.V. Peteghem, M. Vanhoucke, 2010, A Genetic Algorithm for the Preemptive and Non-Preemptive Multi-mode Resource-Constrained Project Scheduling Problem, European Journal of Operational Research, 201,409-418.

[3] C.C. Pantelides, 1994, Unified Frameworks for the Optimal Process Planning and Scheduling, In Proceedings of the Second Conference on Foundations on Computer Aided Operations, Cache Publications, New York, 253.

[4] P.M. Castro, L. Sun, I. Harjunkoski, 2013, Resource−Task Network Formulations for Industrial Demand Side Management of a Steel Plant. Ind. Eng. Chem. Res. 52, 13046.

[5] E. Kondili, C.C. Pantelides, R.W.H. Sargent, 1993, A General Algorithm for Short-term Scheduling of Batch Operations – I. MILP Formulation. Comp. Chem. Eng. 2, 211.

[6] H. Lee, C.T. Maravelias, 2017, Discrete-time Mixed-integer Programming Models for Short-term Scheduling in Multipurpose Environments. Comp. Chem. Eng. 107, 171-183.

[7] E. Balas, 1979, Disjunctive programming, Annals of Discrete Mathematics 5, 3-51.

[8] R. Raman, I.E. Grossmann, 1994. Modeling and computational techniques for logic based integer programming. Comput. Chem. Eng. 18, 563-578.

[9] P.M. Castro, I. E. Grossmann, 2012, Generalized disjunctive programming as a systematic modeling framework to derive scheduling formulations. Ind. Eng. Chem. Res. 51, 5781-5792.

[10] I. Harjunkoski, I.E. Grossmann, 2002, Decomposition Techniques for Multistage Scheduling Problems using Mixed-Integer and Constraint Programming Methods. Comput. Chem. Eng.26, 1533.

[11] C. Méndez, J. Cerdá, 2002, An efficient MILP continuous-time formulation for short-term scheduling of multiproduct continuous facilities. Comput. Chem. Eng. 2002, 26, 687.