Single Machine Scheduling with Deadlines to Minimize the Weighted Number of Tardy Jobs
研究单机调度问题，作业有截止期限和最后期限，提出分支定界算法最小化加权延迟作业数，通过动态规划状态空间松弛得到下界，实验表明对多达300个作业的问题有效。
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.