
Тип работы:	Предмет:	Язык работы:

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

Работа №	102587
Тип работы	Диссертации (РГБ)
Предмет	математика
Объем работы	114
Год сдачи	2021
Стоимость	4230 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено	99

Не подходит работа?

Узнай цену на написание

Содержание

Введение 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

Введение

Актуальность и степень разработанности.
В диссертации рассматриваются задачи маршрутизации перемещений, имеющие своим источником ситуации прикладного характера, возникающие в атомной энергетике при выполнении набора заданий, связанных с демонтажом радиационно опасных элементов. Отметим, что подобные постановки возникают и в других содержательных задачах. Среди них выделим особо задачу управления инструментом при листовой резке деталей па машинах с ЧПУ. Хотя исследуемые задачи маршрутизации, ориентированные па инженерные применения, имеют своим прототипом известную труднорешаемую задачу коммивояжера (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. Gutin G., Риппеп А. Р.The Traveling Salesman Problem and Its Variations.
-Dordrecht: Springer, 2002.
2. Cook William J. In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. — Princeton University Press, 2012. — URL:http://www.jstor.Org/stable/j.ctt7t8kc.
3. Меламед И. И., Сергеев C. IP, Сигал И. X.Задача коммивояжера. Вопросы теории // Автоматика и телемеханика. — 1989. - К" 9. - С. 3-34.
4. Меламед И. II., Сергеев С. II., Сигал И. X. Задача коммивояжера. Точные алгоритмы // Автоматика и телемеханика. — 1989. — № 10. — С. 3-29.
5. Меламед II. II., Сергеев С. II., Сигал IP X. Задача коммивояжера. Приближенные алгоритмы // Автоматика и телемеханика. — 1989. — № 11.-С. 3-26.
6. Рамади Э.Х., Хачай М.Ю. Экстремальные задачи па множествах перестановок. — Екатеринбург: Издательство УМЦ УПИ, 2016.
7. Bellman R. Dynamic Programming Treatment of the Travelling Salesman Problem // J. Assoc. Comput. Mach. — 1962. — no. 9. — Pp. 61-63.
8. Held, M., Karp R. M. A Dynamic Programming Approach to Sequencing Problems // Journal of the Society for Industrial and Applied Mathematics — 1962.-Vol. 10, no. 1. - Pp. 196-210.
9. И. Сергеев С. Использование методов теории оптимального управления для решения некоторых задач дискретной оптимизации. I. Сепарабельная задача // Автоматика и телемеханика. — 2006. - Т4. - С. 42-52.
10. И. Сергеев С. Использование методов теории оптимального управления для решения некоторых задач дискретной оптимизации. II. Статическая задача коммивояжера // Автоматика и телемеханика. — 2006. - Тб.-С. 106-112.
11. И. Сергеев С. Использование методов теории оптимального управления для решения некоторых задач дискретной оптимизации. III. Динамическая задача коммивояжера // Автоматика и телемеханика. — 2006. — № 7. - С. 27-40.
12. An Algorithm for the Traveling Salesman Problem / John D. C. Little, Katta G. Murty, Dura W. Sweeney, Caroline Karel // Operations Research. — 1963. — December. — Vol. 11, no. 6. — Pp. 972-989. — URL:https://ideas.repec.org/a/inm/oropre/vl Iyl963i6p972-989.html.
13. Chisman James A. The clustered traveling salesman problem // Computers & Operations Research. — 1975. — Vol. 2, no. 2. — Pp. 115-119.
14. KJ. Хачай M., Д. Незнахина E.Приближенные схемы для обобщенной задачи коммивояжера // Труды ИММ УрО РАН. — 2016. — Т. 22, № 3. — С. 283-292.
15. Ю. Хачай М., Д. Незнахина Е. Разрешимость обобщенной задачи коммивояжера в классе квази- и псевдопирамидальпых маршрутов // Труды, НММ УрО РАН. - 2017. - Т. 23, № 3. - С. 280-291.
16. Balas Е.New classes of efficiently solvable generalized Traveling Salesman Problems // Annals of Operations Research. — 1999. — January. — Vol. 86, no. 0. - Pp. 529-558.
17. The Traveling Salesman Problem with Precedence Constraints / Lucio Bianco, Aristide Mingozzi, Salvatore Ricciardelli, Massimo Spadoni // Papers of the 19th Annual Meeting/Vorträge der 19. Jahrestagung / Springer. — 1992. — Pp. 299-306.
18. Escudero Laureano F. A production planning problem in FMS // Annals of Operations Research. — 1989. — Vol. 17, no. 1. — Pp. 69-103.
19. Kubo Mikio, Kasugai Hiroshi. The precedence constrained traveling salesman problem // Journal of the Operations Research Society of Japan — 1991. — Vol. 34, no. 2. - Pp. 152-172.
20. Gouveia Luis, Ruthmair Mario. Load-dependent and precedence-based models for pickup and delivery problems // Computers & Operations Research. —
2015.- 04. - Vol. 63. - Pp. 56-71.
21. В. Салий Я. Влияние условий предшествования на вычислительную
сложности решения маршрутных задач методом динамического программирования// Вестник Удмуртского университета.
Математика. Механика. Компьютерные науки.
22. Salii Yaroslav. Revisiting Dynamic Programming for Precedence-Constrained Traveling Salesman Problem and Its Time-Dependent Generalization // Euro¬pean Journal of Operational Research. — 2017. — 04. — Pp. 32-42.
23. M. Плотинский Ю. Обобщенная задача развозки // Автомат, и телемех.
24. Fiala Timlin Marie Т, Pulleyblank William R. Precedence constrained routing and helicopter scheduling: heuristic design // Interfaces. — 1992. — Vol. 22, no. 3. - Pp. 100-111.
25. Escudero Laureano F. A production planning problem in FMS // Annals of Operations Research. — 1989. — Vol. 17, no. 1. — Pp. 69-103.
26. Dubowsky Steven, Blubaugh TD. Planning time-optimal robotic manipulator motions and work places for point-to-point tasks // Robotics and Automation, IEEE Transactions on. — 1989. — Vol. 5, no. 3. — Pp. 377-381.
27. Spieckermann Sven, Gutenschwager Kai, Voß Stefan. A sequential ordering problem in automotive paint shops // International journal of production re¬search. — 2004. — Vol. 42, no. 9. — Pp. 1865-1878.
28. Петунии А. А. О некоторых стратегиях формирования маршрута инструмента при разработке управляющих программ для машин термической резки материала // Вестник Уфимского государственного авиационного технического университета. — 2009. — Vol. 13, по. 2. — Рр. 280-286.
29. Ascheuer Norbert. Hamiltonian path problems in the on-line optimization of flexible manufacturing systems: Ph.D. thesis / Technische Universität Berlin Germany. — 1995.
30. Kalantari Bahman, Hill Arthur V, Arora Sant R. An algorithm for the travel¬ing salesman problem with pickup and delivery customers / / European Journal of Operational Research. — 1985. — Vol. 22, no. 3. — Pp. 377-386.
31. Shobaki Ghassan, Jamal Jafar. An exact algorithm for the sequential ordering problem and its application to switching energy minimization in compilers // Computational Optimization and Applications. — 2015. — Vol. 61, no. 2. — Pp. 343-372.
32. Lawler E.L. Efficient implementation of dynamic programming algorithms for sequencing problems. CWI Technical report // BW 106/79: Stichting Mathe¬matisch Centrum. — 1979. — Pp. 1-16.
33. Mitten L G. Composition principles for synthesis of optimal multistage pro¬cesses // Operations Research. — 1964. — Vol. 12, no. 4. — Pp. 610-619.
34. Morin Thomas L. Monotonicity and the principle of optimality // Journal of Mathematical Analysis and Applications. — 1982. — Vol. 88, no. 2. — Pp. 665-674.
35. А.Г. Ченцов, А.А. Ченцов, A.H. Сесекин. Задачи маршрутизации перемещений с аддитивным агрегированием затрат. — Москва: Лепапд, 2020.
36. Alkaya AU, Duman Ekrem. A new generalization of the Traveling salesman problem // Applied and Computational Mathematics. — 2010. — 01. — Vol. 9.-Pp. 162-175.
37. Lokin FCJ. Procedures for travelling salesman problems with additional constraints // European Journal of Operational Research. — 1979. — Vol. 3, no. 2.-Pp. 135-141.
38. Garey M. R., Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences). — First Edition edition. — W. H. Freeman, 1979. — URL:http://www.amazon.com/Computers-Intractability-NP-Completeness-Mathematical-Sciences/dp/0716710455.
39. Р. Веллман, Р. Калаба. Динамическое программирование и современная теория управления. — Москва: Наука, 1969.
40. Ченцов А. Г. Одна параллельная процедура построения функции Веллмана в обобщенной задаче курьера с внутренними работами // Автоматика и телемеханика. — 2012. — № 3. — С. 134-149.
41. А.М. Григорьев, Е.Е. Иванко, А.Г. Ченцов. Динамическое программирование в обобщённой задаче курьера с внутренними работами: элементы параллельной структура! // Моделирование и анализ информационных систем. - 2011. - Т. 18, № 3. - С. 101-124.
42. Динамическое программирование в обобщенной задаче курьера, осложненной внутренними работами / Григорьев А.М., Иванко Е.Е., Князев С.Т., Ченцов А.Г. // Мехатроника, автоматизация, управление. — 2012. — № 7. - С. 14-21.
43. A. G. Chentsov, А.М. Grigoryev. Scheme of independent calculations in a prece¬dence constrained routing problem // Lecture Notes in Computer Science. —
2016.- Vol. 9869. - Pp. 121-135.
44. Ченцов А. Г., Григорьев А.М. Динамическое программирование в задаче маршрутизации: схема независимых вычислений // Мехатроника, Автоматизация, Управление. — 2016. — Т. 17, А2 12. — С. 834-846.
45. A.G. Chentsov, А.М. Grigoryev, A.A. Chentsov. Scheme of independent calculations in a precedence constrained routing problem // CEUR-WS. — 2017. - Vol. 1987. - Pp. 123-130.
46. А.Г. Ченцов, А.А. Ченцов, А.М. Григорьев. Об одной задаче маршрутизации, моделирующей перемещения в радиационных полях // Вестн. УдГУ. Математика. Механика. Компьютерные науки — 2017. — Т. 27, А2 4. — С. 540-557.
47. Григорьев А.М. Решение задачи об оптимальном распределении заданий методом динамического программирования с применением параллельных вычислений // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. — 2017. — Т. 27, А2 1. — С. 129-137.
48. Chentsov A.G., Grigoryev A.M., Chentsov A. A. Optimizing the starting point in a precedence constrained routing problem with complicated travel cost func¬tions // Ural Mathematical Journal. — 2018. — Vol. 4, no. 2. — Pp. 43-55.
49. A.M. Grigoryev, L. Tashlykov 0. Solving a routing optimization of works in radiation fields with using a supercomputer // AIP Conference Proceedings. — 2018. - Vol. 2015. - P. 6.
50. A.G. Chentsov, A.M. Grigoryev, A.A. Chentsov. Solving a Routing Problem with the Aid of an Independent Computations Scheme // Bulletin South Ural State Univ. Ser. Math. Modelling, Programming & Computer Software — 2018. - Vol. 11, no. 1. - Pp. 60-74.
51. Ченцов А. Г., Григорьев A. M.Оптимизирующие мультивставки в задачах маршрутизации с ограничениями // Вести. Удмуртск. ун-та. Матем. Мех. Компъют. науки. — 2018. — Т. 28, А5 4. — С. 513-530.
52. A.G. Chentsov, A.M. Grigoryev, A.A. Chentsov. Optimization “In Windows” for Routing Problems with Constraints // Communications in Computer and Information Science. — 2019. — Vol. 1090. — Pp. 470-485.
53. A.M. Grigoryev, L. Tashlykov O. Route optimization during works in nonsta- tionary radiation fields with obstacles // AIP Conference Proceedings. — 2019. - Vol. 2174. - P. 6.
54. Ченцов А. Г. Экстремальные задачи маршрутизации и распределения зада¬ний: вопросы теории. — Москва-Ижевск: НИЦ «Регулярная и хаотическая динамика», 2008.
55. Методы маршрутизации и их приложения в задачах повышения безопасности и эффективности эксплуатации атомных станций / В.В. Коробкин, А.Н. Сесекин, О.Л Ташлыков, А.Г. Ченцов. — Москва: Новые технологии, 2012.
56. Ташлыков О. Л. Дозовые затраты персонала в атомной энергетике. Анализ. Пути снижения. Оптимизация. — LAP LAMBERT Academic Publishing, 2011.
57. LeonИ Jorge, Peters Brett A. Replanning and analysis of partial setup strate¬gies in printed circuit board assembly systems // International Journal of Flexible Manufacturing Systems. — 1996. — Vol. 8, no. 4. — Pp. 389-411. — URL:https://doi.org/10.1007/BF00170019.
58. Finable J., Cire A.A., van Hoeve W.J. Hybrid optimization methods for time-dependent sequencing problems // European Journal of Operational Re¬search. - 2017. - 6. - Vol. 259, no. 3. - Pp. 887-897.
59. Лету пин А. А. О некоторых стратегиях формирования маршрута инструмента при разработке управляющих программ для машин термической резки материала // Вестник У ГАТУ. Серия: Управление, вычислительная техника и информатика. — 2009. — Т. 13, № 2 (35). — С. 280—286.
60. Петунии, А. А., Ченцов А.Г., Ченцов П.А.К вопросу о маршрутизации движения инструмента в машинах листовой резки с числовым программным управлением // Науч.-техн, ведомости СПбГПУ. Серия: Информатика. Телекоммуникации. Управление. — 2013. — V 2 (169). — С. 103-111.
61. Фроловский В.Д. Автоматизация проектирования управляющих программ тепловой резки металла па оборудовании с ЧПУ // Информационные технологии в проектировании и производстве. — 2005. - > 4. - С. 63—66.
62. Wang Gary, XIEz S. Optimal process planning for a combined punch-and-laser cutting machine using ant colony optimization // International Journal of Production Research - INT J PROD RES. — 2005. — 06. — Vol. 43. — Pp. 2195-2216.
63. Dewil Reginald, Vansteenwegen Pieter, Cattrysse Dirk Construction heuris¬tics for generating tool paths for laser cutters // International Journal of Pro¬duction Research. — 2014. — Vol. 52, no. 20. — Pp. 5965-5984. — URL: https://doi.org/10.1080/00207543.2014.895064.
64. Дъедонне Ж. Основы современного анализа. — Москва: Мир, 1964.
65. Кормен Т, Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ. — Москва: МЦНМО, 2000.
по
66. Ченцов Л. Г. К вопросу о маршрутизации комплексов работ // Вестник Удм. ун-та. Математика. Механика. Комп, науки — 2013. — № 1. - С. 59-82.
67. Ченцов А. Г., Ченцов П. А. Оптимизация точки старта в задаче последовательного обхода мегаполисов при наличии условий предшествования // Вести. ЮУрГУ. Сер. Матем. моделирование и программирование. — 2018. — Vol. 11, по. 2. — Р. 83-95.
68. Ченцов А. Г., Ченцов П. А. Об одной задаче маршрутизации с оптимизацией точки старта-финиша // Изв. ИМИ УдГУ. — 2018. — Vol. 52. - Р. 103-115.
69. Ченцов А. Г., Ченцов И. А. Маршрутная задача с оптимизацией стартовой точки: динамическое программирование // Изв. ИМИ УдГУ. — 2019. — Т. 54. - С. 102-121.
70. Alkaya Ali Fuat, Duman Ekrem.Combining and solving sequence dependent traveling salesman and quadratic assignment problems in PCB assembly // Discrete Applied Mathematics. — 2015. — Vol. 192. — Pp. 2-16.
71. Ченцов А. Г., Ченцов А. А. Задача маршрутизации с ограничениями, зависящими от списка заданий // Доклады Академии наук. — 2015. — Т. 465, № 2. - С. 154-158.
72. Ченцов А. Г., Ченцов И.А. Маршрутизация в условиях ограничений: задача о посещении мегаполисов // Автоматика и телемеханика. — 2016. - № 11. - С. 96-117.
73. Петунии А. А., Ченцов А. Г., Ченцов И.А. Локальные вставки на основе динамического программирования в задаче маршрутизации с ограничениями // Вестник Удмуртского университета. — 2014. — № 2. — С. 56-75.
74. Ченцов А. Г. Беллмановские вставки в задаче маршрутизации с ограничениями и усложненной функцией стоимости // Вестник Удмуртского университета. — 2014. — № 4. — С. 122-141.
75. Ченцов А. Г. Оптимизирующие вставки в задачах маршрутизации и их реализация на основе динамического программирования // Вестник Удмуртского университета. — 2016. — № 4. — С. 565-578.
76. Ченцов А. Г. Об оптимальной маршрутизации в условиях ограничений // Доклады Академии наук. — 2008. — Т. 423, № 3. - С. 303-307.
77. Ченцов А. Г. Задача последовательного обхода мегаполисов с условиями предшествования // Автоматика и телемеханика. — 2014. — ..V0 4.
С. 170-190.
78. Ченцов А. Г., Ченцов Л.Л. К вопросу о нахождении значения маршрутной задачи с ограничениями // Проблемы управления и информатики. — 2016. - № 1. - С. 41-54.
79. Ченцов А. Г. Одна параллельная процедура построения функции Веллмана в обобщенной задаче курьера с внутренними работами // Вестник ЮУрГУ. Сер. Мат. моделирование и программирование. — 2012. — Т. 12, № 18. - С. 53-76.
80. Ченцов А. Г., Ченцов А. А. Моделвнвш вариант задачи о последовательной утилизации источников излучения (итерации на основе оптимизирующих вставок) // Изв. ИМИ УдГУ. — 2017. — Т. 50. — С. 83-109.
81. Александров И. С., Маркушевич А.И., Хинчин А.Я. Энциклопедия элементарной математики. Книга 3. Функции и пределы. — М.-Л.: ГИТТЛ, 1952.
82. Ченцов А. Л.7Ченцов А. Г., Ченцов И. А. Экстремальная задача маршрутизации с внутренними потерями // Тр. ИММ УрО ВАН. — 2008. — Т. 14, № 3. - С. 183-201.
83. Ченцов А. Л.7Ченцов А. Г. Задача последовательного обхода мегаполисов // Вестник Тамбовского университета. Сер. Естественные и технические науки. — 2014. — Т. 19, № 2. — С. 454-475.
84. Ченцов А. Г., Кошелева М. С. Динамическое программирование в задаче курьера со стоимостями, зависящими от списка заданий // Мехатроника, автоматизация, управление. — 2015. — Уо1. 16, по. 4. — Рр. 232-244.
85. Куратовский К., Мостовский А. Теория множеств. — Москва: Мир, 1970.
86. Элементах динамического программирования в конструкциях локального
улучшения эвристических решений задач маршрутизации с ограничениями / А. А. Петунии, А. А. Ченцов, А. Г. Ченцов, П. А. Ченцов // Автоматика и телемеханика. — 2017. ..V0 4. С. 106-125.
87. Возможности математических методов моделирования в решении проблемы снижения облучаемости персонала / Ташлыков О. Л., Сесекин А.Н., Щеклеин С.Е. et al. // Вопросы радиационной безопасности.
-2009). - по. 4. - Р. 47-57.
88. Собрание законодательства Российской Федерации > 3 ст.Ц1- Федеральный закон «О радиационной безопасности населения» А5 3-ФЗ от 09.01.96. — Москва, 1996.
89. 2.6.1.2523-09 СанПиН. Нормы радиационной безопасности (НРБ-99/2009).-Москва, 2009.
90. 2.6.1.2612-10 СП. Основные санитарные правила обеспечения радиационной безопасности (ОСПОРБ - 99/2010). — Москва, 2010.
91. 2.6.5.054-2017 МУ. Оптимизация радиационной защиты персонала предприятий Госкорпорации «Росатом». Методические указания. — Москва: Федеральное медико-биологическое агентство, 2017.
92. Чнецов А.Г., Ченцов П.А. К вопросу о построении процедуры разбиения конечного множества на основе метода динамического программирования // Автоматика и телемеханика. — 2000...V0 4. С. 129-142.
93. Ченцов А. Г., Ченцов П. А. Динамическое программирование в задаче
оптимизации разбиений // Автоматика и телемеханика. — 2002...V0 5.-С. 133-146.
94. Schrage Linus, Baker Kenneth R. Dynamic programming solution of sequenc¬ing problems with precedence constraints // Operations Research. — 1978. — Vol. 26, no. 3. - Pp. 444-449.
95. Ченцов А. Г., Ченцов П. А. Маршрутная задача с условиями
предшествования (задача курьера): метод динамического
программирования // Вести. УГТУ-УПИ. — 2004. — по. 15. —Рр. 148-151.
96. Ченцов А. Г. О структуре одной экстремальной задачи маршрутизации с ограничениями в виде условий предшествования // Вести. Удмуртского ун-та. Математика. — 2006. — no. 1. — Рр. 127-150.
97. Ченцов А. Г. Экстремальные задачи маршрутизации с ограничениями // Изв. института матем. и информатики. — 2006. — по. 3. — Рр. 163-166.
98. Buhmann Martin D. Radial Basis Functions: Theory and Implementations. — Cambridge University Press, 2003.
99. Dijkstra E. W. A Note on Two Problems in Connexion with Graphs // NU-MERISCHE MATHEMATIK. - 1959. - Vol. 1, no. 1. - Pp. 269-271.
100. Левитин А.В. Алгоритмы: введение в разработку и анализ. — Москва: Издательский дом "Вильямс 2006.
101. Омельченко А. В. Теория графов. — Москва: МЦНМО, 2018.
102. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация: Алгоритмы и сложность. — Москва: Мир, 1984.
103. Оре О. Теория графов. — Москва: Наука, 1980.
104. Burkard Rainer., Dell'Amico Mauro., Martello Silvano. Assignment Problems. — Society for Industrial and Applied Mathematics, 2012. — URL:https://epubs.siam.org/doi/abs/10.1137/1.9781611972238.
105. Kuhn H. W. The Hungarian method for the assignment problem // Naval Research Logistics Quarterly. — 1955. — Vol. 2, no. 1-2. — Pp. 83-97. — URL: https: / / onlinelibrary.wiley.com/doi / abs /10.1002/ nav.3800020109.
106. Kellerer Hans, Pferschy Ulrich, Pisinger David Knapsack Problems. — 2004. - 01.
107. Papadimitriou Christos H., Yannakakis Mihalis. Optimization, approximation, and complexity classes // Journal of Computer and System Sciences. — 1991.
— Vol. 43, no. 3. — Pp. 425 - 440. — URL:http://www.sciencedirect.com/science/article/pii/002200009190023X.
108. Коротаева Л.Н., Назаров Э.М., Ченцов A.Г. Об одной задаче о назначениях // Журн. въьчисл. математики и мат. физики. — 1993. — Т. 33, № 4. - С. 483-494.
109. Беллман Р. Динамическое программирование. — Москва: Издательство иностранной литературы, 1960.
ПО. Мину М. Математическое программирование. — Москва: Наука, 1990.
111. Ченцов П. А. О некоторых алгоритмах распределения заданий между участниками // Автоматика и телемеханика. — 2006. — № 8. — С. 77-91.
112. Григорьев А.М. Решение минимаксной распределительной задачи методом динамического программирования с применением параллельных вычислений // Научный сервис в сети Интернет: экзафлопсное будущее: Труды Международной суперкомпъютерной конференции — 2011. — С. 580-586.
113. Антонов А. С. Параллельное программирование с использованием технологии MPI: Учебное пособие. — Москва: МГУ, 2004.