Metric and Approximated Solution of the Single Machine Total Tardiness Minimization Scheduling Problem

In this paper, we consider the NP-hard minimizing total tardiness on a single machine scheduling problem. We propose a metric for that problem and present a polynomial approximation scheme based on search for the polynomially solvable instance which has a minimal distance from an initial instance.