|
Vestnik Yuzhno-Ural'skogo Universiteta. Seriya Matematicheskoe Modelirovanie i Programmirovanie, 2013, Volume 6, Issue 1, Pages 124–133
(Mi vyuru38)
|
|
|
|
Computer Sciences
Dynamic Programming Method in Bottleneck Tasks Distribution Problem with Equal Agents
E. E. Ivanko Institute of Mathematics and Mechanics, Ural Branch, Russian Academy of Sciencies, Ekaterinburg, Russian Federation
Abstract:
The paper considers a number of specific variants of dynamic programming method used to solve the bottleneck problem of tasks distribution in case when the performers are the same and their order is not important. Developed schemes for recursive dynamic programming method is shown to be correct, the comparison of computational complexity of the classical and the proposed schemes is done. We demonstrate that the usage of the specific conditions of performers equivalence can reduce the number of operations in the above dynamic programming method compared to the classical method more than 4 times. Herewith increase of the dimension of the original problem leads only to the increase in the relative gain. One of the techniques used to reduce computing — \flqq counter\frqq dynamic programming — apparently is common to a whole class of problems that allow use of the Bellman principle. The application of this technique bases on incomplete calculation of the Bellman function in problem that has some internal symmetry, then the original problem is obtained by gluing the resulting array of values of Bellman.
Keywords:
dynamic programming method, tasks distribution.
Received: 05.07.2012
Citation:
E. E. Ivanko, “Dynamic Programming Method in Bottleneck Tasks Distribution Problem with Equal Agents”, Vestnik YuUrGU. Ser. Mat. Model. Progr., 6:1 (2013), 124–133
Linking options:
https://www.mathnet.ru/eng/vyuru38 https://www.mathnet.ru/eng/vyuru/v6/i1/p124
|
|