Algorithms for a class of single-machine weighted tardiness and earliness problems

The authors address the problem of determining schedules for static, single-machine scheduling problems where the objective is to minimize the sum of weighted tardiness and weighted earliness. They develop optimal and heuristic procedures for the special case of weights that are proportional to the processing times of the respective jobs. The optimal procedure uses dominance properties to reduce the number of sequences that must be considered, and some of the heuristics use these properties as a basis for constructing good initial sequences. A pairwise interchange procedure is used to improve the heuristic solutions. An experimental study shows that the heuristic procedures perform very well.