Single Machine Scheduling with Deadlines to Minimize the Weighted Number of Tardy Jobs

This paper considers as 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.