Parallel machine scheduling with release dates, due dates and family setup times

In manufacturing, there is a fundamental conflict between efficient production and delivery performance. Maximizing machine utilization by batching similar jobs may lead to poor delivery performance. Minimizing customers’ dissatisfaction may lead to an inefficient use of the machines. In this paper, the authors consider the problem of scheduling n independent jobs with release dates, due dates, and family setup times on m parallel machines. The objective is to minimize the maximum lateness of any job. The authors present a branch-and-bound algorithm to solve this problem. This algorithm exploits the fact that an optimal schedule is contained in a specific subset of all feasible schedules. For lower bounding purposes, the authors see setup times as setup jobs with release dates, due dates and processing times. They present two lower bounds for the problem with setup jobs, one of which proceeds by allowing preemption.