Weighted Tardiness Single Machine Scheduling with Proportional Weights
Wlodzimierz Szwarc, John J. Liu
Management Science · 1993 · Volume 39 · Issue 5
Abstract
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.
Keywords
scheduling problem, precedence relation, proportional weights
Enable JavaScript for citation tools and additional paper interactions.