Archive of Issues
Russia Yekaterinburg
Section  Computer science 
Title  Solution of the problem of optimal task distribution by the method of dynamic programming with parallel computing 
Author(s)  Grigoryev A.M.^{a} 
Affiliations  Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences^{a} 
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 
UDC  519.6 
MSC  49L20, 90C39 
DOI  10.20537/vm170111 
Received  25 January 2017 
Language  Russian 
Citation  Grigoryev A.M. Solution of the problem of optimal task distribution by the method of dynamic programming with parallel computing, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2017, vol. 27, issue 1, pp. 129137. 
References 

Full text 