Dominance Rules for the Parallel Machine Total Weighted Tardiness Scheduling Problem with Release Dates

We address the parallel machine total weighted tardiness scheduling problem with release dates. We describe dominance rules and filtering methods for this problem. Most of them are adaptations of dominance rules based on solution methods for the single-machine problem. We show how it is possible to deduce whether or not certain jobs can be processed by a particular machine in a particular context and we de-scribe techniques that use this information to improve the dominance rules. On the basis of these techniques we describe an enumeration procedure and we provide experimental results to determine the effec-tiveness of the dominance rules