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.

• 저널Management Science · 40(12) · 1712–1719
• 토픽Scheduling and Optimization Algorithms · Industrial and Manufacturing Engineering
• DOI10.1287/mnsc.40.12.1712
• 저자A.M.A. Hariri, Chris N. Potts