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

Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27) 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

• $\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
• scientific article; zbMATH DE number 1003262 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• 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 competitive algorithms for maximizing weighted throughput of unit jobs
• Online Interval Scheduling: Randomized and Multiprocessor Cases
• Online Scheduling of Equal‐Length Jobs: Randomization and Restarts Help
• Online scheduling with partial job values: does timesharing or randomization help?
• Randomized online interval scheduling
• Scheduling broadcasts with deadlines

Cited in

(14)

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

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)