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, b...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 ChinaAustrian"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.
