A Branch-and-Bound Algorithm for the Prize-Collecting Single-Machine Scheduling Problem with Deadlines and Total Tardiness Minimization
研究了带硬截止时间的奖赏收集单机调度问题，目标是最小化总延误与总奖赏之差，提出了预处理规则和分支定界算法，并在随机算例上比较了算法与整数规划模型的性能。
We study a prize-collecting single-machine scheduling problem with hard deadlines, where the objective is to minimize the difference between the total tardiness and the total prize of the selected jobs. This problem is motivated by industrial applications, both as a stand-alone model and as a pricing subproblem in column-generation algorithms for parallel machine scheduling problems. A preprocessing rule is devised to identify jobs that cannot belong to any optimal schedule. The resulting reduced problem is solved to optimality by a branch-and-bound algorithm and two integer linear programming formulations. The algorithm and the formulations are experimentally compared on randomly generated benchmark instances.