文献类型：期刊文献

中文题名：Pm||C_(max)问题的算法A_(KK)的一个改进的最坏情况性能比(英文)

英文题名：Improved Worst-case Ratio of AKK Algorithm for Pm||C_max

作者：李红英[1];鲁习文[1];陈秀宏[2]

机构：[1]华东理工大学理学院数学系,上海200237;[2]淮阴师范学院数学系,江苏223001

年份：2005

卷号：9

期号：3

起止页码：17

中文期刊名：运筹学学报

外文期刊名：Operations Research Transactions

收录：CSTPCD;;北大核心:【北大核心2004】；CSCD:【CSCD2011_2012】；

语种：中文

中文关键词：运筹学;平行机排序;最大完工时间;最坏情况性能比;Pm‖Cmax

外文关键词：Operations research, scheduling, parallel machine, makespan, worstcase ratio

摘要：本文考虑的是平行机排序问题Pm||Cmax.对此问题Knuth和Kleitman给出了一个近似算法AKK,Graham证明了此算法的最坏情况性能比不大于1+(1-1/m/1+|k/m|),而且当k(?)0(modm)时这个界是紧的.在本文中我们给出了此算法的一个改进的最坏情况性能比:1+max{1-1/m/1+k1+1/m,1-1/m-k2/1+k1},其中k1和k2为非负整数且k1m+k2=k.本文证明了当k2≠0时,它好于Graham的结果,同时我们给出了两个实例说明这个界是紧的.
The parallel machine scheduling problem Pm‖ Cmax is considered here. Knuth and Kleitman provided an approximation algorithm AKK for this problem. Graham hasproved that the worst-case ratio of algorithm AKK is 1＋1-1/m/1＋｜k/m｜ and the bound on AKKis the best possible for k ≡ 0 （modm）. In this paper, we give an improved worst-caseratio 1＋max{1-1/m/1＋k1＋1/m,1-1/m-k2/1＋k1}about algorithm AKK , in which k1m＋ k2 = k andk1, k2 are nonnegative integer. And we prove that it is better than the result of Grahmwhen k2 ≠ 0. And we give two instances to show it is tight.