Search academic texts

Information × Registration Number 2117U006234, Article popup.category Опубліковано, Стаття Title PARALLELING MODIFIED METHOD OF BRANCH AND BOUND TO SOLVE PROBLEM OF MATCHING CURVES FROM ENDANGERED OR THREATENED popup.author Данильченко А. О.Danylchenko A. popup.publication 30-11-2017 popup.source_user Журнал "Радіоелектроніка, інформатика, управління" (Національний університет "Запорізька політехніка") popup.source https://ric.zp.edu.ua/article/view/115531 popup.publisher National University "Zaporizhzhia Polytechnic" Description Актуальність. Розглянуто задачу складання розкладу проходження процедур пацієнтами санаторію, яка зведена до розширеної задачі пошуку максимального паросполучення в дводольному графі. Для поставленої задачі про паросполучення зі зникаючим дугами було розроблено оптимальний алгоритм її рішення на базі методу гілок і меж. Алгоритм враховує обмеження сумісності процедур. Проведено розрахунковий експеримент в основі якого лежить доказ доцільності розпаралелювання оптимального алгоритму розв’язання задачі складання розкладу прийому лікувальних процедур пацієнтами для прикладного використання його в санаторних закладах України.Мета роботи. Довести доцільність розпаралелювання оптимального алгоритму розв’язання задачі складання розкладу проходження процедур пацієнтами санаторію.Метод. Сформульована математична модель задачі про паросполучення зі зникаючим дугами. Обрані обчислювальні платформи різної конфігурації, що мають різні обчислювальні потужності: різну кількість ядер процесора, різний обсяг пам’яті, і т.д. Написано авторське програмне забезпечення для проведення експерименту. Програма складається з двох модулів: серверний модуль, який контролює процес виконання розрахунків і клієнтський модуль, який виконується на відокремлених ПЕОМ з метою обчислення паралельних операцій. Проведено обчислювальний експеримент по распараллеливанию оптимального алгоритму розв’язання задачі про паросполучення зі зникаючим дугами. Експеримент проводився на базі санаторію «Дениші». Обчислювальний експеримент проведений на серії випадкових умов задачі, що генеруються програмою. Проведено аналіз отриманих результатів шляхом порівняння часу рішення задачі про паросполучення зі зникаючим дугами оптимальним алгоритмом на різних обчислювальних платформах.Результати. Модифікований метод гілок та меж показує стабільність зменшення часу складання розкладу проходження процедур при збільшенні обчислювальних потужностей.Висновки. Прогнозований найменший час складання розкладу, отримано на обчислювальній платформі з максимальною кількістю задіяних ПЕОМ. Прогнозований час складання розкладу при використанні алгоритму розпаралелювання модифікації методу гілок і меж прямо пропорційно залежить від кількості вершин дводольного графа (що дорівнює сумі кількості процедур і кількості пацієнтів), кількості призначених процедур і обмежень. popup.nrat_date 2026-02-09 Close