Метод динамического программирования в минимаксной задаче распределения заданий с равноценными исполнителями

В работе рассмотрен ряд специфических вариантов метода динамического программирования, используемых для решения минимаксной задачи распределения заданий при условии, что исполнители равноценны, и их порядок не важен. Для разработанных рекурсивных схем метода динамического программирования показана корректность, проводится сравнение вычислительной трудоемкости классической и предложенных схем. Демонстрируется, что использование специфики условия равноценности исполнителей позволяет сократить количество операций в рассмотренном методе динамического программирования по сравнению с классическим более чем в 4 раза, при этом при увеличении размерности исходной задачи относительный выигрыш лишь увеличивается. Одна из использованных техник сокращения вычислений - "встречное" динамическое программирование - по-видимому является общей для целого класса задач, допускающих использование при решении принципа Беллмана. Применение данной техники связано с неполным расчетом значений функции Беллмана в задаче, обладающей некоторой внутренней симметрией, после чего решение исходной задачи получается склеиванием полученных массивов значений функции Беллмана.

Ключевые слова

метод динамического программирования, распределение заданий.

Литература

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