|
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 Sciencesa
|
|
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. 129-137.
|
|
References
|
- Korobkin V.V., Sesekin A.N., Tashlykov O.L., Chentsov A.G. Metody marshrutizatsii i ikh prilozheniya v zadachakh povysheniya effektivnosti i bezopasnosti ekspluatatsii atomnykh stantsii (Routing methods and their applications in problems of improving the efficiency and safety of operation of nuclear power plants), Moscow: Novye tekhnologii, 2012, 234 p.
- Burkard R., Dell'Amico M., Martello S. Assignment problems, SIAM Philadelphia, 2009. DOI: 10.1137/1.9781611972238
- Kuhn H.W. The Hungarian method for the assignment problem, Naval Research Logistics Quarterly, 1955, vol. 2, no. 1-2, pp. 83-97. DOI: 10.1002/nav.3800020109
- Kellerer H., Pferschy U., Pisinger D. Knapsack problems, Springer, 2005. DOI: 10.1007/978-3-540-24777-7
- Papadimitriou C.H., Yannakakis M. Optimization, approximation and complexity classes, Journal of Computer and System Sciences, 1991, vol. 43, issue 3, pp. 425-440. DOI: 10.1016/0022-0000(91)90023-X
- Chentsov A.G., Chentsov P.A. On the construction of a procedure for partitioning a finite set, based on the dynamic programming method, Automation and Remote Control, 2000, vol. 61, issue 4, pp. 658-670.
- Chentsov A.G., Chentsov P.A. Dynamic programming in the problem of decomposition optimization, Automation and Remote Control, 2002, vol. 63, issue 5, pp. 815-828. DOI: 10.1023/A:1015406222958
- Chentsov A.G., Chentsov A.G. Ekstremal'nye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii (Extremal problems of routing and assignment of tasks: questions of theory), Moscow-Izhevsk: Regular and Chaotic Dynamics, Institute of Computer Science, 2008, 240 p.
- Chentsov P.A. Job distribution algorithms, Automation and Remote Control, 2006, vol. 67, issue 8, pp. 1251-1264. DOI: 10.1134/S0005117906080054
- Bellman R. Dynamic programming, Princeton, New Jersey: Princeton University Press, 1957. Translated under the title Dinamicheskoe programmirovanie, Moscow: Inostr. Lit., 1960, 400 p.
- Minoux M. Programation mathematique. Theorie et algorithmes, Paris: Dunod, 1983, tome 1: 294 p., tome 2: 236 p. Translated under the title Matematicheskoe programmirovanie. Teoriya i algoritmy, Moscow: Nauka, 1990, 488 p.
- Korotaeva L.N., Nazarov E.M., Chentsov A.G. An assignment problem, Computational Mathematics and Mathematical Physics, 1993, vol. 33, issue 4, pp. 443-452.
- Grigoryev A.M. Solution of minimax distribution problem by method of dynamic programming with the use of parallel computing, Nauchnyi servis v seti Internet: ekzaflopsnoe budushchee: Trudy Mezhdunarodnoi superkomp'yuternoi konferentsii (Scientific service in the Internet: Exaflop future: Proceedings of the International Supercomputer Conference), Moscow: Lomonosov Moscow State University, 2011, pp. 580-586 (in Russian).
- Antonov A.S. Parallel'noe programmirovanie s ispol'zovaniem tekhnologii MPI (Parallel programming using the MPI technology), Moscow: Lomonosov Moscow State University, 2004, 71 p.
|
|
Full text
|
|
+7 (3412) 91 60 92
Russian