摘要
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.
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.
基金
National Natural Science Founation of China
Austrian"Fonds sur Frdorung der wissonachaftlichen Forschung,Project S32/01"
