A competitive algorithm for throughput maximization on identical machines

期刊论文
出版模式：

开放获取
发表日期：

2024年1月10日

查看全文

Benjamin Moseley,
Kirk Pruhs,
Clifford Stein,
Rudy Zhou

摘要

This paper considers the basic problem of scheduling jobs online with preemption to maximize the number of jobs completed by their deadline on m identical machines. The main result is an O(1) competitive deterministic algorithm for any number of machines $m >1$ $m > 1$ .