AI summary · arXiv: 2611.12034v1 · cs.DS
The Power of Migration on Identical Machines is Two
The essentials
Every migratorily feasible preemptive schedule on m identical machines can be converted into a non-migratory schedule on 2m−1 machines, and this tight bound is computable in strongly polynomial time.
Question
How many identical machines are sufficient to schedule jobs without migration when the instance is feasible with migration on m machines? Can a schedule attaining that bound be constructed efficiently?
Method
The authors construct a supercanonical schedule on the original m machines with O(n²) processing blocks using window shrinking and min-cost flow. They then color its conflict graph with 2m−1 colors using pause separators and Kempe exchanges; each color class becomes a non-migratory machine assignment, and the construction runs in strongly polynomial time.
Findings
-
Result
Every instance feasible with migration on m identical machines has a feasible non-migratory schedule on 2m−1 identical machines.
See the passage in the paper
Every instance admitting a feasible migratory schedule on $m$ identical machines admits a feasible non-migratory schedule on $2m-1$ identical machines.
-
Result
The 2m−1 machine bound is tight for every m.
See the passage in the paper
The bound is tight for every $m$ [16].
-
Result
A schedule meeting the bound can be computed in strongly polynomial time.
See the passage in the paper
Such a schedule can be computed in strongly polynomial time.
-
Result
For weighted preemptive throughput on the same m machines, forbidding migration retains at least an m/(2m−1) fraction of the migratory optimum, and the paper states this guarantee is tight.
See the passage in the paper
Eliminating migration from an optimal migratory schedule by Theorem 1 and retaining the $m$ heaviest of the $2m-1$ machine classes yields
-
Authors’ interpretation
On the original m machines, speed two suffices to eliminate migration, and the authors establish asymptotic optimality of this speedup.
See the passage in the paper
Every instance feasible with migration on $m$ identical unit-speed machines can be scheduled without migration on $m$ speed-two machines in strongly polynomial time.
Limitations
- The main machine bound concerns identical machines without eligibility restrictions; under restricted assignment, even two eligible machines per job can require a logarithmic factor increase in machine copies.
See the passage in the paper
under unit-speed restricted assignment with at most two eligible machines per job, $\Omega(m\log m)$ copies in total may be necessary even in the free model, and thus $\mu=\Omega(\log m)$ in the uniform model.
- The construction guarantees job partitioning, not task partitioning, where all jobs belonging to the same recurrent task must remain on one processor.
See the passage in the paper
Our construction may assign different jobs of a task to different processors and therefore gives no guarantee for task partitioning.
Why it matters
The paper closes a gap open for more than 25 years by proving the tight migration-elimination bound and giving a strongly polynomial construction. The authors also derive consequences for throughput maximization and speed augmentation, while showing that restricted assignment can invalidate a constant-factor machine bound.
Written by AI from the paper. Passages are checked word for word against the text we analysed; the rest may contain errors.
Ask questions about this paper to our AI assistant
How to chat with this paper? Illustrated guide
You can also chat with multiple papers at once here.
Keep this conversation — a free account saves your questions and answers, your collections of papers and your alerts.
Continue with Google Create a free accountTools for this paper
Advanced tools Premium
For researchers who follow a field closely: citation alerts, journal-club slides, version comparison and Zotero export. Discover Premium
Among the 23 papers around this one, the name that comes back most: Benjamin Moseley (3 papers)
6 more people sign several of them. The full map adds their institutions and approaches, from the papers of the last years.
Papers around this one
See them on a mapRanked 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.
Disclaimer: The AI-based summarization tool and virtual assistant provided on this website may not always provide accurate and complete summaries or responses. We encourage you to carefully review and evaluate the generated content to ensure its quality and relevance to your needs.