(769d) Online Scheduling: Addressing Endogenous Uncertainties
In this work we propose a simulation framework for carrying out online scheduling in the presence of endogenous uncertainties. We address the following: (i) variations in processing times; (ii) fluctuations in batch yields; and (iii) unit breakdowns. These uncertainties are inevitable in production scheduling and their observation depends on the scheduling decisions. There are two unique contributions that we make which results in this framework being general.
First, we discuss different probability distributions from which the endogenous uncertainties are sampled for simulation purposes. We model uncertainties in processing time as a Poisson distribution, task yields as a combination of exponential and triangular distribution, and unit breakdowns through exponential distribution. Importantly, we provide quantitative relations, with proofs, for scaling the parameters of these distributions with the uncertainty sampling frequency. For example, when batches are monitored for delays every 0.5Î´ h instead of Î´ h, the corresponding parameter for the Poisson distribution, which denotes the mean observed delays, should also be scaled to 0.5Î» from Î». In addition, we discuss a stopping criterion for accumulating sufficient number of simulation samples. Our framework is modular and new probability distributions can be easily incorporated.
Second, we provide an algorithm to overcome the inevitable infeasibility in scheduling decisions that results from faster endogenous uncertainty sampling (Î´) than the re-optimization frequency (Î). This is not trivial, like it is in the case of exogenous uncertainties where appropriate slack variables can be introduced and penalized. In this algorithm, which we refer to as the adjustment algorithm, we introduce new binary variables to keep track of tasks that are shifted in time, re-assigned to a different unit, or have their batch-sizes modified. We also introduce continuous variables to measure the amount of adjustment in the schedule, and appropriately penalize all these new variables to obtain minimum needed adjustments while restoring feasibility.
Further, using the above framework, we carry out closed-loop simulations, for structurally different scheduling networks, from which we draw several insights. First, changing the horizon length does not result in any advantage for mitigating disturbances. Second, re-optimizing often is beneficial to tackle uncertainty and becomes more and more important as uncertainty increases. Third, frequent schedule adjustments, even if sub-optimal from an open-loop perspective, are better than in-frequent periodic full re-optimizations. Finally, allowing for full re-optimization rather than a limited schedule adjustment, when large unusual disturbances, e.g. unit breakdowns, are observed results in higher quality schedules.
To our knowledge, the work presented herein is the first systematic framework for online scheduling under endogenous uncertainties, and thus takes us one-step forward, towards synthesizing and testing general strategies to obtain high-quality closed-loop schedules.
Gupta, D.; Maravelias, C.T.; Wassick, J.M. From rescheduling to online scheduling. Chemical Engineering Research and Design, 116 (2016), 83-97.
Grossmann, I. E.; Apap, R. M.; Calfa, B. A.; García-Herreros, P.; Zhang, Q. Recent advances in mathematical programming techniques for the optimization of process systems under uncertainty. Computers & Chemical Engineering, 91 (2016), 3-14.
Colvin, M.; Maravelias, C. T. R&D pipeline management: Task interdependencies and risk management. European Journal of Operational Research, 215 (2011), 616-628.
Goel, V.; Grossmann, I. E. A class of stochastic programs with decision dependent uncertainty. Mathematical programming, 108 (2006), 355-394.