Русский   English
   

Реферат за темою випускної роботи

Зміст

Вступ

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

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

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

1. Актуальність теми

Графік проходження лікувально-оздоровчих процедур повинен враховувати велику кількість обмежень, пов'язаних з предметною областю. У першу чергу повинні бути дотримані норми діагностичних і лікувально-реабілітаційних послуг (процедур). Необхідно дотримуватися послідовності проведення процедур, призначених лікарем, а також правильно розподіляти навантаження на обладнання. Через безліч обмежень і специфічних особливостей, не властивих іншим галузям, складання розкладу проходження лікувально-оздоровчих процедур вручну є дуже трудомісткою і витратною за часом роботою. А автоматизація даної задачі дозволить досягти оптимального рішення.

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

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

2. Мета і задачі дослідження

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

Для досягнення поставленої мети необхідно вирішити такі задачі, які будуть виконані в розділах магістерської роботи:

  1. Дослідити існуючі методи і алгоритми формування розкладів.
  2. Виконати формалізацію завдання формування оптимального графіка із застосуванням модифікованого генетичного алгоритму.
  3. Створити програмне забезпечення формування оптимального графіка проходження процедур на основі розробленого алгоритму.

Об'єкт дослідження: методи теорії розкладів.

Предмет дослідження: складання оптимального розкладу із застосуванням модифікованого генетичного алгоритму.

3. Наукова новизна і практична цінність

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

Розроблена динамічна модель процесу проходження лікувально-оздоровчих процедур, представлена у вигляді мережі Петрі [1].

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

4. Математична постановка задачі

Для формування графіка проходження лікувально-оздоровчих процедур необхідно мати певний набір вхідних даних. Санаторно-курортний комплекс розрахований на певну кількість пацієнтів, представлену безліччю P = {pі}, де i ∈ [1, n]. Лікар пацієнта, згідно з його діагнозом, призначає перелік обов'язкових процедур, виходячи з безлічі всіх можливих: Proc = {procj}, де j ∈ [1, m], а також періодичність сеансів та їх кількість. Пацієнт також має право на відвідування додаткових процедур загального призначення, погодивши це з лікарем.

Процедурні кабінети працюють за графіком і мають певну кількість обладнання, представлене безліччю Eq = {eqz}, де z ∈ [1, f]. При цьому кожне обладнання призначене для певної процедури або виду процедур. Тому обладнання eqz(eqznum, eqztype) характеризується номером eqznum і типом проведених процедур eqztype. Проведення кожної процедури займає якийсь проміжок часу. Відповідно, передбачається безліч часових інтервалів T = {tk}, де k ∈ [1, h]. Кожен часовий інтервал характеризується двома параметрами tk(tkdate,tktime), де tkdate – дата проведення лікувально-оздоровчої процедури (номер дня), tktime – час (номер часового інтервалу протягом дня) [3].

Виходячи з викладеної раніше інформації, можна зробити висновок, що проведення процедури procj для пацієнта pі характеризується обладнанням eqz, на якому буде надана процедура, а також часовим інтервалом tk.

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

  1. За термінами надання процедур: Tф ≤ Tпр,
    де Tпр - час перебування пацієнта pі в санаторії;
    Tф - фактичний час проведення процедур procj пацієнту pі.
  2. За кількістю проведення процедур : Nпл = Nф,
    де Nпл - кількість запланованих процедур procj;
    Тф - фактична кількість проведених процедур procj.
  3. За час безперервної роботи обладнання: Nпр * Tпр ≤ Tнр,
    де Nпр - кількість проведених процедур procj за день, на обладнанні eqz;
    Tпр - час проведення (тривалість) процедури procj;
    Tнр - час безперервної роботи обладнання eqz.
  4. За кількістю процедур за день: Nд ≤ Nдоп,
    де Nд - кількість процедур, призначених пацієнту pі за день;
    Nдоп - допустима кількість процедур за день для пацієнта pі.
  5. За часом простою обладнання: 0 ≤ ΔTожид об ≤ Tпрост,
    ΔTожид об - різниця в часі між закінченням процедури procj і початком наступної на обладнанні eqz;
    Tпрост - допустимий час простою обладнання eqz.
  6. За часовим розкидом між процедурами: 0 ≤ ΔTожид п ≤ Tсв,
    ΔTожид п - різниця в часі між закінченням процедури procj і початком наступної, призначеної пацієнту pі;
    Tсв - вільний час між процедурами pі.

Математичне вираження іншої групи обмежень, які також впливають на алгоритм складання розкладу:

  1. Відсутність накладок на роботу обладнання: ∀ (eqz, tk) ∃! (pі, procj),
    означає, що для кожної впорядкованої двійки елементів обладнання і часовий проміжок існує або єдина двійка пацієнт і процедура, що означає проведення процедури procj для пацієнта pі на обладнанні eqz під час інтервалу часу tk, або відсутність призначення.
  2. Відповідність типу обладнання проведеної процедури: ∀(pі, procj) ∃ eqz, where procjtype ∈ eqztype,
    означає, що для кожного призначення процедури procj пацієнту pі треба вибирати таке обладнання, щоб тип процедури procjtype відповідав типу процедур, що проводяться на даному обладнанні eqztype.

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

Матриця зайнятості обладнення

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

Цільова функція

де Kp – значення критерію втрати якості для однієї з призначених процедур пацієнту. При цьому Kp обчислюється за формулою:

Формула критерію втрати якості

де koefq - значення коефіцієнта штрафу за невиконання q-го приватного критерію, cі - оцінка, що визначає ступінь невиконання q-го приватного критерію, eqz - обладнання, tk - часовий інтервал.

Таким чином, завдання зводиться до того, щоб розробити алгоритм, який задовольняє всім сформульованим раніше умовам і обмеженням [3].

5. Динамічна модель процесу

Для побудови динамічної моделі процесу проходження лікувально-оздоровчих процедур була обрана мережа Петрі. Це математичний апарат для моделювання дискретних динамічних систем. Процес функціонування мережі Петрі може бути наочно представлений графом досяжних маркувань. Вони дозволяють визначити загальну структуру та принципи роботи системи. Мережі Петрі розглядаються як допоміжний інструмент аналізу систем. Проблеми аналізу вказують на вади в проекті [1].

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

Динамическая модель процесса

Рисунок 1 – Динамічна модель процесу

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

6. Аналіз методів рішення

Існують наступні методи вирішення задачі календарного планування: математичне програмування, комбінаторні методи, статистичні методи і евристичні методи.

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

Основою для розробки відповідного заданим вимогам алгоритму формування графіка проходження лікувально-оздоровчих процедур можуть стати метаэвристики, які добре себе показали при вирішенні оптимізаційних, комбінаторних, а також інших видів завдань. Алгоритм метаэвристик заснований на випадковому пошуку можливих рішень задачі, оптимальних або близьких до оптимальних, поки не буде виконана умова, чи досягнуто задане число ітерацій [5].

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

Мурашиний алгоритм - алгоритм для знаходження наближених рішень задачі комівояжера, а також вирішення аналогічних завдань пошуку маршрутів на графах [6].

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

Генетичний алгоритм - це евристичний алгоритм пошуку шляхом послідовного підбору, комбінування і варіації шуканих параметрів з використанням механізмів, що нагадують біологічну еволюцію [7].

Рішення задачі на основі ГА можна представити такою послідовністю дій:

  1. Установка параметрів еволюції. Ініціалізація початкової популяції для одного пацієнта. Особина представлена у вигляді двох хромосом, де інформація 1-oї - обладнання, а 2-ої – сеанси (проміжки часу) [3].
    У запропонованому генетичному алгоритмі не потрібне кодування генів хромосом у вигляді нулів і одиниць, як це прийнято в існуючих генетичних алгоритмах. Гени приймають цілочислові значення, які кодують номери обладнання, тимчасові інтервали.
    В обох хромосомах однакова кількість генів рівна pі, рівне кількості призначених процедур пацієнту. Отже, i гену 1-ої хромосоми відповідає обладнання (з числа допустимих), вибране для надання процедури, а i гену 2-ої хромосоми - час її проведення (рис. 3).
    2. Структура особини

    Рисунок 3 – Структура особини

  2. Оцінка особин, що входять до популяції, відбір найбільш пристосованих особин (селекція), мають кращі значення функції придатності порівняно з іншими особинами.
    Оператор відбору є найважливішим чинником, що впливає на ефективність генетичного алгоритму, оскільки невдалий вибір методу селекції може призвести до звуження області пошуку та до втрати найбільш пристосованих особин популяції. Для запобігання втрати кращих особин в якості методу відбору пропонується використовувати метод, турнірного відбору, доповнений принципом елітизму. З попередньої популяції вибирається L окремих особин (число L визначено з самого початку, і має фіксоване числове значення), що мають максимальне значення функції придатності (функцією придатності в даному випадку є цільова функція (10), описана в математичній постановці задачі) [8].
  3. Створення нащадків вибраних пар батьків – виконання оператору кросинговеру. Для кожної пари відібраних особин випадковим чином вибираються позиції гена G1 і G2 і проводиться обмін ділянками генетичного коду між відповідними хромосомами батьківських особин. Якщо такі гени вже зустрічаються в нащадка, то вони пропускаються, а решту нащадка доповнюють генами першого батька [3].
  4. Мутація нових особин. Мутація відіграє досить важливу роль у роботі генетичного алгоритму: вносить додаткову різноманітність у поточну популяцію і тим самим розширює простір пошуку оптимального рішення. В результаті мутації n-го 1-ої хромосоми буде присвоєно z -ий номер обладнання, з допустимого набору обладнань, призначених для проведення даної процедури, а для n-го гена 2-ої хромосоми буде вибрано k-е вільне значення часового інтервалу для даного обладнання [8].
  5. Перевірка значень функції конфліктів. Якщо цей ген не дорівнює нулю, значить в хромосомі або однаковим часовим інтервалам відповідають різні процедури, або одному обладнанню відповідає різні процедури, такий розклад містить конфлікт, який обов'язково повинен бути дозволений. У тому випадку слід замінити номер обладнання або часового інтервалу.
    Ген «конфліктів» дозволяє скоротити час проведення обчислювального експерименту на порядок, тобто він прискорює процес збіжності алгоритму та отримання оптимального рішення [8].
  6. Розширення популяції новими породженими особинами. Оператор відбору виконує функції фільтруючого інструменту, який виділяє у складі популяції особини, що мають низьке значення функції придатності. Виділені знайдені слабкі особини видаляються з популяції, відбувається скорочення розширеної популяції до початкового розміру.
  7. Виявлена збіжність чи досягнуто максимальна кількість ітерацій. Якщо критерій зупинки алгоритму виконано, то вибір кращої особини в кінцевій популяції – результат роботи алгоритму. Інакше перехід на крок 2 [3].
  8. Результуючу особину необхідно перевірити на існування. Послідовність проходження процедур перевіряємо на раніше розробленій динамічній моделі. Для зберігання інформації про завантаження обладнання необхідно занести інформацію про нові призначення в матрицю зайнятості.

Висновки

На даному етапі виконання магістерської роботи був проведений аналіз процесу формування графіка проходження лікувально-оздоровчих процедур на основі динамічної моделі. Сформульована математична постановка поставленої задачі. Також, були проаналізовані основні алгоритми складання розкладів: мурашиний та генетичний.

Мурашиний алгоритми, не дивлячись на свою динамічність, використання пам'яті колоній і збіжності до оптимального рішення має ряд недоліків. Графове подання даної задачі не є оптимальним. Результати роботи методу сильно залежать від початкових параметрів пошуку. [9]

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

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

На момент написання реферату, магістерська робота не завершена. Остаточне завершення планується в травні 2018 року. Повний текст роботи та матеріали по темі можуть бути отримані у магістранта або його наукового керівника не раніше зазначеної дати.

Перелік джерел

  1. Tadao Murata Petri Nets: Properties, Analysis and Applications // Department of Electrical Engineering and Computer Science, University of Illinois, Chicago, IL 60680, USA.
  2. Branimir Sigl Solving Timetable Scheduling Problem by Using Genetic Algorithms / Branimir Sigl, Marin Golub, Vedran Mornar // Faculty of Electrical Engineering and Computing, University of Zagreb Unska 3, Zagreb, Croatia.
  3. Ю.С. Кабальнов Композиционный генетический алгоритм составления расписания учебных занятий /Ю.С. Кабальнов, Л.И. Шехтман, Г.Ф. Низамова, Н.А. Земченкова // Вестник УГАТУ / Научные статьи и доклады / Информационные технологии - Уфа: УГАТУ, 2006 г. - Том 7, № 2 (15). - с. 99–107.
  4. К.С. Мышенков Метод решения задачи календарного планирования ремонтов технологического оборудования предприятия с использованием генетического алгоритма / К.С. Мышенков, А.Ю. Романов // Наука и образование / Электронное научно-техническое издание - Москва: ФГБОУ ВПО "МГТУ им. Н.Э. Баумана", 2011г.
  5. А.С. Аничкин Современные модели и методы теории расписаний / А. С. Аничкин, В. А. Семенов // Труды Института системного программирования РАН - Москва,2014 г. - Том 26, выпуск 3.
  6. В.А. Светличная Использование алгоритмов муравьиных колоний при решении задач оптимизации календарного планирования / Светличная В.А., Червинская Н.В., Хаустова Д.А. // ДонНТУ, г. Донецк.
  7. А.Б. Сидорин Методы автоматизации составления расписания занятий Часть 2. Эвристические методы оптимизации / А.Б. Сидорин, Л.В. Ликучева, А. М. Дворянкин // Известия ВолгГТУ / Актуальные проблемы управления, вычислительной техники и информатики в технических системах - Волгоград, 2009г. - № 12 (60) с. 120-123.
  8. И.Ф. Астахова Составление расписания учебных занятий на основе генетического алгоритма /И.Ф. Астахова, А.М. Фирас //Вестник ВГУ / Системный анализ и информационные технологии – Воронеж: ВГУ, 2013г., - № 2, с. 93-99.
  9. Т.В. Панченко Генетические алгоритмы: Учебно-методическое пособие / под ред. Ю.Ю. Тарасевича. - Астрахань: АГУ, 2007. - 87 с.
  10. А.А. Лазарев Теория расписаний. Задачи и алгоритмы /А.А. Лазарев, Е.Р. Гафаров - М.: Московский государственный университет им. М.В. Ломоносова (МГУ), 2011. — 222 с.
  11. Е.Г. Задорожная Метаэвристические алгоритмы формирования оптимального графика прохождения лечебно-оздоровительных процедур / Е.Г. Задорожная, Е.О. Савкова //Информатика, управляющие системы, математическое и компьютерное моделирование (ИУСМКМ – 2017) / Материалы VIII международной научно-технической конференции - Донецк: ДонНТУ, 2017г. - с. 270-275.