Одна задача маршрутизации работ в условиях повышенной радиации
Ключевые слова:
динамическое программирование, демонтаж, маршрут
Аннотация
Исследуется задача последовательного обхода мегаполисов, ориентированная на проблему демонтажа системы радиационно опасных объектов при ограничениях в виде условий предшествования. Радиационное воздействие на исполнителей оценивается дозами, получаемыми при перемещениях и при выполнении работ по демонтажу. Рассматривается маршрутная задача минимизации дозовой нагрузки работников, осуществляющих демонтаж в той или иной последовательности операций. Исследуется процедура построения оптимального решения с использованием варианта динамического программирования. На этой основе построен алгоритм, реализованный на ПЭВМ. Приведены примеры численного решения модельной задачи на минимум дозовой нагрузки.
Литература
1. Петунин А.А. О некоторых стратегиях формирования маршрута инструмента при разработке управляющих программ для машин термической резки материала // Вестник Уфимского государственного авиационного технического университета. 2009. Т. 13. № 2 (35). С. 280-286.
https://elibrary.ru/item.asp?id=15134316
2. Chentsov A.G., Chentsov P.A., Petunin A.A., Sesekin A.N. Model of megalopolises in the tool path optimisation for CNC plate cutting machines // International Journal of Production Research. 2018. Vol. 56. Issue 14. P. 4819-4830.
https://doi.org/10.1080/00207543.2017.1421784
3. Ченцов А.Г., Ченцов А.А., Сесекин А.Н. Задачи маршрутизации перемещений с неаддитивным агрегированием затрат. М.: URSS, 2020.
4. Коробкин В.В., Сесекин А.Н., Ташлыков О.Л., Ченцов А.Г. Методы маршрутизации и их приложения в задачах повышения безопасности и эффективности эксплуатации атомных станций. М.: Новые технологии, 2002.
5. Ченцов А.Г., Ченцов А.А., Сесекин А.Н. О задаче последовательного обхода мегаполисов с условиями предшествования и функциями стоимости с зависимостью от списка заданий // Труды Института математики и механики УрО РАН. 2020. Т. 26. № 3. С. 219-234.
https://doi.org/10.21538/0134-4889-2020-26-3-219-234
6. Ченцов А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории. Ижевск: Институт компьютерных исследований, 2008.
7. Gutin G., Punnen A.P. The traveling salesman problem and its variations. Boston: Springer, 2007.
https://doi.org/10.1007/b101971
8. Cook W.J. In pursuit of the traveling salesman: mathematics at the limits of computation. Princeton: Princeton University, 2012.
9. Гимади Э.Х., Хачай М.Ю. Экстремальные задачи на множествах перестановок. Екатеринбург: УМЦ УПИ, 2016.
10. Литл Дж., Мурти К., Суини Д., Кэрел К. Алгоритм для решения задачи о коммивояжере // Экономика и математические методы. 1965. Т. 1. Вып. 1. С. 94-107.
11. Беллман Р. Применение динамического программирования к задаче о коммивояжере // Кибернетический сборник. М.: Мир, 1964. Вып. 9. С. 219-228.
12. Хелд М., Карп Р.М. Применение динамического программирования к задачам упорядочения // Кибернетический сборник. М.: Мир, 1964. Вып. 9. С. 202-218.
13. Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Вопросы теории // Автоматика и телемеханика. 1989. Вып. 9. С. 3-33.
http://mi.mathnet.ru/at6414
14. Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Точные алгоритмы // Автоматика и телемеханика. 1989. Вып. 10. С. 3-29.
http://mi.mathnet.ru/at6433
15. Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Приближенные алгоритмы // Автоматика и телемеханика. 1989. Вып. 11. С. 3-26.
http://mi.mathnet.ru/at6463
16. Куратовский К., Мостовский А. Теория множеств. М.: Мир, 1970.
17. Дьедонне Ж. Основы современного анализа. М.: Мир, 1964.
18. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2002.
19. Ченцов А.Г. К вопросу о маршрутизации комплексов работ // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. 2013. Вып. 1. C. 59-82.
https://doi.org/10.20537/vm130107
20. Чеблоков И.Б., Ченцов А.Г. Об одной задаче маршрутизации с внутренними работами // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. 2012. Вып. 1. C. 96-119.
https://doi.org/10.20537/vm120109
21. Ченцов А.Г. Одна параллельная процедура построения функции Беллмана в обобщенной задаче курьера с внутренними работами // Вестник Южно-Уральского государственного университета. Сер. «Математическое моделирование и программирование». 2012. Вып. 12. C. 53-76.
http://mi.mathnet.ru/vyuru57
22. Chentsov A.A., Chentsov A.G., Sesekin A.N. An extremal routing problem with constraints and complicated cost functions // Advanced Control Systems: Theory and Applications. River Publishers, 2021. P. 21-52.
23. Lawler E.L. Efficient implementation of dynamic programming algorithms for sequencing problems. Stichting Mathematisch Centrum, 1979.
24. Ченцов А.Г., Ченцов А.А. К вопросу о нахождении значения маршрутной задачи с ограничениями // Проблемы управления и информатики. 2016. № 1. С. 41-54.
25. Петунин А.А., Ченцов А.Г., Ченцов П.А. Оптимальная маршрутизация инструмента машин фигурной листовой резки с числовым программным управлением. Математические модели и алгоритмы. Екатеринбург: Изд-во Урал. ун-та, 2020.
26. Ченцов А.Г., Ченцов А.А. Модельный вариант задачи о последовательной утилизации источников излучения (итерации на основе оптимизирующих вставок) // Известия Института математики и информатики Удмуртского государственного университета. 2017. Т. 50. C. 83-109.
https://doi.org/10.20537/2226-3594-2017-50-08
https://elibrary.ru/item.asp?id=15134316
2. Chentsov A.G., Chentsov P.A., Petunin A.A., Sesekin A.N. Model of megalopolises in the tool path optimisation for CNC plate cutting machines // International Journal of Production Research. 2018. Vol. 56. Issue 14. P. 4819-4830.
https://doi.org/10.1080/00207543.2017.1421784
3. Ченцов А.Г., Ченцов А.А., Сесекин А.Н. Задачи маршрутизации перемещений с неаддитивным агрегированием затрат. М.: URSS, 2020.
4. Коробкин В.В., Сесекин А.Н., Ташлыков О.Л., Ченцов А.Г. Методы маршрутизации и их приложения в задачах повышения безопасности и эффективности эксплуатации атомных станций. М.: Новые технологии, 2002.
5. Ченцов А.Г., Ченцов А.А., Сесекин А.Н. О задаче последовательного обхода мегаполисов с условиями предшествования и функциями стоимости с зависимостью от списка заданий // Труды Института математики и механики УрО РАН. 2020. Т. 26. № 3. С. 219-234.
https://doi.org/10.21538/0134-4889-2020-26-3-219-234
6. Ченцов А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории. Ижевск: Институт компьютерных исследований, 2008.
7. Gutin G., Punnen A.P. The traveling salesman problem and its variations. Boston: Springer, 2007.
https://doi.org/10.1007/b101971
8. Cook W.J. In pursuit of the traveling salesman: mathematics at the limits of computation. Princeton: Princeton University, 2012.
9. Гимади Э.Х., Хачай М.Ю. Экстремальные задачи на множествах перестановок. Екатеринбург: УМЦ УПИ, 2016.
10. Литл Дж., Мурти К., Суини Д., Кэрел К. Алгоритм для решения задачи о коммивояжере // Экономика и математические методы. 1965. Т. 1. Вып. 1. С. 94-107.
11. Беллман Р. Применение динамического программирования к задаче о коммивояжере // Кибернетический сборник. М.: Мир, 1964. Вып. 9. С. 219-228.
12. Хелд М., Карп Р.М. Применение динамического программирования к задачам упорядочения // Кибернетический сборник. М.: Мир, 1964. Вып. 9. С. 202-218.
13. Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Вопросы теории // Автоматика и телемеханика. 1989. Вып. 9. С. 3-33.
http://mi.mathnet.ru/at6414
14. Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Точные алгоритмы // Автоматика и телемеханика. 1989. Вып. 10. С. 3-29.
http://mi.mathnet.ru/at6433
15. Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Приближенные алгоритмы // Автоматика и телемеханика. 1989. Вып. 11. С. 3-26.
http://mi.mathnet.ru/at6463
16. Куратовский К., Мостовский А. Теория множеств. М.: Мир, 1970.
17. Дьедонне Ж. Основы современного анализа. М.: Мир, 1964.
18. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2002.
19. Ченцов А.Г. К вопросу о маршрутизации комплексов работ // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. 2013. Вып. 1. C. 59-82.
https://doi.org/10.20537/vm130107
20. Чеблоков И.Б., Ченцов А.Г. Об одной задаче маршрутизации с внутренними работами // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. 2012. Вып. 1. C. 96-119.
https://doi.org/10.20537/vm120109
21. Ченцов А.Г. Одна параллельная процедура построения функции Беллмана в обобщенной задаче курьера с внутренними работами // Вестник Южно-Уральского государственного университета. Сер. «Математическое моделирование и программирование». 2012. Вып. 12. C. 53-76.
http://mi.mathnet.ru/vyuru57
22. Chentsov A.A., Chentsov A.G., Sesekin A.N. An extremal routing problem with constraints and complicated cost functions // Advanced Control Systems: Theory and Applications. River Publishers, 2021. P. 21-52.
23. Lawler E.L. Efficient implementation of dynamic programming algorithms for sequencing problems. Stichting Mathematisch Centrum, 1979.
24. Ченцов А.Г., Ченцов А.А. К вопросу о нахождении значения маршрутной задачи с ограничениями // Проблемы управления и информатики. 2016. № 1. С. 41-54.
25. Петунин А.А., Ченцов А.Г., Ченцов П.А. Оптимальная маршрутизация инструмента машин фигурной листовой резки с числовым программным управлением. Математические модели и алгоритмы. Екатеринбург: Изд-во Урал. ун-та, 2020.
26. Ченцов А.Г., Ченцов А.А. Модельный вариант задачи о последовательной утилизации источников излучения (итерации на основе оптимизирующих вставок) // Известия Института математики и информатики Удмуртского государственного университета. 2017. Т. 50. C. 83-109.
https://doi.org/10.20537/2226-3594-2017-50-08
Поступила в редакцию
2021-07-05
Опубликована 2021-11-20
Опубликована 2021-11-20