节点文献

三台平行机排序的一个复合半在线问题的算法

A Semi-Online Algorithm for Parallel Machine Scheduling on Three Machines

  • 推荐 CAJ下载
  • PDF下载
  • 不支持迅雷等下载工具，请取消加速工具后下载。

【作者】 华荣伟； 胡觉亮； 卢璐；

【Author】 HUA Rong-wei~(1,2),HU Jue-liang~3,LU Lu~4(1.Department of Mathematics,Zhejiang University,Hangzhou 310027,China;2.Zhejiang Medicine College,Hanzhou 310053,China;3.Department of Information and Computing Science,Zhejiang Sci-Tech University,Hangzhou 310033,China; 4.Intel Company,Shanghai Branch,Shanghai 200031,China)

【机构】 浙江大学数学系； 浙江理工大学； 英特尔产品上海有限公司 浙江杭州310027； 浙江医学高等专科学校； 浙江杭州310053； 浙江杭州310033； 上海200031；

【摘要】 本文讨论一个三台平行机半在线排序问题。对预先知道工件的总加工时间和最大的工件的加工时间的复合半在线模型,我们证明了不存在半在线算法,其竞争比为4/3,并给出了一个竞争比为7/5的半在线算法,两者的差距小于0.067。

【Abstract】 This paper considers a semi-online parallel machine scheduling problem on a 3-machine system.We assume that the total processing time of all jobs and the largest processing time are known in advance.We present a new semi-online algorithm with competitive ratio 7/5 while no algorithm can have competitive ratio smaller than 4/3.The gap between them is less than 0.067.

【关键词】 排序； 半在线； 近似算法；
【Key words】 scheduling； semi-online； approximation algorithm；
【基金】 浙江省自然科学基金资助项目(Y605316)
  • 【文献出处】 管理工程学报 ,Journal of Industrial Engineering and Engineering Management , 编辑部邮箱 ,2006年03期
  • 【分类号】O223
  • 【被引频次】1
  • 【下载频次】100
打印本页
节点文献中：