A note on LPT scheduling

In the theory of parallel-machine scheduling, the Largest Processing-Time-first (LPT) heuristic has been the touchstone for the design of efficient off-line algorithms. In this note, a new property of the LPT schedules is explored. As a result, Graham’s bound of 4/3-1/(3m) and the generalized bound (Coffman and Sethi) for the performance of LPT heuristic is readily obtained from this property. This note also corrects a flaw in the latter bound in Coffman and Sethi.