A new dominance rule for the total weighted tardiness problem
Abstract
We present a new dominance rule for the single
machine total weighted tardiness problem with job dependent
penalties. The proposed dominance rule provides a su cient
condition for local optimality. We show that if any sequence
violates the dominance rule, then switching the violating jobs
either lowers the total weighted tardiness or leaves it
unchanged. We also develop a new algorithm based on the
dominance rule, which is compared to a number of competing
heuristics for a set of randomly generated problems. Our computational
results of over 40000 problems indicate that the
proposed algorithm dominates the competing heuristics in all
runs.
Description
This is the author's version of the work. It is posted here by permission of Taylor & Francis for personal use, not for redistribution. The definitive version was published in Production Planning & Control, Vol. 10, No. 2, 1999.