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

带复合信息的三台平行机半在线排序问题
引用本文:闵啸.带复合信息的三台平行机半在线排序问题[J].运筹学学报,2006,10(1):61-72.
作者姓名:闵啸
作者单位:嘉兴学院数学与信息科学学院,浙江嘉兴,314001
摘    要:本文讨论在已知加工工件总长度(sum)以及机器带一个缓冲区(buffer)两个复合信息下的同型平行机半在线排序问题. Dosa和He研究了当机器数m=2时的情形,设计出竞争比为5/4的最优半在线算法.本文将其情况推广到三台机器,给出竞争比为4/3的半在线算法,并得到一个11/9的问题下界.

关 键 词:运筹学  排序  半在线  近似算法  竞争比  缓冲区
收稿时间:2005-03-02
修稿时间:2005年3月2日

Semi On-line Scheduling on Identical Machines with Combined Partial Information
Min Xiao.Semi On-line Scheduling on Identical Machines with Combined Partial Information[J].OR Transactions,2006,10(1):61-72.
Authors:Min Xiao
Institution:Department of Mathematics and Information Science, Jiaxing College, Jiaxing 314001, China
Abstract:This paper investigates a semi on-line scheduling problem on three identical machines with combined partial information. We assume that the total processing time of all the jobs has been known in advance and a buffer is available. When the number of machines is m = 2, Dosa and He present an algorithm with a competitive ratio of 5/4 and it has been the best possible. In this paper the author generalizes this problem by considering three identical machines. Firstly, an algorithm with a competitive ratio of 4/3 is proposed, then a lower bound of 11/9 is derived.
Keywords:Operation research  scheduling  semi on-line  approximation algorithm  competitive ratio  buffer
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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