Аналіз методів оптимізації розкладів у контексті відновлювальної терапії

Размещено на http://www.allbest.ru/

Аналіз методів оптимізації розкладів у контексті відновлювальної терапії

О.С. Ковалишин

Національний університет "Львівська політехніка", м. Львів, Україна

Проаналізовано існуючі способи вирішення задач багатокритеріальної оптимізації в контексті побудови розкладів, а саме: метод логічного програмування з обмеженнями, метод імітації відпалу, метод розфарбовування графу, метод імітаційного моделювання, метод генетичного алгоритму. Досліджено чинні методи побудови та оптимізації планів відновлювальної терапії пацієнтів медичних закладів. Окреслено переваги генетичних алгоритмів відносно інших методів та обґрунтовано доцільність їх використання в задачі багатокритеріальної оптимізації розкладу функціонування медичних установ. на підстаі проведеного дослідження побудовано модель представлення розкладу медичних закладів у вигляді, придатному для використання алгоритмом; визначено структуру хромосоми для задачі; розроблено методи побудови опорного розкладу для подальшої оптимізації з використанням скінченного автомата; наведено еволюційні оператори перетворення розкладу для збільшення його відповідності поставленим критеріям якості. Для оцінки прогресу процесу оптимізації запропоновано використати агрегований критерій, заснований на штрафах за порушення обмежень, накладених на розклад. Подано критерії зупинки роботи алгоритму за умови досягнення глобального оптимального рішення. Розроблено метод багатокритеріальної оптимізації розкладів функціонування медичних установ, заснований на використанні генетичних алгоритмів.

Ключові слова: лікувальні заклади; багатокритеріальна оптимізація; оптимізація розкладу; оптимізація планів відновлювальної терапії; еволюційні алгоритми; генетичні алгоритми.

Вступ. Відновлювальна терапія є актуальною для усіх верств населення будь-якого суспільства. Вона є ефективним методом лікування людей з такими вадами здоров'я, як: ураження опорно-рухового апарату та центральної і периферичної нервової системи; хвороби органів слуху та зору; захворювання внутрішніх органів, серцево-судинної системи тощо.

За даними Всесвітньої організації охорони здоров'я, реабілітаційних заходів у розвинених країнах потребують 20-25 % стаціонарних хворих і 40-45 % хворих, які лікуються в поліклініках. Постійний розвиток відновлювальної терапії сприяє підвищенню якості життя тяжкохворих та зменшенню бюджетних коштів, витрачених державою на утримання людей з обмеженими можливостями (Bezginov & Tregubov, 2005; Gladkov et al., 2006).

Для України особливого значення ця проблема набуває з огляду на постійне зростання частки інвалідів у загальній структурі населення, яка збільшилась від 3,0 % у 1994 р. до 5,7 % у 2009 р. Тому впродовж останніх років Верховна Рада України ухвалила низку законодавчих актів щодо розвитку системи реабілітації, в яких особливе місце відведено питанням щодо надання індивідуально орієнтованих реабілітаційних послуг. Їхнє успішне проведення значною залежить від рівня планування відновлюваної терапії (Glibovetc & MedvM, 2003; Lazarev, 2011).

Задачу побудови та оптимізації планів відновлювальної терапії не можна розглядати тільки в контексті єдиного пацієнта без урахування специфіки предметної галузі - власне медичного закладу. До уваги варто брати кількість всіх пацієнтів клініки, необхідність узгодження графіків використання медичного обладнання, наявність кваліфікованого медичного персоналу для прове-дення кожної конкретної процедури в певний момент часу, доступність відповідного устаткування тощо.

Фактично, для розв'язання цієї задачі необхідно побудувати повноцінний розклад функціонування медичного закладу, на який накладаються множини жорстких обмежень - умов, що потрібно обов'язково виконувати для забезпечення коректності розкладу, та м'яких - виконання яких є бажаним (Azadeh et al., 2015; Anderson et al., 2015; Vrugt et al., 2018).

Враховуючи велику кількість цих обмежень, а також збільшення напливу пацієнтів, ручне складання розкладів відновлювальної терапії стає неефективним і потребує автоматизації процесу (Rezaeiahari & Khasawneh, 2017; Wang, Chen & Xu, 2018).

Аналіз останніх публікацій. Для розв'язання задачі побудови розкладу медичних установ використовують такі методи: повного перебору, гілок та границь, логічного програмування з обмеженнями, розфарбування графу, імітації відпалу, імітаційного моделювання, ге-нетичного алгоритму тощо. Враховуючи належність зазначеної задачі до класу NP (не існує ефективного поліноміального алгоритму побудови розкладу), прийнятною альтернативою її розв'язання є використання ев-ристичних підходів (Peng, Qu & Shi, 2014).

Метод логічного програмування з обмеженнями. Побудову розкладу можна представити у вигляді задачі задоволення обмежень. Розв'язання її полягає у визна-ченні деякої множини змінних x1,..., xn . Область їх значень описує обмеження, яким повинні задовольняти змінні. Враховуючи це, необхідно знайти такі значення змінних, які б задовольняли всім заданим обмеженням одночасно. Внаслідок реалізації цього методу визначається множина значень кожної змінної, що не суперечить зазначеним обмеженням. Основна перевага цього методу полягає у зменшенні кількості варіантів пошуку. Це досягається завдяки, виключенню з розгляду неперспективних варіантів (Gorissen, Unkelbach & Bortfeld, 2016).

Метод імітації відпалу. Цей метод імітує фізичний процес нагрівання та наступного контрольованого охолодження субстанції. Він є одним із прикладів методів Монте-Карло. Під час пошуку оптимального результату допускається перехід із деякою ймовірністю у стан, що покращує значення цільової функції. оптимізація розклад відновлювальний терапія

У контексті задачі складання розкладу цей метод можна представити подальшим чином. Перед початком ітеративного оптимізаційного процесу генерується деякий початковий розклад X0, що задовольняє жорсткі обмеження, та інтерпретується як поточний розв'язок задачі X = X0. Також задається початкове високе значення температури Т0, деякий критерій зупинки роботи алгоритму та операція перетворення розкладу.

Процес оптимізації складається з таких етапів:

1. на підстаі введених операцій перетворення та поточного розв'язку генерується новий коректний розклад X , який дещо відрізняється від поточного.

2. Визначається зміна цільової функції Af = f (X) - f (X ). Якщо Af < 0 (розв'язок не погіршився), то новий варіант розкладу стає поточним (X = X ). Якщо Af > 0 (розв'язок погіршився), то новий розклад стає поточним тільки з ймовірністю p . Відповідно, з ймовірністю (1 - р) попередній розклад зберігається як поточний.

3. Виконується функція зміни поточної температури. Температура, і, відповідно, ймовірність прийняти поточний розклад із більшим значенням цільової функції зменшується на кожній ітерації.

4. Якщо не виконується критерій зупинки оптимізаційного процесу, то відбувається перехід на п. 1.

Метод розфарбування графу. Складання розкладу можна представити як процес розфарбовування графу - пошук мінімального числа кольорів, необхідних для розфарбовування вершин деякого графу так, щоб для кожної пари сусідніх вершин використовували різні кольори. Така задача є NP-повною. Для її розв'язання найчастіше використовують різні "жадібні" алгоритми.

Під час складання розкладу як задачі розфарбовування графу будується деякий граф, кожна вершина якого є запланованою активністю. У разі виникнення конфлікту між вершинами вони з'єднуються ребром, що еквівалентно забороно одночасне проведення цих активностей. Відповідно, складання розкладу представляють як процес мінімізації кількості кольорів, необхідних для розфарбовування графа. Кожен період проведення активностей відповідає конкретному кольору. Застосування цього підходу для розв'язку реальних задач, очевидно, малоефективне. Але задача розфарбовування графа в процесі складання розкладу може бути корисною у випадку її комбінації з іншими алгоритмами.

Метод імітаційного моделювання. Враховуючи №- повноту задачі, для її розв'язання застосовують імітацію роботи експерта, що складає плани відновлювальної терапії. У цьому випадку метод оперує безпосередньо зі списком пацієнтів та процедурами, які необхідно включити до розкладу.

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

1. Обирається процедура зі списку незапланованих. Вибір робиться внаслідок аналізу найбільш пріоритетних ресурсів клініки.

2. Для обраної процедури визначаються всі можливі варіанти розміщення в розкладі, які задовольняють жорстким обмеженням. Кожна альтернатива оцінюється за допомогою цільової функції та процедура розміщується в найкращій із знайдених позицій.

3. У разі суперечливої ситуації проводиться видалення конфліктуючих процедур із розкладу та їх внесення назад у список незапланованих.

Особливу увагу під час розроблення методу, заснованого на імітаційній моделі, приділяють евристичним правилам вибору процедури, визначенню найкращої для неї альтернативи, її розміщенню в розкладі та його оцінці. До позитивних сторін такого підходу можна віднести можливість докладного врахування специфіки задачі, що розв'язується. Проте варто зазначити, що навіть за незначних змін у процесах функціонування клініки доведеться вносити істотні зміни в метод. Оскільки алгоритм ґрунтується на діях, які виконує експерт під час складання розкладу, то існує можливість організувати діяльний діалог між користувачем і системою у процесі пошуку найкращого розкладу. Проте це справедливо тільки для відносно невеликих задач, оскільки в протилежному випадку значна залежність алгоритму від дій користувача може зробити такий діалог малоефективним.

Метод генетичного алгоритму. Генетичні алгоритми - стохастичні евристичні оптимізаційні методи, основну ідею яких взято з теорії еволюційного розвитку видів, та використання еволюційних механізмів для пошуку рішення. Основними концепціями теорії еволюції є спадковість та природний відбір. Ці ж механізми використовуються генетичними алгоритмами.

Першим кроком розробки генетичного алгоритму є кодування структури задачі у вигляді певного вектору значень ("хромосоми"), що буде розв'язком.

Наступним кроком є генерація деякої кількості початкових елементів ("початкової популяції"). У випадку задачі побудови та оптимізації розкладів необхідно розбудувати такі їх множини, які б задовольняли жорстким обмеженням, що накладаються предметною галуззю.

Для роботи алгоритму оптимізації потрібно розробити метод оцінювання розвитку в популяціях. Таким методом може бути вимога мінімізації цільової функції або, в термінах генетичних алгоритмів, фітнес-функції.?

Тут доцільно використати інтегральний показник оптимальності розкладу, заснований на штрафах за невдоволення поставлених до розв'язку вимог.

Перетворення розкладу здійснюється завдяки використанню еволюційних операторів мутації та кросоверу. У процесі їх реалізації також беруть до уваги жорсткі обмеження, наприклад: послідовність слідування процедур у планах лікування пацієнтів, наявність медичного обладнання тощо.

Для закінчення роботи алгоритму будується критерій зупинки. Таким критерієм може бути:

* досягнення глобального оптимального рішення;

* вичерпання числа ітерацій генетичного алгоритму;

* вичерпання часу роботи генетичного алгоритму.

Отже, розмістивши початкову популяцію у створене середовище та реалізувавши еволюційні процеси, отримують ітераційний метод пошуку оптимального рішення. На кожному його етапі виконуються такі дії:

1. Кожна особина поточної популяції оцінюється за допомогою фітнес-функції.

2. Кращі рішення копіюються в нову популяцію без змін.

3. на підстаі пропорційного відбору з поточної популяції вибираються хромосоми, які піддаються рекомбінації.

4. Якщо нова популяція сформована, то стара видаляється. Після цього переходимо до п. 5, а у протилежному випадку - до п. 3.

5. Якщо не виконується критерій зупинки оптимізаційного процесу, то відбувається перехід на п. 1.

Виклад основного матеріалу дослідження. Серед зазначених вище методів, які використовують для розв'язання задачі побудови розкладу медичних установ, найбільше переваг має метод генетичних алгоритмів. Ці переваги проявляються за умови розгляду основних їх відмінностей, порівняно з традиційними методами. За даними, ці основні відмінності проявляються у такому.

1. Наведені методи базуються на ітераційній техніці для покращення результатів. Протягом кожної ітерації здійснюється побудова більш оптимального розв'язку, ніж поточний. Якщо таке рішення знайдено, то його приймають за поточне і використовується в наступній ітерації. Г енетичний алгоритм використовує кілька точок пошукового простору одночасно, а не переходить від точки до точки, як це відбувається у традиційних методах. Це дає змогу подолати один з їхніх недоліків - небезпеку потрапляння в локальний екстремум цільової функції.

2. Генетичні алгоритми у процесі роботи не використовують ніякої додаткової інформації, що підвищує швидкість роботи. Винятком є множина допустимих значень параметрів і цільової функції в довільній точці.

3. Г енетичний алгоритм використовує як ймовірнісні правила для побудови нових розв'язків, так і детерміновані правила для переходу від одних розв'язків до інших. Одночасне використання елементів випадковості та детермінованості дає значно більший ефект, ніж роздільне. Зважаючи на ці переваги, ми запропонували використати метод генетичних алгоритмів для оптимізації розкладу клініки.

Представлення розкладу функціонування клініки Перед початком оптимізації необхідно сформувати представлення розкладу у вигляді, придатному для по-дальшого його оброблення методом генетичного алгоритму. Для цього кластеризуємо процедури за типами на підстаі необхідного обладнання, наявності медично

го персоналу, вимог до періоду проведення процедур, можливості об'єднання пацієнтів у групи тощо. Для кожного типу згрупованих процедур розіб'ємо період, охоплений розкладом, на часові інтервали, придатні для їх проведення (рис. 1).

Математично множину часових проміжків проведення процедур можна представити так:

де: - дата проведення процедури; .. - час проведення процедури; - максимально допустима кількість паралельних процедур.

Внаслідок графічної інтерпретації представлення розкладу (див. рис. 1) отримано тривимірний масив, характеристики якого відповідають за: часовий розподіл за числами місяця; розподіл за часом упродовж дня; можливістю проведення декількох або групових процедур в один і той самий часовий відрізок.

Наступним етапом процесу оптимізації розкладу клініки є кодування та формування структури хромосоми. Для вирішення питання щодо кодування хромосоми у вигляді числових або символьних значень не виправдовується через складність задачі та часові затрати на кодування декодування проміжних результатів. У цьому випадку доцільно у вигляді хромосоми представити множину процедур, з яких складається розклад.

Рис. 1. Представлення розкладу функціонування клініки у вигляді тривимірного масиву

Математично множину процедур розкладу можна представити так:

де: гр - дата та час проведення процедури; гр - медичний персонал, що проводить процедуру; г; - множина пацієнтів, для яких процедура проводиться; ге - множина обладнання, необхідного для проведення процедури; - загальна кількість медичного персоналу клініки; Ыр - загальна кількість пацієнтів клініки; Ые - загальна кількість медичного обладнання.

Графічно структуру хромосоми наводимо на рис. 2.

Рис. 2. Структура хромосоми задачі оптимізації розкладу клініки

Наступним етапом після формування структури хромосоми є ініціалізація початкової популяції для подальшої оптимізації. У цьому випадку на етапі ініціалізації початкової популяції необхідно побудувати множину опорних розкладів, що будуть відповідати жорстким обмеженням:

1) несуперечність розкладу - медичний персонал та пацієнти не можуть перебувати на двох процедурах одночасно;

2) послідовність процедур - їх необхідно проводити в порядку, визначеному індивідуальним планом лікування;

3) наявність обладнання та персоналу - не можна проводити процедури у випадку відсутності або часткового забезпечення устаткуванням чи лікарями.

Процес побудови розкладу доцільно представити у вигляді кінцевого автомату - абстракції, що використовується для описання способу зміни стану об'єкта залежно від досягнутого стану та інформації отриманої ззовні. Математичну модель апарата можна описати так:

де: X -- множина вхідних даних автомата; Y - множина вихідних даних автомата; 5 - множина допустимих станів автомата; fy - функція виходів автомата; Д - функція переходів з одного стану автомата в інший; д0 - початковий стан автомата.

Вхідними даними X автомата є набір процедур для включення в розклад, а на виході отримується множина процедур Y , включених у цей розклад.

Алгоритм роботи автомата побудови розкладу складається з шести етапів (множина станів буде мати вигляд 5 = S = {S0, S1, S2, S3, S4, S5} :

1 - отримання вхідних даних (перехід в Я0);

2 - вибір процедури для включення в розклад із вхідної множини (перехід в Я! ).

3 - пошук доступного устаткування, необхідного для про ведення процедури (перехід в Я2);

4 - пошук доступних часових проміжків для проведення процедури (перехід в Я3 );

5 - аналіз задоволення обмежень предметної галузі (перехід у Я4 );

6 - вибір часового проміжку та устаткування на підстав задоволення обмежень предметної галузі, запис процедури до розкладу та включення її до вихідної множини даних (перехід в Я5 ).

Умови переходів є булевими функціями (оскільки недопустимим є часткове задоволення обмежень предметної галузі тощо), що визначаються окремо для кожного стану.

Для роботи генетичного алгоритму необхідно визначити оператори перетворення розкладу, з яких здебільшого використовують схрещування та мутацію. Процедура схрещування у генетичному алгоритмі відбувається у такий спосіб: для двох обраних особин проводиться обмін частками генетичного коду між відповідними хромосомами.

Оператор мутації з деякою ймовірністю змінює значення декількох параметрів (генів) у хромосомі нової особини на інші, що входять у число допустимих значень цього гена.

У цьому випадку використовують такі оператори, що застосовуються з певною імовірністю на кожній ітерації оптимізаційного процесу:

1) зміна часу проведення процедури, що полягає в перенесенні певної процедури з одного часового проміжку на довільний інший доступний часовий проміжок упродовж того самого дня;

2) зміна дати проведення процедури полягає в перенесенні певної процедури з одного часового проміжку на довільний інший доступний часовий проміжок іншого дня;

3) обмін пацієнтів процедур полягає у взаємозаміні пацієнтів двох однакових процедур;

4) обмін медичного персоналу полягає у частковій взаємозаміні кваліфікованого персоналу, що проводить дві процедури одного типу.

Після досягнення прийнятних результатів оптиміза- ції зупинити роботу методу. Зупинка відбувається у випадку, якщо впродовж визначеної кількості поколінь оптимізації не відбувається покращення хромосоми з найвищим рівнем оцінки. Це означає, що застосування наведених вище операторів позитивно впливає на якість результуючого розкладу (чи взагалі спричиняє його погіршення). Іншими словами, зупинка алгоритму відбувається в момент досягнення екстремуму та в час збіжності значень фітнес-функції.

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

де: - поточне значення і -го критерію порушень; - максимальне можливе значення і-го критерію порушень; - мінімальне можливе значення і-го критерію порушень; [0,1].

Виділивши в такий спосіб множину критеріїв оптимізації, стає можливим згортання векторного критерію для переходу до однокритеріальної оптимізації, що можна зробити за допомогою використання засобів та методів нечіткої логіки.

Розроблений метод дає змогу провести оптимізацію розкладів відновлювальної терапії без відриву від середовища їх проведення - медичного закладу, з урахуванням вимог медичного процесу як жорсткі обмеження, а також побажань пацієнтів - м'які обмеження. Використання генетичного алгоритму дає можливість досягнути розв'язку, найбільш відповідного множині критеріїв оцінки. Висновки:

1. Одне із найголовніших питань відновлювальної терапії та лікування загалом є надання пацієнтам лікувальних закладів індивідуально орієнтованих реабілітаційних послуг. Ефективне їх проведення неможливе без удосконалення та оптимізації планів проведення та розкладів виконання процедур у лікувальних закладах.

2. Проблема побудови та оптимізації розкладів належить до класу КР-повних. Для таких категорій задач характерною є відсутність алгоритмів розв'язку за поліноміальний час залежно від розмірності. Одним із найефективніших підходів для оптимізації розкладів медичних закладів, що дає можливість уникнути локальних екстремумів та отримати множину глобальних оптимальних рішень, є використання генетичних алгоритмів.

3. Проведений аналіз та розроблений метод дають змогу провести багатокритеріальну оцінку та оптимізацію якості планів відновлювальної терапії та розкладів медичних установ загалом, що забезпечує підвищення ін.

4. дивідуалізації надаваних послуг та, як наслідок, сприяє істотному підвищенню ефективності діяльності закладів медичного спрямування.

Перелік використаних джерел

1. Anderson, K., Zheng, B., Yoon, S. W., & Khasawneh, M. T. (2015). An analysis of overlapping appointment scheduling model in an outpatient clinic. Operations Research for Health Care, 4, 5-14. https://doi.org/10.1016/i.orhc.2014.12.0Q1

2. Azadeh, A., Baghersad, M., Farahani, M. H., & Zarrin, M. (2015). Se-mi-online patient scheduling in pathology laboratories. Artificial Intelligence in Medicine, 64(3), 217-226. https://doi.org/10.1016/i.artmed.2015.05.001

3. Bezginov, N. A., & Tregubov, S. Yu. (2005). Obzor sushchestvu- iushchikh metodov sostavleniia raspisanii. Informatcionnye tekhnolo- gii iprogrammirovanie. Mezhvuzovskii sbornikstatei. [In Russian].

4. Gladkov, L. A., Kureichik, V. M., & Kureichik, V. V. (2006). Gene- ticheskie algoritmy (2nd ed.). FIZMATLIT. [In Russian].

5. Glibovetc, H. N., & Medvіd, S. A. (2003). Genetichiskie agoritmy i ikh ispolzovanie dlia resheniia zadachi sostavleniia raspisaniia. Ki- bernetika i sisttemnyi analiz, 12, 95-108. [In Russian].

6. Gorissen, B. L., Unkelbach, J., & Bortfeld, T. R. (2016). Mathemati-cal Optimization of Treatment Schedules. International Journal of Radiation Oncology*Biology*Physics, 96(1), 6-8. https://doi.org/10.1016/nirobp.2016.04.Q12 Lazarev, A. A. (2011). Teoriia raspisanii. Zadachi i algoritmy. Moscow: MGU. [In Russian].

7. Peng, Y., Qu, X., & Shi, J. (2014). A hybrid simulation and genetic algorithm approach to determine the optimal scheduling templates for open access clinics admitting walk-in patients. Computers & Industrial Engineering, 72, 282-296. https://doi.org/10.1016/i.cie.2014.03.026 Rezaeiahari, M., & Khasawneh, M. T. (2017). An optimization model for scheduling patients in destination medical centers. Operations Research for Health Care, 15, 68-81.

8. https://doi.org/10.1016/i.orhc.2017.09.004 Vrugt, N. V., Luen-English, S., Bastiaansen, W., Kleinluchtenbeld, S., Lardinois, W., Pots, M.,... Boucherie, R. (2018). Integrated scheduling of tasks and gynecologists to improve patient appointment scheduling; a case study. Operations Research for Health Care, 16, 10-19. https://doi.org/10.1016/i.orhc.2017.11.002 Wang, J., Chen, Y., & Xu, M. (2018). Optimization and approximation methods for dynamic appointment scheduling with patient choices. Computers & Operations Research, 92, 65-76.

9. https://doi.org/10.1016/i.cor.2017.12.009

О.С. Ковалишин. Анализ методов оптимизации расписания в контексте восстановительной терапии

Проанализированы существующие способы решения задач многокритериальной оптимизации в контексте построения расписаний, а именно: метод логического программирования с ограничениями, метод имитации отжига, метод раскрашивания графа, метод имитационного моделирования, метод генетического алгоритма. Исследованы действующие методы построения и оптимизации планов восстановительной терапии пациентов медицинских учреждений. Определены преимущества генетических алгоритмов относительно других методов и обоснована целесообразность их использования в задаче многокритериальной оптимизации расписания функционирования медицинских заведений. На основе проведенного исследования построена модель представления расписания медицинских учреждений в виде, пригодном для использования алгоритмом, определена структура хромосомы для задачи, разработаны методы построения опорного расписания для дальнейшей оптимизации с использованием конечного автомата, приведены эволюционные операторы преобразования расписания с целью увеличения его соответствия поставленным критериям качества. Для оценки прогресса процесса оптимизации предложено использовать агрегированный критерий, который основан на штрафах за нарушение ограничений, наложенных на расписание. Поданы критерии остановки работы алгоритма при условии достижения глобального оптимального решения. Разработан метод многокритериальной оптимизации расписаний функционирования медицинских учреждений, который основан на использовании генетических алгоритмов.

Ключевые слова: лечебные учреждения; многокритериальная оптимизация; оптимизация расписания; оптимизация планов восстановительной терапии; эволюционные алгоритмы; генетические алгоритмы.

O.S. Kovalyshyn. Schedule optimisation methods analysis in terms of rehabilitation therapy

Renewal therapy is relevant to all segments of the population of any society. It is an effective method for treating people with such disorders of the body as a lesion of the musculoskeletal system and the central and peripheral nervous system; hearing and vision diseases; diseases of the internal organs, cardiovascular system, etc. In this regard, in the process of rehabilitation, special attention is given to the issue of individually oriented rehabilitation services, since at present plans for rehabilitation therapy are very limited to the interests of patients themselves, which directly affects the quality of treatment. In order to solve the problem, it is necessary to consider the set of restrictions imposed on the process - the need to consolidate schedules of the medical equipment usage, the availability of qualified medical personnel for each specific procedure at a certain time, the availability of off-the-shelf equipment, etc. To solve this problem it is necessary to construct a full functioning schedule of the medical institution, which is superimposed on the set of hard restrictions - the conditions that must necessarily be fulfilled to ensure the correctness of the schedule, and soft requirements - the implementation of which is desirable - the actual interests of patients. Regarding other methods, genetic algorithms have several advantages, such as: simultaneous use of several points of the search space, the use of probabilistic and deterministic rules for the transition between solutions, the absence of the need to use an external extra data and operations. Therefore, it is proposed to use genetic algorithms to solve the problem of multi-criteria optimization of rehabilitation therapy plans. To assess the progress of optimization, a mechanism for evaluating alternatives based on fines for breaching the schedule restrictions has been constructed. For the organization of the optimization process, the mechanisms of population development - crossover and mutation operators have been developed. Method stoppage occurs if, for a certain number of generations of optimization, there is no improvement in the chromosome with the highest level of evaluation. The conducted analysis and the developed method allow providing multi-criteria optimization of plans for restorative therapy in the context of the schedules of medical institutions. Taking into account the interests of patients as restrictions makes it possible to increase the individualization of the services provided and, consequently, contributes to the improvement of the efficiency of the activities of medical institutions.

Keywords: medical institutions; multicriteria optimization; schedule optimization; optimization of plans for restorative therapy; evolutionary algorithms; genetic algorithms.

Размещено на Allbest.ru