摘要
研究了已知工件最大加工时间,目标为极小化最大机器负载的半在线平行机排序问题.证明了对于一般的m(>6)台机器,任意的半在线算法的竞争比至少是(33+3)/6.同时还设计了一个半在线算法,算法的竞争比为2-1/(m-1).
A semi-online multiprocessor scheduling problem with the longest given processing time is studied, and the objective is to minimize the makespan, i.e. the maximum completion time on the processors. It is shown that the lower bound of the problem is at least （√33＋3）/6 when the number of machine is greater than 6, and a semionline algorithm is presented which has a competitive ratio at most 2-1/（m-1） for any number of processors.
出处
《浙江大学学报（理学版）》
CAS
CSCD
北大核心
2008年第1期23-26,共4页
Journal of Zhejiang University（Science Edition）
关键词
平行机排序
竞争比
半在线
parallel machine scheduling
competitive ratio
semi-online
