RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Южно-Уральского государственного университета. Серия «Математическое моделирование и программирование» // Архив

Вестн. ЮУрГУ. Сер. Матем. моделирование и программирование, 2013, том 6, выпуск 1, страницы 124–133 (Mi vyuru38)

Программирование

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

Е. Е. Иванко

Институт математики и механики УрО РАН (г. Екатеринбург, Российская Федерация)

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

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

УДК: 519.168

MSC: 90C39

Поступила в редакцию: 05.07.2012



© МИАН, 2024