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

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$). 
@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},
     publisher = {mathdoc},
     volume = {47},
     number = {6},
     year = {2007},
     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
PB  - mathdoc
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
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZVMMF_2007_47_6_a12/
%G ru
%F ZVMMF_2007_47_6_a12
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/