Geodesic
Solution of the problem of optimal task distribution by the method of dynamic programming with parallel computing
Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 27 (2017) no. 1, pp. 129-137 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The aim of the study is to construct a parallel algorithm for solving a bottleneck (minmax) problem connected with partitioning a finite set of tasks between a finite number of agents. We describe the algorithm of finding an optimal partition of tasks through dynamic programming with a parallel computation of the Bellman function and provide a computational complexity estimate for the two algorithms (with and without the parallel construction). The algorithm was implemented for the Uran supercomputer, and a computational experiment was conducted; computation time was measured for the serial algorithm and for the parallel one on varying numbers of processor cores.
Keywords: dynamic programming, parallel algorithm.
Mots-clés : partition 
@article{VUU_2017_27_1_a10,
     author = {A. M. Grigoryev},
     title = {Solution of the problem of optimal task distribution by the method of dynamic programming with parallel computing},
     journal = {Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹ\^uternye nauki},
     pages = {129--137},
     year = {2017},
     volume = {27},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VUU_2017_27_1_a10/}
}
TY  - JOUR
AU  - A. M. Grigoryev
TI  - Solution of the problem of optimal task distribution by the method of dynamic programming with parallel computing
JO  - Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
PY  - 2017
SP  - 129
EP  - 137
VL  - 27
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VUU_2017_27_1_a10/
LA  - ru
ID  - VUU_2017_27_1_a10
ER  - 
%0 Journal Article
%A A. M. Grigoryev
%T Solution of the problem of optimal task distribution by the method of dynamic programming with parallel computing
%J Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
%D 2017
%P 129-137
%V 27
%N 1
%U http://geodesic.mathdoc.fr/item/VUU_2017_27_1_a10/
%G ru
%F VUU_2017_27_1_a10
A. M. Grigoryev. Solution of the problem of optimal task distribution by the method of dynamic programming with parallel computing. Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 27 (2017) no. 1, pp. 129-137. http://geodesic.mathdoc.fr/item/VUU_2017_27_1_a10/

[1] Korobkin V. V., Sesekin A. N., Tashlykov O. L., Chentsov A. G., Routing methods and their applications in problems of improving the efficiency and safety of operation of nuclear power plants, Novye tekhnologii, M., 2012, 234 pp.

[2] Burkard R., Dell'Amico M., Martello S., Assignment problems, SIAM Philadelphia, 2009 | DOI | MR | Zbl

[3] Kuhn H. W., “The Hungarian method for the assignment problem”, Naval Research Logistics Quarterly, 2:1–2 (1955), 83–97 | DOI | MR | Zbl

[4] Kellerer H., Pferschy U., Pisinger D., Knapsack problems, Springer, 2005 | DOI | MR

[5] Papadimitriou C. H., Yannakakis M., “Optimization, approximation and complexity classes”, Journal of Computer and System Sciences, 43:3 (1991), 425–440 | DOI | MR | Zbl

[6] Chentsov A. G., Chentsov P. A., “On the construction of a procedure for partitioning a finite set, based on the dynamic programming method”, Automation and Remote Control, 61:4 (2000), 658–670 | MR | Zbl

[7] Chentsov A. G., Chentsov P. A., “Dynamic programming in the problem of decomposition optimization”, Automation and Remote Control, 63:5 (2002), 815–828 | DOI | MR | Zbl

[8] Chentsov A. G., Extremal problems of routing and assignment of tasks: questions of theory, Regular and Chaotic Dynamics, Institute of Computer Science, M.–Izhevsk, 2008, 240 pp.

[9] Chentsov P. A., “Job distribution algorithms”, Automation and Remote Control, 67:8 (2006), 1251–1264 | DOI | MR | Zbl

[10] Bellman R., Dynamic programming, Princeton University Press, Princeton, New Jersey, 1957 | MR | Zbl

[11] Minu M., Matematicheskoe programmirovanie, Nauka, M., 1990, 488 pp.; Minoux M., Programation mathematique. Theorie et algorithmes, v. 1, Dunod, Paris, 1983, 294 pp. ; v. 2, 236 pp. | MR

[12] Korotaeva L. N., Nazarov E. M., Chentsov A. G., “An assignment problem”, Computational Mathematics and Mathematical Physics, 33:4 (1993), 443–452 | MR | Zbl

[13] Grigoryev A. M., “Solution of minimax distribution problem by method of dynamic programming with the use of parallel computing”, Scientific service in the Internet: Exaflop future, Proceedings of the International Supercomputer Conference, Lomonosov Moscow State University, M., 2011, 580–586 (in Russian)

[14] Antonov A. S., Parallel programming using the MPI technology, Lomonosov Moscow State University, M., 2004, 71 pp.