Minimizing the weighted number of tardy jobs on a single machine with release dates

In this paper, we describe an exact algorithm to minimize the weighted number of tardy jobs on a single machine with release dates. The algorithm uses branch-and-bound; a surrogate relaxation resulting in a multiple-choice knapsack provides the bounds. Extensive computational experiments indicate the proposed exact algorithm solves either weighted or unweighted problems. It solves the hardest problems to date. Indeed, it solves all previously unsolved instances. Its run time is the shortest to date. Scope and purpose: In many industrial sectors, satisfying due dates is a critical issue. Thus, lateness related measures such as the weighted number of tardy jobs are relevant performance measures of schedules in these industries. Our paper studies minimizing the weighted number of tardy jobs on a single machine with release and due dates, and proposes a new exact algorithm. For both weighted and unweighted problems, the exact algorithm solves the largest problems to date. (c) 2005 Elsevier B.V. All rights reserved.