A new dominance rule for the total weighted tardiness problem
Akturk, M. Selim
Yildirim, Mehmet Bayram
MetadataShow full item record
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.
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.