Eliminating Migration in Multi-processor Scheduling

✍ Scribed by Bala Kalyanasundaram; Kirk R Pruhs

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 186 KB
• Volume: 38
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.2000.1128

✦ Synopsis

We investigate the power of migration in real-time multi-processor 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 on 6m -5 processors. We can conclude from this result that, for many scheduling problems, such as P r i pmtn w i 1 -U i and special cases thereof, 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 6m -5 to 12m -5). As an example of the usefulness of this result, we give a polynomial-time 6-approximation reduction from the problem P r i pmtn w i 1 -U i to the problem 1 r i pmtn w i 1 -U i . The proof of correctness of this reduction critically uses the fact that there is a nonmigratory schedule that closely approximates the optimal migratory schedule.