Improved Randomized Online Scheduling of Unit Length Intervals and Jobs

DOI10.1007/978-3-540-93980-1_5zbMath1209.68660OpenAlexW1526632872MaRDI QIDQ3602829

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

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

Related Items (6)

On-line scheduling of equal-length intervals on parallel machines ⋮ Online interval scheduling with a bounded number of failures ⋮ Competitive algorithms for multistage online scheduling ⋮ Improved randomized online scheduling of intervals and jobs ⋮ Improved randomized results for the interval selection problem ⋮ Online scheduling of jobs with fixed start times on related machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the competitiveness of on-line real-time task scheduling
• Randomized online interval scheduling
• On-line scheduling of jobs with fixed start and end times
• Online scheduling with partial job values: does timesharing or randomization help?
• Scheduling broadcasts with deadlines
• Online competitive algorithms for maximizing weighted throughput of unit jobs
• An improved randomized on-line algorithm for a weighted interval selection problem
• A Near Optimal Scheduler for On-Demand Data Broadcasts
• Improved Randomized Results for That Interval Selection Problem
• On randomized online scheduling
• Improved On-Line Broadcast Scheduling with Deadlines
• Online Interval Scheduling: Randomized and Multiprocessor Cases
• Bounding the Power of Preemption in Randomized Scheduling
• $\text{D}^{\textit{over}}$: An Optimal On-Line Scheduling Algorithm for Overloaded Uniprocessor Real-Time Systems
• 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