文献类型：期刊文献

中文题名：同型平行机上在线排序问题的近似算法

英文题名：Approximation Algorithms for On-line Scheduling Problems on Identical Parallel Machines

作者：鲁习文[1]

机构：[1]华东理工大学理学院数学系,上海200237

年份：2004

卷号：13

期号：6

起止页码：11

中文期刊名：运筹与管理

外文期刊名：Operations Research and Management Science

收录：CSTPCD;;国家哲学社会科学学术期刊数据库;CSCD:【CSCD_E2011_2012】；

基金：国家自然科学基金资助项目(19731001);校科研基金资助项目(XD20K01211)

语种：中文

中文关键词：在线排序;算法SSPT;同型平行机;竞争比

外文关键词：on-line scheduling; algorithm SSPT; identical parallel machines; competitive ratio

摘要：本文研究同型平行机上的在线排序问题。通过平移工件的到达时间,提出了一类在线确定型算法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.