Online interval scheduling: Randomized and multiprocessor cases

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

zbMATH Keywords

intervalsschedulingrandomizationonline algorithms

Mathematics Subject Classification ID

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

• MOCA

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