Preemptive scheduling on a small number of hierarchical machines

DOI10.1016/j.ic.2007.11.004zbMath1148.68332MaRDI 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 algorithm; optimal schedule

Mathematics Subject Classification ID

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

Related Items

Makespan minimization in online scheduling with machine eligibility, Makespan minimization in online scheduling with machine eligibility, A note on hierarchical scheduling on two uniform machines, Online and semi-online hierarchical scheduling for load balancing on uniform machines, Total completion time minimization scheduling on two hierarchical uniform machines, On the optimality of the LP-based algorithm for online scheduling with GoS eligibility constraints, Online scheduling on uniform machines with two hierarchies, Optimal online algorithms on two hierarchical machines with tightly-grouped processing times, 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

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