A new dominance rule to minimize total weighted tardiness with unequal release dates

A new dominance rule to minimize total weighted tardiness with unequal release dates

0.00 Avg rating0 Votes
Article ID: iaor20021695
Country: Netherlands
Volume: 135
Issue: 2
Start Page Number: 394
End Page Number: 412
Publication Date: Dec 2001
Journal: European Journal of Operational Research
Authors: ,
Keywords: heuristics
Abstract:

We present a new dominance rule by considering the time-dependent orderings between each pair of jobs for the single machine total weighted tardiness problem with release dates. The proposed dominance rule provides a sufficient condition for local optimality. Therefore, if any sequence violates the dominance rule then switching the violating jobs either lowers the total weighted tardiness or leaves it unchanged. We introduce an 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 indicate that the proposed algorithm dominates the competing algorithms in all runs, therefore it can improve the upper bounding scheme in any enumerative algorithm. The proposed time-dependent local dominance rule is also implemented in two local search algorithms to guide these algorithms to the areas that will most likely contain the good solutions.

Reviews

Required fields are marked *. Your email address will not be published.