Структура комп’ютерної програми для визначення оптимального шляху орієнтованого графа при використанні алгоритму Дейкстри

СТРУКТУРА КОМП’ЮТЕРНОЇ ПРОГРАМИ ДЛЯ ВИЗНАЧЕННЯ ОПТИМАЛЬНОГО ШЛЯХУ ОРІЄНТОВАНОГО ГРАФА ПРИ ВИКОРИСТАННІ АЛГОРИТМУ ДЕЙКСТРИ

STRUCTURE OF A COMPUTER PROGRAM FOR DETERMINING THE OPTIMAL PATH DIRECTED GRAPH USING DIJKSTRA’S ALGORITHM

Сторінки: 269-272. Номер: №6, 2022 (315)  
Автори:
ЩЕРБАНЬ Володимир
Київський національний університет технологій та дизайну
ORCID ID: 0000-0002-4274-4425
scherbanvu@ukr.net
ІЩЕНКО Валентин
Київський національний університет технологій та дизайну
ORCID ID: 0000-0003-2180-5257
kipt@i.com.ua
КОЛИСКО Оксана
Київський національний університет технологій та дизайну
ORCID ID: 0000-0003-4043-1238
kipt@i.com.ua
МЕЛЬНИК Геннадій
Київський національний університет технологій та дизайну
ORCID ID: 0000-0002-0002-7663
kipt@i.com.ua
ЩЕРБАНЬ Юрій
Київський фаховий коледж прикладних наук
ORCID ID: 0000-0001-5024-8387
scherban@i.ua
SHCHERBAN Volodymyr, ISHCHENKO Valentin, KOLISKO Oksana, MELNIK Genadij
Kyiv National University of Technologies and Design, Kyiv, Ukraine
SHCHERBAN Yuryj
Kyiv Professional College of Applied Sciences
DOI: https://www.doi.org/10.31891/2307-5732-2022-315-6-270-273

Анотація мовою оригіналу

Забезпечення мінімального натягу при переробці нитки на технологічному обладнанні дозволяє зменшити простої обладнання за рахунок виключення чи суттєвого скорочення обривів ниток. Мінімізація натягу забезпечується оптимізацією форми лінії заправки нитки, при якій сумарний кут охоплення напрямних буде мінімальним. Ця задача вирішується за допомогою використання алгоритму Дейкстри при пошуку оптимального шляху орієнтованого графа. Комп’ютерна програма для реалізації  цього алгоритму дозволяє оптимізувати форму заправки нитки на технологічному обладнанні.
Ключові слова: комп’ютерна програма, оптимальний шлях, орієнтований граф, алгоритм Дейкстри.

Розширена анотація англійською  мовою

Ensuring the minimum tension during thread processing on technological equipment allows to reduce equipment downtime due to the elimination or significant reduction of thread breaks. Minimization of tension is ensured by optimization of the shape of the thread filling line, in which the total angle of coverage of the guides will be minimal. This problem is solved by using Dijkstra’s algorithm in finding the optimal path of a directed graph. The computer program for implementing this algorithm allows you to optimize the form of filling the thread on the technological equipment. The development of application packages of computer programs allows to reduce the time for the design of technological processes in the light and textile industry as much as possible. This is due to the modernization of the thread filling line on the technological equipment, which allows to minimize thread tension in the working area. Minimization of tension is ensured by optimization of the shape of the thread filling line, in which the total angle of coverage of the guides will be minimal.
This problem is solved by using Dijkstra’s algorithm in finding the optimal path of a directed graph. Construction of the optimal path of the directed graph will allow to obtain the minimum tension in the working area. Constructive structural elements in the form of guides, elements of tensioning devices, break control devices, which have a cylindrical, elliptical shape, and discrete segments of a straight line act as obstacles in the path of the thread. Straight line segments can have an inclination relative to the vertical axis. Taking into account the large number of structural elements of the thread feeding system on light and textile industry machines and their location, there is a need to develop a special computer program for determining the optimal shape of the thread feeding line using the Dijkstra algorithm when searching for the optimal path of a directed graph.
The objective function in the problem is the minimum necessary tension, which is the minimum sum of the angles covered by the thread of guide surfaces that have a cylindrical, elliptical shape, discrete segments of a straight line. The use of a computer program allows you to determine tensions and changes in relative tension in the filling zones of light and textile industry machines, which allows you to optimize the shape of the thread supply line even at the stage of designing the technological process. The use of algorithms for computer programs for finding the optimal path of an undirected graph, for cylindrical, elliptical guides, discrete segments of a straight line, allows you to determine the influence of coverage angles on the target tension function. Determining the effect of coverage angles, for cylindrical, elliptical guides, discrete segments of a straight line, on the objective function during the computer determination of the optimal path for an oriented graph is an important component of the optimization of thread tension in the working area of machines of the light and textile industry, the formation of knitted and textile products.
Keywords: computer program, optimal path, directed graph, Dijkstra’s algorithm.

Література

1. Щербань В.Ю. Механіка нитки / В.Ю. Щербань. – К. : Освіта України, 2018. – 533 с.
2. Базове проектуюче забезпечення САПР в індустрії моди / [В.Ю. Щербань, Ю.Ю. Щербань, О.З. Колиско, Г.В. Мельник, М.І. Шолудько, В.Ю. Калашник]. – К. : Освіта України, 2018. – 902 с.
3. Scherban V. Yu., Krasnitsky S.M., Rezanov V.G. Mathematical Models in CAD. Selected sections and examples of application. K.: KNUTD, 2011. 220 p.
4. Щербань В.Ю. САПР оборудования и технологических процессов легкой и текстильной промышленности / В.Ю. Щербань, О.И. Волков, Ю.Ю. Щербань. – К. : Бумсервис, 2004. – 519 с.
5. Щербань В.Ю. Дослідження впливу матеріалу нитки і анізотропії тертя на її натяг і форму осі / В.Ю. Щербань, В.Ю. Калашник, О.З. Колиско, М.І. Шолудько // Вісник Хмельницького національного університету. Технічні науки. – 2015. – 223(2). – С. 25–29.
6. Shcherban V.Y., Kolisko O.Z., Melnyk G.V., Sholudko M.I., Kalashnik V.Y. Computer systems design: software and algorithmic components. К. : Education of Ukraine, 2019. 902 p.
7. Scherban V. Yu., Kolisko O.Z., Sholudko M.I., Kalashnik V. Yu. Algorithmic, software and mathematical components of CAD in the fashion industry. К.: Education of Ukraine, 2017. 745 p.
8. Shcherban V., Melnyk G., Sholudko M., Kalashnyk V. Warp yarn tension during fabric formation. Fibres and Textiles. 2018. Volume 25. № P. 97–104.
9. Yakubitskaya I.A., Chugin V.V., Shcherban V.Yu. Differential equations of the relative motion of the filament element on the end sections of the coil of the winding drum. Technology of the textile industry. 1997. № P. 50–54.

References

1. Scherban V.Yu. Mechanics of Threads. K.: Formation of Ukraine, 2018. 533 p.
2. Shcherban V.Yu., Shcherban Y.Y., Kolisko O.Z., Melnik G.V., Sholudko M.I., Kalashnik V.Y. Basic design support of CAD in the fashion industry. Kyiv: Education of Ukraine, 2018. 902 p.
3. Scherban V. Yu., Krasnitsky S.M., Rezanov V.G. Mathematical Models in CAD. Selected sections and examples of application. K.: KNUTD, 2011. 220 p.
4. Scherban V.Yu., Volkov O.I., Shcherban Yu.Yu. CAD equipment and technological processes for light and textile industries. K.: Boomservice, 2004. 519 p.
5. Scherban V.Yu., Kalashnik V.Yu., Kolisko O.Z., Sholudko M.I. Investigation of the influence of the thread material and the anisotropy of friction on its tension and the shape of the axis. Herald of Khmelnytskyi National University. Technical sciences. 2015.Volume 223. Issue 2. p. 25–
6. Shcherban V.Y., Kolisko O.Z., Melnyk G.V., Sholudko M.I., Kalashnik V.Y. Computer systems design: software and algorithmic components. К. : Education of Ukraine, 2019. 902 p.
7. Scherban V. Yu., Kolisko O.Z., Sholudko M.I., Kalashnik V. Yu. Algorithmic, software and mathematical components of CAD in the fashion industry. К.: Education of Ukraine, 2017. 745 p.
8. Shcherban V., Melnyk G., Sholudko M., Kalashnyk V. Warp yarn tension during fabric formation. Fibres and Textiles. 2018. Volume 25. № P. 97–104.
9. Yakubitskaya I.A., Chugin V.V., Shcherban V.Yu. Differential equations of the relative motion of the filament element on the end sections of the coil of the winding drum. Technology of the textile industry. 1997. № P. 50–54.