首页 | 本学科首页   官方微博 | 高级检索  
     检索      

P|rj,on-line|∑Cj的一类在线算法与竞争比分析
引用本文:刘培海,鲁习文.P|rj,on-line|∑Cj的一类在线算法与竞争比分析[J].运筹与管理,2007,16(3):56-60.
作者姓名:刘培海  鲁习文
作者单位:华东理工大学,理学院数学系,上海,200237
基金项目:国家自然科学基金;教育部留学回国人员科研启动基金;华东理工大学校科研基金
摘    要:本文研究平等机上的在线排序问题,优化目标是使总完工时间最小,算法SSPT是此问题的一类在线算法,论文引入一个拟时间表,此时间表具有SRPT时间表的部分性质,论文通过此辅助时间表证明了SSPT算法是(3-(1/m))-competitive的.

关 键 词:应用数学  竞争比  在线算法  排序  平行机
文章编号:1007-3221(2007)03-0056-05
修稿时间:2007年1月18日

A Class of On- lne Algorithms for Problem P|rj, on-line|∑Cj
LIU Pei-hai,LU Xi-wen.A Class of On- lne Algorithms for Problem P|rj, on-line|∑Cj[J].Operations Research and Management Science,2007,16(3):56-60.
Authors:LIU Pei-hai  LU Xi-wen
Abstract: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.
Keywords:applied mathematics  competitive ratio  on-line algorithm  scheduling  identical parallel m achine
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号