Метаэвристические алгоритмы формирования оптимального графика прохождения лечебно-оздоровительных процедур

Аннотация

Задорожная Е.Г., Савкова Е.О. Метаэвристические алгоритмы формирования оптимального графика прохождения лечебно-оздоровительных процедур. В данной работе описаны особенности составления данного вида графика и разработана динамическая модель процесса. В качестве методов решение приведены такие метаэвристические алгоритмы, как генетический и муравьиный.

Ключевые слова: оптимизация, график, динамическая модель, сеть Петри, генетический алгоритм, муравьиный алгоритм.

Введение

Главным фактором успешной работы лечебно-оздоровительных учреждений на сегодняшний день, является повышение качества и скорости предоставления услуг Все решение должны приниматься оперативно и быть оптимальными. Задачи оперативно-календарного планирования решались неоднократно и различными методами, однако, достаточно сложно определить качество получаемых расписаний. К тому же, в рамках данной предметной области, процесс формирования оптимального графика прохождения лечебно-оздоровительных процедур специфических особенностей, не характерных другим отраслям производства. Данный факт объясняет актуальность разработки оптимального алгоритма прохождения процедур.

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

Постановка задачи

Для формирования графика прохождения лечебно-оздоровительных процедур необходимо иметь определённый набор входных данных. Санаторно-курортный комплекс рассчитан на определённое количество пациентов, представленное множеством P = {p_i}, где i ∈ [1, n]. Лечащий врач пациента, в соответствии с его диагнозом, назначает перечень обязательных процедур, исходя из множества всех возможных: Proc = {proc_j}, где j ∈ [1, m], а также периодичность сеансов и их количество. Пациент также имеет право на посещение дополнительных процедур общего назначения, согласовав это с лечащим врачом.

Процедурные кабинеты работают по графику и имеют определенное количество оборудования, представленное множеством Eq = {eq_z}, где z ∈ [1, f]. При этом каждое оборудование предназначено для определённой процедуры или вида процедур. Проведение каждой процедуры занимает какой-то промежуток времени. Соответственно, предполагается множество временных интервалов T = {t_k}, где k ∈ [1, h].

Исходя из изложенной ранее информации, можно сделать вывод, что проведение процедуры proc_j для пациента p_i характеризуется оборудованием eq_z, на котором будет предоставлена процедура, а также временным интервалом t_k.

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

1. По срокам предоставления процедур: T_ф ≤ T_пр,
   где T_пр - время пребывания пациента p_i в санатории;
   T_ф - фактическое время проведения процедур proc_j пациенту p_i.
2. По количеству проведения процедур : N_пл = N_ф,
   где N_пл - количество запланированных процедур proc_j;
   Т_ф - фактическое количество проведенных процедур proc_j.
3. По времени непрерывной работы оборудования: N_пр * T_пр ≤ T_нпр,
   где N_пр - количество проведенных процедур proc_j за день, наоборудовании eq_z;
   T_пр - время проведения (длительность) процедуры proc_j;
   T_нпр - время непрерывной работы оборудования eq_z.
4. По количеству процедур за день: N_д ≤ N_доп,
   где N_д - количество процедур, назначенных пациенту p_i за день;
   N_доп - допустимое количество процедур за день для пациента p_i.
5. По времени простоя оборудования: 0 ≤ ΔT_{ожид об} ≤ T_прост,
   ΔT_{ожид об} - разница во времени между окончанием процедуры proc_j и началом следующей на оборудовании eq_z;
   T_прост - допустимое время простоя оборудования eq_z.
6. По временному разбросу между процедурами: 0 ≤ ΔT_{ожид п} ≤ T_св,
   ΔT_{ожид п} - разница во времени между окончанием процедуры процедуры proc_j и началом следующей, назначенной пациенту p_i;
   T_св - свободное время между процедурами p_i.

Таким образом, задача сводится к тому, чтобы разработать алгоритм, который удовлетворяет всем сформулированным ранее условиям и ограничениям.

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

Для построения динамической модели процесса прохождения лечебно-оздоровительных процедур была выбрана сеть Петри. Это математический аппарат для моделирования динамических дискретных систем. Процесс функционирования сети Петри может быть наглядно представлен графом достижимых маркировок. Они позволяют определить общую структуру и принципы работы системы. Сети-Петри рассматриваются как вспомогательный инструмент анализа систем. Проблемы анализа указывают на изъяны в проекте. [1]

Сеть Петри характеризуется входной и выходной функцией, а так множеством позиций (мест) и множеством переходов. Переход срабатывает, когда метка из входной позиции перехода перемещается в выходную позицию. Запуски могут осуществляться до тех пор, пока существует хотя бы один разрешенный переход. Когда ни одного разрешенного перехода не остается, то выполнение прекращается [2].

В рамках решаемой проблемы сети Петри являются удобным инструментом, для создания высокоуровневой модели работы процесса. На рис. 1 представлена динамическая модель процесса прохождения лечебно-оздоровительных процедур в виде сети Петри второго рода, с иерархической композицией объектов. Имея информацию о назначенной процедуре необходимо понимать, на каком типе оборудования её можно проводить (выбор кабинета). Далее следует выбрать свободное оборудование в данный момент времени. Для наглядности оборудование отмечено в виде закрашенного круга. Это связано с тем, что оборудованием в данный момент времени может пользоваться лишь один клиент. После предоставления процедуры клиенту, он возвращается к моменту выбора кабинета, для следующей процедуры. Это будет длится до тех пор, пока перечень процедур не закончится. В случае, если нет свободного оборудования, клиент дожидается его освобождения.

Анализ методов решения

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

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

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

В виде муравья в данном случае можно рассматривать пациента, тогда вершинами графа будет выступать оборудование. Каждая вершина содержит информацию о процедурах, которые могут проводиться на данном типе оборудования, и массив промежутков времени. В основе муравьиного алгоритма лежит поведение муравьиной колонии – маркировка более удачных путей большим количеством феромона. Когда муравей находит подходящее назначенной процедуре оборудование, то занимает интервал времени на её проведение. Затем, он возвращается в начало, оставляя за собой след из феромона.

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

Решение задачи на основе ГП можно представить следующей последовательностью действий:

1. Установка параметров эволюции. Инициализация начальной популяции для одного пациента. Особь представлена в виде двух хромосом, где информация 1-ой - оборудование, а 2-ой – сеансы (промежутки времени) [5]. В обеих хромосомах одинаковое количество генов равное pi, равное количеству назначенных процедур пациенту. Следовательно i гену 1-ой хромосомы соответствует оборудование (из числа допустимых), выбранное для предоставления процедуры, а i гену 2-ой хромосомы - время её проведения (рис. 2).


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

2. Оценка особей, входящих в популяцию, отбор наиболее приспособленных особей (селекция), имеющих более предпочтительные значения функции пригодности по сравнению с остальными особями.
3. Создание потомков выбранных пар родителей – выполнение оператор кроссинговера. Для каждой пары отобранных особей случайным образом выбираются позиции гена G1 и G2 и производится обмен участками генетического кода между соответствующими хромосомами родительских особей. Если такие гены уже встречаются в потомке, то они пропускаются, а оставшуюся часть потомка дополняют генами первого родителя.
4. Мутация новых особей. Мутация играет достаточно важную роль в работе генетического алгоритма: вносит дополнительное разнообразие в текущую популяцию и тем самым расширяет пространство поиска оптимального решения. В результате мутации z-му 1-ой хромосомы будет присвоен номер оборудования, из допустимого набора оборудований, предназначенных для проведения данной процедуры, а для k-го гена 2-ой хромосомы будет выбрано любое свободное значение временного интервала для данного оборудования. [5]
5. Расширение популяции новыми порожденными особями. Оператор отбора выполняет функции фильтрующего инструмента, который выделяет в составе популяции особи, имеющие низкое значение функции пригодности. Выделенные найденные слабые особи удаляются из популяции, происходит сокращение расширенной популяции до исходного размера.
6. Обнаружена сходимость или достигнуто максимальное количество итераций. Если критерий останова алгоритма выполнен, то выбор лучшей особи в конечной популяции – результат работы алгоритма. Иначе переход на шаг 2.
7. Результирующую особь необходимо проверить на существование. Последовательность прохождения процедур проверяем на ранее разработанной динамической модели. Для хранения информации о загрузке оборудования необходима матрица plan_ij, где i - это перечень всего имеющегося оборудования, а j - интервалы времени. Полученные результаты заносим в матрицу.

Вывод

В рамках данной работы был проведён анализ работы процесса формирования графика прохождения процедур на основе динамической модели. Также, были проанализированы основные алгоритмы составления расписаний: муравьиный и генетический.

Муравьиный алгоритмы, не смотря на свою динамичность, использование памяти колоний и сходимости к оптимальному решению имеет ряд недостатков. Графовое представление данной задачи не является оптимальным. Результаты работы методы сильно зависят от начальных параметров поиска.

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

Список использованной литературы

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. И.С. Конькова Использование генетического алгоритма в задаче оптимизации расписания вуза // Вестник ТвГТУ, 2012г., 128 (Вып. 22). стр. 26-31
4. В.А. Светличная Использование алгоритмов муравьиных колоний при решении задач оптимизации календарного планирования / Светличная В.А., Червинская Н.В., Хаустова Д.А. // ДонНТУ, г. Донецк.
5. Ю.С. Кабальнов Композиционный генетический алгоритм составления расписания учебных занятий /Ю.С. Кабальнов, Л.И. Шехтман, Г.Ф. Низамова, Н.А. Земченкова // Вестник УГАТУ / Научные статьи и доклады / Информационные технологии - Уфа: УГАТУ, 2006 г. - Том 7, № 2 (15). - с. 99–107.