Algorithms for Scheduling a Single Machine to Minimize the Weighted Number of Late Jobs
研究单机调度问题，目标是最小化加权延迟作业数，提出了O(n log n)的线性规划松弛算法、基于该下界的约简算法和分支定界算法，并给出了多达1000个作业的计算结果。
This paper considers the problem of scheduling n jobs, each having a processing time, a due date and a weight, on a single machine to minimize the weighted number of late jobs. An O(n log n) algorithm is given for solving the linear programming problem obtained by relaxing the integrality constraints in a zero-one programming formulation of the problem. This linear programming lower bound is used in a reduction algorithm that eliminates jobs from the problem. Also, a branch and bound algorithm that uses the linear programming lower bound is proposed. Computational results with branch and bound algorithms that use this and other lower bounds and with a dynamic programming algorithm for problems with up to 1000 jobs are given.