A performance comparison of heuristics for the total weighted tardiness problem

The single machine total weighted tardiness problem is an NP-hard problem that requires the use of heuristic solution procedures when more than 50 jobs are to be scheduled. In the literature, a well-tuned simulated annealing method and a descent heuristic with zero interchanges (DESO) both generated the best solutions for a large set of randomly generated problems. Due dates are generated by defining two parameters: the relative range of due dates (RDD) and the average tardiness factor (TF). In this paper, we define several heuristics based on dynamic programming and then use these and DESO heuristics to solve 50-job, 100-job, 200-job, and 500-job problems.