Dynamic Programming Method in Bottleneck Tasks Distribution Problem with Equal Agents

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.

Keywords

dynamic programming method, tasks distribution.

References

1. Bellman R. Dinamicheskoe programmirovanie [Dynamic Programming]. Moscow, 1960. 400 p.
2. Chentsov A.G. Ekstremalnie zadachi marshrutizacii i raspredeleniya zadanii: voprosi teorii [Extreme Problems of Routing and Tasks Distribution: Theory]. Moscow, 2007. 240 p.
3. Held M., Karp R.M. A Dynamic Programming Approach to Sequencing Problems. J. of the Society for Industrial and Applied Mathematics, 1962, vol. 10, no.,1, pp.,196-210.
4. Karp R.M. Dynamic Programming Meets the Principle of Inclusion and Exclusion. Oper. Res. Lett., 1982, no.,1(2), pp.,49-51.
5. Ivanko E.E. Stability Criterion for the Optimal Route in Traveling Salesman Problem in Case of the One City Addition [Kriterii ustoichivosti optimalnogo marshruta v zadache kommivoyazhera pri dobavlenii vershini]. Vestnik Udmurtskogo universiteta. Matematika. Mekhanica. Kompyuternie nauki, 2011, no.,1, pp.,58-66.
6. Ivanko E.E. Sufficient conditions of stability in Traveling Salesman Problem [Dostatochnie usloviya ustoichivosti v zadache kommivoyazhera]. Trudi Instituta matematiki i mekhaniki UrO RAN, 2011, no.,3, pp.,155-168.
7. Chentsov P.A., Chentsov A.G., Ivanko E.E. On One Approach to Solving Traveling Salesman Problem with Several Performers [Ob odnim podhode k resheniyuzadachi marshrutizacii peremeschenii s neskolkimi uchastnikami]. J. of Computer and Systems Sciences International, 2010, vol. 49, no.,4, pp.,570-578.
8. Korotaeva L.N., Nazarov E.M., Chentsov A.G. On one variant of Assignment Problem [Ob odnoi zadache o naznacheniyah]. J. vichislitelnoi matematiki i matematicheskoi fiziki [Computational Mathematics and Mathematical Physics], 1993, vol. 33, no.,4, pp.,483-494.
9. Chentsov P.A., Chentsov A.G. To the Problem of Finite Set Partition Construction Based on Dynamic Programming [K voprosu o postroenii proceduri razbieniya konechnogo mnozhestva na osnove metoda dinamicheskogo programmirovaniya]. Avtomatika i telemehanika [Automation and Remote Control], 2000, no.,4. pp.,129-142.
10. Alekseev O.G. Kompleksnoe primenenie metodov discretnoi optimizacii [Complex Application of Discrete Optimization Methods]. Moscow, 1986, 247 p.
11. Gutin G. The Traveling Salesman Problem and Its Variations. Berlin: Springer, 2002, 850 p.