Optimal on-line algorithms to minimize makespan on two machines with resource augmentation

DOI10.1007/S00224-007-9007-8zbMath1140.68008OpenAlexW1997281120MaRDI QIDQ927393

Arik Ganot, Leah Epstein

Publication date: 6 June 2008

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-007-9007-8

zbMATH Keywords

SchedulingLoad balancingOnline algorithmsResource augmentation

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (2)

OPTIMAL ONLINE ALGORITHMS ON TWO HIERARCHICAL MACHINES WITH RESOURCE AUGMENTATION ⋮ Semi-online scheduling: a survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A lower bound for randomized on-line multiprocessor scheduling
• New algorithms for an ancient scheduling problem.
• Preemptive on-line scheduling for two uniform processors
• A better lower bound for on-line scheduling
• On-line scheduling revisited
• Optimal preemptive semi-online scheduling to minimize makespan on two related machines
• An optimal algorithm for preemptive on-line scheduling
• A lower bound for on-line scheduling on uniformly related machines
• Scheduling Independent Tasks on Uniform Processors
• Tighter Bounds for LPT Scheduling on Uniform Processors
• Bounds for LPT Schedules on Uniform Processors
• A Level Algorithm for Preemptive Scheduling
• 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
• Speed is as powerful as clairvoyance
• Maximizing job completions online
• A Better Algorithm for an Ancient Scheduling Problem
• On-Line Load Balancing for Related Machines
• Preemptive Online Scheduling: Optimal Algorithms for All Speeds
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• Optimal non-preemptive semi-online scheduling on two related machines
• Semi-online scheduling with decreasing job sizes
• Randomized on-line scheduling on two uniform machines
• Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios
• Preemptive multiprocessor scheduling with rejection

This page was built for publication: Optimal on-line algorithms to minimize makespan on two machines with resource augmentation