МЕТОД ГЕНЕТИЧЕСКОГО ПРОГРАММИРОВАНИЯ РЕШЕНИЯ ЗАДАЧИ ОПЕРАТИВНО-КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ ДИСКРЕТНОГО ПРОИЗВОДСТВА:

К. О. Обухов; И. Ю. Квятковская; А. В. Морозов

К. О. Обухов Астраханский государственный технический университет
И. Ю. Квятковская Астраханский государственный технический университет
А. В. Морозов Астраханский государственный технический университет

Ключевые слова: Задачи планирования, дискретное производство, теория расписаний, генетические алгоритмы, многокритериальная оптимизация

Аннотация

Одним из основных условий успешного функционирования предприятия является грамотно
организованный процесс производственного планирования. Автоматизировать эту деятельность
позволяют системы производственного планирования класса APS/MES, основой которых являют-
ся алгоритмы построения производственных планов. В работе исследуется проблема составления
расписания для предприятий дискретного типа производства, относящаяся к области задач мно-
гокритериальной оптимизации. Приведено формальное описание задачи планирования с учетом
основных производственных ограничений (временные ограничения, требования к оснастке и по-
рядку выполнения операций). Кратко рассмотрены основные методы решения задач данного
класса, отмечены их основные достоинства и недостатки. Для решения поставленной задачи
выбран подход на основе генерации эвристических правил, применяемых при планировании произ-
водственных операций на заданные ресурсы. На основе данного подхода предложен двухэтапный
алгоритм построения производственных расписаний, включающий в себя генерацию правил дис-
петчеризации и их дальнейшее применение при построении расписания. За генерацию правил дис-
петчеризации отвечает генетический алгоритм. Подробно описана реализация его генетических
операторов, а также состав хромосомы и древовидное представление входящих в хромосому пра-
вил диспетчеризации. Реализация алгоритма выполнена на языке C# 12 с использованием свобод-
ной платформы .NET 8. Построенный алгоритм показал свою эффективность по сравнению с
жадным алгоритмом на небольших сгенерированных наборах данных. Дальнейшими исследова-
ниями в этой области является оценка эффективности построенного алгоритма с более слож-
ными генетическими операторами и структурой дерева выражений, а также снижение длитель-
ности процесса генерации эвристических правил для больших наборов данных.

Литература

1. Ctrategiya tsifrovoy transformatsii obrabatyvayushchikh otrasley promyshlennosti v tselyakh dostizheniya ikh
«tsifrovoy zrelosti» do 2024 goda i na period do 2030 goda [Strategy for digital transformation of manufacturing
industries in order to achieve their “digital maturity” by 2024 and for the period up to 2030]. Available at:
https://www.tadviser.ru/images/8/83/Stateg_info_2021_compressed.pdf (accessed 07 November 2024).
2. Korchevskaya A.A. [i dr.]. Trendy i stsenarii razvitiya rynka sistem rasshirennogo planirovaniya
proizvodstva (APS-sistem) v ramkakh napravleniya «Tekhnet» NTI. Ekspertno-analiticheskiy dok-lad:
monografiya [Trends and scenarios for the development of the market of advanced production planning
systems (APS systems) within the framework of the Technet direction of the NTI. Expert and analytical
report: monograph]. Saint Petersburg: POLITEKH-PRESS, 2024, 112 p.
3. Obukhov K.O. Sravnitel'nyy analiz sistem proizvodstvennogo planirovaniya v razreze raboty s
al'ternativnymi tsepochkami proizvodstvennykh operatsiy [Comparative analysis of production planning
systems in the context of working with alternative chains of production operations], Molodoy
uchenyy [Young scientist], 2022, No. 20 (415), pp. 143-147. Available at: https://moluch.ru/archive/
415/91773/ (accessed 07 November 2024).
4. Klimova E.Z., Pavlova I.A., Makusheva Yu.A. Mesto i rol' operativno-proizvodstvennogo pla-nirovaniya
v upravlenii predpriyatiem [Place and role of operational production planning in enterprise management],
EGI [EGI], 2022, No. 42 (4). Available at: https://cyberleninka.ru/article/n/mesto-i-rol-operativnoproizvodstvennogo-
planirovaniya-v-upravlenii-predpriyatiem (accessed 07 November 2024).
5. Dzhukha V.M., Kirillov D.O. Potentsial'nye preimushchestva APS-sistem v prodazhakh i operatsionnom
planirovanii [Potential advantages of APS systems in sales and operational planning], UEkS [Management
of economic systems], 2013, No. 7 (55). Available at: https://cyberleninka.ru/ article/n/potentsialnyepreimuschestva-
aps-sistem-v-prodazhah-i-operatsionnom-planirovanii-1 (accessed 10 December 2024).
6. Lazarev A.A., Gafarov E.R. Teoriya raspisaniy. Zadachi i algoritmy [Scheduling theory. Problems and
algorithms]. Moscow: Fizicheskiy fakul'tet MGU, 2011, 222 p.
7. Job shop scheduling: Classification, constraints and objective functions. Available at:
https://www.researchgate.net/publication/339128833_Job_shop_scheduling_Classification_constraints
_and_objective_functions (accessed 07 November 2024).
8. A review on job shop scheduling with setup times. Available at: https://www.researchgate.net/ publication/
275317984_A_review_on_job_shop_scheduling_with_setup_times (accessed 10 December 2024).
9. Planirovanie i optimizatsiya protsessov perenaladki [Planning and optimization of changeover processes].
Available at: https://habr.com/ru/companies/ds/articles/533788 (accessed 10 December 2024).
10. A Flexible Branch and Bound Method for the Job Shop Scheduling Problem. Available at:
https://www.researchgate.net/publication/238723625_A_Flexible_Branch_and_Bound_Method_for_t
he_Job_Shop_Scheduling_Problem (accessed 07 November 2024).
11. Dynamic Programming for Routing and Scheduling. Available at: https://research.vu.nl/ws/portalfiles/
portal/42163578/complete+dissertation.pdf (accessed 07 November 2024).
12. Designing Dispatching Rules to Minimize Total Tardiness. Available at: https://www.researchgate.net/
publication/226253624_Designing_Dispatching_Rules_to_Minimize_Total_Tardiness (accessed 07
November 2024).
13. A Job-Shop Scheduling Problem (JSSP) using Genetic Algorithm (GA). Available at:
https://www.researchgate.net/publication/242081421_A_JOB-SHOP_SCHEDULING_PROBLEM_JSSP_
USING_GENETIC_ALGORITHM_GA (accessed 07 November 2024).
14. Sochnev A.N. Planirovanie proizvodstva na osnove upravlyaemoy geneticheskim algoritmom imitatsionnoy
modeli [Production planning based on a simulation model controlled by a genetic algorithm], Zhurnal SFU.
Tekhnika i tekhnologii [Journal of SFU. Engineering and Technology], 2021, No. 2. Available at:
https://cyberleninka.ru/article/n/planirovanie-proizvodstva-na-osnove-upravlyaemoy-geneticheskimalgoritmom-
imitatsionnoy-modeli (accessed 07 November 2024).
15. Solving the Job Shop Scheduling Problem with Ant Colony Optimization. Available at:
https://www.researchgate.net/publication/363500511_Solving_the_Job_Shop_Scheduling_Problem_w
ith_Ant_Colony_Optimization (accessed 07 November 2024).
16. Zhang F., Mei Y., Nguyen S. and Zhang M. Survey on Genetic Programming and Machine Learning
Techniques for Heuristic Design in Job Shop Scheduling, in IEEE Transactions on Evolutionary
Computation, Feb. 2024, Vol. 28, No. 1, pp. 147-167.
17. Dynamic flexible job shop scheduling method based on improved gene expression programming. Available
at: https://www.researchgate.net/publication/343612768_Dynamic_flexible_job_shop_ scheduling_
method_based_on_improved_gene_expression_programming (accessed 10 December 2024).
18. Zhang F., Mei Y., Nguyen S. and Zhang M. Evolving Scheduling Heuristics via Genetic Programming
With Feature Selection in Dynamic Flexible Job-Shop Scheduling, in IEEE Transactions on Cybernetics,
April 2021, Vol. 51, No. 4, pp. 1797-1811,
19. Genetic Programming: An Introduction and Tutorial. Available at: https://wiki.eecs.yorku.ca/
course_archive/2010-11/W/4403/_media/gp1.pdf (accessed 07 November 2024).
20. Polikarpova N.I., Tochilin V.N. Primenenie geneticheskogo programmirovaniya dlya realizatsii sistem
so slozhnym povedeniem [Application of genetic programming for the implementation of systems
with complex behavior], Nauchno-tekhnicheskiy vestnik informatsionnykh tekhnologiy, mekhaniki i
optiki [Scientific and technical bulletin of information technologies, mechanics and optics], 2007,
No. 39. Available at: https://cyberleninka.ru/article/n/primenenie-geneticheskogo-programmirovaniyadlya-
realizatsii-sistem-so-slozhnym-povedeniem (accessed 07 November 2024).