Online Scheduling

In the last two decades there has been an increasing thrust towards using advanced optimization-based methods to construct better schedules. Finding the schedule once, however, is only part of the whole process. Due to disruptions or arrival of new information, the incumbent schedule can become suboptimal or even infeasible, thus motivating the need for online (re)scheduling. Accordingly, we are investigating how the design of the online scheduling problem (the open-loop problem), and the frequency at which it is solved, affects the quality of the actual implemented schedule (the closed-loop schedule). The ultimate goal is to find the best “online scheduling algorithm”. We have developed a framework for analyzing the relationship between the open-loop problem and the quality of the resulting closed-loop schedule. Through the use of this framework, we have shown, for example, that modifications made keeping an open-loop implementation in mind, do not necessarily result in an improved closed-loop performance. This counter-intuitive observation, along with many other interesting findings, suggest that online scheduling is poorly understood – it is a confounding problem ripe with challenges which, through the efforts in our group, we are now just beginning to understand.

Figure 1: Online scheduling using a moving (rolling) horizon. Schedule revision and further schedule generation happen in the same iteration. State of the plant represents complete information of the ``current status" as a result from the previous state, the scheduling decisions, and disturbances.

Figure 1: Online scheduling using a moving (rolling) horizon. Schedule revision and further schedule generation happen in the same iteration. State of the plant represents complete information of the “current status” as a result from the previous state, the scheduling decisions, and disturbances.