ОБНАРУЖЕНИЕ ВОЗМОЖНЫХ КОНФЛИКТОВ ОТНОШЕНИЙ ПРИ РЕШЕНИИ ЗАДАЧ О ПАРОСОЧЕТАНИЯХ С ИСЧЕЗАЮЩИМИ ДУГАМИ

Данильченко Анна Александровна

ассистент кафедры Информатики и компьютерного моделирования Житомирского Государственного Технологического Университета, г. Житомир

E-mail: 

Введение

Назначение процедур в современных санаторных и лечебных учреждениях является сложным процессом, который должен учитывать большое количество факторов, основными из которых являются [1, 2]:

·перечень назначенных врачом процедур;

·время работы процедурного кабинета;

·пропускная способность процедурного кабинета (одну процедуру одновременно могут принимать несколько пациентов);

·продолжительность приема процедуры (для различных процедур длительность их приема разная);

·продолжительность времени технического перерыва процедурного кабинета;

·совместимость процедур (пациент не может одновременно принимать несколько процедур, но кроме этого, на расписание накладывается дополнительное ограничение — пациент не может принимать следующие процедуры ранее некоторого времени после принятия предыдущей, для каждой пары процедур значение времени совместимости может различаться).

Указанная конкретная ситуация может быть распространена на большое количество родственных задач составления оптимальных расписаний при наличии некоторого множества ограничений. Например, распределение по времени ограниченных ресурсов, назначения различных видов работ (операций, задач, процессов). При решении данного класса задач применяют различные методы комбинаторной оптимизации [5]. Однако наличие дополнительных ограничений существенно усложняет их решение.

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

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

Поэтому до начала решения задачи целесообразно анализировать исходные данные с целью выявления возможных несоответствий в них.

Основная часть

В статье [1] решена задача составления расписания прохождения процедур пациентами. Расписание назначенных пациенту процедур представлено двудольным графом , где X — множество вершин графа, соответствующих всем возможным сеансам приема процедур (согласно установленного графика работы соответствующего процедурного кабинета) ||X||=m; Y — множество вершин графа, соответствующих процедурам, назначенным пациентам, ||Y||=n (при этом каждая вершина множества Y имеет признак принадлежности к определенному пациенту); Е — множество ребер графа. Ребро (x_i, y_k)E, x_iX, y_kY, i=1...m, k=1...n в том случае, когда процедура y_k может быть назначена пациенту в промежуток времени x_i.

Известные ограничения по исходным данным заданы множеством отношений следствия С, таких, что . Эти ограничения учитывают, прежде всего, невозможность назначения одной и той же процедуры разным пациентам на одинаковое время (с учетом пропускной способности процедурного кабинета), а также взаимную совместимость процедур. Кроме того, можно при необходимости учесть и некоторую последовательность принятия процедур (например, некоторая процедура должна обязательно предшествовать заданному множеству других процедур) и т. д.

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

Очевидно, в данном случае размерность нашей задачи может быть существенно уменьшена за счет разбиения исходной задачи на две подзадачи и решения только одной из них.

Представим расписание назначенных пациенту процедур в виде двудольного графа  (рис. 1), где  — множество вершин графа, которые соответствуют процедурам 1 и 2 соответственно; . При этом . Множество дуг графа также может быть представлено двумя подмножествами дуг: , .

Рисунок 1. Построение двудольного графа (Пример 1).

Формализация приведенных выше ограничений сводится к тому, что для любой дуги подмножества Е₁ отношение следствия будет содержать все дуги подмножества Е₂ и наоборот. Также у каждой дуги отношение следствия может содержать некоторое множество дуг «своей» подгруппы.

Имеем следующие отношения следствия:

;

;

;

;

;

.                          (1)

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

Рассмотрим еще один пример (Пример 2) — пациенту назначена процедура «первичный осмотр», ранее которой ни одна из других процедур не может быть проведена.

Пусть всего было назначено три процедуры (рис. 2). При этом на процедуры 1 и 2 накладывается ограничение в 1 час интервала между ними, а Процедура 3 — «первичный осмотр» — исключает проведение любой другой процедуры. Ограничения совместимости с Процедурой 3 для процедур 1 и 2 не определены.

Рисунок 2. Построение двудольного графа (Пример 2).

То есть имеем такие отношения следствия:

;

;

;

;

;

.                          (2)

Понятно, что решение задачи является тривиальным.

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

В статье [8] автором предложена соответствующая рассматриваемой задаче модификация генетического алгоритма; в статье [9] — метода ветвей и границ.

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

Но заметим, что, в частности, для второго примера модифицированный метод ветвей и границ [9] найдет решение на первом шаге, а модифицированный генетический алгоритм [8] может вообще его не найти, поскольку функция приспособленности дуги  никогда не будет максимальной на анализируемой популяции.

Для непосредственно программной реализации анализа входных данных целесообразно привести табличное представление отношений следствия.

Для первого примера (отношение (1)) имеем:

                           (3)

Для второго примера (отношение (2)) имеем:

                 (4)

Для сравнения приведем задачу, решенную в [1] (Пример 3).

Двудольный граф (рис. 3) G=(X, Y, E) содержит множество вершин, соответствующих возможным сеансам приема процедур X={9.30—10.30; 11.00—12.00; 12.30—13.30; 9.30—10.00; 11.00—11.30; 12.30—13.00}, ||X||=6; множество вершин графа, соответствующих процедурам, назначенным пациентам Y={1₁; 2₁; 1₂}, ||Y||=3.

Рисунок 3. Построение двудольного графа (Пример 3).

Заданы ограничения:

·     назначение одной и той же процедуры разным пациентам на одинаковое время невозможно;

·     следующая процедура не может назначаться после первой раньше, чем через 1 час.

Ограничения определены множеством отношений следствия:

;

;

;

;

;

;

;

;

.                                                  (5)

Табличное представление отношений следствия будет иметь вид:

Как видно из приведенных данных, рассмотренные конфликтные ситуации в отношениях следствия локализуются строками с максимальным количеством (равным ) единиц.

Выводы

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

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

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

Список литературы:

1.Данильченко А.А., Ибрагим С.А. Организация вычислительного кластера ЖДТУ // Сборник научных трудов по материалам ІІІ Всеукраинская конференция молодых ученых “Информационные технологии в науке и технике” Черкассы, апрель 2002. — С. 272—275.

2.Данильченко А.М., Данильченко А.А., Ибрагим С.А. Решение задач расписаний на кластерных системах // Труды IV Междунар. науч.-практ. конф. “Современные информационные и электронные технологии” Одесса, май 2003. — С. 147—149.

3.Майника Э. Алгоритмы оптимизации в сетях и графах: Пер. с англ. — М.: Мир, 1981. — 323 с.

4.Ope О. Теория графов. — М.: Наука, Гл. ред. физ.-мат. лит., 1980. — 336 с.

5.Рыбников К.А. Введение в комбинаторный анализ. — М.: Изд-во МГУ, 1985. — 312 с.

6.Харари Ф. Теория графов: Пер. с англ. и предисл. В.П. Козырева / Под ред. Г.П. Гаврилова. — 2-е. изд. — М.: Едиториал УРСС, 2003. — 296 с.

7.Панішев А.В., Данильченко А.М., Данильченко А.А., «Задача про паросполучення зі «зникаючими» дугами» — Збірник наукових праць «Моделювання та інформаційні технології».— Київ: 2012 — В63 — С. 75—81.