A PERFORMANCE COMPARISON OF HEURISTICS FOR THE TOTAL WEIGHTED TARDINESS PROBLEM

The single machine total weighted tardiness problem is an NP-hard prob lem that requires the use of heuristic solution procedures when more t han 50 jobs are to be scheduled. In the literature, a well-tuned simul ated annealing method and a descent heuristic with zero interchanges ( DESO) both generated the best solutions for a large set of randomly ge nerated 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 pr ogramming and then use these and DESO heuristics to solve 50-job, 100- job, 200-job, and 500-job problems. (C) 1997 Elsevier Science Ltd.