Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 2017, Volume 27, Issue 1, Pages 129–137
Solution of the problem of optimal task distribution by the method of dynamic programming with parallel computing
A. M. Grigoryev
N.N. Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, ul. S. Kovalevskoi, 16, Yekaterinburg, 620219, Russia
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.
dynamic programming, partition, parallel algorithm.
PDF file (279 kB)
MSC: 49L20, 90C39
A. M. Grigoryev, “Solution of the problem of optimal task distribution by the method of dynamic programming with parallel computing”, Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 27:1 (2017), 129–137
Citation in format AMSBIB
\paper Solution of the problem of optimal task distribution by the method of dynamic programming with parallel computing
\jour Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki
Citing articles on Google Scholar:
Related articles on Google Scholar:
|Number of views:|