(610e) Task Selection, Assignment and Sequencing in Multistage Batch Processes

Intro ? Motivation: Multi-stage batch processes are common in the food, fine chemical and pharmaceutical industries. They consist of several stages (e.g. mixing, reaction, separation, etc), and each stage consists of a set of parallel equipment units. A batch of a product must be processed in one unit in each stage, and all equipment units are shared among many products. In addition to being of great industrial importance, the scheduling of multi-stage plants is a hard optimization problem, and thus academically challenging. In this work, we present a general mixed-integer programming (MIP) model and two solution methods for the scheduling of multi-stage batch processes.

Review: To address the scheduling of multi-stage batch processes, researchers and practitioners have proposed mixed-integer programming (MIP) formulations [1,2,3,4] that are computationally more effective than the more general State Task Network (STN) formulations [5]. Specifically, the proposed formulations exploit the fact that there is no batch splitting/mixing and recycle streams, and that the sequence of tasks for a given order is given. Another important assumption in all existing approaches is that the number of orders is fixed. This assumption implies that the total number of tasks carried out in any feasible solution is also fixed, while it allows the use of tight assignment constraints. In this paper we develop a multi-stage formulation to addresses problems where the number of batch tasks is unknown. This class of problems appears very often in practice, and specifically when there are units of different capacities in the same stage (e.g. due to expansion of the plant). If all units have the same capacity, it is easy to a priori calculate how many batches are required to meet customer's orders and treat this number of batches as independent (and fixed) orders. But when capacities are different, the type and number of batches required to meet a customer's order becomes an optimization variable. Interestingly enough, previous MIP models handle dissimilar parallel units in terms of processing times and changeover costs and times, but not parallel units of different capacity, the reason being that the latter leads to substantially different (and harder to solve) models.

Proposed Model: For this generalized multistage scheduling problem there are three levels of decisions: a) Task selection: the type and number of tasks required to meet the given orders. b) Task assignment: the equipment unit to be used for each task c) Task sequencing: sequence of the tasks in each unit To model these levels we use three binary variables: selection variables Z, assignment variables X, and sequencing variables Y. For a given customer order, binaries Z satisfy a demand constraint, i.e. the sum of the sizes of the selected batches is larger or equal to the amount due. For the selected batches (via binaries Z), binaries X must satisfy an assignment constraint, i.e. every selected batch must be assigned to exactly one suitable unit in every stage. For the tasks assigned to a unit (via binaries X), binaries Y must satisfy sequencing constraints. We consider both fixed and variable processing times, and variable batch sizes. We also develop a set of strong valid inequalities that yield a tighter formulation and lead to shorter solution times. To our knowledge, the proposed MIP model is the first to include selection decisions for multi-stage plants. At the same time it exploits the sequential structure of such plants. It can be viewed, therefore, as the equivalent of STN-based formulations for multi-stage batch processes. Note that for fixed Z's it reduces to a traditional multi-stage formulation.

Industrial Application: A multistage process that exhibits the characteristics described above is the production of aluminum casts from different alloys processed in parallel furnaces and casters. The process features not only parallel units with non-uniform capacities but also variable processing times, unique connectivity between units at any given time, and capacities in the form of ranges. To accurately model the operation of furnaces, we also introduce material balance constraints for the level of alloys in furnaces. In order to tackle large problems we develop a decomposition scheme that consists of a master problem that is an approximation of the full MIP model, and a sub-problem that is essentially the full problem with a partial fixing of variables. An instance with 3 parallel furnaces, 2 casters, 2 feed sources and 12 orders is solved. The objective function is the weighted minimization of changeovers and earliness/tardiness. The full MIP model consists of 578 binary variables and yields the optimal solution in 7,200 CMU seconds (without proving optimality). Using the iterative scheme described earlier the same optimal solution is reached in 40 CPU seconds and optimality is proved in 50 seconds.

Parallel Computing: Finally, we develop an algorithm that lends itself to parallel computing. The original MIP is solved on the master computer with the integrality constraints on binary variables X and Y removed. For each integer solution, a MIP subproblem with variables Z fixed, and variables X and Y treated as binaries is generated and solved in a ?slave? machine. Feasible solutions and best bounds are passed back to the master computer and non-promising sub-problems are pruned. Computational enhancements of 1-2 orders of magnitude are achieved.

References: [1] Pinto, J.; Grossmann, I.E. A continuous-time mixed-integer linear-programming model for short-term scheduling of multistage batch plants. Ind. Eng. Chem. Res., 1995, 34(9), 3037-3051. [2] Mendez, C.A.; Henning, G.P.; Cerda, J. An MILP continuous-time approach to short-term scheduling of resource-constrained multistage flowshop batch facilities. Comp. Chem. Eng., 2001, 25(4-6), 701-711. [3] Gupta, S.; Karimi, I.A. An improved MILP formulation for scheduling multiproduct, multistage batch plants. Ind. Eng. Chem. Res., 2003, 42(11), 2365-2380. [4] Castro, P.M.; Grossmann, I.E. New continuous-time MILP model for the short-term scheduling of multistage batch plants. Ind. Eng. Chem. Res., 2005, 44(24), 9175. [5] Kondili, E.; Pantelides, C. C.; Sargent, R. A general algorithm for short-term scheduling of batch operations ? I. MILP formulation. Comput. Chem. Eng., 1993, 17, 211-227.