摘要
讨论两台同型机上的可中断半在线排序问题,目标函数为极大化最小的机器完工时间Cmin.首先考虑已知所有工件的加工时间在p和rp(p>0,r≥1)之间的情形,对任意的参数r,设计了最优半在线算法.接着,对已知最大工件加工时间的情形作了研究,得到了一个竞争比为54的最优半在线算法.
Two preemptive semi online scheduling problems to maximize the minimum machine completion time on two identical machines were investigated. In the first semi-online problem, it is known in advance that all jobs have their processing times in between p and rp（p〉0,r≥l）. For every r≥l , an optimal semi-online algorithm is pro- posed. In the second semi-online problem, it is known that the size of the largest job in advance, and then an optimal semi-online algorithm with competitive ratio 5/4 is proposed.
出处
《浙江大学学报（理学版）》
CAS
CSCD
北大核心
2006年第1期19-23,共5页
Journal of Zhejiang University（Science Edition）
关键词
同型机
半在线
可中断排序
竞争比
identical machines
semi online
preemptive scheduling
competitive ratio
