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

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

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},
     publisher = {mathdoc},
     volume = {27},
     number = {1},
     year = {2017},
     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
PB  - mathdoc
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
%I mathdoc
%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/