Geodesic
Pseudopolynomial Approximation Algorithm for Solving the $NP$-Complete Problem of Minimizing Maximum Lateness
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Kazanskii Gosudarstvennyi Universitet. Uchenye Zapiski. Seriya Fiziko-Matematichaskie Nauki, Tome 150 (2008) no. 4, pp. 154-161 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

The article states and proves pseudopolynomial complexity approximation algorithm for solving the scheduling theory known as $NP$-complete problem, namely minimizing maximum lateness on a single machine, interruption in job processing being banned. The bound value absolute error of criterion function for schedule constructed by algorithm is received.
Keywords: schedule, lateness, $NP$-complete, complexity.
Mots-clés : pseudopolynomial algorithm 
@article{UZKU_2008_150_4_a13,
     author = {O. N. Shulgina and N. K. Sherbakova},
     title = {Pseudopolynomial {Approximation} {Algorithm} for {Solving} the $NP${-Complete} {Problem} of {Minimizing} {Maximum} {Lateness}},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {154--161},
     year = {2008},
     volume = {150},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2008_150_4_a13/}
}
TY  - JOUR
AU  - O. N. Shulgina
AU  - N. K. Sherbakova
TI  - Pseudopolynomial Approximation Algorithm for Solving the $NP$-Complete Problem of Minimizing Maximum Lateness
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2008
SP  - 154
EP  - 161
VL  - 150
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/UZKU_2008_150_4_a13/
LA  - ru
ID  - UZKU_2008_150_4_a13
ER  - 
%0 Journal Article
%A O. N. Shulgina
%A N. K. Sherbakova
%T Pseudopolynomial Approximation Algorithm for Solving the $NP$-Complete Problem of Minimizing Maximum Lateness
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2008
%P 154-161
%V 150
%N 4
%U http://geodesic.mathdoc.fr/item/UZKU_2008_150_4_a13/
%G ru
%F UZKU_2008_150_4_a13
O. N. Shulgina; N. K. Sherbakova. Pseudopolynomial Approximation Algorithm for Solving the $NP$-Complete Problem of Minimizing Maximum Lateness. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Kazanskii Gosudarstvennyi Universitet. Uchenye Zapiski. Seriya Fiziko-Matematichaskie Nauki, Tome 150 (2008) no. 4, pp. 154-161. http://geodesic.mathdoc.fr/item/UZKU_2008_150_4_a13/

[1] Bruker P., Lenstra J. K., Rinnooy Kan A. H. G., “Complexity of machine scheduling problems”, Studies in integer programming (Bonn, 1975), Ann. of Discrete Math., 1, North-Holland, Amsterdam, 1977, 343–362 | MR

[2] Lebedinskaya N. B., “Minimizatsiya maksimalnogo otkloneniya v sluchae preryvaniya rabot”, Zap. nauch. seminarov. Leningr. otd. Matem. in-ta AN SSSR, 80, 1978, 117–124 | MR | Zbl

[3] Horn W. A., “Some simple scheduling algorithms”, Nav. Res. Log. Quart. 21, 1974, no. 1, 177–185 | DOI | MR | Zbl

[4] Lageweg B. J., Lenstra J. K., Rinnooy Kan A. H. G., “Minimizing maximum lateness on one machine: computational experience and some applications”, Statist. Neer., 1976, no. 1, 25–41 | DOI | MR | Zbl

[5] Jackson J. R., Scheduling a production line to minimize maximum tardiness, Res. Report 43, Manag. Sci. Res. Project, Univ. of California, Los Angeles, 1955

[6] Frederickson G. N., “Scheduling unit-time tasks with integer release times and deadlines”, Inform. Process. Lett., 16:4 (1983), 171–173 | DOI | MR | Zbl

[7] Simons B. A., “A fast algorithm for single processor scheduling”, 19th Annu. Symp. Found. Comput. Sci., Ann. Arbor, Mich., N. Y., 1978, 246–252 | MR

[8] Shulgina O. N., “Tochnyi psevdopolinomialnyi algoritm resheniya odnoi $NP$-trudnoi zadachi teorii raspisanii”, Issled. po prikl. matem. i inform., 25, Kazan. gos. un-t, Kazan, 2004, 148–151

[9] Tanaev V. S., Gordon V. S., Shafranskii Ya. M., Teoriya raspisanii. Odnostadiinye sistemy, Nauka, M., 1984, 384 pp. | MR | Zbl

[10] Shulgina O. N., Scherbakova N. K., “Ob odnom priblizhennom algoritme resheniya $NP$-trudnoi zadachi teorii raspisanii”, Issled. po prikl. matem. i inform., 24, Kazan. gos. un-t, Kazan, 2003, 146–155

[11] Shulgina O. N., “Protsedura postroeniya dopustimogo raspisaniya dlya zadachi minimizatsii maksimalnogo vremennogo smescheniya”, Issled. po prikl. matem. i inform., 23, Izd-vo Kazan. matem. ob-va, Kazan, 2001, 150–158 | MR

[12] Lazarev A. A., Effektivnye algoritmy resheniya nekotorykh zadach teorii raspisanii dlya odnogo pribora s direktivnymi srokami obsluzhivaniya trebovanii, Dis. $\dots$ kand. fiz.-mat. nauk, Kazan, 1989, 108 pp.

[13] Knut D., Iskusstvo programmirovaniya dlya EVM. T. 3: Sortirovka i poisk, Mir, M., 1973, 348 pp. | MR