The Power of Migration on Identical Machines is Two
Auteurs : Nicole Megow, Bart Zondervan
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
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
-
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.