摘要
本文研究了的随机算法及其最坏情况界.我们给出了在线排序问题新的随机上界,并给出了的最好随机算法,其最坏情况界为2/3.对已知工件加工时间递减半在线模型,我们给出了一最坏情况界为6/7的随机算法并证明了它为最好的.
In this paper, we present randomized algorithms for parallel machine scheduling with objective to maximize the minimum machine completion time. We give a new lower bound for general m > 1 machines case. For m = 2, we present best possible randomized algorithms for its on-line version and a semi on-line version with job decreasing processing time.
出处
《应用数学学报》
CSCD
北大核心
2002年第4期746-751,共6页
Acta Mathematicae Applicatae Sinica
基金
国家973重点基础研究专项经费(G1998030401(2))
高等学校优秀青年教师教学科研奖励计划资助项目
关键词
在线排序
随机算法
最坏情况界
On-line scheduling, randomized algorithm, worst-case ratio
