Task Distributions on Multiprocessor Systems

摘要

We consider the problem of scheduling of n independent jobs on m unrelated machines to minimize the max(t1,t2,…,tm), ti being the completion time of machine i. In [1] was suggested a polynomial 2-approximation algorithm for this problem. It was also proved that there can exist no polynomial 1.5-approximation algorithm unless P=NP. Here we improve this earlier performance bound 2 to 2-1/m. In [1] is also proved a general rounding theorem, which allows to construct in polynomial time 1-job approximations to the optimum, i.e. schedules with an absolute bound equal to the largest job processing time. We also improve this result and obtain (1-1/m)-job approximation to optimal.