An absolute approximation algorithm for scheduling unrelated machines

Non‐preemptive scheduling of n independent jobs on m unrelated machines so as to minimize the maximal job completion time is considered. A polynomial algorithm with the worst‐case absolute error of min{(1 − 1/ m ) p max , p   max ′ } is presented, where p max is the largest job processing time and p   max ′is the m th element from the non‐increasing list of job processing times. This is better than the earlier known best absolute error of p max . The algorithm is based on the rounding of acyclic multiprocessor distributions. An O ( n m 2 ) algorithm for the construction of an acyclic multiprocessor distribution is also presented. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006