A competitive algorithm for throughput maximization on identical machines

DOI10.1007/978-3-031-06901-7_30zbMath1497.90096arXiv2111.06564OpenAlexW4285196344MaRDI QIDQ2164724

Rudy Zhou, Benjamin Moseley, Clifford Stein, Kirk R. Pruhs

Publication date: 16 August 2022

Full work available at URL: https://arxiv.org/abs/2111.06564

zbMATH Keywords

schedulingcompetitive analysisonline algorithm

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (1)

Online Throughput Maximization on Unrelated Machines: Commitment is No Burden

Cites Work

• On the competitiveness of on-line real-time task scheduling
• MOCA: A multiprocessor on-line competitive algorithm for real-time system scheduling
• An improved algorithm for online machine minimization
• Eliminating Migration in Multi-processor Scheduling
• Speed is as powerful as clairvoyance
• An $\mathcal{O}(\log {m})$-Competitive Algorithm for Online Machine Minimization
• Maximizing job completions online
• A general framework for handling commitment in online throughput maximization
• Optimal time-critical scheduling via resource augmentation

This page was built for publication: A competitive algorithm for throughput maximization on identical machines