Помощь студентам в учебе
НЕКОТОРЫЕ ЗАДАЧИ МАРШРУТИЗАЦИИ С ОГРАНИЧЕНИЯМИ И ФУНКЦИЯМИ СТОИМОСТИ, ЗАВИСЯЩИМИ ОТ СПИСКА ЗАДАНИЙ
|
Введение 4
Глава 1. Реализация схемы независимых вычислений в обобщённой задаче курьера 13
1.1 Некоторые прикладные задачи с элементами маршрутизации ...13
1.2 Математическая постановка задачи 15
1.3 Вспомогательные конструкции для процедуры решения по
динамическому программированию 20
1.4 Рекуррентная процедура построения слоев функции Веллмана . .22
1.5 Построение оптимального маршрута 24
1.6 Схема независимых вычислений 25
1.7 Построение слоев функции Веллмана в параллельной реализации30
1.8 Параллельный алгоритм 33
1.9 Функции стоимости в задачах АЭС 36
1.10 Вычислительный эксперимент 39
1.11 Апробация параллельного алгоритма па экземплярах задач
ТБРЫВ БОР 42
1.12 Жадный алгоритм в задаче с АЭС 45
Глава 2. Мультивставка в маршрутных задачах 50
2.1 Краткое введение 50
2.2 Общие понятия и обозначения 51
2.3 Постановка основной задачи 51
2.4 Оптимизирующие вставки: общие свойства 55
2.5 Мультивставка 64
2.6 Вычислительный эксперимент 72
Глава 3. Разные оптимизационные задачи 77
3.1 Введение 77
3.2 Задача дозиметриста 78
3.2.1 Постановка задачи о выборе маршрута посещения
заданных точек 80
3.2.2 Построение радиационной карты помещения 82
3.2.3 Вычисление функций стоимости (па основе измерений и метода РБФ) 84
3.2.4 Вычислительный эксперимент 87
3.3 Параллельная реализация динамического программирования в
задачах об оптимальном распределении заданий 91
3.3.1 Формальная постановка задачи 93
3.3.2 Метод динамического программирования 94
3.3.3 Параллельная реализация алгоритма 96
3.3.4 Оценка вычислительной сложности 97
3.3.5 Вычислительный эксперимент 99
Заключение 102
Список литературы 103
Глава 1. Реализация схемы независимых вычислений в обобщённой задаче курьера 13
1.1 Некоторые прикладные задачи с элементами маршрутизации ...13
1.2 Математическая постановка задачи 15
1.3 Вспомогательные конструкции для процедуры решения по
динамическому программированию 20
1.4 Рекуррентная процедура построения слоев функции Веллмана . .22
1.5 Построение оптимального маршрута 24
1.6 Схема независимых вычислений 25
1.7 Построение слоев функции Веллмана в параллельной реализации30
1.8 Параллельный алгоритм 33
1.9 Функции стоимости в задачах АЭС 36
1.10 Вычислительный эксперимент 39
1.11 Апробация параллельного алгоритма па экземплярах задач
ТБРЫВ БОР 42
1.12 Жадный алгоритм в задаче с АЭС 45
Глава 2. Мультивставка в маршрутных задачах 50
2.1 Краткое введение 50
2.2 Общие понятия и обозначения 51
2.3 Постановка основной задачи 51
2.4 Оптимизирующие вставки: общие свойства 55
2.5 Мультивставка 64
2.6 Вычислительный эксперимент 72
Глава 3. Разные оптимизационные задачи 77
3.1 Введение 77
3.2 Задача дозиметриста 78
3.2.1 Постановка задачи о выборе маршрута посещения
заданных точек 80
3.2.2 Построение радиационной карты помещения 82
3.2.3 Вычисление функций стоимости (па основе измерений и метода РБФ) 84
3.2.4 Вычислительный эксперимент 87
3.3 Параллельная реализация динамического программирования в
задачах об оптимальном распределении заданий 91
3.3.1 Формальная постановка задачи 93
3.3.2 Метод динамического программирования 94
3.3.3 Параллельная реализация алгоритма 96
3.3.4 Оценка вычислительной сложности 97
3.3.5 Вычислительный эксперимент 99
Заключение 102
Список литературы 103
Актуальность и степень разработанности.
В диссертации рассматриваются задачи маршрутизации перемещений, имеющие своим источником ситуации прикладного характера, возникающие в атомной энергетике при выполнении набора заданий, связанных с демонтажом радиационно опасных элементов. Отметим, что подобные постановки возникают и в других содержательных задачах. Среди них выделим особо задачу управления инструментом при листовой резке деталей па машинах с ЧПУ. Хотя исследуемые задачи маршрутизации, ориентированные па инженерные применения, имеют своим прототипом известную труднорешаемую задачу коммивояжера (TSP в англоязычной литературе) [1-12], в них возникают существенные особенности не только количественного, по и качественного характера: ограничения, усложненные функции стоимости, многовариантности возможных перемещений и др. Исследования в области решений т.п. обобщенной задачи коммивояжера (GTSP) [1;13-16] также не покрывают потребности интересующих пас инженерных приложений, хотя и учитывают многовариантности возможных перемещений (объектами посещения являются кластеры или мегаполисы, а не города, как в TSP).
Полезно отметить задачу коммивояжера с условиями предшествования (TSP-PC) (см. [17-22]и др.), где, в частности, исследовалось влияние условий предшествования па сложности вычислений. Отметим, что в русскоязычной литературе используется термин "задача курьера" (см. [3—5;23]). Отметим ряд работ, посвящённых TSP-PC, ориентированных па приложения; см. [24] (инспекция нефтяных вышек), [18;25-28] (оптимизация производственных процессов), организация складской деятельности [29]. Отметим работы [30; 31], использующие элементы метода ветвей и границ для решения TSP-PC. В связи с применением для решения TSP динамического программирования (ДП) отметим особо работы [7; 8;32]. Развиваемая в настоящей работе конструкция восходит в идейном отношении к подходу [7], имеющему смысл попятной процедуры.
В настоящем обзоре мы воздержимся от обсуждения работ, связанных с решением задач маршрутизации с неаддитивным агрегированием затрат, ограничиваясь [33-35]. В задачах, исследуемых в настоящей работе, критерий качества предполагается аддитивным.
В связи с производственными задачами, приводящими к идеям маршрутизации с обобщениями, отметим исследование, посвящённое вопросам монтажа печатных плат [36]. Здесь же отметим работу [37], которая относится к GTSP- РС и связана с инженерной задачей обработки листа (сверление, развертывание отверстий, нарезка резьбы).
В настоящей работе исследуется комплекс вопросов, связанных с применением параллельных алгоритмов для решения задач маршрутизации, ориентированных па инженерные приложения, связанные с атомной энергетикой. Речь идет, в первую очередь, о вопросах, связанных со снижением облучаемости персонала АЭС и специалистов аварийно-спасательных формирований при ликвидации аварийных ситуаций, возникающих па АЭС, в которых существенную роль имеет маршрутизация выполняемых заданий. Дело в том, что снижать облучаемость можно не только с помощью различных защитных сооружений, по и за счет разумной организации последовательности выполняемых операций (в работе приведен соответствующий пример). В этой связи задачи маршрутизации настоящей работы могут представлять не только теоретический, по и серьезный практический интерес в плане снижения радиационного воздействия па исполнителей операций по демонтажу радиационно опасных объектов.
В то же время сама реализация упомянутых возможностей по снижению радиационного воздействия связана с решением очень сложных задач маршрутизации, имеющих лишь весьма отдалённое сходство со своим прототипом - задачей коммивояжера или TSP, хотя известные вопросы, связанные с труднорешаемостью TSP (см. [38]), в полной мере сохраняют свое значение и в задачах, рассматриваемых в настоящей работе. Речь идет о комбинаторных задачах с ограничениями и усложненными функциями стоимости, которые допускают зависимость от списка заданий, не выполненных па текущий момент. Кроме того, сами упомянутые зависимости в типичных случаях включают при своем построении интегрирование нелинейных зависимостей и комбинирование интегральных эффектов, создаваемых отдельными излучателями.
Возникающая при должной формализации постановка выходит за пределы круга задач, исследуемых в дискретной оптимизации и включает объективно элементы задач управления с дискретным временем. В этой связи отметим, что используемый в работе вариант ДП, восходящий к схеме Р. Веллмана [7], соответствует в идейном отношении процедурам па основе ДП, применяемым в теории управления; в этой связи отметим [39]. В дискретной оптимизации при решении TSP и задач типа TSP чаще используется вариант Хелда-Карпа; см. [8] (стоит отметить, что при решении самой исходной TSP и многих слабо осложненных задач, ДП используется крайне редко и в основном теоретически - для оценки вычислительной сложности).
Методология и методы исследования. Выбор ДП в качестве основного метода исследования (что нетипично для дискретной оптимизации) связан с определённой "всеядностью" процедур па основе ДП, что и позволило встраивать в эти процедуры элементы соблюдения ограничений и разнообразные условия функций стоимости. Таким образом, именно ДП позволяет (по крайней мере па теоретическом уровне) учитывать реальные интересы решения прикладных задач, что достигается, конечно, при соответствующей формализации исходной задачи с использованием ее разнообразных преобразований и должной теоретической проработки основных этапов исследования.
Целью диссертационной работы является исследование применения параллельных методов для решения ряда прикладных задач, возникающих в атомной энергетике.
Для достижения поставленной цели потребовалось решить следующие задачи:
1. Выполнить анализ модели перемещений с условиями предшествования и функциями стоимости, зависящими от списка невыполненных заданий, применительно к различным инженерным задачам.
2. Построить параллельный алгоритм поиска оптимального решения па основе ДП для задач маршрутизации и распределения заданий.
3. Разработать и реализовать комплекс программ, провести обширный вычислительный эксперимент.
4. Оцепить влияние условий предшествования па степень распараллеливания предложенных алгоритмов ДП.
Положения, выносимые на защиту:
1. Предложен алгоритм "вертикального" распараллеливания (схема независимых вычислений [40]) ДП в системах с распределенной памятью с применением программного интерфейса MPI, использован принцип разбиения задачи верхнего уровня на подзадачи меньшей размерности.
2. Реализован программный комплекс для точного решения задачи маршрутной оптимизации с ограничениями в виде условий предшествования и функциями стоимости, учитывающими возможную зависимость от списка невыполненных заданий.
3. Реализован эвристический алгоритм для решения "больших" маршрутных задач, учитывающий ограничения в виде условий предшествования и функции стоимости, зависящие от списка заданий.
4. Предложен метод улучшения эвристического алгоритма на основе оптимизирующих мультивставок с использованием параллельных вычислений. В результате решения этой задачи реализован программный комплекс на вычислительном кластере.
5. Построен параллельный алгоритм и реализован программный комплекс для решения задачи распределения заданий между участниками.
Научная новизна:
1. Разработан алгоритмический аппарат для решения задач маршрутизации с ограничениями и усложнёнными функциями стоимости. Впервые реализована схема распараллеливания динамического программирования на вычислительном кластере, при которой вычислительные узлы выполняют "сквозные" вычисления, не использующие обмен данными между узлами при последовательном расчёте слоев функции Веллмана. Данная реализация позволила существенно повысить размерность решаемых задач и сократить время вычислений.
2. Для решения прикладной задачи минимизации дозовой нагрузки работников атомных электростанции при проведении работ по демонтажу выводимого из эксплуатации оборудования или персонала аварийно-спасательных формирований при ликвидации чрезвычайных ситуаций на АЭС, построен и реализован в виде программы для МВС параллельный алгоритм. Данная прикладная задача предполагает учет ряда ограничений в виде условий предшествования и возможную зависимость функций стоимости от списка невыполненных заданий.
3. Для решения задач маршрутизации, имеющих большую размерность, построен параллельный алгоритм, реализующий оптимизирующие мультивставки в эвристические решения с целью улучшения качества исследуемого процесса.
4. Построен параллельный алгоритм на основе ДП для решения задачи распределения заданий.
Теоретическая и практическая значимость.
Построены новые параллельные алгоритмы решения задач маршрутизации перемещений и распределения заданий между участниками; в основе данных алгоритмов находится аппарат ДП и схемы независимых вычислений в условиях возможного перекрытия потоков данных вычислительной процедуры.
Построенные в работе алгоритмы могут быть использованы при решении таких актуальных инженерных задач, как проблема демонтажа радиационно опасных объектов при авариях на АЭС, подобных Чернобылю и Фукусиме, плановом выводе из эксплуатации отработавшего радиационно опасного оборудования на АЭС и управления инструментом при листовой резке деталей на машинах с ЧПУ (задача, связанная с раскроем). Другие возможные применения связаны с транспортными задачами, авиапожарным патрулированием лесов, задачей о сборе космического "мусора".
Степень достоверности полученных результатов обеспечивается строгими выводами и математическими доказательствами, воспроизводимостью прогнозируемых результатов при вычислительных экспериментах с использованием МВС, сопоставлением известным из литературы результатам для аналогичных моделей в тех случаях, когда упомянутые аналогичные результаты имеются.
Апробация работы. Основные результаты работы докладывались на:
— Григорьев А.М., Иванко Е.Е., Ченцов А.Г. К вопросу о применении параллельных алгоритмов для решения задач маршрутизации по методу динамического программирования {{ Анализ моделирование, развитие экономических систем : V междунар. шк.-симп. АМУР-2011 (Украина, Севастополь, 2011)
— Григорьев, А. М. Решение минимаксной распределительной задачи методом динамического программирования с применением параллельных вычислений // Научный сервис в сети Интернет: экзафлонсное будущее (Россия, Новороссийск, 2011)
— Григорьев А.М., Иванко Е.Е., Ченцов А.Г., Ченцов П.А. Параллельная реализация метода динамического программирования в обобщённой задаче курьера ! ! Научный сервис в сети Интернет: поиск новых решений (Россия, Новороссийск, 2012)
— Григорьев А.М., Иванко Е.Е. Об одной реализации метода динамического программирования для задачи коммивояжера осложнённой условиями предшествования {{ 47-я молодежная школ а-конференция "Современные проблемы математики и ее приложений" (Россия, Екатеринбург, 2016)
- Chentsov A. G., Grigoryev А.М. Scheme of Independent Calculations in a Precedence Constrained Routing Problem {{ Discrete Optimization and Operations Research - (DOOR 2016): 9th International Conference (Russia, Vladivostok, 2016)
- Chentsov A. G., Grigoryev A.M., Chentsov A. A. An Extremal Problem in Minimizing Staff Exposure to Radiation During Tasks Connected with Dismantlement of Radiation Sources {{ VIII Intern. Conf. “OPTIMIZATION AND APPLICATIONS” (OPTIMA-2017) (Montenegro, Petrovac, 2017)
- Grigoryev A.M., Tashlykov O.L. Solving a routing optimization of works in radiation fields with using a supercomputer {{ Physics, Technologies and Innovation (PTI-2018) (Russia, Ekaterinburg, 2018)
— Ченцов А.Г., Григорьев A.M., Ченцов А.А. Экстремальная маршрутизация с выбором точки старта и ее применение в задаче о демонтаже излучающих элементов {{ Анализ, моделирование, управление, развитие социально-экономических систем: сборник научных трудов XII Международной школы-симпозиума АМУР-2018 (Россия, Симферополь-Судак, 2018)-Grigoryev А.М., Tashlykov O.L. Route optimization during works in non- stationary radiation fields with obstacles {{ Physics, Technologies and Innovation (PTI-2019) (Russia, Ekaterinburg, 2019)
Основные результаты по теме диссертации изложены в 23 печатных и электронных изданиях, 4 из которых изданы в журналах и в трудах конференций, рекомендованных ВАК, 9 - в журналах и в трудах конференций, индексируемых системами WoS и Scopus, 10 - в тезисах докладов.
Личный вклад. Основные результаты диссертации опубликованы в [41-53]. В работах, написанных в соавторстве с научным руководителем, А.Г. Ченцову принадлежит постановка задачи и теоретические конструкции, связанные с процедурами па основе ДП, а А.М. Григорьеву эффективные параллельные алгоритмы, реализованные па суперкомпьютере; кроме того, им проведен обширный вычислительный эксперимент, позволивший выявить целый ряд полезных качественных зависимостей. В статьях, написанных в соавторстве с А.А. Ченцовым, соавтору А.А. Ченцову принадлежат выводы формул, оценивающих радиационное воздействие па различных этапах перемещений исполнителя, а также построение алгоритмов и программ для ПЭВМ, которые использовались в экспериментах при сравнении производительности с алгоритмами для МВС. В работах, написанных в соавторстве с О.Л. Ташлыковым, соавтору О.Л. Ташлыкову принадлежит инженерная постановка и описание физических явлений, связанных с задачей дозиметриста; А.М. Григорьевым была предложена математическая постановка и построен параллельный алгоритм, реализованный па супервычислителе. В работах, написанных в соавторстве с Е.Е. Иванко, соавтору Е.Е. Иванко принадлежит разработка алгоритмов и оценка их трудоемкости, А.М. Григорьеву принадлежит построение параллельного алгоритма, программная реализация и проведение вычислительных экспериментов. В статье «Григорьев А.М., Иванко Е.Е., Чепцов А.Г., Сесекин А.И., Ташлыков О.Л., Щеклеин С.Е. Решение задач маршрутизации применительно в радиационно опасным объектам с использованием суперкомпьютера "Урай"// Безопасность АЭС и подготовка кадров: тез. докл. 12-й Междунар. конф.- Обнинск, 2011- Т.2.- С.103-105» соавторам А.И. Сесекину и С.Е. Щеклейну принадлежит содержательная постановка рассматриваемой инженерной задачи, а диссертанту - построение параллельного алгоритма. В работе «Григорьев А.М., Иванко Е.Е., Князев С.Т., Чепцов А.Г. Динамическое программирование в обобщенной задаче курьера, осложненной внутренними работами // Мехатроника. Автоматизация. Управление.- 2012.-У5 7.- С. 14-21.» соавтору Князеву С.Т. принадлежит некоторые элементы содержательной постановки задачи об авиапожарном патрулировании лесов. В статье «Григорьев А.М., Иванко Е.Е., Чепцов А.Г., Чепцов И.А. Параллельная реализация метода динамического программирования в обобщенной задаче курьера // Междунар. суперкомпьютер, конф. "Научный сервис с сети Интернет: поиск новых решений Абрау-Дюрсо,- 2012: труды.
С.315-319.» соавтору П.А. Ченцову принадлежит алгоритм решения обобщеной задачи курьера для ПЭВМ (результаты решения па ПЭВМ использовались в целях сравнения с аналогичными результатами для МВС).
Объем и структура работы. Диссертация состоит из введения, трёх глав, заключения и списка литературы. Полный объём диссертации составляет 114 страниц с 13 рисунками Список литературы содержит 113 наименований.
Введение дает общую характеристику работы, как того требует ГОСТ Р 7.0.11—2011 "Диссертация и автореферат диссертации. Структура и правила оформления".
Глава1 посвящена вопросам параллельного решения задачи последовательного обхода мегаполисов с условиями предшествования и внутренними работами, связанными с посещением мегаполисов; данная задача является обобщением СТ8Р-РС и включает, па уровне постановки, функции стоимости, зависящие от списка невыполненных (па текущий момент) заданий. На основе метода ДП построен параллельный алгоритм для на-хождения оптимального решения. Кроме того, построен эффективный эвристический (жадный) алгоритм и проведено сравнение последнего с оптимальным в смысле достигаемого результата: выполнен вычисли-тельный эксперимент па МВС решения точным и эвристическим алгоритмами.
Глава2 посвящена вопросу локального улучшения эвристических решений в задаче последовательного обхода мегаполисов с условиями предшествования и функциями стоимости, допускающими зависимость от списка заданий. Данное улучшение реализуется параллельным алгоритмом, реализуемым в рамках построения специальной оптимизирующей мультивставки (имеется в виду система оптимизирующих вставок в эвристическое решение). Приведен вычислительный эксперимент па супервычислителе, показывающий значительное улучшение исходного эвристического решения.
Глава3 посвящена исследованию задачи оптимизации маршрута перемещения персонала при проведении работ в нестационарных радиационных полях с учётом обхода возможных препятствий. Описывается метод построения карты радиационного фона па плоскости по заранее измеренным значениям уровня радиации в ряде точек па этой плоскости. Рассматривается параллельная реализация метода ДП в задачах об оптимальном распределении заданий.
Заключение представляет изложение итогов исследования, рекомендаций и перспектив дальнейшей разработки темы.
В диссертации рассматриваются задачи маршрутизации перемещений, имеющие своим источником ситуации прикладного характера, возникающие в атомной энергетике при выполнении набора заданий, связанных с демонтажом радиационно опасных элементов. Отметим, что подобные постановки возникают и в других содержательных задачах. Среди них выделим особо задачу управления инструментом при листовой резке деталей па машинах с ЧПУ. Хотя исследуемые задачи маршрутизации, ориентированные па инженерные применения, имеют своим прототипом известную труднорешаемую задачу коммивояжера (TSP в англоязычной литературе) [1-12], в них возникают существенные особенности не только количественного, по и качественного характера: ограничения, усложненные функции стоимости, многовариантности возможных перемещений и др. Исследования в области решений т.п. обобщенной задачи коммивояжера (GTSP) [1;13-16] также не покрывают потребности интересующих пас инженерных приложений, хотя и учитывают многовариантности возможных перемещений (объектами посещения являются кластеры или мегаполисы, а не города, как в TSP).
Полезно отметить задачу коммивояжера с условиями предшествования (TSP-PC) (см. [17-22]и др.), где, в частности, исследовалось влияние условий предшествования па сложности вычислений. Отметим, что в русскоязычной литературе используется термин "задача курьера" (см. [3—5;23]). Отметим ряд работ, посвящённых TSP-PC, ориентированных па приложения; см. [24] (инспекция нефтяных вышек), [18;25-28] (оптимизация производственных процессов), организация складской деятельности [29]. Отметим работы [30; 31], использующие элементы метода ветвей и границ для решения TSP-PC. В связи с применением для решения TSP динамического программирования (ДП) отметим особо работы [7; 8;32]. Развиваемая в настоящей работе конструкция восходит в идейном отношении к подходу [7], имеющему смысл попятной процедуры.
В настоящем обзоре мы воздержимся от обсуждения работ, связанных с решением задач маршрутизации с неаддитивным агрегированием затрат, ограничиваясь [33-35]. В задачах, исследуемых в настоящей работе, критерий качества предполагается аддитивным.
В связи с производственными задачами, приводящими к идеям маршрутизации с обобщениями, отметим исследование, посвящённое вопросам монтажа печатных плат [36]. Здесь же отметим работу [37], которая относится к GTSP- РС и связана с инженерной задачей обработки листа (сверление, развертывание отверстий, нарезка резьбы).
В настоящей работе исследуется комплекс вопросов, связанных с применением параллельных алгоритмов для решения задач маршрутизации, ориентированных па инженерные приложения, связанные с атомной энергетикой. Речь идет, в первую очередь, о вопросах, связанных со снижением облучаемости персонала АЭС и специалистов аварийно-спасательных формирований при ликвидации аварийных ситуаций, возникающих па АЭС, в которых существенную роль имеет маршрутизация выполняемых заданий. Дело в том, что снижать облучаемость можно не только с помощью различных защитных сооружений, по и за счет разумной организации последовательности выполняемых операций (в работе приведен соответствующий пример). В этой связи задачи маршрутизации настоящей работы могут представлять не только теоретический, по и серьезный практический интерес в плане снижения радиационного воздействия па исполнителей операций по демонтажу радиационно опасных объектов.
В то же время сама реализация упомянутых возможностей по снижению радиационного воздействия связана с решением очень сложных задач маршрутизации, имеющих лишь весьма отдалённое сходство со своим прототипом - задачей коммивояжера или TSP, хотя известные вопросы, связанные с труднорешаемостью TSP (см. [38]), в полной мере сохраняют свое значение и в задачах, рассматриваемых в настоящей работе. Речь идет о комбинаторных задачах с ограничениями и усложненными функциями стоимости, которые допускают зависимость от списка заданий, не выполненных па текущий момент. Кроме того, сами упомянутые зависимости в типичных случаях включают при своем построении интегрирование нелинейных зависимостей и комбинирование интегральных эффектов, создаваемых отдельными излучателями.
Возникающая при должной формализации постановка выходит за пределы круга задач, исследуемых в дискретной оптимизации и включает объективно элементы задач управления с дискретным временем. В этой связи отметим, что используемый в работе вариант ДП, восходящий к схеме Р. Веллмана [7], соответствует в идейном отношении процедурам па основе ДП, применяемым в теории управления; в этой связи отметим [39]. В дискретной оптимизации при решении TSP и задач типа TSP чаще используется вариант Хелда-Карпа; см. [8] (стоит отметить, что при решении самой исходной TSP и многих слабо осложненных задач, ДП используется крайне редко и в основном теоретически - для оценки вычислительной сложности).
Методология и методы исследования. Выбор ДП в качестве основного метода исследования (что нетипично для дискретной оптимизации) связан с определённой "всеядностью" процедур па основе ДП, что и позволило встраивать в эти процедуры элементы соблюдения ограничений и разнообразные условия функций стоимости. Таким образом, именно ДП позволяет (по крайней мере па теоретическом уровне) учитывать реальные интересы решения прикладных задач, что достигается, конечно, при соответствующей формализации исходной задачи с использованием ее разнообразных преобразований и должной теоретической проработки основных этапов исследования.
Целью диссертационной работы является исследование применения параллельных методов для решения ряда прикладных задач, возникающих в атомной энергетике.
Для достижения поставленной цели потребовалось решить следующие задачи:
1. Выполнить анализ модели перемещений с условиями предшествования и функциями стоимости, зависящими от списка невыполненных заданий, применительно к различным инженерным задачам.
2. Построить параллельный алгоритм поиска оптимального решения па основе ДП для задач маршрутизации и распределения заданий.
3. Разработать и реализовать комплекс программ, провести обширный вычислительный эксперимент.
4. Оцепить влияние условий предшествования па степень распараллеливания предложенных алгоритмов ДП.
Положения, выносимые на защиту:
1. Предложен алгоритм "вертикального" распараллеливания (схема независимых вычислений [40]) ДП в системах с распределенной памятью с применением программного интерфейса MPI, использован принцип разбиения задачи верхнего уровня на подзадачи меньшей размерности.
2. Реализован программный комплекс для точного решения задачи маршрутной оптимизации с ограничениями в виде условий предшествования и функциями стоимости, учитывающими возможную зависимость от списка невыполненных заданий.
3. Реализован эвристический алгоритм для решения "больших" маршрутных задач, учитывающий ограничения в виде условий предшествования и функции стоимости, зависящие от списка заданий.
4. Предложен метод улучшения эвристического алгоритма на основе оптимизирующих мультивставок с использованием параллельных вычислений. В результате решения этой задачи реализован программный комплекс на вычислительном кластере.
5. Построен параллельный алгоритм и реализован программный комплекс для решения задачи распределения заданий между участниками.
Научная новизна:
1. Разработан алгоритмический аппарат для решения задач маршрутизации с ограничениями и усложнёнными функциями стоимости. Впервые реализована схема распараллеливания динамического программирования на вычислительном кластере, при которой вычислительные узлы выполняют "сквозные" вычисления, не использующие обмен данными между узлами при последовательном расчёте слоев функции Веллмана. Данная реализация позволила существенно повысить размерность решаемых задач и сократить время вычислений.
2. Для решения прикладной задачи минимизации дозовой нагрузки работников атомных электростанции при проведении работ по демонтажу выводимого из эксплуатации оборудования или персонала аварийно-спасательных формирований при ликвидации чрезвычайных ситуаций на АЭС, построен и реализован в виде программы для МВС параллельный алгоритм. Данная прикладная задача предполагает учет ряда ограничений в виде условий предшествования и возможную зависимость функций стоимости от списка невыполненных заданий.
3. Для решения задач маршрутизации, имеющих большую размерность, построен параллельный алгоритм, реализующий оптимизирующие мультивставки в эвристические решения с целью улучшения качества исследуемого процесса.
4. Построен параллельный алгоритм на основе ДП для решения задачи распределения заданий.
Теоретическая и практическая значимость.
Построены новые параллельные алгоритмы решения задач маршрутизации перемещений и распределения заданий между участниками; в основе данных алгоритмов находится аппарат ДП и схемы независимых вычислений в условиях возможного перекрытия потоков данных вычислительной процедуры.
Построенные в работе алгоритмы могут быть использованы при решении таких актуальных инженерных задач, как проблема демонтажа радиационно опасных объектов при авариях на АЭС, подобных Чернобылю и Фукусиме, плановом выводе из эксплуатации отработавшего радиационно опасного оборудования на АЭС и управления инструментом при листовой резке деталей на машинах с ЧПУ (задача, связанная с раскроем). Другие возможные применения связаны с транспортными задачами, авиапожарным патрулированием лесов, задачей о сборе космического "мусора".
Степень достоверности полученных результатов обеспечивается строгими выводами и математическими доказательствами, воспроизводимостью прогнозируемых результатов при вычислительных экспериментах с использованием МВС, сопоставлением известным из литературы результатам для аналогичных моделей в тех случаях, когда упомянутые аналогичные результаты имеются.
Апробация работы. Основные результаты работы докладывались на:
— Григорьев А.М., Иванко Е.Е., Ченцов А.Г. К вопросу о применении параллельных алгоритмов для решения задач маршрутизации по методу динамического программирования {{ Анализ моделирование, развитие экономических систем : V междунар. шк.-симп. АМУР-2011 (Украина, Севастополь, 2011)
— Григорьев, А. М. Решение минимаксной распределительной задачи методом динамического программирования с применением параллельных вычислений // Научный сервис в сети Интернет: экзафлонсное будущее (Россия, Новороссийск, 2011)
— Григорьев А.М., Иванко Е.Е., Ченцов А.Г., Ченцов П.А. Параллельная реализация метода динамического программирования в обобщённой задаче курьера ! ! Научный сервис в сети Интернет: поиск новых решений (Россия, Новороссийск, 2012)
— Григорьев А.М., Иванко Е.Е. Об одной реализации метода динамического программирования для задачи коммивояжера осложнённой условиями предшествования {{ 47-я молодежная школ а-конференция "Современные проблемы математики и ее приложений" (Россия, Екатеринбург, 2016)
- Chentsov A. G., Grigoryev А.М. Scheme of Independent Calculations in a Precedence Constrained Routing Problem {{ Discrete Optimization and Operations Research - (DOOR 2016): 9th International Conference (Russia, Vladivostok, 2016)
- Chentsov A. G., Grigoryev A.M., Chentsov A. A. An Extremal Problem in Minimizing Staff Exposure to Radiation During Tasks Connected with Dismantlement of Radiation Sources {{ VIII Intern. Conf. “OPTIMIZATION AND APPLICATIONS” (OPTIMA-2017) (Montenegro, Petrovac, 2017)
- Grigoryev A.M., Tashlykov O.L. Solving a routing optimization of works in radiation fields with using a supercomputer {{ Physics, Technologies and Innovation (PTI-2018) (Russia, Ekaterinburg, 2018)
— Ченцов А.Г., Григорьев A.M., Ченцов А.А. Экстремальная маршрутизация с выбором точки старта и ее применение в задаче о демонтаже излучающих элементов {{ Анализ, моделирование, управление, развитие социально-экономических систем: сборник научных трудов XII Международной школы-симпозиума АМУР-2018 (Россия, Симферополь-Судак, 2018)-Grigoryev А.М., Tashlykov O.L. Route optimization during works in non- stationary radiation fields with obstacles {{ Physics, Technologies and Innovation (PTI-2019) (Russia, Ekaterinburg, 2019)
Основные результаты по теме диссертации изложены в 23 печатных и электронных изданиях, 4 из которых изданы в журналах и в трудах конференций, рекомендованных ВАК, 9 - в журналах и в трудах конференций, индексируемых системами WoS и Scopus, 10 - в тезисах докладов.
Личный вклад. Основные результаты диссертации опубликованы в [41-53]. В работах, написанных в соавторстве с научным руководителем, А.Г. Ченцову принадлежит постановка задачи и теоретические конструкции, связанные с процедурами па основе ДП, а А.М. Григорьеву эффективные параллельные алгоритмы, реализованные па суперкомпьютере; кроме того, им проведен обширный вычислительный эксперимент, позволивший выявить целый ряд полезных качественных зависимостей. В статьях, написанных в соавторстве с А.А. Ченцовым, соавтору А.А. Ченцову принадлежат выводы формул, оценивающих радиационное воздействие па различных этапах перемещений исполнителя, а также построение алгоритмов и программ для ПЭВМ, которые использовались в экспериментах при сравнении производительности с алгоритмами для МВС. В работах, написанных в соавторстве с О.Л. Ташлыковым, соавтору О.Л. Ташлыкову принадлежит инженерная постановка и описание физических явлений, связанных с задачей дозиметриста; А.М. Григорьевым была предложена математическая постановка и построен параллельный алгоритм, реализованный па супервычислителе. В работах, написанных в соавторстве с Е.Е. Иванко, соавтору Е.Е. Иванко принадлежит разработка алгоритмов и оценка их трудоемкости, А.М. Григорьеву принадлежит построение параллельного алгоритма, программная реализация и проведение вычислительных экспериментов. В статье «Григорьев А.М., Иванко Е.Е., Чепцов А.Г., Сесекин А.И., Ташлыков О.Л., Щеклеин С.Е. Решение задач маршрутизации применительно в радиационно опасным объектам с использованием суперкомпьютера "Урай"// Безопасность АЭС и подготовка кадров: тез. докл. 12-й Междунар. конф.- Обнинск, 2011- Т.2.- С.103-105» соавторам А.И. Сесекину и С.Е. Щеклейну принадлежит содержательная постановка рассматриваемой инженерной задачи, а диссертанту - построение параллельного алгоритма. В работе «Григорьев А.М., Иванко Е.Е., Князев С.Т., Чепцов А.Г. Динамическое программирование в обобщенной задаче курьера, осложненной внутренними работами // Мехатроника. Автоматизация. Управление.- 2012.-У5 7.- С. 14-21.» соавтору Князеву С.Т. принадлежит некоторые элементы содержательной постановки задачи об авиапожарном патрулировании лесов. В статье «Григорьев А.М., Иванко Е.Е., Чепцов А.Г., Чепцов И.А. Параллельная реализация метода динамического программирования в обобщенной задаче курьера // Междунар. суперкомпьютер, конф. "Научный сервис с сети Интернет: поиск новых решений Абрау-Дюрсо,- 2012: труды.
С.315-319.» соавтору П.А. Ченцову принадлежит алгоритм решения обобщеной задачи курьера для ПЭВМ (результаты решения па ПЭВМ использовались в целях сравнения с аналогичными результатами для МВС).
Объем и структура работы. Диссертация состоит из введения, трёх глав, заключения и списка литературы. Полный объём диссертации составляет 114 страниц с 13 рисунками Список литературы содержит 113 наименований.
Введение дает общую характеристику работы, как того требует ГОСТ Р 7.0.11—2011 "Диссертация и автореферат диссертации. Структура и правила оформления".
Глава1 посвящена вопросам параллельного решения задачи последовательного обхода мегаполисов с условиями предшествования и внутренними работами, связанными с посещением мегаполисов; данная задача является обобщением СТ8Р-РС и включает, па уровне постановки, функции стоимости, зависящие от списка невыполненных (па текущий момент) заданий. На основе метода ДП построен параллельный алгоритм для на-хождения оптимального решения. Кроме того, построен эффективный эвристический (жадный) алгоритм и проведено сравнение последнего с оптимальным в смысле достигаемого результата: выполнен вычисли-тельный эксперимент па МВС решения точным и эвристическим алгоритмами.
Глава2 посвящена вопросу локального улучшения эвристических решений в задаче последовательного обхода мегаполисов с условиями предшествования и функциями стоимости, допускающими зависимость от списка заданий. Данное улучшение реализуется параллельным алгоритмом, реализуемым в рамках построения специальной оптимизирующей мультивставки (имеется в виду система оптимизирующих вставок в эвристическое решение). Приведен вычислительный эксперимент па супервычислителе, показывающий значительное улучшение исходного эвристического решения.
Глава3 посвящена исследованию задачи оптимизации маршрута перемещения персонала при проведении работ в нестационарных радиационных полях с учётом обхода возможных препятствий. Описывается метод построения карты радиационного фона па плоскости по заранее измеренным значениям уровня радиации в ряде точек па этой плоскости. Рассматривается параллельная реализация метода ДП в задачах об оптимальном распределении заданий.
Заключение представляет изложение итогов исследования, рекомендаций и перспектив дальнейшей разработки темы.
В диссертации исследовались важные для теории и инженерных приложений задачи маршрутизации, связанные с процедурами последовательного демонтажа системы радиационно-опасных объектов. Возникающая при этом математическая модель является достаточно сложной и требует разработки серьезных теоретических конструкций для своего исследования. В настоящей работе принята модель мегаполисов, которые подлежат последовательному посещению с целью демонтажа источников излучения при соблюдении определённых ограничений, связанных с учётом особенностей исходной инженерной задачи. Среди упомянутых ограничений особую роль играют условия предшествования, которые удаётся использовать "в положительном направлении "в смысле снижения вычислительной сложности.
В диссертации построены методы и алгоритмы решения упомянутых задач маршрутизации, включая задачи ощутимой размерности. В основе используемых конструкций находится метод ДП, а конструируемые на его основе параллельные алгоритмы реализованы в виде стандартных программ на языке С++ для МВС. Эти алгоритмы используют идеи, заложенные в схемах с независимыми вычислениями слоев функции Веллмана. Они реализованы в двух вариантах:
1. точные алгоритмы, доставляющие глобальные экстремум и оптимальные маршруты;
2. алгоритмы, улучшающие качество эвристик за счет применения оптимизирующих мультивставок (оптимизация "в окнах").
В обоих случаях получено существенное продвижение в плане увеличения раз-мерности решаемых задач. Эту цель удалось достичь, в частности, за счет теоретически обоснованного распараллеливания вычислительных процедур. Представляется, что данный подход к решению очень сложных по постановке инженерных задач имеет смысл развивать и в дальнейшем, распространяя упомянутые конструкции на задачи другой природы. Среди таких задач можно отметить задачу управления инструментом при листовой резке на машинах с ЧПУ, задачу авиапожарного патрулирования лесов, транспортные задачи.
В диссертации построены методы и алгоритмы решения упомянутых задач маршрутизации, включая задачи ощутимой размерности. В основе используемых конструкций находится метод ДП, а конструируемые на его основе параллельные алгоритмы реализованы в виде стандартных программ на языке С++ для МВС. Эти алгоритмы используют идеи, заложенные в схемах с независимыми вычислениями слоев функции Веллмана. Они реализованы в двух вариантах:
1. точные алгоритмы, доставляющие глобальные экстремум и оптимальные маршруты;
2. алгоритмы, улучшающие качество эвристик за счет применения оптимизирующих мультивставок (оптимизация "в окнах").
В обоих случаях получено существенное продвижение в плане увеличения раз-мерности решаемых задач. Эту цель удалось достичь, в частности, за счет теоретически обоснованного распараллеливания вычислительных процедур. Представляется, что данный подход к решению очень сложных по постановке инженерных задач имеет смысл развивать и в дальнейшем, распространяя упомянутые конструкции на задачи другой природы. Среди таких задач можно отметить задачу управления инструментом при листовой резке на машинах с ЧПУ, задачу авиапожарного патрулирования лесов, транспортные задачи.