Geodesic
Solution of the NP-hard total tardiness minimization problem in scheduling theory
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 47 (2007) no. 6, pp. 1087-1098 
A. A. Lazarev. Solution of the NP-hard total tardiness minimization problem in scheduling theory. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 47 (2007) no. 6, pp. 1087-1098. http://geodesic.mathdoc.fr/item/ZVMMF_2007_47_6_a12/
@article{ZVMMF_2007_47_6_a12,
     author = {A. A. Lazarev},
     title = {Solution of the {NP-hard} total tardiness minimization problem in scheduling theory},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1087--1098},
     year = {2007},
     volume = {47},
     number = {6},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2007_47_6_a12/}
}
TY  - JOUR
AU  - A. A. Lazarev
TI  - Solution of the NP-hard total tardiness minimization problem in scheduling theory
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2007
SP  - 1087
EP  - 1098
VL  - 47
IS  - 6
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2007_47_6_a12/
LA  - ru
ID  - ZVMMF_2007_47_6_a12
ER  - 
%0 Journal Article
%A A. A. Lazarev
%T Solution of the NP-hard total tardiness minimization problem in scheduling theory
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2007
%P 1087-1098
%V 47
%N 6
%U http://geodesic.mathdoc.fr/item/ZVMMF_2007_47_6_a12/
%G ru
%F ZVMMF_2007_47_6_a12

Voir la notice de l'article provenant de la source Math-Net.Ru

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$).

[1] Du J., Leung J. Y.-T., “Minimizing total tardiness on one processor is NP-hard”, Math. Operat. Res., 15 (1990), 483–495 | DOI | MR | Zbl

[2] Lawler E. L., “A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness”, Ann. Discrete Math., 1 (1977), 331–342 | DOI | MR | Zbl

[3] Szwarc W., Della Croce F., Grosso A., “Solution of the single machine total tardiness problem”, J. Scheduling, 2 (1999), 55–71 | 3.0.CO;2-5 class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[4] Szwarc W., Grosso A., Della Croce F., “Algorithmic paradoxes of the single machine total tardiness problem”, J. Scheduling, 4 (2001), 93–104 | DOI | MR | Zbl

[5] Potts C. N., van Wassenhove L. N., “A decomposition algorithm for the single machine total tardiness problem”, Operat. Res. Letts, 1 (1982), 177–182 | DOI

[6] Della Croce F., Grosso A., Psachos V., “Lower bounds on the approximation ratios of leading heuristics for singlemachine total tardiness problem”, J. Scheduling, 7 (2004), 85–91 | DOI | MR

[7] Lazarev A. A., Rafarov E. R., “Dokazatelstvo NP-trudnosti chastotnogo sluchaya zadachi minimizatsii summarnogo zapazdyvaniya dlya odnogo pribora $1\|\sum T_j$”, Izv. RAN. Teoriya i sistemy upravleniya, 2006, no. 3, 120–128 | MR

[8] Lazarev A. A., Kvaratskheliya A. G., “Issledovanie NP-trudnoi problemy teorii raspisanii minimizatsii summarnogo zapazdyvaniya na odnom pribore”, Issl. po prikl. matem., 24, Kazan, 2003, 90–106

[9] Lazarev A. A., Kvaratskheliya A. G., Gafarov E. R., “Algoritmy resheniya NP-trudnoi problemy minimizatsii summarnogo zapazdyvaniya dlya odnogo pribora”, Dokl. RAN, 412:6 (2007), 739–742 | MR

[10] Emmons H., “One machine sequenciim to minimizing certain function of job tardiness”, Operat. Res., 17 (1969), 701–715 | DOI | MR | Zbl

[11] Chang S., Lu Q., Tang G., Yu W., “On decomposition of the total tardiness problem”, Operat. Res. Letts, 17 (1995), 221–229 | DOI | MR | Zbl