(498e) Simultaneous Batching and Scheduling In Multi-Stage Processes with Storage Constraints

Existing methods for the optimization of multi-stage batch processes consider the batching and schduling problems independently. Orders are first divided into batches based on the unit capacities, and these batches are used as input in the scheduling model. This sequential approach can lead to sub-optimal solutions. Furthermore, storage constraints are important in multi-stage batch processing: the existence of storage vessels decouples processing steps and enables better utilization of resources, e.g. storage before and after a bottleneck stage leads to higher production because it allows uninterrupted utilization of the most scarce resources. However, despite its importance, the problem of simultaneous batching and scheduling of multi-stage processes with storage constraints has not been addressed in the literature. The goal of this work is the development of a general framework for this problem generalized problem.

First, we study the different storage policies in the context of multi-stage processes. Interestingly, the modeling of storage constraints in multi-stage processes, where batch mixing and splitting is not allowed, is more challenging than in network-based formulations, where batches can be mixed and the number of states is fixed. In particular, storage in multi-stage processes depends not only on the size, but also on the number of storage vessels and batches. The number of batches, however, is an optimization decision which means that we cannot always determine a priori the storage policies of a given process. To address this challenge, we propose a general classification of storage policies in multi-stage processes based on the storage capacity (number and size of vessels) and timing constraints (limited/unlimited/zero-wait). We use this classification to develop a formulation that accounts for all policies and their combinations.

Second, we develop a mixed-integer programming (MIP) formulation for the generalized problem we consider. Storage vessels are treated as pseudo-units for which assignment and sequencing constraints are expressed. While a batch has to be assigned to one of the processing units in a given stage, a batch can be transferred to a unit in the following stage directly. We use a precedence-based method to achieve sequencing of batches in units/vessels. Also, we sequence the batches assigned to the same vessel in intermediate stages, but allow the batches of the same order to share a storage vessel in the last stage as a finished product. Further, we account for storage time (in storage vessels) and waiting time (in processing units) through bounding constraints. We present how the proposed MIP model can be used to address all the classes of storage policies identified in our classification.

Third, we present several extensions. We extend our model to address sequence-dependent changeover times and costs. We discuss how the model can be simplified to address problems with fixed number and sizes of batches. We develop a class of tightening inequalities based on time windows.

Finally, we illustrate the significance of storage constraints in batching and scheduling of multi-stage processes using several examples. We show how storage constraints can impact both the objective and the batching decisions and illustrate how storage considerations for finished products affect the solution. We also show how standalone scheduling problems can be solved. We close with a computational study that shows that the addition of the tightening constraints reduces the integrality gap and enhances the solution process.