Weighted Tardiness Single Machine Scheduling with Proportional Weights

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.