(76c) Online Scheduling Design Principles

Gupta, D., University of Wisconsin-Madison
Maravelias, C. T., University of Wisconsin-Madison
It is now widely recognized that unforeseen disruptions or arrival of new information can make the current schedule of chemical production facility suboptimal or even infeasible, thus motivating the need for online (re)scheduling (Subramanian et al., 2012; Gupta and Maravelias, 2016). However, while the need for online scheduling is recognized, there are a number of open questions regarding the design of online scheduling algorithms. Three pertinent, but for the most part unexplored, aspects of an online scheduling algorithm are (1) the look-ahead or prediction horizon length, (2) the frequency of rescheduling, and (3) the incorporation of feedback through re-optimization (Gupta et al., 2016).

The goal of this work is to develop the principles and a methodology that would allow us to address the following fundamental question: Given a production environment (i.e., resource availability and recipes) and the distributions of the disturbances, what are the best rescheduling frequency and prediction horizon?

We first study how demand uncertainty affects the quality of the implemented schedule. For example, does the time at which uncertainty is observed affect solution quality? How does demand variability 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?

Thereafter, we identify the key factors that affect the selection of online scheduling parameters, namely, production load, demand uncertainty, and 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 explicit expression 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 various networks.

Interestingly, the work presented herein can be viewed as the counter part of controller design for dynamic systems. Given a production system (rather than a dynamic process) described in terms of the aforementioned auxiliary variables (rather than time constants(s)), we decide the parameters of the online scheduler (rather than controller). To our knowledge, the proposed framework is the first systematic attempt to design the online scheduling algorithm, and thus takes us one-step forward, towards synthesizing a general strategy to obtain high-quality closed-loop schedules.


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.