Preemptive scheduling on a small number of hierarchical machines

DOI10.1016/j.ic.2007.11.004zbMath1148.68332OpenAlexW2043370925MaRDI QIDQ924724

Leah Epstein, György Dósa

Publication date: 19 May 2008

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2007.11.004

zbMATH Keywords

online algorithmoptimal schedule

Mathematics Subject Classification ID

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

Related Items

Total completion time minimization in online hierarchical scheduling of unit-size jobs ⋮ OPTIMAL ONLINE ALGORITHMS ON TWO HIERARCHICAL MACHINES WITH RESOURCE AUGMENTATION ⋮ Online Hierarchical Scheduling on Two Uniform Machines with Bounded Job Sizes ⋮ A note on hierarchical scheduling on two uniform machines ⋮ Total completion time minimization scheduling on two hierarchical uniform machines ⋮ Online scheduling on uniform machines with two hierarchies ⋮ Online and semi-online hierarchical scheduling for load balancing on uniform machines ⋮ Makespan minimization in online scheduling with machine eligibility ⋮ Makespan minimization in online scheduling with machine eligibility ⋮ On the optimality of the LP-based algorithm for online scheduling with GoS eligibility constraints ⋮ Online fractional hierarchical scheduling on uniformly related machines ⋮ Optimal online algorithms on two hierarchical machines with tightly-grouped processing times

Cites Work

• A lower bound for randomized on-line multiprocessor scheduling
• Online and semi-online scheduling of two machines under a grade of service provision
• Preemptive on-line scheduling for two uniform processors
• A lower bound for randomized on-line scheduling algorithms
• On-line algorithms for the channel assignment problem in cellular networks.
• An optimal algorithm for preemptive on-line scheduling
• A lower bound for on-line scheduling on uniformly related machines
• Optimal online algorithms for scheduling on two identical machines under a grade of service
• On-Line Load Balancing in a Hierarchical Server Topology
• The Competitiveness of On-Line Assignments
• On-line routing of virtual circuits with applications to load balancing and machine scheduling
• On-Line Load Balancing for Related Machines
• Preemptive Online Scheduling: Optimal Algorithms for All Speeds
• Bounds for Certain Multiprocessing Anomalies
• 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