On-Line Load Balancing for Related Machines

DOI10.1006/jagm.1999.1070zbMath0954.68050OpenAlexW2062657914MaRDI QIDQ4953248

Piotr Berman, Moses Charikar, Marek Karpinski

Publication date: 4 October 2000

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jagm.1999.1070

zbMATH Keywords

scheduling

Mathematics Subject Classification ID

Theory of operating systems (68N25)

Related Items (39)

A survey on makespan minimization in semi-online environments ⋮ Better Algorithms for Online Bin Stretching ⋮ Tight upper bounds for semi-online scheduling on two uniform machines with known optimum ⋮ ONLINE MINIMUM MAKESPAN SCHEDULING WITH A BUFFER ⋮ ONLINE SCHEDULING OF MIXED CPU-GPU JOBS ⋮ Rejecting jobs to minimize load and maximum flow-time ⋮ Semi-online scheduling: a survey ⋮ A two-phase algorithm for bin stretching with stretching factor 1.5 ⋮ Lower bounds for online makespan minimization on a small number of related machines ⋮ Configuration balancing for stochastic requests ⋮ Well-behaved online load balancing against strategic jobs ⋮ Parallel solutions for preemptive makespan scheduling on two identical machines ⋮ Online and semi-online hierarchical scheduling for load balancing on uniform machines ⋮ Online bin stretching with three bins ⋮ Unnamed Item ⋮ Tight Bounds for Online Vector Scheduling ⋮ Online scheduling with rejection and withdrawal ⋮ Preemptive scheduling on a small number of hierarchical machines ⋮ The hierarchical model for load balancing on two machines ⋮ Optimal on-line algorithms to minimize makespan on two machines with resource augmentation ⋮ Robust algorithms for preemptive scheduling ⋮ A lower bound for on-line scheduling on uniformly related machines ⋮ Online Makespan Scheduling with Job Migration on Uniform Machines ⋮ Deterministic monotone algorithms for scheduling on related machines ⋮ On the optimality of list scheduling for online uniform machines scheduling ⋮ Online Scheduling on a CPU-GPU Cluster ⋮ Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios ⋮ On-line load balancing of temporary tasks revisited ⋮ Online scheduling of jobs with favorite machines ⋮ Preemptive online scheduling: Optimal algorithms for all speeds ⋮ Starting time minimization for the maximum job variant ⋮ Online scheduling with general machine cost functions ⋮ Online makespan scheduling with job migration on uniform machines ⋮ Tight lower bounds for semi-online scheduling on two uniform machines with known optimum ⋮ Optimal and online preemptive scheduling on uniformly related machines ⋮ Approximating the Optimal Algorithm for Online Scheduling Problems via Dynamic Programming ⋮ Minimum Congestion Mapping in a Cloud ⋮ A lower bound on deterministic online algorithms for scheduling on related machines without preemption ⋮ A manifesto for the computational method

This page was built for publication: On-Line Load Balancing for Related Machines