Migration cuts machines needed for job scheduling in half

The Power of Migration on Identical Machines is Two

Data Structures and AlgorithmsDiscrete Mathematics

Summary

Scheduling tasks on identical machines can be tricky when jobs need to move between machines (migration). The authors found that if it's possible to schedule jobs with migration on a certain number of machines, then you only need about twice as many machines to schedule the jobs without any migration. They proved this precise number and provided a way to find such a schedule efficiently. Their discovery closes a question that was open for over 25 years in how much extra resource is needed if migration is not allowed.

What this means in practice

A theory result. No direct application yet.

Authors

Nicole Megow, Bart Zondervan

Abstract

We study the power of migration in preemptive scheduling on identical parallel machines with time windows. If an instance admits a migratory schedule on $m$ machines, how many machines are needed to schedule it without migration? Kalyanasundaram and Pruhs (2001) showed that $6m-5$ machines suffice and gave a polynomial-time construction using $12m-5$ machines, whereas $2m-1$ machines may be necessary. We close this gap, which has been open for more than 25 years: $2m-1$ machines always suffice, and a corresponding non-migratory schedule can be computed in strongly polynomial time. Our proof has two main technical ingredients. First, we introduce supercanonical schedules and prove that the conflict graph of every such schedule on $m$ machines is $(2m-1)$-colorable. The key property is that whenever a job pauses, the jobs running alongside it just before and just after the pause separate the jobs processed entirely during the pause from the rest of the conflict graph. We use these separators and Kempe exchanges to compute a coloring in polynomial time. Second, we construct a supercanonical schedule with polynomially many processing blocks by shrinking job windows as far as possible while preserving feasibility and solving a min-cost flow problem.