作者：李红英; 鲁习文; 陈秀宏运筹学平行机排序最大完工时间最坏情况性能比
摘要：本文考虑的是平行机排序问题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的结果,同时我们给出了两个实例说明这个界是紧的.
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
