Résumé IA · arXiv: 2611.12034v1 · cs.DS
The Power of Migration on Identical Machines is Two
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.
Posez des questions sur cet article à notre assistant IA
Comment discuter avec cet article ? Guide illustré
Vous pouvez aussi discutez avec plusieurs papiers à la fois ici.
Gardez cette conversation — un compte gratuit conserve vos questions et réponses, vos collections d’articles et vos alertes.
Continuer avec Google Créer un compte gratuitOutils pour cet article
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
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.
Les articles autour de celui-ci
Les voir sur une carteClassé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
-
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 · 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.
-
On the Value of Job Migration in Online Makespan MinimizationS. 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…
-
Preemptive scheduling of independent jobs on identical parallel machines subject to migration delaysS. 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.
-
Online Makespan Scheduling with Job Migration on Uniform MachinesMatthias 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…
-
Robust algorithms for total completion timeL. 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 …
-
General Profit Scheduling and the Power of Migration on Heterogeneous MachinesSung-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.
-
The Power of Migration in Multiprocessor Scheduling of Real-Time SystemsG. 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.
-
A competitive algorithm for throughput maximization on identical machinesBenjamin 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
-
Non-migratory online deadline scheduling on multiprocessorsH. 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.
-
Parallel Processor Scheduling with Limited Number of PreemptionsO. 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.
-
Partitioned Scheduling of Recurrent Real-Time TasksPontus 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.
-
A Unified Rounding Algorithm For Unrelated Machines Scheduling ProblemsNikhil 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…
-
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 · 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…
Aller plus loin
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.
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.