带复合信息的三台平行机半在线排序问题(英文)  

Semi On-line Scheduling on Identical Machines with Combined Partial Information

作　　者：闵啸[1] 

机构地区：[1]嘉兴学院数学与信息科学学院,浙江嘉兴314001

出　　处：《运筹学学报》2006年第1期61-72,共12页Operations Research Transactions

摘　　要：本文讨论在已知加工工件总长度(sum)以及机器带一个缓冲区(buffer)两个复合信息下的同型平行机半在线排序问题． Dosa和He研究了当机器数m=2时的情形,设计出竞争比为5／4的最优半在线算法．本文将其情况推广到三台机器,给出竞争比为4／3的半在线算法,并得到一个11／9的问题下界．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^[1] 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.

关 键 词：运筹学 排序 半在线 近似算法 竞争比 缓冲区 

分 类 号：O223[理学—运筹学与控制论] TV148.1[理学—数学]