(301a) On the Derivation of Continuous-Time Scheduling Formulations From Generalized Disjunctive Programming

Process Systems Engineering has been responsible for a variety of scheduling models that are primarily classified according to process and time representation. While the unified frameworks (STN, RTN) provide a systematic way of converting the real plant entities (e.g. units, products, utilities) into virtual entities that can be used by a mathematical model, most scheduling models feature variables and constraints derived from intuition and trial and error so as to maximize computational performance. This aspect becomes particularly relevant when switching from a discrete to a continuous-time representation, which has more freedom from a modeling point of view.

Continuous-time approaches can be classified as precedence (Méndez et al. 2001; Jain and Grossmann 2001), single (Castro et al. 2004) or multiple time grid (Castro and Grossmann, 2006; Susarla and Karimi, 2010; Seid and Majozi, 2012) based (a.k.a unit-specific; Ierapetritou and Floudas, 1998). Some of the latter, when applied to the more general multipurpose production environment, have raised serious concerns over the years with respect to generality, suggesting that: (i) either the underlying time representation concept does not account for all possibilities; (ii) not all the required variables or constraints are effectively part of the model. It is thus highly desirable to have a systematic modeling framework that, starting with a simple concept for time representation, can generate the constraints to make it work.

Generalized Disjunctive Programming (GDP) provides a high level framework for modeling mixed-integer programs starting from a logic representation in which mixed-integer logic is represented through disjunctions and integer logic through propositions. In fact, different formulations can systematically be derived using for example big-M and convex hull reformulations, which have complementary strengths. The former has the advantage of being simpler and does not require the definition of additional continuous variables and constraints but has the drawback of being less tight.

In this work, we examine the relatively simple case of single stage scheduling problems with single and parallel units focusing on continuous-time representations and specifically on the immediate, general precedence and multiple time grid alternatives. Starting with the linear GDP models, we derive the equivalent mixed-integer linear programming models using the big-M and convex hull reformulations to show that well-known models from the literature trace back to a particular elementary time representation/reformulation pair. Their performance is then evaluated on a set of test problems with up to 30 orders and 5 parallel units, with the results showing that the multiple time grid model with the convex hull reformulation is the best performer. This is essentially the model proposed by Castro and Grossmann (2006). Other interesting result is that the two similar precedence concepts give opposite results with represent to the most efficient reformulation.

References:

Castro, P.M.; Barbosa-Póvoa, A.P.; Matos, H.A.; Novais, A.Q. (2004). Simple Continuous-time Formulation for Short-Term Scheduling of Batch and Continuous Processes. Ind. Eng. Chem. Res. 43, 105.

Castro, P.; Grossmann, I.E. (2006). An Efficient MILP Model for the Short-term Scheduling of Single Stage Batch Plants. Comput. Chem. Eng. 30, 1003.

Ierapetritou, M.G.; Floudas, C.A. (1998). Effective continuous-time formulation for short-term scheduling. 1. Multipurpose batch processes. Ind. Eng. Chem. Res. 37, 4341.

Jain, V.; Grossmann, I.E. (2001). Algorithms for Hybrid MILP/CP Models for a Class of Optimization Problems. Informs Journal on Computing, 13 (4), 258.

Méndez, C.A.; Henning, G.P.; Cerdá, J. (2001). An MILP continuous-time approach to short-term scheduling of resource-constrained multistage flowshop batch facilities. Comput. Chem. Eng. 25, 701.

Seid, R.; Majozi, T. (2012). A robust mathematical formulation for multipurpose batch plants. Chem. Eng. Sci. 68, 36.

Susarla, N.; Li, J.; Karimi, I.A. (2010). A Novel Approach to Scheduling Multipurpose Batch Plants Using Unit-Slots. AIChE J. 56, 1859.