МОДЕЛЮВАННЯ DAG-СТРУКТУР РОБОЧИХ НАВАНТАЖЕНЬ
DOI:
https://doi.org/10.34185/1991-7848.itmm.2026.01.057Ключові слова:
інформаційні технології, програмне забезпечення, конструктивно-продукційне моделювання, направлений ациклічний граф, формальні граматики, графові граматики, планування задач, Kubernetes, оркестрація контейнерів, генерація робочих навантаженьАнотація
Запропоновано конструкційну модель породження DAG-структур робочих навантажень для тестування планувальників кластерів Kubernetes. Модель базується на апараті узагальненого конструктора та спеціалізує його компоненти для предметної області направлених ациклічних графів задач. Формалізовано механізм підстановки як частковий випадок контекстно-вільної графової граматики із заміною вузлів з чотирма типами правил: атрибутування, підстановка підграфа, реплікація та алгоритмічна генерація. Введено систему атрибутів, що розширює ідеї атрибутних граматик Кнута на графові структури. Доведено збереження ацикличності при кожній підстановці та завершимість процесу породження. Конструктор реалізовано мовою Python з декларативним YAML DSL. Експериментально підтверджено практичну придатність моделі на множині з 100 породжених DAG.
Посилання
Chomsky N. Three models for the description of language // IRE Trans. on Information Theory. — 1956. — Vol. 2, No. 3. — P. 113–124.
Knuth D. E. Semantics of context-free languages // Mathematical Systems Theory. — 1968. — Vol. 2, No. 2. — P. 127–145.
Shynkarenko V. I., Ilman V. M. Constructive-Synthesizing Structures and Their Grammatical Interpretations. I. Generalized Formal Constructive-Synthesizing Structure // Cybernetics and Systems Analysis. — 2014. — Vol. 50, No. 5. — P. 655–662. DOI: 10.1007/s10559-014-9655-z.
Skalozub V., Ilman V., Shynkarenko V. Ontological support formation for constructive-synthesizing modeling of information systems development processes // Eastern-European Journal of Enterprise Technologies. — 2018. — Vol. 5, No. 4(95). — P. 55–63. DOI: 10.15587/1729-4061.2018.143968.
Rozenberg G. (ed.) Handbook of Graph Grammars and Computing by Graph Transformation. Vol. 1: Foundations. — World Scientific, 1997.
Cordeiro D., Mounié G., Perarnau S., Trystram D., Vincent J.-M., Wagner F. Random graph generation for scheduling simulations // Proc. 3rd International ICST Conference on Simulation Tools and Techniques (SIMUTools 2010). — 2010. — P. 1–10. DOI: 10.4108/ICST.SIMUTOOLS2010.8667.
Canon L.-C., Sayah M., Héam P.-C. A Comparison of Random Task Graph Generation Methods for Scheduling Problems // Euro-Par 2019. LNCS, vol. 11725. — Springer, 2019. — P. 61–73.
