(298e) On the Solution of Batch Process Scheduling MIP Models

Batch process scheduling has received considerable attention in the process systems engineering (PSE) community over the last two decades. Based on the batch process structure and material handling constraints, scheduling problems can be classified as sequential and network. While both the process structures are common in batch process industry, the scheduling problems in the latter have been studied extensively.

One of the key aspects of network-based models is the time representation. Two widely used representations are i) discrete-time, and ii) continuous-time. Discrete-time approaches partition the scheduling horizon into a known number of periods of equal length defining a time grid that is common across all resources (units, states, etc.). The processing times are assumed to be constant (Kondili et al, 1993; Shah et al., 1993). Although the models based on this representation have numerous advantages, they often lead to large MIP formulations which has lead researchers to explore an alternative time representation.

The motivation for the development of continuous-time models has been centered around two inter-related shortcomings of discrete-time models, namely the formulation size and solution accuracy (Castro et al., 2001; Maravelias and Grossmann, 2003; Janak et al., 2004; Sundaramoorthy and Karimi, 2005). Although continuous-time models lead to small MIP formulations, they have several disadvantages: poor relaxation, difficulty in modeling holding and backlog costs linearly, additional computational costs in modeling intermediate shipments etc.

The objective of this work is to critically review and computationally evaluate the network-based approaches. Precisely, we analyze the modeling capabilities of discrete-time and continuous-time approaches, and perform an exhaustive computational study of these two approaches. Given the large pool of modeling approaches and mixed-integer formulations (MIP) for network processes, we believe that our findings in this study will motivate further discussion in the research community leading to the development of effective solution methods.

First, we compare and contrast discrete-time and continuous-time modeling approaches in terms of formulation size and modeling capabilities. We briefly review the main characteristics of the two approaches and outline their advantages and disadvantages.

Second, we perform an extensive computational comparison between the two methods using a collection of a large set of problem instances, which cover:

a) five different process networks with a wide range of process features (e.g., material routing, storage restrictions, etc).

b) various objective functions (sales maximization, cost minimization etc.)

c) a wide range of process features (fixed and variable processing times, utilities, etc.)

d) different scheduling horizons

e) different time discretization (number of periods) Our problem pool consists of more than 200 instances.

Third, we further explore the computational performance of discrete-time models and consider aspects such as holding and backlog costs, setups, and intermediate due dates.

We discuss how computational requirements increase as the scheduling horizon increases for discrete- and continuous-time models. We also discuss how solution quality is affected by the chosen time partition. We study the effect of variable processing times (a limitation of discrete-time models) in computational requirements and solution quality. We show that the computational requirements of discrete-time models increase moderately with the incorporation of additional process features, which is not the case with their continuous-time counterparts.

Further, we highlight the advantages and disadvantages of the two schools of thought, thereby arriving at a number of conclusions that we believe will lead to fruitful discussions in the area and foster further development of modeling and solution methods for batch process scheduling.

References:

1. Kondili, E.; Pantelides, C.C.; Sargent, R.W.H. A General Algorithm for Short-Term Scheduling of Batch Operations ? I. MILP Formulation. Comput. Chem. Eng., 1993, 17, 211-227.

2. Shah, N.; Pantelides, C.C.; Sargent, R.W.H. A General Algorithm for Short-Term Scheduling of Batch Operations ? II. Computaional Issues. Comput. Chem. Eng., 1993, 17, 229-244.

3. Castro, P.; Barbosa-Povoa, A.P.F.D.; Matos, H. An Improved RTN Continuous-Time Formulation for the Short-Term Scheduling of Multipurpose Batch Plants. Ind. Eng. Chem. Res., 2001, 40, 2059-2068.

4. Maravelias, C. T.; Grossmann, I. E. New Continuous-Time State Task Network Formulation for the Scheduling of Multipurpose Batch Plants. Ind. Eng. Chem. Res., 2003, 42 , 3056 ? 3074.

5. Janak, S.L.; Lin, X.; Floudas, C.A. Enhanced Continuous-Time Unit-Specific Event-Based Formulation for Short-Term Scheduling of Multipurpose Batch Processes: Resource Constraints and Mixed Storage Policies. Ind. Eng. Chem. Res., 2004, 43, 2516-2533.

6. Sundaramoorthy, A.; Karimi, I.A. A simpler better slot-based continuous-time formulation for short-term scheduling in multipurpose batch plants. Chem. Eng. Sci., 2005, 60, 2679-2702.