摘要
本文研究平等机上的在线排序问题,优化目标是使总完工时间最小,算法SSPT是此问题的一类在线算法,论文引入一个拟时间表,此时间表具有SRPT时间表的部分性质,论文通过此辅助时间表证明了SSPT算法是(3-1/m)-competitive的。
In this paper,we consider the problem of non-preemptive scheduling jobs on-line on identical parallel machines with the objective to minimize total completion time.We give a general algorithm for the m-machine problem.We construct a new schedule which has some character of SRPT schedule.Through this assistant schedule,we show that the algorithm SSPT for the problem is(3-1/m)-ccompetitive.
出处
《运筹与管理》
CSCD
2007年第3期56-60,65,共6页
Operations Research and Management Science
基金
国家自然科学基金资助项目
教育部回国人员科研启动基金资助项目
校科研基金资助项目
关键词
应用数学
竞争比
在线算法
排序
平行机
applied mathematics
competitive ratio
on-line algorithm
scheduling
identical parallel m achine
