|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
МАТЕМАТИКА
Оптимизирующие мультивставки в задачах маршрутизации с ограничениями
А. Г. Ченцовab, А. М. Григорьевa a Институт математики и механики им. Н.Н. Красовского УрО РАН, 620219, Россия, г. Екатеринбург, ул.
С. Ковалевской, 16
b Уральский федеральный университет, 620002, Россия, г. Екатеринбург, ул. Мира, 19
Аннотация:
Рассматривается задача последовательного обхода мегаполисов (непустых конечных множеств) с условиями предшествования и функциями стоимости, зависящими от списка заданий. Постановка ориентирована на инженерные задачи, возникающие в атомной энергетике и связанные со снижением облучаемости работников, а также в машиностроении (маршрутизация движения инструмента при листовой резке на машинах с ЧПУ). Предполагается, что исследуемая задача дискретной оптимизации имеет ощутимую размерность, что вынуждает к использованию эвристик. Обсуждается процедура локального улучшения качества последних посредством применения оптимизирующих мультивставок, определяемых всякий раз в виде конечного дизъюнктного набора вставок. Предполагается, что в каждой вставке используется процедура оптимизации на основе широко понимаемого динамического программирования. Показано, что в «аддитивной» маршрутной задаче вышеупомянутого типа (с ограничениями и усложненными функциями стоимости) улучшения достигаемого результата также агрегируются аддитивно. Предлагаемая конструкция допускает реализацию в виде параллельной процедуры с использованием МВС; при этом отдельные вставки выделяются вычислительным узлам и формируются независимо.
Ключевые слова:
динамическое программирование, мультивставки, параллельный алгоритм.
Поступила в редакцию: 17.09.2018
Образец цитирования:
А. Г. Ченцов, А. М. Григорьев, “Оптимизирующие мультивставки в задачах маршрутизации с ограничениями”, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 28:4 (2018), 513–530
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vuu654 https://www.mathnet.ru/rus/vuu/v28/i4/p513
|
Статистика просмотров: |
Страница аннотации: | 313 | PDF полного текста: | 296 | Список литературы: | 29 |
|