Online Makespan Scheduling with Job Migration on Uniform Machines

DOI10.4230/LIPIcs.ESA.2018.26OpenAlexW2889114784MaRDI QIDQ5009583

David Mezlaf, Matthias Englert, Matthias Westermann

Publication date: 4 August 2021

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9489/pdf/LIPIcs-ESA-2018-26.pdf/

zbMATH Keywords

competitive analysisonline algorithmsminimum makespan schedulingjob migration

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (1)

Semi-online scheduling: a survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Online scheduling with one rearrangement at the end: revisited
• Online scheduling with rearrangement on two related machines
• Optimal algorithms for online scheduling with bounded rearrangement at the end
• Online scheduling with a buffer on related machines
• Online scheduling with reassignment
• New algorithms for an ancient scheduling problem.
• Online scheduling on two uniform machines to minimize the makespan
• Semi on-line algorithms for the partition problem
• A better lower bound for on-line scheduling
• On-line scheduling revisited
• Optimal preemptive semi-online scheduling to minimize makespan on two related machines
• New lower and upper bounds for on-line scheduling
• A lower bound on deterministic online algorithms for scheduling on related machines without preemption
• On the value of job migration in online makespan minimization
• ONLINE MINIMUM MAKESPAN SCHEDULING WITH A BUFFER
• Online Scheduling with Bounded Migration
• The Power of Reordering for Online Minimum Makespan Scheduling
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• Tighter Bounds for LPT Scheduling on Uniform Processors
• Better Bounds for Online Scheduling
• A Parametric Worst Case Analysis of the LPT Heuristic for Two Uniform Machines
• On-line routing of virtual circuits with applications to load balancing and machine scheduling
• Improved Bounds for the Online Scheduling Problem
• A Better Algorithm for an Ancient Scheduling Problem
• On-Line Load Balancing for Related Machines
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• Preemptive Online Scheduling with Reordering
• Max-min Online Allocations with a Reordering Buffer

This page was built for publication: Online Makespan Scheduling with Job Migration on Uniform Machines