Solution of the NP-hard total tardiness minimization problem in scheduling theory

The classical NP-hard (in the ordinary sense) problem of scheduling jobs in order to minimize the total tardiness for a single machine $1\|\sum T_j$ is considered. An NP-hard instance of the problem is completely analyzed. A procedure for partitioning the initial set of jobs into subsets is proposed. Algorithms are constructed for finding an optimal schedule depending on the number of subsets. The complexity of the algorithms is $O(n^2\sum p_j)$, where $n$ is the number of jobs and $p_j$ is the processing time of the $j$th job ($j=1,2,\dots,n$).