Abstract
We study the dynamic scheduling problem for jobs with fixed start and end times on multiple machines. The problem is to maintain an optimal schedule under 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. Based on this result, we provide a data structure that updates the optimal schedule in O(d+log n) worst-case time, where d is the depth of the set idle intervals and n is the number of jobs. Furthermore, we show this bound to be tight for any data structure that maintains a nested schedule.