An optimal rounding gives a better approximation for scheduling unrelated machines

A polynomial-time algorithm is suggested for non-preemptive scheduling of n-independent jobs on m-unrelated machines to minimize the makespan. The algorithm has a worst-case performance ratio of 2 - 1/m. This is better than the earlier known best performance bound 2. Our approach gives the best possible approximation ratio that can be achieved using the rounding approach. (C) 2004 Elsevier B.V. All rights reserved.