文献类型：期刊文献

中文题名：P|rj,on-line|∑C_j的一类在线算法与竞争比分析

英文题名：A Class of On-lne Algorithms for Problem P｜rj,on-line｜∑C_j

作者：刘培海[1];鲁习文[1]

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

年份：2007

卷号：16

期号：3

起止页码：56

中文期刊名：运筹与管理

外文期刊名：Operations Research and Management Science

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

基金：国家自然科学基金资助项目;教育部回国人员科研启动基金资助项目;校科研基金资助项目

语种：中文

中文关键词：应用数学;竞争比;在线算法;排序;平行机

外文关键词：applied mathematics;competitive ratio;on-line algorithm;scheduling;identical parallel m achine

摘要：本文研究平等机上的在线排序问题,优化目标是使总完工时间最小,算法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.