(648f) On the Choice of Open-Loop Optimization Model for Online Batch Scheduling Under Uncertainty

When a schedule is computed, disruptions or the arrival of new information can render the current schedule sub-optimal or even infeasible, thereby necessitating online (re)scheduling. In online scheduling, the information on future demands, processing times and batch yields can be uncertain. For handling these uncertainties different methods exist: (i) deterministic; (ii) robust; and (iii) stochastic optimization (Engell, 2009 and Gupta et al., 2020). In an online setting, these optimization problems are solved iteratively as the horizon is shifted forward to determine the open-loop schedule. The closed-loop schedule is then generated by injecting the decisions computed at the initial times of each open-loop schedule.

In this work, we focus on scheduling of batches under demand uncertainty, wherein demand is modeled in the form of orders with the order sizes being drawn from a probability distribution. Demand uncertainty is composed of two aspects: (i) observation time (η) and (ii) order size max-mean relative difference (ε) (Gupta et al., 2019). The demand uncertainty observation time is the length of the horizon, within which there is no uncertainty in demand and order size max-mean relative difference captures the difference between the maximum and mean order size relative to the mean order size.

We present a systematic procedure for carrying out closed-loop simulations and evaluating the closed-loop performance of the three methods in the presence of demand uncertainty. In the deterministic optimization method, the model does not incorporate information about the uncertainties and a mean order size is assumed for orders beyond η. In the robust method, a worst case scenario is considered with order sizes near the maximum for orders beyond η. Lastly, in the stochastic method, an optimal scenario reduction technique is applied to generate a finite set of scenarios for the orders beyond η and a multi-stage stochastic programming approach is used.

On carrying out simulations, we observe that there is no particular method which performs the best across settings, for example, although stochastic methods can find good open-loop solutions, their online computation is typically expensive. So, we want to understand the performance of the different methods as the inventory, backlog and fixed cost parameters in the cost minimization objective are varied. We develop general relationships across the parameter space, to guide the selection of the appropriate method for the problem at hand. Based on preliminary results, we have found that the “load” of the network used in the scheduling problem, calculated based on the production capacity of the network and the demand profile, plays a pivotal role in differentiating the performance of the methods. In general, across different networks, we observe that at higher loads, the robust method performs better than the other methods as the backlog cost predominantly influences the closed-loop cost, while, at lower loads, the stochastic method performs better as the inventory cost is more dominant.

We discuss how the closed-loop performance across the three methods differ as η, ε, and the load are varied. We then draw useful insights that are applicable to general scheduling problems and expound on the counter-intuitive trends that solely depend on the network attributes. To the best of our knowledge, our work is the first of its kind to provide guidelines on the choice of the method/optimization model for online batch scheduling by quantitatively characterizing the demand uncertainty.

References

1. Engell, S. (2009) Uncertainty, decomposition and feedback in batch production scheduling. Computer Aided Chemical Engineering, 26, 43-62.
2. Gupta, D., and Maravelias, C.T. (2020) Framework for studying online production scheduling under endogenous uncertainty. Computers & Chemical Engineering, 129, 106517.
3. Gupta, D., and Maravelias, C.T. (2019) On the design of online production scheduling algorithms. Computers & Chemical Engineering, 135, 106670.