A NOTE ON GENERALIZING THE MAXIMUM LATENESS CRITERION FOR SCHEDULING

In this paper 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.