The LPT rule is a heuristic method to distribute jobs among identical machines so as to minimize the makes pan of the resulting schedule. If the processing times of the jobs are assumed to be independent identically distributed random variables, then (under a mild condition on the distribution) the absolute error of this heuristic is known to converge to 0 almost surely. In this note we show that the speed of convergence is proportional to logn/n, thus extending earlier results obtained for the uniform and exponential distribution.

Name | Memorandum COSOR |
---|

Volume | 8501 |
---|

ISSN (Print) | 0926-4493 |
---|