Note—Sequencing n Jobs on m Machines to Minimise Maximum Tardiness: A Branch-and-Bound Solution

Each of n jobs is to be sequenced on m machines, with each job having a due date, and we wish to minimise the maximum tardiness of any job. The problem has been solved by Smith [Smith, W. E. 1956. Various optimizers for single-state production. Naval Research Logistics Quarterly3 59–66] for the case of one machine. This note develops a branch-and-bound method for the general case.