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/

[1] Lazarev A. A., Effektivnye algoritmy resheniya nekotorykh zadach teorii raspisanii dlya odnogo pribora s direktivnymi srokami obsluzhivaniya trebovanii, Dissertatsiya na soiskanie uchenoi stepeni k.f.-m.n., Kazanskii gos. un-t, Kazan, 1989

[2] Lazarev A. A., Shulgina O. N., “Psevdopolinomialnyi algoritm resheniya NP-trudnoi zadachi minimizatsii maksimalnogo vremennogo smescheniya”, Trudy XI mezhdunarodnoi Baikalskoi shkoly-seminara “Metody optimizatsii i ikh prilozheniya” (5–12 iyulya), SEI SO RAN, Irkutsk, Baikal, 1998, 163–167 | MR

[3] Adams J., Balas E., Zawack D., “The shifting bottleneck procedure for job shop scheduling”, J. Manag. Sci., 34:3 (1988), 391–401 | DOI | MR | Zbl

[4] Baker K. R., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., “Preemptive scheduling of a single machine to minimize maximum cost subject to release dates and precedence constraints”, J. Oper. Res., 31:2 (1983), 381–386 | DOI

[5] Baker K. R.,Su Z. S., “Sequencing with due dates and early start times to minimize tardiness”, J. Naval Res. Logist. Quart., 21:1 (1974), 171–176 | DOI | MR | Zbl

[6] Carlier J., “The one-machine sequencing problem”, European J. of Oper. Res., 11:1 (1982), 42–47 | DOI | MR | Zbl

[7] Graham R. L., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., “Optimization and approximation in deterministic sequencing and scheduling: a survey”, Ann. Discrete Math., 5 (1979), 287–326 | DOI | MR | Zbl

[8] Hall L. A., Shmoys D. B., “Jackson's rule for one-machine scheduling: making a good heuristic better”, J. Math. Oper. Res., 17:1 (1992), 22–35 | DOI | MR | Zbl

[9] Hoogeveen J. A., “Minimizing maximum promptness and maximum lateness on a single machine”, J. Math. Oper. Res., 21:1 (1996), 100–114 | DOI | MR | Zbl

[10] Jackson J. R., Scheduling a production line to minimize maximum tardiness, Manag. Sci. Res. Project, No 43. UCLA, 1955

[11] Lageweg B. J., Lenstra J. K., Rinnooy Kan A. H. G., “Minimizing maximum lateness on one machine: computational experience and some applications”, J. Statistica Neerlandica, 30:1 (1976), 25–41 | DOI | MR | Zbl

[12] Lawler E. L., “Optimal sequencing of a single machine subject to precedence constraints”, J. Manag. Sci., 19:5 (1973), 544–546 | DOI | Zbl

[13] Lenstra J. K., Rinnooy Kan A. H. G., Brucker P., “Complexity of machine scheduling problems”, Annals of Oper. Res., 1 (1975), 343–362 | MR

[14] Mastrolilli M., “Efficient approximation schemes for scheduling problems with release dates and delivery times”, J. of Scheduling, 6:6 (2003), 521–531 | DOI | MR | Zbl

[15] McMahon G., Florian M., “On scheduling with ready times and due dates to minimize maximum lateness”, J. Oper. Res., 23:3 (1975), 475–482 | DOI | MR | Zbl

[16] Péridy L., Pinson E., Rivraux D., “Using short-term memory to minimize the weighted number of late jobs on a single machine”, European J. of Oper. Res., 148:3 (2003), 591–603 | DOI | MR | Zbl

[17] Potts C. N., “Analysis of a heuristic for one machine sequencing with release dates and delivery times”, J. Oper. Res., 28:6 (1980), 1436–1441 | DOI | MR | Zbl

[18] Simons B. B., “A fast algorithm for single processor scheduling”, Proc. of the 19th Annual symposium foundftion of computer science, Ann. Arbor, New York, 1978, 246–252 | MR