(667c) On the Design of an Online Scheduling Algorithm

Disruptions or arrival of new information can make the incumbent schedule suboptimal or even infeasible, thus motivating the need for online (re)scheduling (Subramanian et al., 2012). In this talk, we will investigate how to formulate the scheduling problem solved online (open-loop), so that it leads to high quality implemented (closed-loop) schedule. This is not trivial, because, even in the deterministic case, open-loop and closed-loop scheduling are two different problems (Gupta and Maravelias, 2016).

When uncertainty is present, online scheduling methods need not always explicitly model it; they can employ a nominal (deterministic) model, and still mitigate the effect of uncertainties by treating them as disturbances, and relying solely on recourse, through feedback (Gupta et al., 2016). Deterministic models are more computationally tractable, in real-time, than their stochastic counterparts, thus have a wider applicability. Furthermore, any stochastic modeling, if attempted, is always approximate which means that, eventually, stochastic optimization methods will also be faced with the challenge of mitigating uncertainties/disturbances. Therefore, the findings of this work are broadly applicable to all online scheduling methods.

There are two goals of this work. Our first goal is to study how demand uncertainty affects the quality of the implemented schedule. How does demand variability affect solution quality? Does the time at which uncertainty is observed affect solution quality? Do different demand patterns, characterized by, for example, the frequency of orders, pose any particular challenges? In addition, how do network characteristics (e.g. shared intermediate materials, availability of buffer production capacity), aggravate or diminish the above effect? We also study if and how horizon length and re-optimization frequency can be used to deal with demand uncertainty.

Our second goal is to develop a general method for the design of an online scheduling algorithm, that is, determining, specifically, but not limited to, the horizon length and the re-optimization frequency. In other words, we develop a method which, given an instance (e.g., network data and some demand uncertainty description), explicitly predicts the needed online scheduling parameters.

From our simulations, first, we find that demand uncertainty is an important consideration, and that it is indeed beneficial to invest in obtaining good forecasts. Second, counter-intuitively, this is more important for lightly loaded facilities than heavily loaded facilities. This is because the latter will run close to capacity irrespective of fluctuations in order sizes. Third, the choice of horizon is contingent on the mean load at which we are operating, and not the accuracy of the demand forecast, as has been sometimes covertly assumed. Fourth, re-optimization is very effective, especially, for under-loaded facilities, as it can help exploit uncommitted resources, which are not necessarily present under heavy loads. Interestingly, we show how the recommendations by Gupta and Maravelias (2016), who considered the deterministic problem, are consistent with the results of this study.

In accordance with goal 2, we first identify the key factors that affect the selection of online scheduling parameters. Some of these factors are production load, demand uncertainty, process network characteristics. Second, for each factor, we define an “auxiliary parameter” to quantify it. In some cases, defining this auxiliary parameter is straightforward (e.g., use standard deviation to describe demand variability) but in some cases it is far from trivial. For example, quantifying the load of a facility, subject to a demand pattern, depends on a series of factors and there is no formula to calculate it. We present procedures to calculate all these auxiliary parameters. Third, we present methods to determine the online scheduling parameters (e.g., horizon of optimization problem and re-optimization frequency) from the instance-specific auxiliary parameters. Finally, to test our framework, we present results for two networks that were not used during the development of the framework under different demand patterns.

To our knowledge, the work presented herein is the first systematic framework for the design of an online scheduling algorithm, and thus takes us one-step forward, towards synthesizing a general strategy to obtain high-quality closed-loop schedules.

References:

Subramanian, K.; Rawlings J.B.; Maravelias, C.T. "A state-space model for chemical production scheduling." Computers & chemical engineering 47 (2012): 97-110.

Gupta, D.; Maravelias, C.T. On deterministic online scheduling: Major considerations, paradoxes and remedies. Computers & Chemical Engineering, 94 (2016), 312–330.

Gupta, D.; Maravelias, C.T.; Wassick, J.M. From rescheduling to online scheduling. Chemical Engineering Research and Design, 116 (2016), 83-97