Reallocation Problems in Scheduling

In traditional on-line problems, such as scheduling, requests arrive over time, demanding available resources. As each request arrives, some resources may have to be irrevocably committed to servic-ing that request. In many situations, however, it may be possible or even necessary to reallocate previously allocated resources in order to satisfy a new request. This reallocation has a cost. This paper shows how to service the requests while minimizing the realloca-tion cost. We focus on the classic problem of scheduling jobs on a multi-processor system. Each unit-size job has a time window in which it can be executed. Jobs are dynamically added and removed from the system. We provide an algorithm that maintains a valid sched-ule, as long as a sufficiently feasible schedule exists. The algorithm reschedules only O(min{log ∗ n, log∗∆}) jobs for each job that is inserted or deleted from the system, where n is the number of active jobs and ∆ is the size of the largest window