Improved Randomized Online Scheduling of Unit Length Intervals and Jobs

DOI10.1007/978-3-540-93980-1_5MaRDI QIDQ3602829zbMATH OpenOpenAlexFDO

Authors Chung Keung Poon, Feifeng Zheng, Stanley P. Y. Fung

Publication date 12 February 2009

Published in Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-93980-1_5

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Randomized algorithms (68W20) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Improved randomized online scheduling of intervals and jobs
• Online Scheduling of Equal‐Length Jobs: Randomization and Restarts Help
• Online Interval Scheduling: Randomized and Multiprocessor Cases
• Online interval scheduling: Randomized and multiprocessor cases
• Automata, Languages and Programming

Cites work

• scientific article; zbMATH DE number 1003262 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• $\text{D}^{\textit{over}}$: An Optimal On-Line Scheduling Algorithm for Overloaded Uniprocessor Real-Time Systems
• A Near Optimal Scheduler for On-Demand Data Broadcasts
• An improved randomized on-line algorithm for a weighted interval selection problem
• Bounding the Power of Preemption in Randomized Scheduling
• Considering suppressed packets improves buffer management in QoS switches
• Improved On-Line Broadcast Scheduling with Deadlines
• Improved Randomized Results for That Interval Selection Problem
• On randomized online scheduling
• On the competitiveness of on-line real-time task scheduling
• On-line scheduling of jobs with fixed start and end times
• Online Interval Scheduling: Randomized and Multiprocessor Cases
• Online Scheduling of Equal‐Length Jobs: Randomization and Restarts Help
• Online competitive algorithms for maximizing weighted throughput of unit jobs
• Online scheduling with partial job values: does timesharing or randomization help?
• Randomized online interval scheduling
• Scheduling broadcasts with deadlines

Cited in

(13)

• Improved randomized results for the interval selection problem
• On-line scheduling of equal-length intervals on parallel machines
• Improved upper bounds for online malleable job scheduling
• Online Scheduling of Bounded Length Jobs to Maximize Throughput
• ONLINE SCHEDULING OF UNIT JOBS WITH BOUNDED IMPORTANCE RATIO
• Online competitive algorithms for maximizing weighted throughput of unit jobs
• Online interval scheduling with a bounded number of failures
• Improved randomized online scheduling of intervals and jobs
• Competitive algorithms for multistage online scheduling
• Automata, Languages and Programming
• Online scheduling of jobs with fixed start times on related machines
• Improved competitive algorithms for online scheduling with partial job values
• Online Scheduling of Equal‐Length Jobs: Randomization and Restarts Help

This page was built for publication: Improved Randomized Online Scheduling of Unit Length Intervals and Jobs

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