In this note, we consider generalizing the objective criterion of minimizing maximum lateness in scheduling models. By isolating the properties of this objective function, we are able to show that certain approximation algorithms for the lateness model can be modified to handle a more general objective function, while preserving some performance guarantee. In particular, a special case of the more general criterion is minimizing the maximum weighted completion time of any job, and so our results highlight the close resemblance this objective function bears to minimizing maximum lateness.
This paper has appeared in Discrete Appl. Math. 47 (1993), 129-137.
If you would like a reprint, you can contact me at leslie@jhu.edu.