AI summary · arXiv: 2611.12034v1 · cs.DS

The Power of Migration on Identical Machines is Two

Nicole Megow, Bart Zondervan
Original paper Submitted to arXiv on 09 Nov. 2026 License: CC BY 4.0 Also in: fr

How to read this summary? Illustrated guide

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.

AI-generated keywords: Preemptive scheduling migration identical parallel machines conflict-graph coloring time windows

Read further

  • Comprehensive Summary
  • Layman's Summary
  • Blog article
  • Original abstract
The paper studies how much migration helps in preemptive scheduling with time windows on identical parallel machines. Each job has a release date, a deadline, and a required processing time. It may be interrupted, but cannot run on two machines simultaneously. In a migratory schedule, a job may resume on a different machine. The central question is: if a set of jobs can be scheduled with migration on \(m\) machines, how many machines are sufficient to schedule it without migration? Earlier work showed that \(6m-5\) machines suffice, with a polynomial-time construction using \(12m-5\) machines, while examples established that \(2m-1\) machines may be necessary. The paper closes this gap: \(2m-1\) machines always suffice, and the authors provide a strongly polynomial-time algorithm for constructing such a non-migratory schedule. The bound is tight for every \(m\). For example, \(2m-1\) jobs with a common unit-length window and processing time \(m/(2m-1)\) can be scheduled migratorily on \(m\) machines. Without migration, however, each job requires its own machine because it needs more than half of the available window. The proof has two main parts. First, the authors construct a carefully structured schedule on the original \(m\) machines and color its conflict graph. The graph has one vertex per job, with an edge between two jobs that run simultaneously. Assigning each color to a machine then produces a non-migratory schedule. The authors introduce “supercanonical” schedules, which exclude both priority swaps—where an earlier-completing job could take processing time from a later-completing job—and delay swaps, which could postpone a job’s start. They prove that the conflict graph of any such schedule can be colored with \(2m-1\) colors. The coloring argument does not depend on every vertex having low degree. Indeed, the paper shows that even a supercanonical schedule on two machines can have a conflict graph with minimum degree greater than \(2m-2\). Instead, the argument uses pauses in jobs. The jobs running alongside a paused job immediately before and after the pause form a separator between the jobs processed entirely during the pause and the rest of the graph. Kempe exchanges—swapping two colors within suitable connected components—use these separators to free a color for each job. The resulting coloring algorithm runs in polynomial time in the number of jobs and schedule blocks. Second, the paper shows how to obtain a supercanonical schedule with only \(O(n^2)\) processing blocks, where \(n\) is the number of jobs. The authors first shrink each job’s time window as much as possible while preserving feasibility, using feasibility tests and min-cost flow. They then select a minimum-cost processing allocation that favors earlier processing for earlier-completing jobs and realize it using a greedy rule. This produces a canonical schedule and, because the windows are minimal, excludes delay swaps. Together, the two parts establish the machine bound and provide the algorithm. The result also implies that migration can be eliminated on the original \(m\) machines by doubling their speed. The paper gives a lower-bound example showing that the required speed approaches two as \(m\) grows. For weighted throughput, a non-migratory schedule on the same \(m\) machines can retain at least \(m/(2m-1)\) of the migratory optimum, and this fraction is tight. The authors also identify a limitation of the identical-machine setting: with restricted assignment, eliminating migration may require a number of machine copies on the order of \(m\log m\), even when each job is eligible on at most two machines.

Was this synthesis useful?

Score: 0

Why do we need votes?

Votes are used to determine whether we need to re-run our summarizing tools. If the count reaches -10, our tools can be restarted.

Figures and plots

Ask about a figure by number or use its question button to request visual analysis. Up to two figures and four image panels per question. Values read from plots are approximate; check the original data.

AI assistant instructions?

Tools for this paper

Explain it differently 1 free rewrite left today
Save to a collection Group papers in collections to compare them, chat with them and export them. Continue with Google Create a free account Log in

Advanced tools Premium

For researchers who follow a field closely: citation alerts, journal-club slides, version comparison and Zotero export. Discover Premium

Zotero Zotero guide
Citation alerts Citation alerts guide
Who works on it?

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.

Continue with Google Create a free account: your first map is free
Weekly letter Presented in "Computing beyond AI this week" of 16 November 2026. Computing beyond AI this week: The costs hidden in our maps, networks and algorithms · Receive one by email for free

Papers around this one

See them on a map

Ranked by how close their title and abstract are to this paper’s. Select some to read them together.

Closest papers

  1. Very close* Broader context
    Preemptive Scheduling of Independent Jobs on Identical Parallel Machines Subject to Migration Delays
    A. 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.

  2. Very close Broader context
    On the Value of Job Migration in Online Makespan Minimization
    S. 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…

  3. Very close* Broader context
    Preemptive scheduling of independent jobs on identical parallel machines subject to migration delays
    S. 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.

  4. Close Broader context
    Online Makespan Scheduling with Job Migration on Uniform Machines
    Matthias 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…

  5. Close Broader context
    Robust algorithms for total completion time
    L. 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 …

  6. Close* Broader context Cited by this paper
    General Profit Scheduling and the Power of Migration on Heterogeneous Machines
    Sung-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.

  7. Close* Same question Cited by this paper Used in depth by this paper
    The Power of Migration in Multiprocessor Scheduling of Real-Time Systems
    G. 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.

  8. Close Broader context Cited by this paper
    A competitive algorithm for throughput maximization on identical machines
    Benjamin 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

  1. Related* Broader context
    Non-migratory online deadline scheduling on multiprocessors
    H. 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.

  2. Related* Broader context
    Parallel Processor Scheduling with Limited Number of Preemptions
    O. 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.

  3. Related Broader context
    Partitioned Scheduling of Recurrent Real-Time Tasks
    Pontus 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.

  4. Related Another approach to the problem
    A Unified Rounding Algorithm For Unrelated Machines Scheduling Problems
    Nikhil 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…

  5. Related Broader context
    Approximation Algorithms for Maximum Weighted Throughput on Unrelated Machines
    George 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…

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.

The illustrated guide to the papers around a paper

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.