The Asymptotic Optimality of the LPT Rule

For the problem of minimizing makespan on parallel machines of different speed, the behaviour of list scheduling rules is subjected to a probabilistic analysis under the assumption that the processing requirements of the jobs are independent, identically distributed nonnegative random variables. Under mild conditions on the probability distribution, we obtain strong asymptotic optimality results for the LPT (Longest Processing Time) rule, in which the jobs are assigned to the machines in order of nonincreasing processing requirements.