Optimal semi-online algorithms for machine covering

DOI10.1016/j.tcs.2006.11.015zbMath1108.68023OpenAlexW1987709673MaRDI QIDQ870840

Zhiyi Tan, Yong Wu

Publication date: 15 March 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.11.015

zbMATH Keywords

schedulingcompetitive ratiosemi-onlinedesign and analysis of algorithms

Mathematics Subject Classification ID

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

Related Items

Improved approaches to the exact solution of the machine covering problem ⋮ Semi-online scheduling: a survey ⋮ Fair division of indivisible goods: recent progress and open questions ⋮ Optimal algorithms for semi-online machine covering on two hierarchical machines ⋮ Machine covering with combined partial information

Cites Work

• Unnamed Item
• Semi-on-line multiprocessor scheduling with given total processing time
• The exact LPT-bound for maximizing the minimum completion time
• Semi on-line algorithms for the partition problem
• Semi on-line scheduling on two identical machines
• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• Bin stretching revisited
• The optimal on-line parallel machine scheduling
• Semi-on-line problems on two identical machines with combined partial information
• Semi-online algorithms for parallel machine scheduling problems
• Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
• On-line machine covering
• Semi-online scheduling with decreasing job sizes
• Semi-on-line scheduling problems for maximizing the minimum machine completion time
• On-line bin-stretching