|
COMPUTER SCIENCE
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
Abstract:
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, partition, parallel algorithm.
Received: 25.01.2017
Citation:
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
Linking options:
https://www.mathnet.ru/eng/vuu574 https://www.mathnet.ru/eng/vuu/v27/i1/p129
|
Statistics & downloads: |
Abstract page: | 422 | Full-text PDF : | 181 | References: | 47 |
|