Geodesic
Estimates of the absolute error and a scheme for an approximate solution to scheduling problems
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 49 (2009) no. 2, pp. 382-396

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

An approach is proposed for estimating absolute errors and finding approximate solutions to classical NP-hard scheduling problems of minimizing the maximum lateness for one or many machines and makespan is minimized. The concept of a metric (distance) between instances of the problem is introduced. The idea behind the approach is, given the problem instance, to construct another instance for which an optimal or approximate solution can be found at the minimum distance from the initial instance in the metric introduced. Instead of solving the original problem (instance), a set of approximating polynomially/pseudopolynomially solvable problems (instances) are considered, an instance at the minimum distance from the given one is chosen, and the resulting schedule is then applied to the original instance. 
@article{ZVMMF_2009_49_2_a14,
     author = {A. A. Lazarev},
     title = {Estimates of the absolute error and a~scheme for an approximate solution to scheduling problems},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {382--396},
     publisher = {mathdoc},
     volume = {49},
     number = {2},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2009_49_2_a14/}
}
TY  - JOUR
AU  - A. A. Lazarev
TI  - Estimates of the absolute error and a scheme for an approximate solution to scheduling problems
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2009
SP  - 382
EP  - 396
VL  - 49
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2009_49_2_a14/
LA  - ru
ID  - ZVMMF_2009_49_2_a14
ER  - 
%0 Journal Article
%A A. A. Lazarev
%T Estimates of the absolute error and a scheme for an approximate solution to scheduling problems
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2009
%P 382-396
%V 49
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZVMMF_2009_49_2_a14/
%G ru
%F ZVMMF_2009_49_2_a14
A. A. Lazarev. Estimates of the absolute error and a scheme for an approximate solution to scheduling problems. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 49 (2009) no. 2, pp. 382-396. http://geodesic.mathdoc.fr/item/ZVMMF_2009_49_2_a14/