(423a) A Unified Approach to Batch Scheduling

In the context of scheduling, batch processes can be classified into sequential and network processes. In sequential processes, batches are processed in a predefined sequence of operations; mixing and splitting of batches are not allowed thereby preserving the identity of each batch. In network processes, on the other hand, batches are allowed to be mixed, split and recycled, which implies that the identity of a batch is not preserved and material balances (rather than batch tracking) are important. Existing approaches to batch scheduling address each of these processes separately.

The approaches developed to address problems in sequential processes, henceforth referred to as sequence-based formulations, are primarily based on the notion of ?batch? and they most often require that the number of batches is fixed (given) (Mendez et al., 2006; Pinto and Grossmann, 1995; Hui and Gupta, 2000; Mendez et al., 2001). They typically include assignment and sequencing constraints expressed in terms of batches: each batch has to be assigned to exactly one unit at each stage and the batches assigned to the same unit have to be sequenced. In addition to exploiting the sequential structure of the process, most sequence-based approaches are based on a series of restricting assumptions (e.g. unlimited utilities and storage capacity) which lead to highly specialized but computationally effective formulations.

On the other hand, the approaches developed for network processes, henceforth called network-based formulations (Kondili et al., 1993; Pantelides, 1994), are rather general. They can be used to address problems with storage as well as resource constraints. The main idea behind these approaches is the partition of the scheduling horizon into (discrete or continuous) time periods and the enforcement of i) material balance, ii) unit assignment and iii) resource constraints for each period. Importantly, these constraints are expressed similarly to flow balance constraints in networks. One of the limitations of this ?flow? representation, however, is that it does not keep track of batches. Therefore, network-based approaches cannot be used to address problems in sequential processes.

Proposed Work

The goal of this work is the development of a unified framework that accounts for sequential and network structures simultaneously. The advantage of the proposed framework is that it can be used to address problems in facilities that include both sequential and network structures, e.g. process where batch identity has to be preserved in early stages for quality control purposes, but bulk (i.e. network-like) processing is allowed in later stages (e.g. packing). Furthermore, the proposed mixed-integer programming model considers batching and scheduling decisions simultaneously, and accounts for utility and storage constraints. To our knowledge, this is the first work that addresses this integrated problem simultaneously.

First, we present the basic components that enable the representation of all processes in a unified manner:

1) A global discrete-time representation to ensure that material balance constraints (for the network portion of the process) and utility constraints are seamlessly enforced.

2) A systematic method for the transformation of a problem in a sequential process (i.e. expressed in terms of batches, stages and units) into a problem expressed in terms of a network-based formulation (i.e. in terms of tasks, states, and units).

3) A systematic method for the representation of a mixed facility (i.e. a facility with sequential and network substructures) as a purely network facility. This is achieved via the definition of four classes of states (nodes): i) in/out network, ii) in-network/out-sequential, iii) in-sequential/out-network, and d) in/out-sequential.

Note that the above methods result in a unified network structure for the entire facility.

Second, we discuss two new modeling concepts that allow us to enforce sequential processing in the unified network structure resulting from the previous step:

1) We introduce ?unit-connecting? and material flow variables between process units to enforce connectivity constraints in the sequential potion of the process.

2) We develop novel storage constraints that ensure that batches are not mixed nor split in storage vessels in the sequential portion of the process.

Third, we discuss new methods for the reduction in the computational requirements, including tightening constraints and reformulation methods, as well as explore the use of existing techniques (e.g. search strategies, generation of different types of cutting planes, etc.) for the solution of large-scale problems.

Finally, we present a number of example problems to illustrate how various sub-classes of the general scheduling problem can be solved effectively using our framework. We also present extensive computational results for a large collection of instances.

Keywords: scheduling, batch processes, sequence-based, network processes, mixed-integer linear programming

Reference:

1. Mendez, C.A.; Cerda, J.; Grossmann, I.E.; Harjunkoski, I.; Fahl, M. State-of-the-art review of optimization methods for short-term scheduling of batch processes. Comput. Chem. Eng., 2006, 30, 913-946.

2. Pinto, J.M.; Grossmann, I.E. A Continuous Time Mixed Integer Linear Programming Model for Short Term Scheduling of Multi-stage Batch Plants. Ind. Eng. Chem. Res., 1995, 34, 3037-3051.

3. Hui, C.H.; Gupta, A. A novel MILP formulation for short-term scheduling of multistage multiproduct batch plants. Comput. Chem. Eng., 2000, 24, 1611-1617.

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

5. 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.

6. Pantelides, C.C. Unified frameworks for the optimal process planning and scheduling. In proceeding on the second conference on foundations of Computer Aided operations; AIChE: New York, 1994, pp 253-274.