Optimal on-line algorithms to minimize makespan on two machines with resource augmentation
From MaRDI portal
Publication:927393
DOI10.1007/S00224-007-9007-8zbMath1140.68008OpenAlexW1997281120MaRDI QIDQ927393
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
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