Improved competitive algorithms for online scheduling with partial job values

DOI10.1016/J.TCS.2004.02.046MaRDI QIDQ1884846zbMATH OpenOpenAlexFDO

Authors Francis Y. L. Chin, Stanley P. Y. Fung

Publication date 27 October 2004

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

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

zbMATH Keywords

SchedulingOnline algorithmsResource augmentationPartial job values

Mathematics Subject Classification ID

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

Recommendations

• Improved competitive algorithms for online scheduling with partial job values
• Improved randomized online scheduling of intervals and jobs
• Improved Bounds for the Online Scheduling Problem
• Competitive online scheduling of perfectly malleable jobs with setup times
• An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time
• Competitive algorithms for multistage online scheduling
• Improved Randomized Online Scheduling of Unit Length Intervals and Jobs
• A new approach to online scheduling: approximating the optimal competitive ratio
• A new approach to online scheduling: approximating the optimal competitive ratio
• Improved upper bounds for online malleable job scheduling

Cites work

• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 1559529 (Why is no real title available?)
• scientific article; zbMATH DE number 1796988 (Why is no real title available?)
• $\text{D}^{\textit{over}}$: An Optimal On-Line Scheduling Algorithm for Overloaded Uniprocessor Real-Time Systems
• On the competitiveness of on-line real-time task scheduling
• Online scheduling with partial job values: does timesharing or randomization help?
• Performance guarantee for online deadline scheduling in the presence of overload
• Preemptive scheduling in overloaded systems.
• Speed is as powerful as clairvoyance

Cited in

(5)

• Improved competitive algorithms for online scheduling with partial job values
• Randomized two-valued bounded delay online buffer management
• scientific article; zbMATH DE number 1670547 (Why is no real title available?)
• Partial servicing of on-line jobs
• Online scheduling with partial job values: does timesharing or randomization help?

This page was built for publication: Improved competitive algorithms for online scheduling with partial job values

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