摘要
本文考虑一类新的在线平行机排序模型一实时到达在线问题．该模型中，工件是陆续到达的．工件的个数及到达时间是事先未知的，而且只有当工件到达，才知其加工时间，所求目标是使所有工件都加工完的时间达到最小．对两台平行机的情形，Ｃｈｅｎ与Ｖｅｓｔｊｅｎｓ［２］给出了近似比为３／２的在线ＬＰＴ算法，并证明不存在近似比小于（５－）／２的算法．我们利用黄金分割数设计了一个新的算法，其近似比不超过（１８－５）／１１．
in this paper, we will consider a new on-line scheduling model on two parallel machines where jobs arrive over time. The number of jobs is not known beforehand. Each job becomes available at its release date, which is not known in advance, and its processing time becomes known upon its arrival. The goal is to schedule all jobs such that the makespan is minimized. Chen and Vestjens[5] gave an on-line LPT algorithm which a worst-case ratio of 3/2, and proved that no on-line algorithm with a worst-case ratio no more than (18 -5)/11 and thus improve the previous result.
出处
《应用数学学报》
CSCD
北大核心
2000年第1期31-37,共7页
Acta Mathematicae Applicatae Sinica
基金
国家自然科学基金!19801032
