Тема: НЕКОТОРЫЕ ЗАДАЧИ МАРШРУТИЗАЦИИ С ОГРАНИЧЕНИЯМИ И ФУНКЦИЯМИ СТОИМОСТИ, ЗАВИСЯЩИМИ ОТ СПИСКА ЗАДАНИЙ

Актуальность и степень разработанности.
В диссертации рассматриваются задачи маршрутизации перемещений, имеющие своим источником ситуации прикладного характера, возникающие в атомной энергетике при выполнении набора заданий, связанных с демонтажом радиационно опасных элементов. Отметим, что подобные постановки возникают и в других содержательных задачах. Среди них выделим особо задачу управления инструментом при листовой резке деталей па машинах с ЧПУ. Хотя исследуемые задачи маршрутизации, ориентированные па инженерные применения, имеют своим прототипом известную трудпорешаемую задачу коммивояжера (TSP в англоязычной литературе)1,2,3,4, в них возникают существенные особенности не только количественного, по и качественного характера: ограничения, усложненные функции стоимости, многовариантности возможных перемещений и др. Исследования в области решений т.п. обобщенной задачи коммивояжера (GTSP)5,6,7также не покрывают потребности интересующих пас инженерных приложений, хотя и учитывают многовариантности возможных перемещений (объектами посещения являются кластеры или мегаполисы, а не города, как в TSP).
Полезно отметить задачу коммивояжера с условиями предшествования (TSP-PC)8,9, где, в частности, исследовалось влияние условий предшествования на сложности вычислений. Отметим, что в русскоязычной литературе используется термин "задача курьера". Отметим ряд работ, посвящённых TSP-PC, ориентированных па приложения; инспекция нефтяных вышек, оптимизация производственных процессов11,12, организация складской деятельности. Отметим работы14,15,165 использующие элементы метода ветвей и границ для решения TSP-PC. В связи с применением для решения TSP динамического программирования (ДП) отметим особо работы3,4. Развиваемая в настоящей работе конструкция восходит в идейном отношении к подходу3, имеющему смысл попятной процедуры.
В связи с производственными задачами, приводящими к идеям маршрутизации с различивши обобщениями, отметим исследование, посвящённое вопросам монтажа печатных плат1'. Здесь же отметим работу, которая относится к GTSP-PC и связана с инженерной задачей обработки листа (сверление, развертывание отверстий, нарезка резьбы).
В настоящей работе исследуется комплекс вопросов, связанных с применением параллельных алгоритмов для решения задач маршрутизации, ориентированных па инженерные приложения, связанные с атомной энергетикой. Речь идет, в первую очередь, о вопросах, связанных со снижением облучаемости персонала АЭС и специалистов аварийно-спасательных формирований при ликвидации аварийных ситуаций, возникающих па АЭС, в которых существенную роль имеет маршрутизация выполняемых заданий. Дело в том, что снижать облучаемость можно не только с помощью различных защитных сооружений, по и за счёт разумной организации последовательности выполняемых операций (в работе приведен соответствующий пример). В этой связи задачи маршрутизации настоящей работы могут представлять не только теоретический, но и серьезный практический интерес в плане снижения радиационного воздействия па исполнителей операций по демонтажу радиационно опасных объектов.
В то же время сама реализация упомянутых возможностей по снижению радиационного воздействия связана с решением очень сложных задач маршрутизации, имеющих лишь весьма отдалённое сходство со своим прототипом - задачей коммивояжера или TSP, хотя известные вопросы, связанные с трудпорешаемостыо TSP , в полной мере сохраняют свое значение и в задачах, рассматриваемых в настоящей работе. Речь идет о комбинаторных задачах с ограничениями и усложнёнными функциями стоимости, которые допускают зависимость от списка заданий, не выполненных па текущий момент. Кроме того, сами упомянутые зависимости в типичных случаях включают при своем построении интегрирование нелинейных зависимостей и комбинирование интегральных эффектов, создаваемых отдельными излучателями.
Возникающая при должной формализации постановка выходит за пределы круга задач, исследуемых в дискретной оптимизации и включает объективно элементы задач управления с дискретным временем. В этой связи отметим, что используемый в работе вариант ДП, восходящий к схеме Р. Веллмана, соответствует в идейном отношении процедурам па основе ДП, применяемым в теории управления; в этой связи отметим. В дискретной оптимизации при решении TSP и задач типа TSP чаще используется вариант Хелда-Карпа (стоит отметить, что при решении самой исходной TSP и многих слабо осложненных задач, ДП используется крайне редко и в основном теоретически - для оценки вычислительной сложности).
Методология и методы исследования. Выбор ДП в качестве основного метода исследования (что нетипично для дискретной оптимизации) связан с определённой "всеядностью" процедур па основе ДП, что и позволило встраивать в эти процедуры элементы соблюдения ограничений и разнообразные условия для функций стоимости. Таким образом, именно ДП позволяет (по крайней мере па теоретическом уровне) учитывать реальные интересы решения прикладных задач, что достигается, конечно, при соответствующей формализации исходной задачи с использованием ее разнообразных преобразований и должной теоретической проработке основных этапов исследования.
Целью диссертационной работы является исследование параллельных методов для решения ряда прикладных задач, возникающих в атомной энергетике.
Для достижения поставленной цели потребовалось решить следующие задачи:
1. Выполнить анализ модели перемещений с условиями предшествования и функциями стоимости, зависящими от списка невыполненных заданий, применительно к различным инженерным задачам.
2. Построить параллельный алгоритм поиска оптимального решения па основе ДП для задач маршрутизации и распределения заданий.
3. Разработать и реализовать комплекс программ, провести обширный вычислительный эксперимент.
4. Оцепить влияние условий предшествования па степень распараллеливания предложенных алгоритмов ДП.
Положения, выносимые на защиту:
1. Предложен алгоритм "вертикального" распараллеливания (схема независимых вычислений ) ДП в системах с распределенной памятью с применением программного интерфейса MPI, использован принцип разбиения задачи верхнего уровня па подзадачи меньшей размерности.
2. Реализован программный комплекс для точного решения задачи маршрутной оптимизации с ограничениями в виде условий предшествования и функциями стоимости, учитывающими возможную зависимость от списка невыполненных заданий.
3. Реализован эвристический алгоритм для решения "больших" маршрутных задач, учитывающий ограничения в виде условий предшествования и функции стоимости, зависящие от списка заданий.
4. Предложен метод улучшения эвристического алгоритма па основе оптимизирующих мультивставок с использованием параллельных вычислений. В результате решения этой задачи реализован программный комплекс па вычислительном кластере.
5. Построен параллельный алгоритм и реализован программный комплекс для решения задачи распределения заданий между участниками.
Научная новизна:
1. Разработан алгоритмический аппарат для решения задач маршрутизации с ограничениями и усложнёнными функциями стоимости. Впервые реализована схема распараллеливания динамического программирования на вычислительном кластере, при которой вычислительные узлы выполняют "сквозные" вычисления, не использующие обмен данными между узлами при последовательном расчёте слоев функции Веллмана. Данная реализация позволила существенно повысить размерность решаемых задач и сократить время вычислений.
2. Для решения прикладной задачи минимизации дозовой нагрузки работников атомных электростанций при проведении работ по де-монтажу выводимого из эксплуатации оборудования или персонала аварийно-спасательных формирований при ликвидации чрезвычайных ситуаций на АЭС, построен и реализован в виде программы для МВС оптимальный параллельный алгоритм. Данная прикладная задача предполагает учет ряда ограничений в виде условий предшествования и возможную зависимость функций стоимости от списка невыполненных заданий.
3. Для решения задач маршрутизации, имеющих большую размерность, построен параллельный алгоритм, реализующий оптимизирующие мультивставки в эвристические решения с целью улучшения качества исследуемого процесса.
4. Построен параллельный алгоритм на основе ДП для решения задачи распределения заданий.
Теоретическая и практическая значимость. Построены новые параллельные алгоритмы решения задач маршрутизации перемещений и распределения заданий между участниками; в основе данных алгоритмов находится аппарат ДП и схемы независимых вычислений в условиях возможного перекрытия потоков данных вычислительной процедуры.
Построенные в работе алгоритмы могут быть использованы при решении таких актуальных инженерных задач, как проблема демонтажа радиационно опасных объектов при авариях на АЭС, подобных Чернобылю и Фукусиме, плановом выводе из эксплуатации отработавшего радиационно опасного оборудования на АЭС и управления инструментом при листовой резке деталей на машинах с ЧПУ (задача, связанная с раскроем). Другие возможные применения связаны с транспортными задачами, авиапожарным патрулированием лесов, задачей о сборе космического "мусора".
Степень достоверности полученных результатов обеспечивается строгими выводами и математическими доказательствами, воспроизводимостью прогнозируемых результатов при вычислительных экспериментах с использованием МВС, сопоставлением известным из литературы результатам для аналогичных моделей в тех случаях, когда упомянутые аналогичные результаты имеются.
Апробация работы. Основные результаты работы представлялись в докладах на V Международной школе-симпозиуме "Анализ моделирование, развитие экономических систем: АМУР-2011 "(Украина, Севастополь, 2011); Международной конференции "Научный сервис в сети Интернет: экзафлопсное будущее" (Россия, Новоросийск, 2011); Международной конференции "Научный сервис в сети Интернет: поиск новых решений"(Россия, Новоросийск, 2012); 47-ой Всероссийской молодежной школе-конференции "Современные проблемы математики и ее приложений" (Россия, Екатеринбург, 2016); Международной конференции "Discrete Optimization and Operations Research - (DOOR 2016): 9th International Conference"(Russia, Vladivostok, 2016); VIII Международной конференции "OPTIMIZATION AND APPLICATIONS (ОРТ1МА-2017)"(Montenegro, Petrovac, 2017); V, VI, VII Международных конференциях "Physics, Technologies and Innovation (PTI-2018), (PTI-2019), (РТ1-2020)"(Russia, Ekaterinburg, 2018, 2019, 2020 rr.); XII Международной школе-симпозиуме "Анализ моделирование, развитие экономических систем: АМУР-2018" (Россия, Симферополь-Судак, 2018). Также диссертация представлялась на Научном семинаре по информационным технологиям ЮУрГУ (Россия, Челябинск, 2021); на семинаре лаборатории конструктивных методов исследования динамических моделей ПГНИУ (Россия, Пермь, 2021).
Личный вклад. В работах, написанных в соавторстве с научным руководителем, А.Г. Ченцову принадлежит постановка задачи и теоретические конструкции, связанные с процедурами на основе ДП, а А.М. Григорвеву эффективные параллельные алгоритмах, реализованные на суперкомпьютере; кроме того, им проведен обширный вычислительный эксперимент, позволивший выявить целый ряд полезных качественных зависимостей. В статьях, написанных в соавторстве с А.А. Ченцовым, соавтору А.А. Ченцову принадлежат выводы формул, оценивающих радиационное воздействие на различных этапах перемещений исполнителя, а также построение алгоритмов и программ для ПЭВМ, которые использовались в экспериментах при сравнении производительности с алгоритмами для МВС, а А.М. Григорьеву эффективные параллельные алгоритмы, реализованные на суперкомпьютере, а также проведение обширных вычислительных экспериментов. В работах, написанных в соавторстве с О.Л. Ташлыковым, соавтору О.Л. Ташлыкову принадлежит инженерная постановка и описание физических явлений, связанных с задачей дозиметриста; А.М. Григорьевым была предложена математическая постановка и построен параллельный алгоритм, реализованный на супервычислителе. В работах, написанных в соавторстве с Е.Е. Иванко, соавтору Е.Е. Иванко принадлежит разработка алгоритмов и оценка их трудоемкости, А.М. Григорьеву принадлежит построение параллельного алгоритма, программная реализация и проведение вычислительных экспериментов. В статье [15] соавторам А.Н. Сесекину и С.Е. Щеклейну принадлежит содержательная постановка рассматриваемой инженерной задачи, а диссертанту - построение параллельного алгоритма. В работе [2] соавтору Князеву С.Т. принадлежат некоторые элементы содержательной постановки задачи об авиапожарном патрулировании лесов. В статье [17] соавтору П.А. Ченцову принадлежит алгоритм решения обобщённой задачи курьера для ПЭВМ (результаты решения на ПЭВМ использовались в целях сравнения с аналогичными результатами для МВС).
Публикации. Основные результаты по теме диссертации изложены в 23 печатных и электронных изданиях, 4 из которых изданы в журналах и в трудах конференций, рекомендованных ВАК, 9 - в журналах и в тру¬дах конференций, индексируемых системами WoS и Scopus, 10 - в тезисах докладов.
Объем и структура работы. Диссертация состоит из введения, трёх глав, заключения и списка литературах. Полный объём диссертации составляет 114 страниц с 13 рисунками. Список литературы содержит 113 на именований.
Благодарность. Особую благодарность автор выражает своему научному руководителю - доктору физико-математических наук, член-корреспонденту РАН, Ченцову Александру Георгиевичу за постановку задачи, всестороннюю поддержку в ходе проводимого исследования и постоянное внимание к работе. Работа выполнена в рамках деятельности Уральского математического центра.

Купить

В диссертации исследовались важные для теории и инженерных приложений задачи маршрутизации, связанные с процедурами последовательного демонтажа системы радиационно опасных объектов. Возникающая при этом математическая модель является достаточно сложной и требует разработки серьезных теоретических конструкций для своего исследования. В настоящей работе принята модель мегаполисов, которые подлежат последовательному посещению с целью демонтажа источников излучения при соблюдении определённых ограничений, связанных с учётом особенностей исходной инженерной задачи. Среди упомянутых ограничений особую роль играют условия предшествования, которые удаётся использовать "в положительном направлении "в смысле снижения вычислительной сложности.
В диссертации построены методы и алгоритмы решения упомянутых задач маршрутизации, включая задачи ощутимой размерности. В основе используемых конструкций находится метод ДП, а конструируемые на его основе параллельные алгоритмы реализованы в виде стандартных программ на языке С++ для МВС. Эти алгоритмы используют идеи, заложенные в схемах с независимыми вычислениями слоев функции Веллмана. Они реализованы в двух вариантах:
1. точные алгоритмы, доставляющие глобальные экстремум и оптимальные маршруты;
2. алгоритмы, улучшающие качество эвристик за счёт применения оптимизирующих мультивставок (оптимизация "в окнах").
В обоих случаях получено существенное продвижение в плане увеличения размерности решаемых задач. Эту цель удалось достичь за счёт теоретически обоснованного распараллеливания вычислительных процедур. Представляется, что данный подход к решению очень сложных по постановке инженерных задач имеет смысл развивать и в дальнейшем, распространяя упомянутые конструкции на задачи другой природы. Среди таких задач можно отметить задачу управления инструментом при листовой резке на машинах с ЧПУ, задачу авиапожарного патрулирования лесов, транспортные задачи.

Купить