(733f) Discrete-Time Mixed-Integer Programming Models for Simultaneous Batching and Scheduling in Sequential Environments

Scheduling problems in sequential environments are among the most common in batch manufacturing facilities. In general, a sequential production environments has a series of stages in which batches have to go through without being mixed, split or recycled. Among problems in sequential environments, multistage batch plants are the facilities that have received the most attention (Harjunkoski et al., 2014). However, only a limited number of studies is available for, the more general, (sequential) multipurpose batch plants. Furthermore, most of the existing approaches for scheduling in sequential environments are based on several restrictive assumptions. Specifically, batching decisions are assumed to be decoupled from scheduling decisions, often leading to suboptimal solutions. Another simplifying assumption commonly made is that unlimited intermediate storage is available. Although models that overcome these limitations have been proposed for multistage batch plants (Liu and Karimi, 2008; Sundaramoorthy et al., 2009), no models addressing all these limitations are available for multipurpose facilities.

In this work, we develop two novel discrete-time mixed integer programming models for simultaneous batching and scheduling in multipurpose facilities with storage constraints. The proposed models adopt two different modeling approaches. The first is based on explicit labeling of the batches of an order. Although each batch is labeled and scheduled individually, they are linked through the order satisfaction constraint, as well as the unit utilization constraint. The second is based on identifying possible unit routings for each order and the corresponding batch size intervals. After batch intervals are identified, the problem becomes an assignment problem where batches of a given order are assigned to different batch size intervals to meet demand. Since it is not trivial to identify unit routings and batch size intervals, we develop an algorithm which only need to be run once for each facility. In addition, we propose extensions for both models that allow us to consider limited shared utilities (both fixed and time-varying) and storage with capacity limits.

We provide illustrative examples to showcase the impact of simultaneously considering (1) batching decisions, (2) limited shared resources, and (3) storage with capacity limits on the final schedule. Finally, we carry out a computational study to understand how instance characteristics, such as expected number of batches per order and uniformity in unit capacities, impact the effectiveness of the proposed models. We show that due to the different modeling approaches adopted, their performance shows a clear trend with respect to instance characteristics. Hence, carefully selecting the model allows us to effectively solve large-scale instances.

Reference

1.  Harjunkoski, I., Maravelias, C. T., Bongers, P., Castro, P. M., Engell, S., Grossmann, I. E., Hooker, J., Mendez, C., Sand, G. and Wassick, J. (2014) Scope for industrial applications of production scheduling models and solution methods. Computers & Chemical Engineering. 62, 161-193.
2.  Liu, Y. and Karimi, I. A. (2008) Scheduling multistage batch plants with parallel units and no interstage storage. Computers & Chemical Engineering. 32, 671-693.
3.  Sundaramoorthy, A., Maravelias, C. T. and Prasad, P. (2009) Scheduling of Multistage Batch Processes under Utility Constraints. Industrial & Engineering Chemistry Research. 48, 6050-6058.