Scheduling on uniform parallel machines to minimize maximum lateness

We consider the uniform parallel machine scheduling problem with the objective of minimizing maximum lateness. We show that an extension of the EDD rule to a uniform parallel machine setting yields a maximum lateness value which does not exceed the optimal value by more than p(max), where p(max) is the maximum job processing time. (C) 2000 Elsevier Science B.V. All rights reserved.