Online Nonpreemptive Scheduling of Equal-Length Jobs on Two Identical Machines

被引:4
作者
Goldwasser, Michael H. [1 ]
Pedigo, Mark [1 ]
机构
[1] St Louis Univ, Dept Math & Comp Sci, St Louis, MO 63103 USA
关键词
Admission control; competitive analysis; scheduling;
D O I
10.1145/1435375.1435377
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We consider the nonpreemptive scheduling of two identical machines for jobs with equal processing times yet arbitrary release dates and deadlines. Our objective is to maximize the number of jobs completed by their deadlines. Using standard nomenclature, this problem is denoted as P2 vertical bar p(j) = p, r(j) vertical bar Sigma (U) over bar (j). The problem is known to be polynomially solvable in an offline setting. In an online variant of the problem, a job's existence and parameters are revealed to the scheduler only upon that job's release date. We present an online deterministic algorithm for the problem and prove that it is 3/2-competitive. A simple lower bound shows that this is the optimal deterministic competitiveness.
引用
收藏
页数:18
相关论文
共 11 条