The Power of Migration on Identical Machines is Two
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.
The papers around it, by date and closeness
Higher is closer to this paper; left is older. Lines join papers close to each other: groups of lines are sub-topics. Select a point to see why it is there. Back to the summary of this paper
Papers around this one
Ranked by how close their title and abstract are to this paper’s. Select some to read them together.
Closest papers
-
Preemptive Scheduling of Independent Jobs on Identical Parallel Machines Subject to Migration DelaysA. V. Fishkin, Klaus Jansen, Sergey V. Sevastyanov et al. · 2005 · Embedded Systems and Applications · cited 2 times · Not summarized yet
Preemptive scheduling with migration delays concerns migration in identical-machine scheduling, but the provided title gives no further details.
-
On the Value of Job Migration in Online Makespan MinimizationS. Albers, Matthias Hellwig · 2011 · Algorithmica · cited 17 times · Not summarized yet
On the Value of Job Migration studies migration in online makespan scheduling, rather than preemptive jobs with time windows.
Abstract
Makespan minimization on identical parallel machines is a classical scheduling problem. We consider the online scenario where a sequence of n jobs has to be scheduled non-preemptively on m machines so as to minimize the maximum completion time of any job. The best competitive ratio that can be achieved by deterministic online algorithms is in the range [1.88, 1.9201]. Currently no randomized online algorithm with a smaller competitiveness is known, for general m. In this paper we explore the power of job migration, i.e. an online scheduler is allowed to perform a limited number of job reassignments. Migration is a common technique used in theory and practice to balance load in parallel proce…
-
Preemptive scheduling of independent jobs on identical parallel machines subject to migration delaysS. Sevastyanov, René Sitters, A. V. Fishkin · 2010 · Automation and Remote Control · cited 10 times · Not summarized yet
Preemptive scheduling with migration delays concerns migration in identical-machine scheduling, but the provided title gives no further details.
-
Online Makespan Scheduling with Job Migration on Uniform MachinesMatthias Englert, David Mezlaf, M. Westermann · 2018 · Algorithmica · cited 6 times · Not summarized yet
Online Makespan Scheduling studies limited job reassignment for online makespan on uniform machines, unlike time-window feasibility without migration.
Abstract
In the classic minimum makespan scheduling problem, we are given an input sequence of n jobs with sizes. A scheduling algorithm has to assign the jobs to m parallel machines. The objective is to minimize the makespan, which is the time it takes until all jobs are processed. In this paper, we consider online scheduling algorithms without preemption. However, we allow the online algorithm to change the assignment of up to k jobs at the end for some limited number k. For m identical machines, Albers and Hellwig (Algorithmica 79(2):598–623, 2017) give tight bounds on the competitive ratio in this model. The precise ratio depends on, and increases with, m. It lies between 4/3 and ≈1.4659\document…
-
Robust algorithms for total completion timeL. Epstein, Asaf Levin · 2019 · Discrete Optimization · cited 6 times · Not summarized yet
Robust algorithms for total completion time studies reassignment in online completion-time scheduling, not the machine bound for time-window jobs.
Abstract
Abstract We revisit the problem of scheduling or assigning jobs non-preemptively so as to minimize the total completion time on m identical machines and on m uniformly related machines. This problem is polynomially solvable if all jobs are presented at once, even for unrelated machines. An online algorithm receives jobs one by one, such that every job is scheduled before the next job is presented. A robust algorithm with migration factor γ > 0 also receives jobs one at a time to be assigned immediately, but when a job of size p arrives, the algorithm can re-assign a subset of jobs of total size γ ⋅ p . That is, it can remove the jobs of one such subset from their positions and schedule them …
-
General Profit Scheduling and the Power of Migration on Heterogeneous MachinesSung-Jin Im, Benjamin Moseley · 2016 · ACM Symposium on Parallelism in Algorithms and Architectures · cited 10 times · Not summarized yet
General Profit Scheduling and the Power of Migration studies migration on heterogeneous machines, extending the topic beyond identical-machine time-window scheduling.
-
The Power of Migration in Multiprocessor Scheduling of Real-Time SystemsG. Koren, E. Dar, A. Amir · 2000 · SIAM journal on computing (Print) · cited 7 times · Not summarized yet
The Power of Migration in Multiprocessor Scheduling of Real-Time Systems studies how migration affects real-time multiprocessor scheduling.
-
A competitive algorithm for throughput maximization on identical machinesBenjamin Moseley, K. Pruhs, C. Stein et al. · 2021 · Mathematical programming · cited 7 times · Not summarized yet
A competitive algorithm for throughput maximization schedules deadline jobs online with preemption on identical machines, a neighbouring objective and setting.
Abstract
This paper considers the basic problem of scheduling jobs online with preemption to maximize the number of jobs completed by their deadline on m identical machines. The main result is an O(1) competitive deterministic algorithm for any number of machines m>1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m >1$$\end{document}.
Prior work it builds on
-
Non-migratory online deadline scheduling on multiprocessorsH. Chan, Tak-Wah Lam, Kar-Keung To · 2004 · ACM-SIAM Symposium on Discrete Algorithms · cited 26 times · Not summarized yet
Non-migratory online deadline scheduling concerns deadline jobs on multiprocessors without migration, but its title specifies an online setting.
-
Parallel Processor Scheduling with Limited Number of PreemptionsO. Braun, G. Schmidt · 2003 · SIAM journal on computing (Print) · cited 34 times · Not summarized yet
Parallel Processor Scheduling with Limited Number of Preemptions addresses preemption limits in processor scheduling, rather than migration and time-window feasibility.
-
Partitioned Scheduling of Recurrent Real-Time TasksPontus Ekberg, Sanjoy Baruah · 2021 · IEEE Real-Time Systems Symposium · cited 10 times · Not summarized yet
Partitioned Scheduling of Recurrent Real-Time Tasks studies task assignment and schedulability on identical and heterogeneous multiprocessors.
Abstract
The partitioned scheduling of periodic and sporadic task systems upon multiprocessor platforms (both identical and heterogeneous) is considered. The computational complexity of a large number of such partitioned schedulability problems is examined. New lower and upper bounds on complexity are presented for several problems. Some problems are pigeonholed into their precise complexity classes in this way. A list of problems for which exact classification remains open is compiled.
-
A Unified Rounding Algorithm For Unrelated Machines Scheduling ProblemsNikhil R. Devanur, Janardhan Kulkarni · 2018 · ACM Symposium on Parallelism in Algorithms and Architectures · cited 6 times · Not summarized yet
A Unified Rounding Algorithm develops rounding for interval scheduling on unrelated machines, another algorithmic approach to scheduling jobs in intervals.
Abstract
The rise of cloud computing platforms has led to the study of many scheduling problems. Towards this, general algorithmic techniques that are applicable to a wide range of problems are highly valuable. We develop one such technique by a temporal generalization of the rounding algorithm of \citetShmoysT93 for the generalized assignment problem. Our algorithm gives a bi-criteria approximation algorithm for a problem we introduce, called the generalized interval scheduling problem, on unrelated machines. The problem allows for each job, a specification of a collection of intervals on each machine, with the constraint that the job must be completely processed in one of the given intervals on a s…
-
Approximation Algorithms for Maximum Weighted Throughput on Unrelated MachinesGeorge Karakostas, Stavros G. Kolliopoulos · 2025 · International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algor · cited 4 times · Not summarized yet
Approximation Algorithms for Maximum Weighted Throughput studies weighted job throughput on unrelated machines, not the power of migration.
Abstract
We study the classic weighted maximum throughput problem on unrelated machines. We give a (1 − 1 /e − ε )-approximation algorithm for the preemptive case. To our knowledge this is the first ever approximation result for this problem. It is an immediate consequence of a polynomial-time reduction we design, that uses any ρ -approximation algorithm for the single-machine problem to obtain an approximation factor of (1 − 1 /e ) ρ − ε for the corresponding unrelated-machines problem, for any ε > 0 . On a single machine we present a PTAS for the non-preemptive version of the problem for the special case of a constant number of distinct due dates or distinct release dates. By our reduction this yie…
Go further
How are these papers found?
We compare the title and abstract of this paper with those of every paper summarized on this site, and with the papers Semantic Scholar recommends, those it cites and those citing it (for a much-cited paper, its most recent citations and, from OpenAlex, the most cited ones). Among the prior work and the follow-ups, the papers that use each other in depth, a method it uses and the much-cited follow-ups come a little higher. The levels (very close, close, related) come from the similarity of the texts, not from a judgment of quality; * marks a paper without an abstract, compared by its title. The sentence under a paper is written by an AI from the two abstracts: check it in the papers. A paper marked not relevant by three readers leaves the list.
Updated on 16 November 2026.