Minimizing maximum lateness with job families

This paper examines an optimal solution procedure for scheduling jobs on a single machine to minimize the maximum lateness in the presence of setup times between different job families. We exploit special structure to compress the effective problem size by creating composite jobs; then we accelerate the enumeration with dominance properties and lower bounds. Our computational evaluation highlights the size of setup times and the variation in due dates.