WEIGHTED TARDINESS SINGLE-MACHINE SCHEDULING WITH PROPORTIONAL WEIGHTS

This paper considers Arkin and Roundy's single machine weighted tardin ess scheduling model with tardiness penalties proportional to the proc essing times. It presents a two-Stage decomposition mechanism that pro ves 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 decomp osition method solves 155 out of 320 test problems with job sizes rang ing from 20 to 150. It reduces 163 unsolved problems to smaller subpro blems with sizes not exceeding 25 jobs. The job sizes of the remaining two unsolved subproblems are 30 and 45.