Résumé IA · arXiv: 2611.12034v1 · cs.DS

The Power of Migration on Identical Machines is Two

Nicole Megow, Bart Zondervan
Article original Soumis à arXiv le 09 Nov. 2026 Licence : CC BY 4.0 Aussi en : en

Comment lire ce résumé ? Guide illustré

L’essentiel

L’article établit que toute instance faisable avec migration sur m machines identiques peut être planifiée sans migration sur 2m−1 machines, avec un algorithme en temps fortement polynomial.

Question

Combien de machines faut-il pour éliminer la migration dans une planification préemptive avec fenêtres temporelles sur des machines identiques ? Les auteurs cherchent à déterminer le meilleur majorant général et à produire une construction efficace.

Méthode

Les auteurs construisent en temps fortement polynomial un ordonnancement supercanonique sur les m machines initiales, avec O(n²) blocs, à l’aide d’un rétrécissement des fenêtres et d’un problème de flot à coût minimal. Ils colorient ensuite le graphe de conflits avec 2m−1 couleurs par réinsertion inductive des tâches et échanges de Kempe ; chaque couleur correspond à une machine sans migration.

Résultats

  • Résultat Tout ensemble de tâches faisable avec migration sur m machines admet un ordonnancement sans migration sur 2m−1 machines, et cet ordonnancement se calcule en temps fortement polynomial.
    Voir le passage dans l’article
    Every instance admitting a feasible migratory schedule on $m$ identical machines admits a feasible non-migratory schedule on $2m-1$ identical machines. Such a schedule can be computed in strongly polynomial time.
  • Résultat La borne de 2m−1 machines est serrée pour chaque m.
    Voir le passage dans l’article
    The bound is tight for every $m$ [16].
  • Résultat Tout graphe de conflits issu d’un ordonnancement supercanonique sur m machines est coloriable avec 2m−1 couleurs.
    Voir le passage dans l’article
    We show that the conflict graph of every supercanonical schedule on $m$ machines can be $(2m-1)$-colored in time polynomial in the number of jobs and processing blocks (Section 3).
  • Résultat Les ordonnancements supercanoniques se construisent avec O(n²) blocs en temps fortement polynomial.
    Voir le passage dans l’article
    Every instance feasible on $m$ machines admits a feasible supercanonical schedule on $m$ machines with $O(n^{2})$ blocks. Such a schedule can be computed in strongly polynomial time.
  • Résultat Sur les mêmes m machines, un ordonnancement sans migration conserve au moins une fraction m/(2m−1) de la valeur optimale migratoire en débit pondéré, et cette garantie est serrée.
    Voir le passage dans l’article
    On the same $m$ machines, a non-migratory schedule can always retain at least an $m/(2m-1)$ fraction of the migratory optimum (Section 5.1).

Limites

  • Le résultat principal concerne des machines identiques sans restrictions d’affectation ; avec affectation restreinte, le nombre de copies de machines nécessaire peut croître comme Ω(m log m), même si chaque tâche n’est admissible que sur deux machines.
    Voir le passage dans l’article
    We show that 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.
  • La construction ne garantit pas l’affectation de tous les emplois d’une même tâche récurrente au même processeur.
    Voir le passage dans l’article
    Our construction may assign different jobs of a task to different processors and therefore gives no guarantee for task partitioning.
  • La suffisance éventuelle de O(log m) copies par machine dans le cas d’affectation restreinte reste ouverte.
    Voir le passage dans l’article
    Whether $O(\log m)$ copies of each machine always suffice under unit-speed restricted assignment remains open.

Portée

Les auteurs ferment un écart ouvert depuis plus de 25 ans en montrant que la borne inférieure classique de 2m−1 est également une borne supérieure, avec une construction en temps fortement polynomial. Ils en déduisent aussi une garantie de vitesse deux pour éliminer la migration sur les m machines d’origine.

Rédigé par une IA à partir de l’article. Les passages cités sont vérifiés mot pour mot dans le texte analysé ; le reste peut contenir des erreurs.

Mots clés générés par l'IA : planification préemptive migration des travaux coloration de graphes machines identiques calendriers supercanoniques

Pour aller plus loin

  • Résumé Complet
  • Résumé vulgarisé
  • Article de blog
  • Abstract original
L’article étudie la « puissance de la migration » dans la planification préemptive sur des machines identiques. Si des travaux peuvent être répartis entre \(m\) machines, interrompus puis repris sur une autre machine, combien de machines faut-il pour les planifier sans migration, chaque travail devant alors rester sur la même machine ? Chaque travail est défini par une durée de traitement, une date de disponibilité et une échéance. Avant cette étude, la meilleure borne générale était de \(6m-5\) machines, tandis qu’un exemple montrait qu’il en fallait parfois \(2m-1\). Les auteurs démontrent que cette borne est exacte : \(2m-1\) machines suffisent toujours, et la construction correspondante s’exécute en temps fortement polynomial. La méthode consiste à représenter un calendrier avec migration par un graphe de conflits. Chaque sommet représente un travail, et deux sommets sont reliés lorsque les travaux correspondants sont exécutés simultanément. Colorier ce graphe revient à affecter les travaux à des machines sans conflit. Le défi est donc de construire, sur \(m\) machines, un calendrier dont le graphe de conflits peut être colorié avec \(2m-1\) couleurs. Les calendriers dits canoniques donnent la priorité aux travaux qui terminent le plus tôt, mais cette propriété ne suffit pas : leur graphe de conflits peut nécessiter jusqu’à \(3m-2\) couleurs. Les auteurs introduisent alors les calendriers « supercanoniques », qui excluent également certains échanges susceptibles de retarder le début d’un travail. Le principal résultat structurel concerne les pauses d’un travail. Dans un calendrier supercanonique, les travaux exécutés juste avant et juste après une pause séparent, dans le graphe, les travaux exécutés entièrement pendant cette pause du reste des travaux. Cette séparation permet d’utiliser des échanges de couleurs de Kempe. Les auteurs procèdent par induction : ils retirent puis réinsèrent les travaux dans un ordre approprié. Des échanges locaux libèrent une couleur pour le travail réinséré ou font diminuer un potentiel entier, ce qui garantit que le processus finit par fournir la couleur nécessaire. Le coloriage s’exécute en temps polynomial par rapport au nombre de travaux et de blocs du calendrier. Il faut également construire un calendrier supercanonique suffisamment compact. Les auteurs commencent par réduire autant que possible les fenêtres de disponibilité et les échéances, sans rendre l’instance irréalisable. Cette réduction écarte les échanges qui retarderaient le début d’un travail et fixe l’ordre de fin des travaux. Ils utilisent ensuite un problème de flot à coût minimal pour répartir le traitement entre des intervalles, en favorisant le traitement précoce des travaux qui terminent le plus tôt. Une règle gloutonne réalise cette répartition sans échange de priorité à l’intérieur des intervalles. Le calendrier obtenu comporte \(O(n^2)\) blocs et peut être calculé en temps fortement polynomial. Combinée au coloriage, cette construction établit le résultat principal. La borne \(2m-1\) est serrée pour toute valeur de \(m\). Considérons \(2m-1\) travaux ayant la même fenêtre et une durée de traitement égale à \(m/(2m-1)\). Ils peuvent être exécutés avec migration sur \(m\) machines. En revanche, chaque travail occupe plus de la moitié de la fenêtre et doit donc disposer de sa propre machine en l’absence de migration.

Cette synthèse vous a-t-elle été utile ?

Note : 0

Pourquoi avons-nous besoin de votes ?

Les votes sont utilisés pour déterminer si nous devons réexécuter nos outils de synthèse. Si le compte atteint -10, nos outils peuvent être redémarrés.

Figures et graphiques

Posez une question sur une figure en indiquant son numéro ou en utilisant son bouton de question pour demander une analyse visuelle. Au maximum deux figures et quatre panneaux par question. Les valeurs lues sur les graphiques sont approximatives ; vérifiez les données originales.

Instructions pour utiliser l'assistant IA ?

Outils pour cet article

Expliquer autrement 1 réécriture gratuite restante aujourd'hui
Enregistrer dans une collection Regroupez des articles en collections pour les comparer, les interroger et les exporter. Continuer avec Google Créer un compte gratuit Se connecter

Outils avancés Premium

Pour suivre un domaine de près : alertes de citations, diapositives de journal club, comparaison des versions et envoi vers Zotero. Découvrir Premium

Zotero Guide Zotero
Alertes de citation Guide des alertes de citations
Qui travaille dessus ?

Parmi les 23 articles autour de celui-ci, le nom qui revient le plus : Benjamin Moseley (3 articles)

6 autres personnes en signent plusieurs. La carte complète ajoute leurs institutions et leurs approches, d’après les articles des dernières années.

Continuer avec Google Créez un compte gratuit : votre première carte est offerte
Lettre hebdomadaire Présenté dans « Informatique hors IA cette semaine » du 16 novembre 2026. Informatique hors IA cette semaine : les coûts cachés des réseaux et les limites repoussées des algorithmes · En recevoir une par email gratuitement

Les articles autour de celui-ci

Les voir sur une carte

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

Avertissement : Notre outil de synthèse basé sur l'IA et l'assistant virtuel fournis sur ce site Web peuvent ne pas toujours fournir des résumés complets ou des réponses exactes. Nous vous encourageons à examiner attentivement et à évaluer le contenu généré pour vous assurer de sa qualité et de sa pertinence par rapport à vos besoins.