A Branch-and-Bound Algorithm for Single-Machine Earliness–Tardiness Scheduling with Idle Time

We address the NP-hard single-machine problem of scheduling n independent jobs so as to minimize the sum of α times total completion time and β times total earliness with β > α, which can be rewritten as an earliness–tardiness problem. Postponing jobs by leaving the machine idle may then be advantageous. The allowance of machine idle time between the execution of jobs singles out our problem from most concurrent research on problems with earliness penalties. Solving the problem to optimality poses a computational challenge, since the possibility of leaving the machine idle has a major effect on designing a branch-and-bound algorithm in general, and on computing lower bounds in particular. We present a branch-and-bound algorithm which is based upon many dominance rules and various lower bound approaches, including relaxation of the machine capacity, data manipulation, and Lagrangian relaxation. The algorithm is shown to solve small instances with up to 20 jobs.