Optimal semi-online algorithms for machine covering

DOI10.1016/J.TCS.2006.11.015MaRDI QIDQ870840zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• SEMI-ONLINE MACHINE COVERING
• Approximation and Online Algorithms
• Optimal semi-online algorithm for machine covering with nonsimultaneous machine available times
• Optimal algorithms for semi-online machine covering on two hierarchical machines
• Online, semi-online algorithms for machine covering with non-simultaneous machine available time

Cites work

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

Cited in

(13)

• Approximation and Online Algorithms
• Semi-online machine covering for two uniform machines
• Fair division of indivisible goods: recent progress and open questions
• SEMI-ONLINE MACHINE COVERING
• Improved approaches to the exact solution of the machine covering problem
• Online maximum \(k\)-coverage
• Online, semi-online algorithms for machine covering with non-simultaneous machine available time
• Optimal Semi-online Scheduling Algorithms on a Small Number of Machines
• Optimal algorithms for semi-online machine covering on two hierarchical machines
• Machine covering with combined partial information
• Optimal semi-online algorithm for machine covering with nonsimultaneous machine available times
• A better semi-online algorithm for \(\mathrm Q3/s_{1} = s_{2}\leq s_{3}/C_{\mathrm{min}}\) with the known largest size
• Semi-online scheduling: a survey

This page was built for publication: Optimal semi-online algorithms for machine covering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q870840)