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+logn) 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.
