Weighted tardiness for the single machine scheduling problem:An examination of precedence theorem productivity

Earlier research by Kanet [11] has provided a number of new theorems for deciding precedence between pairs of jobs for 1∣∣Σw_jT_j. The theorems supplant those of Rinnooy Kan, Lageweg, and Lenstra [16]. Presented here are the results of an analysis of the marginal benefit these new theorems provide over the earlier versions of Rinnooy Kan et al. Results show that the new theorems can provide noteworthy improvements in the ability to discover precedence relations between job pairs. For a large set of problem instances the new theorems uncovered up to 8% more precedence relations than the original theorems of Rinnooy Kan et al. The improvement in the productivity in discovering precedence relations shows to be dependent on the coefficient of variation of the distribution of job weights. Logical application of the theorems is to include them in search procedures and/or heuristic approaches to 1||Σw_jT_j. One such heuristic based on the theorems is provided here in which the solutions to a large set of sample problems are within 8–12% of the optimum.