Minimizing the weighted number of tardy jobs on parallel processors

We present a branch-and-bound algorithm to minimize the weighted number of tardy jobs on either identical or non-identical processors. Bounds come from a surrogate relaxation resulting in a multiple-choice knapsack. Extensive computational experiments indicate problems with 400 jobs and several machines can be solved quickly. The results also indicate what parameters affect solution difficulty for this algorithmic approach.