摘要
本文研究同型平行机上的在线排序问题。通过平移工件的到达时间,提出了一类在线确定型算法SSPT。对目标为总完工时间的情形,证明了该算法竞争比不了于2且不超过(4-1m),对目标为加工总长的情形,该算法的竞争比的上界为(3-1m)。
In this paper, we present a general on-line deterministic algorithm SSPT for the scheduling problem on identical parallel machines by shifting release time of job j no less than max｛r_j,p_j｝ and no great than r_j+p_j. We show that this algorithm has competitive ratio of no less than 2 and no larger than 4-1m for objective function of minimizing sum of completion time. Furthermore, we deal with the scheduling problem of minimizing the makespan by the algorithm SSPT. We find that this on-line algorithm to minimize makespan on identical parallel machines is(3-1m)-competitive.
出处
《运筹与管理》
CSCD
2004年第6期11-15,95,共6页
Operations Research and Management Science
基金
国家自然科学基金资助项目(19731001)
校科研基金资助项目(XD20K01211)
关键词
在线排序
算法SSPT
同型平行机
竞争比
on-line scheduling
algorithm SSPT
identical parallel machines
competitive ratio
