Geodesic
Dynamic Programming Method in Bottleneck Tasks Distribution Problem with Equal Agents
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 6 (2013) no. 1, pp. 124-133 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The paper considers a number of specific variants of dynamic programming method used to solve the bottleneck problem of tasks distribution in case when the performers are the same and their order is not important. Developed schemes for recursive dynamic programming method is shown to be correct, the comparison of computational complexity of the classical and the proposed schemes is done. We demonstrate that the usage of the specific conditions of performers equivalence can reduce the number of operations in the above dynamic programming method compared to the classical method more than 4 times. Herewith increase of the dimension of the original problem leads only to the increase in the relative gain. One of the techniques used to reduce computing — \flqq counter\frqq dynamic programming — apparently is common to a whole class of problems that allow use of the Bellman principle. The application of this technique bases on incomplete calculation of the Bellman function in problem that has some internal symmetry, then the original problem is obtained by gluing the resulting array of values of Bellman.
Keywords: dynamic programming method, tasks distribution. 
@article{VYURU_2013_6_1_a10,
     author = {E. E. Ivanko},
     title = {Dynamic {Programming} {Method} in {Bottleneck} {Tasks} {Distribution} {Problem} with {Equal} {Agents}},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a, Matemati\v{c}eskoe modelirovanie i programmirovanie},
     pages = {124--133},
     year = {2013},
     volume = {6},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURU_2013_6_1_a10/}
}
TY  - JOUR
AU  - E. E. Ivanko
TI  - Dynamic Programming Method in Bottleneck Tasks Distribution Problem with Equal Agents
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
PY  - 2013
SP  - 124
EP  - 133
VL  - 6
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VYURU_2013_6_1_a10/
LA  - ru
ID  - VYURU_2013_6_1_a10
ER  - 
%0 Journal Article
%A E. E. Ivanko
%T Dynamic Programming Method in Bottleneck Tasks Distribution Problem with Equal Agents
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
%D 2013
%P 124-133
%V 6
%N 1
%U http://geodesic.mathdoc.fr/item/VYURU_2013_6_1_a10/
%G ru
%F VYURU_2013_6_1_a10
E. E. Ivanko. Dynamic Programming Method in Bottleneck Tasks Distribution Problem with Equal Agents. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 6 (2013) no. 1, pp. 124-133. http://geodesic.mathdoc.fr/item/VYURU_2013_6_1_a10/

[1] Bellman R., Dynamic Programming, M., 1960, 400 pp. | MR

[2] Chentsov A. G., Extreme Problems of Routing and Tasks Distribution: Theory, M., 2007, 240 pp.

[3] M. Held, R. M. Karp, “A Dynamic Programming Approach to Sequencing Problems”, J. of the Society for Industrial and Applied Mathematics, 10:1 (1962), 196–210 | DOI | MR | Zbl

[4] R. M. Karp, “Dynamic programming meets the principle of inclusion and exclusion”, Oper. Res. Lett., 1:2 (1982), 49–51 | DOI | MR | Zbl

[5] Ivanko E. E., “Stability Criterion for the Optimal Route in Traveling Salesman Problem in Case of the One City Addition”, Vestnik Udmurtskogo universiteta. Matematika. Mekhanica. Kompyuternie nauki, 2011, no. 1, 58–66 | Zbl

[6] Ivanko E. E., “Sufficient conditions of stability in Traveling Salesman Problem”, Trudi Instituta matematiki i mekhaniki UrO RAN, 17, no. 3, 2011, 155–168

[7] Chentsov P. A., Chentsov A. G., Ivanko E. E., “On One Approach to Solving Traveling Salesman Problem with Several Performers”, J. of Computer and Systems Sciences International, 49:4 (2010), 570–578 | DOI | MR | Zbl

[8] Korotaeva L. N., Nazarov E. M., Chentsov A. G., “On one variant of Assignment Problem”, Computational Mathematics and Mathematical Physics, 33:4 (1993), 483–494 | MR | Zbl

[9] Chentsov P. A., Chentsov A. G., “To the Problem of Finite Set Partition Construction Based on Dynamic Programming”, Automation and Remote Control, 2000, no. 4, 129–142 | MR | Zbl

[10] Alekseev O. G., Complex Application of Discrete Optimization Methods, M., 1986, 247 pp. | MR

[11] G. Gutin, A. Punnen, The Traveling Salesman Problem and Its Variations, Springer, Berlin, 2002, 850 pp. | MR