| A SIMPLE PROOF OF THE INEQUALITY R_M(MF(κ))≤1.2+(1/2~κ) IN MULTIPROCESSOR SCHEDULING |
| |
| 引用本文： | 越民义,HANS KELLERER,俞忠良.A SIMPLE PROOF OF THE INEQUALITY R_M(MF(κ))≤1.2+(1/2~κ) IN MULTIPROCESSOR SCHEDULING[J].应用数学学报(英文版),1992(3). |
| |
| 作者姓名： | 越民义 HANS KELLERER 俞忠良 |
| |
| 作者单位： | Institute of Applied Mathematics，Academia Sinica，Beijing 100080，China，Institut fur Mathematik，Technische Universitat Graz，A-8010 Graz，Austria.，Mathematics Section，Nanjing Forestry University，Nanjing 200028，China Institut fur Mathematik，Technische Universitat Graz，A-8010 Graz，Austria. |
| |
| 基金项目： | National Natural Science Founation of China，Austrian“Fonds sur Frdorung der wissonachaftlichen Forschung,Project S32/01” |
| |
| 摘 要： | We consider the well-known problem of scheduling n independent tasks nonpreemptivelyon m identical processors with the objective of minimizing the makespan. Coffman, Garey andJohnson described an algorithm MULTIFIT, based on bin-packing, with a worst case performancebetter than the LPT-algorithm. The bound 1.22 obtained by them was claimed by Friesen in1984 that it can be improved to 1.2. In this paper we give a simp1e proof for this bound.
|
| 本文献已被 CNKI 等数据库收录！ |
