Стохастическое планирование производственных процессов

С И Великий; Максим Михайлович Горохов; Валентин Алексеевич Тененев

doi:10.22213/2410-9304-2025-1-54-64

Авторы

С. И. Великий ИжГТУ имени М. Т. Калашникова
М. М. Горохов ИжГТУ имени М. Т. Калашникова; ФКУ НИИ ФСИН России
В. А. Тененев ИжГТУ имени М. Т. Калашникова

DOI:

https://doi.org/10.22213/2410-9304-2025-1-54-64

Ключевые слова:

производственное расписание, метод статистических испытаний, генетический алгоритм, задачи оптимизации, стохастическое планирование

Аннотация

Неопределенность является неизбежным элементом во многих практических средах планирования и составления графиков производства. Задача формулируется следующим образом. Имеется множество заданий. Под заданием понимается любой вид работы в технологическом процессе. Для выполнения определенного задания необходимо использовать множество машин. Выполнение каждого задания на машине характеризуется неопределенным временем. В соответствии с технологическим процессом для каждого или для некоторых работ предписывается технологический маршрут прохождения машин. Для практического использования применяются методы с использованием генетических алгоритмов для поддержки планирования в производственной системе. Генетический алгоритм относится к категории искусственного интеллекта. Это очень эффективный алгоритм для поиска оптимальных или близких к оптимальным решениям оптимизационной задачи. В связи с тем, что методы дискретной оптимизации, типа метода ветвей и границ, являются NP трудными, в работе для решения задач производственного планирования при наличии неопределенности в сроках выполнения заданий на технологическом оборудовании предложено применять генетический алгоритм, включающий элементы метода статистических испытаний. В генетическом алгоритме используется гибкая схема кодирования хромосомы. Эта схема позволяет генерировать допустимые решения во всех генетических операторах: скрещивания, мутации и отбора. Это позволило получить решение с меньшим значением целевой функции по сравнению с методом кодирования с применением сетей Петри. Применение нормального закона распределения случайных величин времени выполнения работ на машинах приводит к распределению, близкому к нормальному, для конечного времени выполнения последней работы. При этом имеется линейная зависимость рассчитанной дисперсии от задаваемого уровня дисперсий. Среднее время выполнения последней работы увеличивается в полтора раза (1.54) при задании дисперсий в виде .

Биографии авторов

С. И. Великий, ИжГТУ имени М. Т. Калашникова

аспирант

М. М. Горохов, ИжГТУ имени М. Т. Калашникова; ФКУ НИИ ФСИН России

доктор физико-математических наук, профессор

В. А. Тененев, ИжГТУ имени М. Т. Калашникова

доктор физико-математических наук, профессор

Библиографические ссылки

Великий С. И., Горохов М. М., Тененев В. А. Задача производственного планирования с неопределенностью времени выполнения работ // Интеллектуальные системы в производстве. 2024. Т. 22, № 1. С. 48-55. DOI: 10.22213/2410-9304-2024-1-48-55.

Zhang J., Cai J. A. Dual-Population Genetic Algorithm with Q-Learning for Multi-Objective Distributed Hybrid Flow Shop Scheduling Problem//Symmetry 2023, 15 (4), 836; https://doi.org/10.3390/sym15040836.

Kun Lei, Peng Guo, Wenchao Zhao, Yi Wang, Linmao Qian, XiangyinMeng,Liansheng Tang. A multi-action deep reinforcement learning framework for flexible Job-shop scheduling problem // Expert Systems with Applications.Volume 205, 2022, 117796. Doi.org/10.1016/j.eswa.2022.117796.

Ronghua Chen, Bo Yang, Shi Li, Shilong Wang A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem // Computers & Industrial Engineering, Volume 149, November 2020. Doi.org/1016/j.cie.2020.106778.

Ensieh Ghaedy-Heidary, Erfan Nejati, Amir Ghasemi, S. Ali Torab. A simulation optimization framework to solve Stochastic Flexible Job-Shop Scheduling Problems - Case: Semiconductor manufacturing// Computers & Operations Research 163 (2024). Doi.org/10.1016/j.cor.2023.106508.

Tao L., Chen L., & Zhang G. Scheduling Stochastic Jobs - Complexity and Approximation Algorithms. Proceedings of the International Conference on Automated Planning and Scheduling, 31 (1), 2021, 367-375. Doi.org/10.1609/icaps.v 31i1.15982.

Sahar Habbadi, Brahim HERROU, Souhail SEKKAT. Job Shop Scheduling Problem Using Genetic Algorithms // Proceedings of the 5th European IEOM Rome Conference, July 25-28 2022, pp. 3050-3062. DOI 10446254/EU05.20220592.

Jayanta Mandi, James Kotary, Senne Berden, Maxime Mulamba, Victor Bucarey, Tias Guns and Ferdinando Fioretto. Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunities // https: arxiv.org/abs/2307.13565.

Kim van den Houten, David M.J. Tax, Mathijs de Weerd. Learning from Scenarios for Repairable Stochastic Scheduling // Conference paper.Integration of Constraint Programming Artificial Intelligence and Operations Research. 21st International Conference CPAIOR 2024 Uppsala Sweden May 28-31, 2024. Proceedings Part II, pp. 234-242.

Richard Stec, Antonin Novak, PremyslSucha, ZdenekHanzalek. Scheduling Jobs with Stochastic Processing Time on Parallel Identical Machines// Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19), pp. 5628-5634. https://doi.org/10.24963/ijcai.2019/781.

Stéphane Dauzère-Pérès, Junwen Ding, Liji Shend, Karim Tamssaouet. The flexible job shop scheduling problem: A review // European Journal of Operational Research 314 (2024), pp. 409-432, journal homepage: www.elsevier.com/locate/ejor.

Шашихина О. Е., Чистякова Т. Б. Компьютерная система для оптимального планирования полимерных производств // Известия Санкт-Петербургского государственного технологического института (технического университета). 2021. № 59 (85). С. 94-100. DOI: 10.36807/1998-9849-2021-59-85-94-100.

Семенкина О. Е., Попов Е. А. Бионические алгоритмы решения иерархической задачи составления расписания при оперативном планировании производства // Вестник Московского государственного технического университета им. Н. Э. Баумана. Серия приборостроение. Московский государственный технический университет им. Н. Э. Баумана (национальный исследовательский университет) (Москва). 2019. № 3 (126). С. 46-63. DOI: 10.18698/0236-3933-2019-3-46-63.

Сочнев А. Н. Планирование производства на основе управляемой генетическим алгоритмом имитационной модели // Техника и технологии. 2021. № 14 (2). С. 233-243. DOI: 10.17516/1999-494X-0304.

Горовых И. И., Горовых С. Н. Гибридный подход к решению NP - сложных задач настройки производства: объединение метода ветвей и границ с генетическим алгоритмом // Молодой исследователь Дона. 2024. Т. 9, № 1 (46). С. 10-19. eISSN 2500-1779.

Семенов Г. Е., Кейно П. П. Применение математических моделей на основе генетических алгоритмов в задачах планирования сложных технических объектов // Прикладная информатика. 2019. Т. 14, № 2 (80). С. 56-62. DOI: 10.24411/1993-8314-2019-10005.

Шитов А. Е., Журавлев И. А. Исследование работы генетического алгоритма в процессе производственно-хозяйственной деятельности // Наукосфера. 2021. № 12-1. С. 236-240. DOI: 10.5281/zenodo.5788763.

Константинова А. Ю. Планирование производства промышленного предприятия на этапе реконструкции средствами искусственного интеллекта // Матрица научного познания. 2020. № 6. С. 71-76. ISSN 2541-8084.

Системный анализ, математическое моделирование и оптимизация процесса формирования производственного расписания обработки металлоконструкций / А. А. Большаков, Л. А. Слободянюк, О. Е. Шашихина, Я. А. Ковальчук // Вестник Технологического университета. 2021. Т. 24, № 7. С. 84-92.