On deterministic online scheduling: Major considerations, paradoxes and remedies

Despite research in the area, the relationship between the (open-loop) optimization problem and the quality of the (closed-loop) implemented schedule is poorly understood. Accordingly, we first show that open-loop and closed-loop scheduling are two different problems, even in the deterministic case. Thereafter, we investigate attributes of the open-loop problem and the rescheduling algorithm that affect closed-loop schedule quality. We find that it is important to reschedule periodically even when there are no “trigger” events. We show that solving the open-loop problem suboptimally does not lead to poor closed-loop solutions; instead, suboptimal solutions are corrected through feedback. We also observe that there exist thresholds for rescheduling frequency and moving horizon length, operating outside of which leads to substantial performance deterioration. Fourth, we show that the design attributes work in conjunction, hence, studying them simultaneously is important. Finally, we explore objective function modifications and constraint addition as methods to improve performance.