1979 Volume 22 Issue 3 Pages 205-224
Six approximation algorithms for the one-machine scheduling problem with ready and due times to minimize the maximum lateness are analyzed. The performance is measured by the relative deviation of approximate values to optimal ones. Best possible upper bounds on the worst case performance of all six algorithms are derived. The average performance is also examined by solving randomly generated problems; one of the six algorithms outperforms others and keeps the average relative deviation within 2%.