Алгоритм оптимизации процессов формирования производственного расписания предприятий позаказного производства

В статье рассматривается проблема простоев производственных предприятий с повременной оплатой труда. Нерациональное использование ресурсов ведет к потерям. Решить данную проблему можно посредством автоматизации процессов формирования производственного расписания. В представленной работе авторами используется терминология теории расписаний. В результате проведенных исследований, разработан алгоритм, который является решением задачи дискретной оптимизации посредством эвристических алгоритмов. Алгоритм предполагает случайный выбор операции на основе критериев с проверкой свободного в данный временной период ресурса и назначением его на соответствующую операцию. Алгоритм выполняется циклично до тех пор, пока не будут задействованы все операции или ресурсы на заданный временной промежуток. Построение алгоритма опирается на вычисленный рекорд, превышение которого ведет к прекращению реализации алгоритма, и его повторному запуску. Описанный алгоритм по истечению количества итераций, заданных пользователем, визуализирует решение, представляя его в виде диаграммы Ганта, для обеспечения диспетчеризации производственных процессов. Полученные авторами результаты позволят создать систему интеллектуального формирования производственного расписания и внедрить ее в существующую систему управления производственным предприятием, занимающимся производством изделий из полимерных композиционных материалов.

1. Лазарев А.А., Гафаров Е.Р. Теория расписаний. Задачи и алгоритмы. М.: Дрофа; 2011. 144 с.

2. Аничкин А.С., Семенов В.А. Объектно-ориентированный каркас для программной реализации приложений теории расписаний. Труды Института системного программирования РАН. 2017;29(3):247–296.

3. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. М.: Издательский дом «Вильямс»; 2000. 384 с.

4. Stastny J., Skorpil V., Balogh Z., Klein R. Job shop scheduling problem optimization by means of graph-based algorithm. Applied Sciences. 2021;11(4). Доступно по: https://www.mdpi.com/2076-3417/11/4/1921/xml. DOI: 10.3390/app11041921 (дата обращения: 07.12.2022).

5. Сиркин Т.В., Чернышова А.П., Мартынов П.А., Морозов А.Д. Разработка автоматизированной системы составления и оптимизации расписания занятий. Молодой ученый. 2020;317(27):65–71.

6. Zang Z., Wang W., Song Y., Lu L., Li W., Wang Y., Zhao Y. Hybrid deep neural network scheduler for job-shop problem based on convolution two-dimensional transformation. Computational Intelligence and Neuroscience. 2019;2019:1–19. Доступно по: https://www.hindawi.com/journals/cin/2019/7172842/. DOI: 10.1155/2019/7172842 (дата обращения: 07.12.2022).

7. Bex P. Implementing a process scheduler using neural network technology. Extended abstract of masters’s thesis. Netherlands; 2008. 65 p. Доступно по: https://theses.ubn.ru.nl/handle/123456789/168 (дата обращения: 11.12.2022).

8. Samira C. Monte Carlo tree search for job shop scheduling problems. Extended abstract of masters’s thesis. Austria; 2017. 90 p. Доступно по: https://pure.unileoben.ac.at/portal/files/2220344/AC14530216n01.pdf (дата обращения: 11.12.2022).

9. Geirsson E. Rollout algorithms for job-shop scheduling. Iceland, University of Iceland; 2012. 53 p. Доступно по: https://skemman.is/bitstream/1946/11956/ 1/Einar_Geirsson_ritgerd.pdf (дата обращения: 13.12.2022).

10. Lenstra J.K., Shmoys D.B., Tardos E. Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming. 1987;46(1–3):217–224. Доступно по: https://www.researchgate.net/publication/4355176_Approximation_Algorithms_for_Scheduling_Unrelated_Paralle_Machines. DOI: 10.1109/SFCS.1987.8 (дата обращения: 13.12.2022).

11. Колесов Н.В., Толмачева М.В. Составление расписаний решения задач в конвейерных вычислительных системах. Информационно-управляющие системы. 2005;(5):16–21.