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

Abstract

We 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. We 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 heuristic 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.