Современные информационные технологии /2. Вычислительная техника и программирование

 

Д.т.н. Хачумов В.М.

Институт системного анализа Российской академии наук, Россия

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

 

Модель совмещения циклов создается в целях совершенствования расписаний управления потоками работ при оказании консультативной и стационарной помощи в лечебно-профилактических учреждениях и повышения  эффективности загрузки имеющихся исполнительных ресурсов (медицинских аппаратов, обслуживающих приборов, врачей) [1,2]. Пусть последовательность лечения производится в соответствии с некоторым медицинским технологическим процессом (МТП), содержащим  операций, среди которых могут быть одинаковые. Множество разных операций обозначим , при этом операция  в алгоритме выполняется  раз, где:  В простейшем случае МТП может быть представлен последовательностью операций, в которой результат i-ой операции служит входом для (i+1) -ой операции. Вход первой операции является входом МТП, а результат последней операции - его выходом. Тогда алгоритм можно представить в виде: .         Пусть имеется набор  исполнительных ресурсов (ИР)  типов, соответствующих операциям МТП. Каждого ресурса  j–го типа может быть несколько, т.е.:    МТП назовем отмеченным (ОМТП), если в алгоритме , кроме выполняемых операций, указаны закрепленные за ними ресурсы. ОМТП имеет следующий вид: . Запись  означает, что исполнительный ресурс с номером  из набора  выполняет операцию на k-ой фазе реализации МТП. В общем случае одному МТП может соответствовать некоторое множество ОМТП. Для организации процесса обслуживания необходимо указать момент начала выполнения МТП. В этом случае при выполнении некоторых условий МТП определяет расписание однократного выполнения медицинского процесса, показывающее шаг за шагом, какая операция за какой следует и на каком ИР выполняется.

Представляет интерес задача многократного выполнения МТП без прерываний. Такая ситуация соответствует случаю, когда на обслуживание поступает поток пациентов, каждый из которых проходит стандартную  процедуру осмотра и лечения. Периодические расписания наилучшим образом подходят для планирования работы, связанной с многократным выполнением процессов. Однократное выполнение ОЛА назовем его циклом. Пусть алгоритм выполняется многократно, причем начала циклов совпадают с моментами . При многократной обработке будем оставлять  неизменным  порядок закрепления ИР за фазами МТП, что является одним из необходимых требований обработки без прерываний. Указанное расписание назовем циклическим с периодом , если для всех его элементов выполняется  соотношение . Будем говорить, что для циклического расписания с периодом  имеет место совмещение вычислительных процессов, если хотя бы для одного элемента расписания выполняется , где - время (в тактах), необходимое для выполнения одного цикла МТП. Процесс совмещенной обработки может быть представлен, таким образом, совокупностью взаимодействующих однократных процессов, описываемых МТП. Качество расписания будем оценивать величиной среднего времени (в тактах), необходимого для получения одного результата  выполнения ОМТП.

         Процесс построения  расписания  для МТП может быть представлен в виде следующей схемы:

1. Генерация вариантов закрепления ИР за фазами выполнения МПТ (генерация вариантов ОМТП).

2. Построение для каждого ОМПТ периодического расписания с совмещением циклов обработки.

3. Выбор лучшего расписания.

         Будем  уделять  основное  внимание вопросам сокращения перебора на каждом из этапов и разработке новой общей схемы для оперативного планирования периодических расписаний без существенного снижения их качества. Формализуем постановку и решение задачи максимального совмещения циклов выполнения МТП. Для каждого ИР выпишем из заданного ОМТП порядковые номера (фазы) закрепленных за ними операций. Если  и  - две разные фазы закрепления ресурса, то величину  назовем сдвигом фазы. Таким  образом, для всех ИР i-го типа можно выписать множество сдвигов фаз , а всему варианту МТП поставить в соответствие множество . Введем далее  множество  такое, что  где , . Множество  определяет запрещенные, а  - разрешенные сдвиги совмещения циклов обработки периодического расписания. Информация о множествах , и длине локального алгоритма  служит формальной моделью ОМТП и является достаточной для построения допустимых периодических расписаний.

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

         С учетом введенного критерия задача нахождения оптимального варианта ОМТП сводится к отысканию такого пути на ярусном орграфе, что  Т.е. выбирается путь, для которого суммарное число разных элементов (сдвигов фаз) в множестве , взятых без повторения, является минимальным.

Рассмотрим поясняющий пример. Пусть задан набор {A,B,C}, в котором каждый элемент обозначает некоторую операцию МТП. Пусть также  заданы подмножества исполнительных ресурсов {A1,A2}, {B1,B2}, {C1,C2}. Различные варианты независимого закрепления ресурсов каждого типа приведены в таблице 1.

Таблица 1 − Таблица вариантов независимого закрепления ресурсов

 

Ресурсы типа C

HC (A*)

Ресурсы типа A

HA(A*)

Ресурсы типа B

HB(A*)

1

C1AABC2AC2ABBC2

{2,4,6}

CA1A2BCA2CA2BBC

{2,3,5}

CAAB1CACAB2B2C

{1}

2

C1AABC2AC1ABBC1

{4,6,10}

CA1A2BCA1CA2BBC

{2,4,6}

CAAB1CACAB2B1C

{6}

3

C1AABC1AC2ABBC1

{4,6,10}

CA1A1BCA2CA1BBC

{1,5,6}

CAAB1CACAB1B2C

{5}

4

C1AABC1AC1ABBC2

{2,4,6}

CA1A1BCA1CA2BBC

{1,3,4}

 

 

5

C1AABC1AC2ABBC2

{4}

CA1A1BCA2CA2BBC

{1,2}

 

 

6

C1AABC2AC2ABBC2

{6}

CA1A2BCA1CA2BBC

{4,5}

 

 

7

C1ABC2АC2ABBC1

{2,10}

CA1A2BCA2CA1BBC

{3,6}

 

 

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

,   .

Можно проверить, что лучшее по времени решение дает путь, которому соответствует  ОМТП:  C1A1A2B1C1A1C2A2B1B2C2.

Для выбранного ОМТП выполняется следующая диаграмма совмещения циклов (таблица 2).

Таблица 2 – Модель совмещения циклов МТП

C1

A1

A2

B1

C2

A1

C1

A2

B1

B2

C2

 

 

 

 

 

C1

A1

A2

B1

C2

A1

C1

A2

B1

B2

C2

 

 

 

 

 

C1

A1

A2

B1

C2

A1

C1

A2

B1

B2

C2

 

 

 

 

 

C1

A1

A2

B1

C2

A1

C1

A2

B1

B2

C2

 

 

 

 

 

C1

A1

A2

B1

C2

A1

C1

A2

B1

B2

C2

 

 

 

 

 

 

 

 

 

 

C1

A1

A2

B1

…

 

 

 

 

 

 

 

 

 

 

 

C1

A1

A2

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

 

При многократно продолжающемся процессе совмещения выделяем повторяющуюся последовательность разрешенных сдвигов (1,1,1,7), которая определяет детерминированное расписание обслуживания. При этом среднее время выполнения цикла в установившемся режиме . Диаграмма совмещения позволяет составить программу и алгоритм управления МТП.  Полученная модель может быть использована для построения конвейерных расписаний работы лечебных учреждений [1,2]. Работа выполнена при поддержке проекта РФФИ № 13-07-12162 офи_м «Исследование и разработка методов и алгоритмов синтеза медицинских технологических процессов на основе прецедентной информации».

Литература:

1.      Хачумов В.М. Модели конвейерного медицинского технологического процесса. – Искусственный интеллект и принятие решений, №3, 2009, с.25-32.

2.       Хачумов В.М., Погодин С.В. Моделирование работы лечебного учреждения  как системы массового обслуживания. - Искусственный интеллект и принятие решений, №1, 2010, с. 49-56.