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.
References
Беллман, Р. Динамическое программирование / Р. Беллман. - М.: Изд-во иностр. лит., 1960. - 400 с.
Ченцов, А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории / А.Г. Ченцов. - М.: РХД, 2007. - 240 с.
Held, M. A Dynamic Programming Approach to Sequencing Problems / M. Held, R.M. Karp // J. of the Society for Industrial and Applied Mathematics. - 1962. - V. 10, №,1. - P.,196-210.
Karp, R.M. Dynamic programming meets the principle of inclusion and exclusion / R.M. Karp // Oper. Res. Lett. - 1982. - №,1(2). - P.,49-51.
Иванко, Е.Е. Критерий устойчивости оптимального маршрута в задаче коммивояжера при добавлении вершины / Е.Е. Иванко // Вестн. Удмурт. ун-та. Математика. Механика. Компьютерные науки. - 2011. - №,1. - С.,58-66.
Иванко, Е.Е. Достаточные условия устойчивости в задаче коммивояжера / Е.Е. Иванко // Тр. Ин-та математики и механики УрО РАН. - 2011. - №,3. - С.,155-168.
Иванко, Е.Е. Об одном подходе к решению задачи маршрутизации перемещений с несколькими участниками / Е.Е. Иванко, А.Г. Ченцов, П.А. Ченцов // Изв. РАН. Теория и системы управления. - 2010. - №,4. - С.,63-71.
Коротаева, Л.Н. Об одной задаче о назначениях / Л.Н. Коротаева, Э.М. Назаров, А.Г. Ченцов // Журн. вычисл. математики и мат. физики. - 1993. - Т. 33, №,4. - С.,483-494.
Ченцов, А.Г. К вопросу о построении процедуры разбиения конечного множества на основе метода динамического программирования / А.Г. Ченцов, П.А. Ченцов // Автоматика и телемеханика. - 2000. - №,4. - С.,129-142.
Алексеев, О.Г. Комплексное применение методов дискретной оптимизации / О.Г. Алексеев. - М.: Наука, 1986. - 247 c.
Gutin, G. The Traveling Salesman Problem and Its Variations / G. Gutin, A. Punnen. - Berlin: Springer, 2002. - 850 p.
