Summary: This paper considers a single machine scheduling problem in which jobs have due dates and deadlines. A job may be completed after its due date, but not after its deadline, in which case it is tardy. A branch-and-bound algorithm is proposed to find a schedule which minimizes the weighted number of tardy jobs. It uses lower bounds which are derived using the dynamic programming state-space relaxation method. Computational experience with test problems having up to 300 jobs indicates that the lower bounds are extremely effective in restricting the size of the branch-and-bound search tree.