| Pm‖Cmax问题的算法AKK的一个改进的最坏情况性能比 |
| |
| 引用本文： | 李红英,鲁习文,陈秀宏.Pm‖Cmax问题的算法AKK的一个改进的最坏情况性能比[J].运筹学学报,2005,9(3):17-23. |
| |
| 作者姓名： | 李红英 鲁习文 陈秀宏 |
| |
| 作者单位： | 1. 华东理工大学理学院数学系,上海,200237
2. 淮阴师范学院数学系,江苏,223001 |
| |
| 摘 要： | 本文考虑的是平行机排序问题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的结果,同时我们给出了两个实例说明这个界是紧的.
|
| 关 键 词： | 运筹学 平行机排序 最大完工时间 最坏情况性能比 Pm‖Cmax |
| 收稿时间： | 2004-07-28 |
| 修稿时间： | 2004年7月28日 |
Improved Worst-case Ratio of AKK Algorithm for Pm‖ Cmax |
| |
| Li Hongying,Lu Xiwen,Chen Xiuhong.Improved Worst-case Ratio of AKK Algorithm for Pm‖ Cmax[J].OR Transactions,2005,9(3):17-23. |
| |
| Authors: | Li Hongying Lu Xiwen Chen Xiuhong |
| |
| Abstract: | 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. |
| |
| Keywords: | Operations research scheduling parallel machine makespan worstcase ratio |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
