Dynamic Algorithms for Multimachine Interval Scheduling Through Analysis of Idle Intervals

Abstract

We study the dynamic scheduling problem for jobs with fixed start and end times on multiple machines. The problem is to design efficient data structures that support the update operations: insertions and deletions of jobs. Call the period of time in a schedule between two consecutive jobs in a given machine an idle interval. We show that for any set of jobs there exists a schedule such that the corresponding set of idle intervals forms a tree under the set-theoretic inclusion. We prove that any such schedule is optimal. Based on this result, we provide a data structure that maintains the updates the optimal schedule in O(d+logn)O(d+log⁡n) worst-case time, where d is the depth of the set of idle intervals and n is the number of jobs. Furthermore, we show this bound is tight.