Christos Maravelias, University of Wisconsin-Madison
Online Scheduling: Basics, Paradoxes, and Open Questions
Production scheduling is one of the many planning functions in the process industries. In the last two decades there has been an increasing thrust towards using advanced optimization methods to compute better schedules. Hence, much work has been accomplished towards building realistic scheduling models and effective solution methods. Finding the schedule once, however, is only part of the whole scheduling 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, in this talk we will investigate how the design of the open-loop problem affects the quality of the actual implemented schedule (closed-loop schedule). Towards this effort, we conceptualized and proposed a state-space scheduling model [1], thereby alleviating many of the difficulties associated with the use of conventional models for online scheduling. Using this model as our workhorse, we develop a framework for analyzing the relationship between the open-loop problem and the resulting closed-loop schedules.
First, we show that open-loop and closed-loop scheduling are two different problems, even in the deterministic case, when no uncertainty is present. We also show how equally good open-loop schedules can translate to very different closed-loop schedules, so much so, that it could mean a difference between no production vs. production at full capacity. In addition, we discuss a paradox, wherein solving a well-defined open-loop problem to optimality in every iteration leads to a worse closed-loop schedule, than if this same open-loop problem were to be solved to a suboptimal solution. Second, we discuss why it is important to reschedule periodically, even when there are no ”trigger” events, something that is in contrast with the current approaches to rescheduling. Third, we show that suboptimalities in the re-optimizations do not “accumulate”, but instead, are corrected through feedback. Fourth, we study how rescheduling frequency, moving horizon length and suboptimal solutions of open-loop problem affect the quality of closed-loop schedules, and found that there exist certain threshold values, operating outside of which leads to bad closed-loop solutions. These thresholds, which depend on characteristics of the network facility, and the demand pattern, can be utilized to appropriately choose the online scheduling algorithm attributes. We also discuss that there is a cross-relation between these attributes, and hence, we should choose an appropriate value for all three in conjunction. Lastly, we explore objective function modifications and addition of constraints to the open-loop problem as effective methods to improve closed-loop performance. Notably, we show that adding constraints can possibly lead to lower quality open-loop solutions, but can ultimately result in higher quality closed-loop (implemented) solutions. We close with some open questions.
References
[1] Kaushik Subramanian, Christos T. Maravelias, and James B. Rawlings. A state-space model for chemical production scheduling. Computers & Chemical Engineering, 47 (2012): 97-110.
Presentation slides
Biography
Christos was born in Athens, Greece. He obtained his Diploma in Chemical Engineering at the National Technical University of Athens, an MSc in Operational Research from the London School of Economics (London, UK), and a PhD from Carnegie Mellon University. He joined the Department of Chemical and Biological Engineering at the University of Wisconsin – Madison in 2004, where he is now a Vilas Distinguished Achievement Professor. He is the recipient of an NSF CAREER award, the 2008 David Smith and the 2013 Outstanding Young Researcher Awards from the CAST division of AIChE. Christos’ research interests lie in the areas of a) chemical production scheduling, b) supply chain optimization, c) chemical process synthesis and analysis, and d) computational methods for novel material discovery.