Weighted Tardiness Single Machine Scheduling with Proportional Weights
研究单机加权延迟调度问题，其中延迟惩罚与加工时间成比例。提出两阶段分解机制，能完全解决或大幅缩小问题规模，在320个测试问题中成功解决155个，并将163个未解问题缩减为不超过25个作业的子问题。
This paper considers Arkin and Roundy's single machine weighted tardiness scheduling model with tardiness penalties proportional to the processing times. It presents a two-stage decomposition mechanism that proves to be powerful in solving the problem completely or reducing it to a much smaller problem. Three types of orderings of adjacent jobs are derived that play a crucial role in problem decomposition. The decomposition method solves 155 out of 320 test problems with job sizes ranging from 20 to 150. It reduces 163 unsolved problems to smaller subproblems with sizes not exceeding 25 jobs. The job sizes of the remaining two unsolved subproblems are 30 and 45.