The Power of Migration on Identical Machines is Two

Auteurs : Nicole Megow, Bart Zondervan

Soumis à arXiv le 09 Nov. 2026
Licence : CC BY 4.0
Résumé scientifique

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.

Les articles autour de lui, par date et par proximité

Plus haut, c’est plus proche de cet article ; à gauche, c’est plus ancien. Les traits relient les articles proches entre eux : les groupes de traits sont des sous-thèmes. Sélectionnez un point pour voir pourquoi il est là. Retour au résumé de cet article

Comment lire cette carte ? Guide illustré

Les articles les plus proches Les travaux antérieurs sur lesquels il s’appuie Les articles qui le citent

Les articles autour de celui-ci

Classés selon la proximité de leur titre et de leur résumé avec ceux de cet article. Sélectionnez-en pour les lire ensemble.

Les articles les plus proches

  1. Très proche* Contexte plus large
    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 · cité 2 fois · Pas encore résumé

    Preemptive Scheduling of Independent Jobs on Identical Parallel Machines Subject to Migration Delays traite aussi la migration en planification préemptive sur machines identiques, mais avec des délais de migration.

  2. Très proche Contexte plus large
    On the Value of Job Migration in Online Makespan Minimization
    S. Albers, Matthias Hellwig · 2011 · Algorithmica · cité 17 fois · Pas encore résumé

    On the Value of Job Migration in Online Makespan Minimization étudie l’effet de la migration sur le makespan en ligne, sans préemption.

    Résumé scientifique

    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. Très proche* Contexte plus large
    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 · cité 10 fois · Pas encore résumé

    Preemptive scheduling of independent jobs on identical parallel machines subject to migration delays porte sur la migration et la préemption sur machines identiques, avec des délais de migration.

  4. Proche Contexte plus large
    Online Makespan Scheduling with Job Migration on Uniform Machines
    Matthias Englert, David Mezlaf, M. Westermann · 2018 · Algorithmica · cité 6 fois · Pas encore résumé

    Online Makespan Scheduling with Job Migration on Uniform Machines analyse la migration limitée pour le makespan en ligne, sans préemption, sur des machines uniformes.

    Résumé scientifique

    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. Proche Contexte plus large
    Robust algorithms for total completion time
    L. Epstein, Asaf Levin · 2019 · Discrete Optimization · cité 6 fois · Pas encore résumé

    Robust algorithms for total completion time étudie la réaffectation de tâches en ligne pour minimiser le temps total d’achèvement, plutôt que l’élimination de la migration.

    Résumé scientifique

    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. Proche* Contexte plus large Cité par cet article
    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 · cité 10 fois · Pas encore résumé

    General Profit Scheduling and the Power of Migration on Heterogeneous Machines examine le rôle de la migration en planification sur machines hétérogènes.

  7. Proche* Même question Cité par cet article Utilisé en profondeur par cet article
    The Power of Migration in Multiprocessor Scheduling of Real-Time Systems
    G. Koren, E. Dar, A. Amir · 2000 · SIAM journal on computing (Print) · cité 7 fois · Pas encore résumé

    The Power of Migration in Multiprocessor Scheduling of Real-Time Systems étudie l’élimination de la migration en planification multiprocesseur temps réel.

  8. Proche Contexte plus large Cité par cet article
    A competitive algorithm for throughput maximization on identical machines
    Benjamin Moseley, K. Pruhs, C. Stein et al. · 2021 · Mathematical programming · cité 7 fois · Pas encore résumé

    A competitive algorithm for throughput maximization on identical machines traite la planification préemptive en ligne sur machines identiques, avec maximisation des tâches achevées avant échéance.

    Résumé scientifique

    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}.

Les travaux antérieurs sur lesquels il s’appuie

  1. Apparenté* Même question
    Non-migratory online deadline scheduling on multiprocessors
    H. Chan, Tak-Wah Lam, Kar-Keung To · 2004 · ACM-SIAM Symposium on Discrete Algorithms · cité 26 fois · Pas encore résumé

    Non-migratory online deadline scheduling on multiprocessors étudie la planification sans migration de tâches à échéance sur plusieurs processeurs.

  2. Apparenté* Contexte plus large
    Parallel Processor Scheduling with Limited Number of Preemptions
    O. Braun, G. Schmidt · 2003 · SIAM journal on computing (Print) · cité 34 fois · Pas encore résumé

    Parallel Processor Scheduling with Limited Number of Preemptions porte sur la planification sur processeurs parallèles avec un nombre limité de préemptions.

  3. Apparenté Contexte plus large
    Partitioned Scheduling of Recurrent Real-Time Tasks
    Pontus Ekberg, Sanjoy Baruah · 2021 · IEEE Real-Time Systems Symposium · cité 10 fois · Pas encore résumé

    Partitioned Scheduling of Recurrent Real-Time Tasks analyse la faisabilité de tâches temps réel périodiques ou sporadiques affectées à des processeurs.

    Résumé scientifique

    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. Apparenté Contexte plus large
    A Unified Rounding Algorithm For Unrelated Machines Scheduling Problems
    Nikhil R. Devanur, Janardhan Kulkarni · 2018 · ACM Symposium on Parallelism in Algorithms and Architectures · cité 6 fois · Pas encore résumé

    A Unified Rounding Algorithm For Unrelated Machines Scheduling Problems développe une méthode d’approximation pour des problèmes de planification par intervalles sur machines non apparentées.

    Résumé scientifique

    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. Apparenté Contexte plus large
    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 · cité 4 fois · Pas encore résumé

    Approximation Algorithms for Maximum Weighted Throughput on Unrelated Machines étudie l’ordonnancement préemptif à débit pondéré maximal sur machines non apparentées.

    Résumé scientifique

    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…

Comment ces articles sont-ils trouvés ?

Nous comparons le titre et le résumé de cet article avec ceux de tous les articles résumés sur ce site, et avec les articles que Semantic Scholar recommande, ceux qu’il cite et ceux qui le citent (pour un article très cité, ses citations les plus récentes et, depuis OpenAlex, les plus citées). Parmi les travaux antérieurs et les suites, les articles qui s’utilisent en profondeur, une méthode qu’il utilise et les suites très citées remontent un peu. Les niveaux (très proche, proche, apparenté) viennent de la similarité des textes, pas d’un jugement de qualité ; * signale un article sans résumé, comparé par son titre. La phrase sous un article est écrite par une IA à partir des deux résumés : vérifiez-la dans les articles. Un article jugé hors sujet par trois lecteurs quitte la liste.

Mis à jour le 16 novembre 2026.

Le guide illustré des articles autour d’un article