An Approximation Algorithm for the Total Tardiness Problem and its Analysis

An approximation algorithm for the total tardiness problem is presented in this paper, which possesses the following properties: polynomial complexity, a local solution with respect to backward shift neighbourhood and finite performance ratio. Much effort has been put on getting the exact value of the performance ratio of the algorithm.