In this paper, we describe an exact algorithm to solve the single machine weighted number of tardy jobs scheduling problem. The algorithm uses branch-and-bound with the bounds obtained from a surrogate knapsack. Extensive computational experiments are carried out. These experiments validate previous work on what constitutes a difficult instance and show that even difficult instances with 2500 jobs can be solved optimally in a reasonable amount of time.
Key Words: Scheduling; combinatorial optimization