Geodesic
A scheme of approximation solution of problem $1|R_j|L_{\max}$
Diskretnyj analiz i issledovanie operacij, Tome 13 (2006) no. 1, pp. 57-76

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

The strongly NP-hard scheduling problem of minimizing the maximum lateness on one machine subject to job release dates is under study. We present a general scheme of approximation solution of the problem which is based on searching for a given problem instance another instance, closest to the original in some metric and belonging to a known polynomially solvable class of instances. For a few concrete variants of the scheme (using different polynomially solvable classes of instances) some analytic formulas are found that make it possible, given a problem instance, to compute easily an upper bound on the absolute error of the solution obtained by a chosen scheme. 
@article{DA_2006_13_1_a4,
     author = {A. A. Lazarev and R. R. Sadykov and S. V. Sevast'yanov},
     title = {A scheme of approximation solution of problem $1|R_j|L_{\max}$},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {57--76},
     publisher = {mathdoc},
     volume = {13},
     number = {1},
     year = {2006},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2006_13_1_a4/}
}
TY  - JOUR
AU  - A. A. Lazarev
AU  - R. R. Sadykov
AU  - S. V. Sevast'yanov
TI  - A scheme of approximation solution of problem $1|R_j|L_{\max}$
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2006
SP  - 57
EP  - 76
VL  - 13
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2006_13_1_a4/
LA  - ru
ID  - DA_2006_13_1_a4
ER  - 
%0 Journal Article
%A A. A. Lazarev
%A R. R. Sadykov
%A S. V. Sevast'yanov
%T A scheme of approximation solution of problem $1|R_j|L_{\max}$
%J Diskretnyj analiz i issledovanie operacij
%D 2006
%P 57-76
%V 13
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2006_13_1_a4/
%G ru
%F DA_2006_13_1_a4
A. A. Lazarev; R. R. Sadykov; S. V. Sevast'yanov. A scheme of approximation solution of problem $1|R_j|L_{\max}$. Diskretnyj analiz i issledovanie operacij, Tome 13 (2006) no. 1, pp. 57-76. http://geodesic.mathdoc.fr/item/DA_2006_13_1_a4/