Worst-case analysis of local search heuristics for the one-machine total tardiness problem

In this article the worst-case performance of four local search heuristics for the total tardiness problem is investigated. Since the denominator of the error ratio, which is the optimal objective value, may become zero, the derivation of the worst-case relative error requires a careful mathematical treatment. After necessary definitions and notations are introduced, the worst-case relative errors of two heuristics are shown to be infinite for a given number of jobs, while those of the other two are shown to be finite.