GENERALIZED BOUND ON LPT SEQUENCING.

For a number of NP-complete sequencing problems, the worst-case performance of heuristics has been bounded relative to optimal performance. The bounds are usually shown to be best in the sense that they are achievable. However, when these bounds are based on a single, pathological example, they are not as informative as might be desired. Such is largely the case with R. L. Graham's bound of 4/3-1/3m on the performance of largest-processing-time-first (LPT) sequencing for the classical problem of minimizing schedule lengths, assuming independent tasks on m greater than equivalent to 2 identical processsors. In this paper Graham's result is generalized to include a parameter characterizing the number of tasks assigned to processors by the LPT rule. The new result will show that the worst-case performance bound for LPT sequencing approaches unity approximately as 1 plus 1/k, where k is the least number of tasks on any processor, or where k is the number of tasks on a processor whose last task terminates the schedule.