(372b) A Slot-Based Formulation For Short-Term Scheduling Of A Two-Stage Batch Plant With Parallel Reactors With Sequence-Dependent Changeovers

In this paper we address the short-term scheduling of parallel identical/non-identical multi-product batch reactors, a challenging problem that has been motivated by a real world application at the Dow Chemical Company. This problem not only poses the difficulty of handling sequence-dependent changeovers with high variance for an industrial-sized data, but also has the difficulty of handling two-stage production with limited and shared intermediate storage. Due to topological restrictions within the plant, batch splitting of the intermediate is required once its production is completed. This combined with having to monitor the level of intermediates in the tanks to avoid shortages or overflows poses several difficulties in handling the mass and inventory balances. This special kind of resource constrained batch scheduling problem can in principle be tackled through discrete time models such as the State Task Network (STN) (Kondilli et al., 1993, Shah et al., 1993) or Resource Task Network (RTN) (Pantelides, 1994). However, the weakness of these discrete time models is that the STN requires a finer discretization of time in order to accommodate small changeovers. Moreover, the number of constraints quickly becomes very large when there are significant number of changeovers. RTN requires defining explicitly additional tasks associated with each type of cleaning as well as different states of cleanliness for each processing units. These difficulties can in principle be overcome with continuous time STN (Schilling and Pantelides, 1996, Zhang and Sargent, 1996, Mockus and Reklaitis, 1999, Giannelos and Georgiadis, 2002, and Maravelias and Grossmann, 2003;) and RTN (Pantelides, 1994, Castro et al., 2001, and Castro et al., 2004) models based on the definition of global time points. However, these have the disadvantage of being computationally expensive since the use of common time grids requires a large number of time points to be defined in order to consider exact transition times and multiple due dates. Similar difficulties are experienced with event models (Ierapetritou and Floudas, 1998; Janak et al., 2004). Another alternative to consider would be to use formulations that are based on the concept of time slots. Relevant work in this area is represented by the formulations of Pinto and Grossmann (1995, 1996), Chen et al., 2002 and Lim and Karimi (2003). While sequence-dependent changeover times can be treated in a straightforward manner, the formulations found in the literature are restricted to sequential processes due to the difficulties in handling batch splitting and monitoring of the shared resources. Although, more recently, Sundaramoorthy and Karimi (2005) developed a novel idea of several balances to deal with network batch processes, but that formulation is built on the assumption of sequence-independent changeovers. In order to tackle this challenging scheduling problem, we propose a novel continuous time MILP optimization model that uses the representation of time slots. The proposed model has the unique feature that it incorporates mass balances and accounts for sequence-dependent changeovers. Each slot represents one potential batch of the product that is assigned to that slot. Since the number of batches of each product is a variable to be determined by the model, the exact number of slots to be utilized is not known a priori. Hence, we postulate more slots than needed for each unit. The assignments of products to these slots are to be determined to define the sequence of production on each unit and each time period. The length of each slot is equal to the batch time of the product that is assigned to that slot plus the corresponding transition time. In order to avoid violations in the use of the limited shared resources, the mass balances are performed on a slot basis. Moreover, since the time slots are not synchronized over the units, we introduce constraints to determine the relative locations of the slots across parallel units to ensure feasible mass transfer. While effective for small problems and short time periods, the proposed model becomes computationally expensive to solve for larger problems and longer time periods. Therefore, we propose a rigorous bi-level decomposition algorithm that reduces the computational expense of the model. The proposed approach involves decomposing the problem into an upper level sequencing and a lower level scheduling model. The upper level is an aggregation of the original problem where the detailed timing of production and changeovers are replaced with time balances and slot based mass balances are aggregated over time periods. The main decisions in this level are the assignments of products to available equipment, number of batches of each product as well as the production and inventory levels. Since the upper level is a relaxation of the original model, it yields a valid upper bound on the profit. Furthermore, it also yields a tighter upper bound on the number of slots to postulate for the lower level through the number of batches. In the lower level, the proposed MILP scheduling model is solved by excluding the products that were not selected by the upper level for the number of slots as determined by the upper level. Since its solution corresponds to a feasible solution of the original problem, it yields a lower bound on the profit. This procedure iterates until the difference between the upper bound and the lower bound is less than a specified tolerance. To expedite the search, we add logic cuts that which help to eliminate symmetric solutions. Application of the proposed solution approach is illustrated with several examples that show that the slot based scheduling model can be solved very effectively on a variety of problems.