Eliminating Migration in Multi-Processor Scheduling

We investigate the power of migration in real-time multiprocessor scheduling with preemption. We show that every collection of jobs that can be completed by some schedule S on m processors, can also be completed by a nonmigratory schedule S 0 on 3m \Gamma 2 processors. We can conclude from this result that, for many scheduling problems, such as P j r i ; pmtn j P w i (1 \Gamma U i ) and special cases there of, the ability of the scheduler to migrate jobs is of only limited advantage. Our proof is constructive, and can be implemented to run in pseudo-polynomial time (or in polynomial time at the cost of raising the bound from 3m2 to 6m-2). As an example of the usefulness of this result, we give a polynomial time 6-approximation reduction from the problem P j r i ; pmtn j P w i (1 \Gamma U i ) to the problem 1 j r i ; pmtn j P w i (1 \Gamma U i ). The proof of correctness of this reduction critically uses the fact there is a nonmigratory schedule that closely approximates the op..