A branch-and-bound algorithm for single-machine earliness-tardiness scheduling with idle time

J.A. Hoogeveen, S.L. van de Velde

Research output: Contribution to journalArticleAcademicpeer-review

190 Downloads (Pure)


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.
Original languageEnglish
Pages (from-to)402-412
JournalINFORMS journal on computing
Issue number4
Publication statusPublished - 1996


  • Single-machine scheduling
  • Earliness
  • Tardiness
  • Branch-and-bound algorithm
  • Machine idle-time
  • Lagrangian relaxation


Dive into the research topics of 'A branch-and-bound algorithm for single-machine earliness-tardiness scheduling with idle time'. Together they form a unique fingerprint.

Cite this