Single machine scheduling with two job classes: Minimizing maximum lateness

In this paper a single machine scheduling problem with two job classes is considered. In this problem, if two adjacent jobs in a schedule belong to the same class no set up time is required. However, if a job belonging to one class is followed by a job belonging to another class, a set up time is required. The scheduling criterion used is the minimization of maximum lateness. For this problem, some optimality conditions are developed. These conditions are incorporated into a branch-and-bound procedure for finding an optimal solution. Similar problems with other scheduling criteria such as minimizing the sum of completion times and minimizing the sum of weighted completion times, and number of tardy jobs, have been considered by other researchers.