Online interval scheduling: Randomized and multiprocessor cases
From MaRDI portal
Publication:1029703
DOI10.1007/s10878-007-9131-zzbMath1176.68038OpenAlexW2592843708MaRDI QIDQ1029703
Feifeng Zheng, Chung Keung Poon, Stanley P. Y. Fung
Publication date: 13 July 2009
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://figshare.com/articles/chapter/Online_interval_scheduling_randomized_and_multiprocessor_cases/10081316
Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)
Related Items (12)
Primal-dual analysis for online interval scheduling problems ⋮ Approximation algorithms for stochastic online matching with reusable resources ⋮ Online interval scheduling on two related machines: the power of lookahead ⋮ On-line scheduling of equal-length intervals on parallel machines ⋮ Improved bounds for randomized preemptive online matching ⋮ Improved online algorithms for the batch scheduling of equal-length jobs with incompatible families to maximize the weighted number of early jobs ⋮ Online C-benevolent job scheduling on multiple machines ⋮ Improved randomized online scheduling of intervals and jobs ⋮ Interval scheduling on related machines ⋮ Improved randomized results for the interval selection problem ⋮ Online interval scheduling to maximize total satisfaction ⋮ Online scheduling of jobs with fixed start times on related machines
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the competitiveness of on-line real-time task scheduling
- Randomized online interval scheduling
- A short proof that `proper = unit'
- MOCA: A multiprocessor on-line competitive algorithm for real-time system scheduling
- On-line scheduling of jobs with fixed start and end times
- Scheduling broadcasts with deadlines
- An improved randomized on-line algorithm for a weighted interval selection problem
- A Near Optimal Scheduler for On-Demand Data Broadcasts
- Improved On-Line Broadcast Scheduling with Deadlines
- Bounding the Power of Preemption in Randomized Scheduling
- Computing and Combinatorics
- $\text{D}^{\textit{over}}$: An Optimal On-Line Scheduling Algorithm for Overloaded Uniprocessor Real-Time Systems
- Theoretical Computer Science
This page was built for publication: Online interval scheduling: Randomized and multiprocessor cases