Approximation algorithms for scheduling on uniform processors

The problem of scheduling independent tasks on uniform processors in order to minimize the maximum completion time of the schedule is strongly NP-complete. Therefore, the existence of a polynomial or even a pseudo-polynomial time algorithm is very unlikely unless P=NP. This paper deals with approximation schemes which attempt to find a solution in polynomial time that is close to the optimal solution. Specifically, two variants of LPT scheduling are shown: one which is polynomial time and the other a probabilistically good algorithm.