摘要
本文考虑的是平行机排序问题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.
出处
《运筹学学报》
CSCD
北大核心
2005年第3期17-23,共7页
Operations Research Transactions
