摘要
本文考虑了平行机实时到达的在线问题．模型中，工件是陆续到达的，工件的个数、到达时间是事先未知的，而且只有当工件到达，才知其加工时间，目标是使所有工件都加工完的时间达到最小．Ｃｈｅｎ与Ｖｅｓｔｊｅｎｓ（１９９６年）证明了该在线问题不存在性能比小于１．３４７３的ｏｎ－ｌｉｎｅ算法．本文将此界改进为（５－５）／２．
A parallel machine scheduling
problem where jobs arrive over time is considered.The number of jobs is unknown in
advance.Each job becomes available at its release date,which is not known indvance,and its
processing time becomes known at its arrival.The paper deal with the problem of minimizing
the makespan,which is the time by which all jobs have been finished.Chen and Vestjens (in
1996)proved that any on line algorithm wound have a performance bound of at least 1
3473.This bound is improved to (5-5)/2≈1 3820 in this paper.
出处
《高校应用数学学报（A辑）》
CSCD
北大核心
1999年第3期315-318,共4页
Applied Mathematics A Journal of Chinese Universities(Ser.A)
基金
国家自然科学基金
国家973基础研究项目
