On the N-Job One-Machine, Sequence-Independent Scheduling Problem with Tardiness Penalties: A Branch-Bound Solution

An efficient branch-bound algorithm is presented for solving the n-job, sequence-independent, single machine scheduling problem where the goal is to minimize the total penalty costs resulting from tardiness of jobs. The algorithm and computational results are given for the case of linear penalty functions. The modifications needed to handle the case of nonlinear penalty functions are also presented.