Розпаралелювання модифікованого методу гілок та меж для розв’язання задачі про паросполучення зі зникаючими дугами

Abstract

UK: Актуальність. Розглянуто задачу складання розкладу проходження процедур пацієнтами санаторію, яка зведена до розширеної задачі пошуку максимального паросполучення в дводольному графі. Для поставленої задачі про паросполучення зі зникаючим дугами було розроблено оптимальний алгоритм її рішення на базі методу гілок і меж. Алгоритм враховує обмеження сумісності процедур. Проведено розрахунковий експеримент в основі якого лежить доказ доцільності розпаралелювання оптимального алгоритму розв’язання задачі складання розкладу прийому лікувальних процедур пацієнтами для прикладного використання його в санаторних закладах України. Мета роботи. Довести доцільність розпаралелювання оптимального алгоритму розв’язання задачі складання розкладу проходження процедур пацієнтами санаторію. Метод. Сформульована математична модель задачі про паросполучення зі зникаючим дугами. Обрані обчислювальні платформи різної конфігурації, що мають різні обчислювальні потужності: різну кількість ядер процесора, різний обсяг пам’яті, і т.д. Написано авторське програмне забезпечення для проведення експерименту. Програма складається з двох модулів: серверний модуль, який контролює процес виконання розрахунків і клієнтський модуль, який виконується на відокремлених ПЕОМ з метою обчислення паралельних операцій. Проведено обчислювальний експеримент по распараллеливанию оптимального алгоритму розв’язання задачі про паросполучення зі зникаючим дугами. Експеримент проводився на базі санаторію «Дениші». Обчислювальний експеримент проведений на серії випадкових умов задачі, що генеруються програмою. Проведено аналіз отриманих результатів шляхом порівняння часу рішення задачі про паросполучення зі зникаючим дугами оптимальним алгоритмом на різних обчислювальних платформах. Результати. Модифікований метод гілок та меж показує стабільність зменшення часу складання розкладу проходження процедур при збільшенні обчислювальних потужностей. Висновки. Прогнозований найменший час складання розкладу, отримано на обчислювальній платформі з максимальною кількістю задіяних ПЕОМ. Прогнозований час складання розкладу при використанні алгоритму розпаралелювання модифікації методу гілок і меж прямо пропорційно залежить від кількості вершин дводольного графа (що дорівнює сумі кількості процедур і кількості пацієнтів), кількості призначених процедур і обмежень. EN: Context. The problem of scheduling the passage of procedures of sanatorium patients, which is reduced to the problem of finding an extended maximum matching in a bipartite graph. For the task of matchings with disappearing arcs developed an optimal algorithm of its solution based on branch and bound method. The algorithm takes into account the limits of compatibility procedures. Spend the current experiment based on the evidence of the feasibility of algorithm parallelization for solving the problem of optimal scheduling patients receiving therapeutic treatments applied to its use in the health institutions of Ukraine. Objective. To prove the feasibility of the algorithm parallelization optimal solution of our problem. Method. A mathematical model of the problem of matchings with disappearing arcs. Selected computing platforms of different configurations with a variety of computing power: a different number of processor cores, different amounts of memory, etc. Written copyright software for the experiment. The program consists of two modules: a server module, which controls the process of performing calculations and client module that runs on the PC are separated for the purpose of calculating the parallel operations. The experiment was conducted on the basis of sanatorium “Denyshi”. Computational experiments for optimal algorithm parallelization for solving the problem of matchings with disappearing arcs. Computer experiment carried out on a series of random conditions of the problem generated by the program. The analysis of the results by comparing the time solving the problem of matchings with disappearing arcs optimal algorithm on different computing platforms. Results. The modified method of branches and borders shows the stability of reducing the time of scheduling transmission procedures with increasing computing power. Conclusions. Estimated minimum time scheduling, received at the computer platform with the maximum number of PCs involved. Estimated time scheduling algorithm parallelization by using modifications of the branch and bound directly proportional to the number of vertices of a bipartite graph (which is equal to the sum of the number of procedures and the number of patients), the number of assigned procedures and restrictions.