SINGLE-MACHINE SCHEDULING WITH RELEASE DATES, DUE-DATES AND FAMILY SETUP TIMES

We address the NP-hard problem of scheduling n independent jobs with r elease dates, due dates, and family setup times on a single machine to minimize the maximum lateness. This problem arises from the constant tug-of-war going on in manufacturing between efficient production and delivery performance, between maximizing machine utilization by batchi ng similar jobs and maximizing customers' satisfaction by completing j obs before their due dates. We develop a branch-and-bound algorithm, a nd our computational results show that it solves almost all instances with up to about 40 jobs to optimality. The main algorithmic contribut ion is our lower bounding strategy to deal with family setup times. Th e key idea is to see a setup time as a setup job with a specific proce ssing time, release date, due date, and precedence relations. We devel op several sufficient conditions to derive setup jobs. We specify thei r parameters and precedence relations such that the optimal solution v alue of the modified problem obtained by ignoring the setup times, not the setup jobs, is no larger than the optimal solution value of the o riginal problem. One lower bound for the modified problem proceeds by allowing preemption. Due to the agreeable precedence structure, the pr eemptive problem is solvable in O(n log n) time.