Our results for the single machine total tardiness problem
We have proofed that the special case {\bf B-1} of the problem
when $d_{max}-d_{min} \leq p_{min}$ is NP-hard in the ordinary sense. We have proposed a polynomial scheme of reduction from NP-complete {\bf Partition Problem} to the special case {\bf B-1}
of the problem $1\mid\,\mid\sum T_j$. For this case a
pseudo-polynomial algorithm with run time $O(n\sum p_j)$ and exact
algorithm for $p_j \notin Z$ have been constructed. Therefore we
can decide the {\bf Partition Problem} when parameters are not
integer. For the case when $d_1\leq \dots \leq d_n$ and $p_1\geq \dots \geq
p_n$ we have constructed algorithms with run times $O(n^2 \sum
p_j)$ operations.
We have showed that the run time of well known algorithms of W.
Szwarc et al., A.A Lazarev, S.Chang et al. for the problem
$1\mid\mid\sum T_j$ are exponential for some "hard"\ cases without
any "paradoxes". For these cases we have new polynomial and
pseudo-polynomial algorithms.
We offer a new scheme of instances generation then popular scheme
C.N.~Potts and L.N.~Van Wassenhove.
Our new {\em hybrid algorithm} has joined qualities of
meta-heuristik methods (acceptable complexity, low error) and
combinatorial properties (Elimination Rules 1-4).
Efficiencies for meta-heuristik algorithm "Ant Colony
Optimization" and {\em hybrid algorithm} has been compared.
Results of our tests show that the relative error of known
algorithm "Ant Colony Optimization" is great than relative error
of {\em hybrid algorithm}.