A competitive algorithm for throughput maximization on identical machines
成果类型：
Article
署名作者：
Moseley, Benjamin; Pruhs, Kirk; Stein, Clifford; Zhou, Rudy
署名单位：
Carnegie Mellon University; Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh; Columbia University
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-023-02045-0
发表日期：
2024
页码：
497-514
关键词：
摘要：
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.