| 平行机问题中GKK算法性能比界的改进 |
| |
| 引用本文： | 陈秀宏.平行机问题中GKK算法性能比界的改进[J].宁夏大学学报(自然科学版),2004,25(3):223-225. |
| |
| 作者姓名： | 陈秀宏 |
| |
| 作者单位： | 淮阴师范学院,数学系,江苏,淮安,223001 |
| |
| 基金项目： | 江苏省高校自然科学基金资助项目(03KJB110012)，江苏省教育厅自然科学基金资助项目(00KJD110001，01KJD110005) |
| |
| 摘 要： | 将n个工件分配到m台平行机上加工，在工件的加工不中断及目标函数是极小化最大完工时间的条件下，对其GKK算法的最坏情形性能比界作了改进，并用实例表明了所得新上界的可达性。
|
| 关 键 词： | 平行机 近似算法 性能比界 GKK算法 可达性 |
| 文章编号： | 0253-2328(2004)03-0223-03 |
| 修稿时间： | 2004年3月19日 |
Improvement of the Performance Ratio Bound for GKK Algorithm in Parallel Processor Problems |
| |
| Chen Xiuhong.Improvement of the Performance Ratio Bound for GKK Algorithm in Parallel Processor Problems[J].Journal of Ningxia University(Natural Science Edition),2004,25(3):223-225. |
| |
| Authors: | Chen Xiuhong |
| |
| Abstract: | We consider one of the basic, well studied problem of scheduling theory, that of nonpreemptive assignment of n independent jobs on m identical parallel processors with the objective of minimizing the makespan. One of the well-known heuristic algorithms which find near optimal schedules is obtained by Graham-Knuth-Kleitman. Its best worst-case the performance ratio bound is 1+1-1/m1+k/m], where k>0 is an integer number and k/m] is the largest integer number no more than k/m. In this paper, we improve the above bound and give some instances which the new bound is realizable. |
| |
| Keywords: | identical parallel processors heuristic algorithm the performance ratio bound GKK algorithm realizability |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
