Optimal preemptive online algorithms for scheduling with known largest size on two uniform machines

DOI10.1007/S10114-005-0829-5zbMath1151.90412OpenAlexW1969445568MaRDI QIDQ856832

Hao Zhou, Yiwei Jiang, Yong He

Publication date: 13 December 2006

Published in: Acta Mathematica Sinica. English Series (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10114-005-0829-5

zbMATH Keywords

competitive ratiouniform machinespreemptive schedulingsemi-online

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Related Items (1)

Linear time algorithms for parallel machine scheduling

Cites Work

• Unnamed Item
• Unnamed Item
• The exact LPT-bound for maximizing the minimum completion time
• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• The optimal on-line parallel machine scheduling
• Ordinal on-line scheduling for maximizing the minimum machine completion time
• Optimal preemptive semi-online scheduling to minimize makespan on two related machines
• Optimal algorithms for semi-online preemptive scheduling problems on two uniform machines
• Preemptive semi-online algorithms for parallel machine scheduling with known total size
• Preemptive machine covering on parallel machines
• Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
• A Level Algorithm for Preemptive Scheduling
• Preemptive Scheduling of Uniform Processor Systems
• On-line machine covering
• Semi-online scheduling with decreasing job sizes

This page was built for publication: Optimal preemptive online algorithms for scheduling with known largest size on two uniform machines