A competitive algorithm for throughput maximization on identical machines
研究在m台同构机器上在线调度可抢占作业，以最大化在截止日期前完成的作业数量，并给出了一个常数竞争比的确定性算法。
Abstract 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>m</mml:mi> <mml:mo>></mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> .