(411h) A Multi-Stage Stochastic Programming Approach for Scheduling of Batch Processes Under Decision-Dependent Uncertainty

Authors: 
Menon, K., University of Waterloo
Ricardez Sandoval, L. A., University of Waterloo
Fukasawa, R., University of Waterloo
Scheduling is one of the decision-making strategies widely used in the industries to manage time and resources effectively such that the desired targets are satisfied at minimum cost. One of the challenging aspects of industrial scheduling is uncertainty modelling, which is key to obtain realistically feasible solutions. Stochastic programming is one of the most widely used uncertainty modelling approaches that allows two sets of decisions- here and now and wait and see decisions, to be made before and after the realization of uncertainty, respectively. A key factor that increases the complexity of uncertainty modelling is the type of uncertainty involved. Most of the available literature on stochastic programming focuses on exogenous uncertainties, which are independent of model decisions. However, in many cases, uncertainty often depends on the model decisions. There are several chemical engineering applications where the time at which the uncertainty realizes depends on other model decisions (e.g. uncertainty in recycle rates, product yields, etc.). This is referred to as type II endogenous uncertainty in the literature [2]. Due to the dependency on model decisions, accounting for such uncertainties becomes highly complex and are therefore often overlooked, despite being very common in chemical engineering applications (e.g. type II endogenous uncertainties such as recycle rate). In this study, the focus is on type II endogenous uncertainty modelling using a multi-stage stochastic programming approach.

The key challenge in developing scenario based stochastic frameworks for modelling type II endogenous uncertainty is to enforce non-anticipativity (ensuring that current decisions are made without anticipating information from the future) throughout the decision-making process. This often involves introduction of auxiliary binary variables and non-anticipativity constraints [4]. Introducing such auxiliary variables and constraints result in large model size, which further increases with the number of scenarios [1], [3]. In our previous work [6], we developed a novel two-stage stochastic approach to model type II endogenous uncertainty that ensures non-anticipativity implicitly via material balance constraints, without the introduction of any auxiliary variable or explicit non-anticipativity constraints. We proposed a large-scale scheduling model to allocate samples (materials) that has to be processed sequentially through a set of tasks and reported significant benefits in using the proposed two-stage approach in modelling actual industrial case studies. The proposed two-stage approach considered uncertainty in recycle rate, i.e. the fraction of samples returned back to a previous task, with a limiting assumption that the recycle rate remains constant throughout the time horizon, independent of how many times a task is being processed. Governed by various operating factors, uncertainties like recycle rate are unlikely to remain constant throughout the operating time horizon. To account for such possible fluctuations in the uncertainty realizations, in this study, we relax the above assumption and provides flexibility to the system by extending the framework to a multi-stage approach, where the time horizon is divided into multiple time periods and a different realization of uncertainty (recycle rate) can be considered in each time period. Enforcing non-anticipativity for a multi-stage framework becomes even more challenging when a type II endogenous uncertainty is considered. To address this challenge, the proposed model considers a node-based approach. Nodes represent the uncertainty realizations. For every time period, the number of nodes represent the number of unique uncertainty realizations of that time period. At every time period, the model solves for each node considering the current uncertainty realization and the realizations of the preceding nodes. Together, with the material balance constraints and the node-based approach, the proposed multi-stage framework enforces implicit non-anticipativity without the need to specify additional auxiliary binary variables and explicit non-anticipativity constraints.

The proposed model has been validated using two case studies - a motivating case study, one of the most widely studied process network from literature [5] and an actual large-scale industrial case study. Computational studies were conducted and value of stochastic solution (VSS) was calculated to estimate the benefits of the proposed approach. Further studies were conducted to analyze the model sensitivity to the number of stages, number of uncertainty realizations and the production capacity. The computational results obtained from both the case studies depict significant benefits in using the proposed multi-stage approach. The results from the motivating case study shows more than 11% increase in the production rate, whereas the industrial case study results shows an increase of 8% in the annual earnings.

References

  1. Colvin, M., & Maravelias, C. T. (2010). Modeling methods and a branch and cut algorithm for pharmaceutical clinical trial planning using stochastic programming. European Journal of Operational Research, 203(1), 205-215.
  2. Goel, V., & Grossmann, I. E. (2006). A class of stochastic programs with decision dependent uncertainty. Mathematical programming, 108(2-3), 355-394.
  3. Gupta, V., & Grossmann, I. E. (2011). Solution strategies for multistage stochastic programming with endogenous uncertainties. Computers & Chemical Engineering, 35(11), 2235-2247.
  4. Jonsbråten, T. W., Wets, R. J., & Woodruff, D. L. (1998). A class of stochastic programs withdecision dependent random elements. Annals of Operations Research, 82, 83-106.
  5. Kondili, E., C. C. Pantelides, and R. W. H. Sargent. "A general algorithm for short-term scheduling of batch operations—I. MILP formulation." Computers & Chemical Engineering2 (1993): 211-227.
  6. Menon, K., Fukasawa, R., & Ricardez-Sandoval, L. A. (2019). A Novel Stochastic Programming Approach for Scheduling of Batch Processes with decision dependent Time of Uncertainty Realization. Annals of Operations Research (submitted for publication)