(769d) Online Scheduling: Addressing Endogenous Uncertainties

Uncertainty can make the current schedule suboptimal or even infeasible, thus motivating the need for online (re)scheduling (Gupta et al., 2016). Uncertainty can be classified into two types: (i) exogenous; and (ii) endogenous. In the exogenous case, the probability distribution of the uncertainty is independent of any scheduling decisions. For example, the price or demand of a product. In contrast, in the endogenous case, either the time of observation or the underlying probability distribution of the uncertainty is influenced by the scheduling decisions (Grossmann et al., 2016). For example, the success of a drug trial can be known only when the trial is actually conducted (Colvin and Maravelias, 2011). Similarly, the choice of the drilling technology, and the decision to drill, together, affect the accessible size of an oil reserve, and the time to observe that size (Goel and Grossmann, 2006). On an abstract level, in the endogenous uncertainty case, when the decisions change, the properties of the system within which the decisions are taken also change. This makes modeling and testing of approaches in this case challenging.

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.

References

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.