(625a) Optimal Scheduling with Preemptive Changeover Tasks: Solving a Benchmark Problem from the 80’s

In 1986, Egli and Rippin published a paper [1] describing a scheduling problem and a computer program for its solution. To the best of my knowledge, this problem is yet to be solved to optimality. The most likely reason is the variety of challenging constraints to enforce. Specifically, the problem deals with a multiproduct batch chemical plant featuring recipes with stable and unstable intermediates, shared resources with limited availability of electricity and steam, non-instantaneous transfer times and the possibility of interrupting sequence-dependent changeover tasks when encountering pre-defined break periods. These involve weekend breaks, during which stable intermediates can remain in the corresponding unit, and a plant shutdown, during which no partially completed batches can remain in the plant. The objective function reflects a tradeoff between storage and changeover costs.

In this paper, such problem is tackled with a discrete-time formulation (1-h slots) based on the Resource-Task Network (RTN) [2] process representation. To model the interruption of changeover tasks, we make their duration dependent on the starting time [3]. Modeling sequence dependent changeovers requires equipment units to be represented as different resources, so that the correct type of cleaning can be applied [4]. Cleaning is required even between consecutive batches of the same product (another way of transitioning in the chemical industry are quality-based changeovers [5]). Compared to almost all benchmark instances in the PSE literature that assume instantaneous material transfer between units [6], reflected in the recipe data of the CProS web-based application for chemical production scheduling recently developed by the leading research group of Prof. Christos Maravelias, all five production recipes in the problem exhibit activity synchronization (from 1 to 3 hours). Synchronization will be achieved in two different ways: (i) activities producing unstable intermediates are merged with the activity(ies) that receive the material, rather than being considered as individual tasks [7]; (ii) stable intermediates will be handled as sequential resources that are never available [8]; this will force the consuming task to start at least one hour before the end of the task producing the intermediate. Some of these modelling tricks are closely related to the RTN extensions given in [9].

Compared to the original approach combining an algorithm and heuristic rules [1], the proposed mixed-integer linear programming formulation achieves savings of 5% in total operating cost. The generated schedule is non-trivial since it opts for lengthier and more costly changeovers (batches of a product are not sequenced consecutively), to benefit from lower storage costs. The computational cost on an Intel i9-9900K desktop running GAMS 36.2 and CPLEX 20.1 in parallel deterministic mode (up to 16 threads), is 838 CPUs (relative optimality gap = 1E-6), which is acceptable for a short-term scheduling problem that considers a time horizon of 20 days (480 h).

Acknowledgments: Financial support from Fundação para a Ciência e Tecnologia (FCT) through projects CEECIND/00730/2017 and UIDB/04561/2020.

References:

[1] Egli, U.M., Rippin, D.W.T., 1986. Short-term Scheduling for Multiproduct Batch Chemical Plants. Comput. Chem. Eng. 10 (4), 303-325.

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

[3] Castro, P.M., Harjunkoski, I., Grossmann, I.E. 2019. Discrete and Continuous-time Formulations for Dealing with Break Periods: Preemptive and Non-preemptive Scheduling. European Journal of Operational Research 278, 563-577.

[4] Dimitriadis, A.D., Shah, N., Pantelides, C.C. 1998. Efficient Modelling of Partial Resource Equivalence in Resource-Task Networks. Comput. Chem. Eng. 22, S563-S570.

[5] Brunaud, B., Perez, H.D., Amaran, S., Bury, S., Wassick, J. 2020. Batch Scheduling with Quality-based Changeovers. Comput. Chem. Eng. 132, 106617.

[6] Ferrer-Nadal, S., Capón-Garcia, E., Méndez, C.A., Puigjaner L. 2008. Material Transfer Operations in Batch Scheduling: A Critical Modelling Issue. Ind. Eng. Chem. Res. 47, 7721-7732.

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

[8] Castro, P.M., Barbosa-Póvoa, A.P., Matos, H.A. 2003. Optimal Periodic Scheduling of Batch Plants using RTN-based Discrete and Continuous-time Formulations. Ind. Eng. Chem. Res. 42, 3346-3360.

[9] Wassick, J.M., Ferrio, J. 2011. Extending the Resource Task Network for Industrial Applications. Comput. Chem. Eng. 35, 2124-2140.