RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 2017, Volume 27, Issue 1, Pages 129–137 (Mi vuu574)  

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.

Funding Agency Grant Number
Russian Foundation for Basic Research 16-01-00649_а


DOI: https://doi.org/10.20537/vm170111

Full text: PDF file (279 kB)
References: PDF file   HTML file

Bibliographic databases:

UDC: 519.6
MSC: 49L20, 90C39
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

Citation in format AMSBIB
\Bibitem{Gri17}
\by A.~M.~Grigoryev
\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
\yr 2017
\vol 27
\issue 1
\pages 129--137
\mathnet{http://mi.mathnet.ru/vuu574}
\crossref{https://doi.org/10.20537/vm170111}
\elib{http://elibrary.ru/item.asp?id=28808561}


Linking options:
  • http://mi.mathnet.ru/eng/vuu574
  • http://mi.mathnet.ru/eng/vuu/v27/i1/p129

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Вестник Удмуртского университета. Математика. Механика. Компьютерные науки
    Number of views:
    This page:263
    Full text:78
    References:31

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020