Dynamic Programming Method in Bottleneck Tasks Distribution Problem with Equal Agents

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 - "counter", 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.