WWW.PDF.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Разные материалы
 

«УДК 519.854.2 ОПТИМАЛЬНОЕ ПЛАНИРОВАНИЕ ОПЕРАЦИЙ ГОСПИТАЛЯ М.Я. Ковалев Объединенный институт проблем информатики НАН Беларуси Беларусь, ...»

5185

УДК 519.854.2

ОПТИМАЛЬНОЕ ПЛАНИРОВАНИЕ ОПЕРАЦИЙ

ГОСПИТАЛЯ

М.Я. Ковалев

Объединенный институт проблем информатики НАН Беларуси

Беларусь, 220012, Минск, Сурганова ул., 6

E-mail: kovalyov_my@newman.bas-net.by

Э. Козан

Технологический университет Брисбена

Австралия, School of Mathematical Sciences, QUT, GPO Box 2434, Brisbane Qld 4001

E-mail: e.kozan@qut.edu.au

Ключевые слова: теория расписаний, оптимальное планирование, операции госпиталя Аннотация: Изучается следующая задача. Имеются пациенты, каждый из которых ожидает операцию, которая должна быть проведена в одной из операционных комнат госпиталя в одном из заданных рабочих интервалов времени с нефиксированным временем завершения. В качестве рабочих интервалов могут рассматриваться смены или полусмены. Каждый рабочий интервал связан со стоимостью единицы времени увеличения момента его завершения. Каждый пациент связан с моментом готовности, ранее которого операция не может быть начата, директивным сроком, до которого она должна быть завершена, весом, длительностью операции и множеством недопустимых рабочих интервалов. Моменты готовности и директивные сроки согласованы так, что более ранний момент готовности соответствует более раннему директивному сроку. Задача состоит 1) в определении значений увеличения моментов завершения рабочих интервалов так, что суммарная стоимость их увеличения не превосходит заданного порога, 2) в выборе подмножества пациентов и 3) в допустимом назначении выбранных пациентов в операционные комнаты в рабочих интервалах так, что их суммарных вес максимален. Исследуются два случая определенных и неопределенных длительностей операций. Неопределенный случай моделируется дискретно-непрерывными сценариями, и для принятия решения о назначении используется оптимизация в худшем случае.

1. Введение Имеется n пациентов множетва N, каждый из которых ожидает операцию, которая должна быть проведена в одном из нескольких операционных комнат госпиталя в заданных рабочих интервалах времени [At, Bt ], где At Bt, t = 1,..., T. Каждый момент Bt завершения интервала может быть увеличен, и единица времени увеличения стоит ct. Значение увеличения Bt не должно превосходить t. Суммарная стоимость увеличения всех рабочих интервалов не должна превосходить заданного порога C.

XII ВСЕРОССИЙСКОЕ СОВЕЩАНИЕ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ

ВСПУ-2014 Москва 16-19 июня 2014 г Каждый рабочий интервал связан с операционной комнатой. Эта связь делает различными рабочие интервалы с одинаковыми моментами начала и завершения.

Рабочие интервалы различных операционных комнат могут пересекаться или совпадать, а рабочие интервалы одной и той же операционной комнаты не могут пересекаться. В практической ситуации, мотивирующей наши исследования, имеется много рабочих интервалов с одинаковыми моментами начала и завершения, связанными с различными операционными комнатами. Для того, чтобы обрабатывать эту специфику более эффективно, предполагается, что множество {1,..., T } индексов рабочих интервалов разбито на подмножества Sv, |Sv | 1, v = 1,..., V, V T, такие, что каждое подмножество Sv содержит индексы интервалов с одинаковыми моментами начала и завершения, а различные подмножества Sv содержат индексы непересекающихся интервалов. Мы предполагаем, что индексы интервалов одного и того же множества Sv являются последовательными.

Каждый пациент j связан с моментом готовности rj, ранее которого его операция не может начаться, с директивным сроком dj, до которого его операция должна завершиться, с весом wj, отражающим относительную важность его операции или доход от нее, с длительностью pj его операции, и с множеством Mj {1,..., T } индексов недопустимых рабочих интервалов, в которых операция j не может быть проведена, поскольку в соответствующих операционных комнатах отсутствуют необходимые для нее ресурсы. Моменты готовности и директивные сроки согласованы таким образом, что более ранние моменты готовности соответствуют более ранним директивным срокам. Кроме того, rj {At, Bt | t = 1,..., T } и rj {At, Bt | t = 1,..., T } для всех j N. Все числовые данные являются неотрицательными действительными числами.

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

Рассматриваются два варианта этой задачи, а именно, детерминированный и неопределенный. В детерминированном варианте все числовые параметры являются заданными числами. В неопределенном варианте длительности операций являются неопределенными. Их неопределенность предлагается моделировать с помощью дискретно-непрерывных сценариев и использовать для принятия оптимального решения подход оптимизации в худшем случае. Этот подход борьбы с неопределенностью широко используется в комбинаторной оптимизации и оптимальном планировании, см., например, Коувелис и Ю [6], Айсси и др. [2], Рой [8], Айсси и др. [1], Перейра и Авербах [7] и Долгий и Ковалев [4].

Рассмотрим вектор длительностей операций p = (p1,..., pn ). Обозначим через S множество сценариев для значений этого вектора. Таким образом, p S. Пусть (i) (i) S = S1 · · ·Ss, где Si = {p | pj [aj, bj ], j = 1,..., n}, i = 1,..., s. Здесь s - количество типов сценариев. Если s = 1, то сценарии являются интервальными, в которых каждая длительность pj может принять любое действительное значение в заданных границах независимо от других длительностей. Интервальные сценарии моделируют ситуацию, в которой границы длительностей операций могут быть надежно определеXII ВСЕРОССИЙСКОЕ СОВЕЩАНИЕ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ ВСПУ-2014 Москва 16-19 июня 2014 г (i) (i) ны. Если aj = bj, j = 1,..., n, сценарии являются дискретными, в которых вектор p длительностей операций принадлежит заданному множеству сценариев мощности s.

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

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

2. Практическая ситуация и ее сведение к задаче MaxWeight Рассмотрим следующую практическую задачу. Госпиталь имеет список пациентов, каждый из которых ожидает проведение операции. Этот список обновляется каждое утро. Операции этого списка заранее разбиты на группы, например, на группы g = 1,..., G0, такие, что операции одной и той же группы g имеют одинаковый момент готовности r(g) and одинаковый директивный срок d(g). Момент готовности и директивный срок являются результатом соглашения между пациентом и госпиталем, которое принимает во внимание дату заявки на операцию, состояние здоровья пациента, необходимые предварительные процедуры и другие факторы. Госпиталь использует политику диспетчеризации, которая предполагает, что моменты готовности и директивные сроки операций согласованы так, что r(1) · · · r(G ) и d(1) · · · d(G ). В большинстве случаев r(g) является началом дня и d(g) является концом того же дня. Операции проводятся в допустимых рабочих интервалах операционных комнат. Параметры операций одной и той же группы, отличные от моментов готовности и директивных сроков, например, длительности операций и множества недопустимых рабочих интервалов, могут быть различными. Предполагается, что время операции включает время необходимых предварительных и послеоперационных процедур, которые зависят от операции и не зависят от операционной комнаты.

Госпиталь заинтересован в максимизации количества проведенных операций.

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

Необходимо принять решение о допустимых значениях расширения рабочих интервалов такое, что суммарная стоимость расширения не превосходит заданного порога C, о выборе операций из первых групп 1,..., G, G G0, списка, и о расписании

–  –  –

3. Детерминированная задача Введем действительнозначные переменные zt, t = 1,..., T, такие, что zt является значением увеличения момента Bt рабочего интервала [At, Bt ], t = 1,..., T. Введем

–  –  –

0-1 переменные xjt, j = 1,..., n, t = 1,..., T, такие, что T xjt 1. Предположим, t=1 что xjt = 1 тогда и только тогда, когда пациент j назначен в рабочий интервал [At, Bt ], t = 1,..., T. Введем 0-1 переменные yj такие, что yj = 1 тогда и только тогда, когда операция j выбрана для выполнения в каком-либо рабочем интервале, j = 1,..., n. Обозначим T -размерный вектор с координатами zt как z и nT матрицу с элементами xjt как x. Обозначим y = (y1,..., yn ).

Для каждой операции j вычислим множество Ij индексов рабочих интервалов, в которых эта операция на может быть выполнена, поскольку они недопустимы либо противоречат моменту готовности или директивному сроку операции:

–  –  –

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

1. Aissi H., Aloulou M.A., Kovalyov M.Y. Minimizing the number of late jobs on a single machine under due date uncertainty // Journal of Scheduling. 2011. Vol. 14, No. 4. P. 351-360.

2. Aissi H., Bazgan C., Vanderpooten D. Complexity of the min-max and min-max regret assignment problem // Operations Research Letters. 2005. Vol. 33. P. 634-640.

3. Cardoen B. Demeulemeester E. Belien J. Operating room planning and scheduling: A literature review // European Journal of Operational Research. 2010. Vol. 201, No. 3. P. 921-932.

4. Dolgui A., Kovalev S. Min-max and min-max (relative) regret approaches to representatives selection problem // 4OR. 2012. Vol. 10, No. 2. P. 181-192.

5. Hans E., Wullink G., van Houdenhoven M., Kazemier G. Robust surgery loading // European Journal of Operational Research. 2008. Vol. 185. P. 1038-1050.

6. Kouvelis P., Yu G. Robust discrete optimization and its applications. Boston: Kluwer Academic Publishers, 1997.

7. Pereira J., Averbakh I. Exact and heuristic algorithms for the interval data robust assignment problem // Computers and Operations Research. 2011. Vol. 38, No. 8. P. 1153-1163.

8. Roy B. Robustness in operational research and decision aiding: A multi-faceted issue // European Journal of Operations Research. 2010. Vol. 200. P. 629-638.

–  –  –



Похожие работы:

«Информатика, вычислительная техника и инженерное образование. – 2013. № 2 (13) Раздел II. Автоматизация проектирования УДК 658.512 Кулаков А.А. РАЗМЕЩЕНИЕ СТАНДАРТНЫХ ЯЧЕЕК СБИС ТРЕХМЕРНОЙ КОМПОНОВКИ МЕТОДОМ ИМИТАЦИИ ОТЖИГА В работе рассмотрена проб...»

«Сметанин Ю.Г.1, Ульянов М.В.2 Вычислительный центр им. А.А. Дородницына, Российская академия наук, г. Москва, д.ф.-м.н., главный научный сотрудник, smetanin.iury2011@yandex.ru Институт проблем управления им. В.А. Трапезни...»

«РОССИЙСКАЯ АКАДЕМИЯ НАУК ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР при поддержке РОССИЙСКОГО ФОНДА ФУНДАМЕНТАЛЬНЫХ ИССЛЕДОВАНИЙ МАТЕМАТИЧЕСКИЕ МЕТОДЫ РАСПОЗНАВАНИЯ ОБРАЗОВ (ММРО-11) Доклады 11-й Всероссийской конференции Москва Оргкомитет Председатель: Журавлев Юрий Иванович, академик РАН Зам. председателя: Лахно Виктор Дмитриевич, д.ф.-м.н. Дюкова Еле...»

«Э. М. БРАНДМАН ГЛОБАЛИЗАЦИЯ И ИНФОРМАЦИОННАЯ БЕЗОПАСНОСТЬ ОБЩЕСТВА Глобальная информатизация и новые информационные технологии открывают небывалые возможности во всех сферах человеческой деятельности, порождают новые проблемы, св...»

«Московский Государственный Университет им. М.В. Ломоносова Факультет Вычислительной Математики и Кибернетики Кафедра Математических Методов Прогнозирования Метод статистической верификации регрессионных мо...»

«Министерство образования Республики Беларусь Учреждение образования «Белорусский государственный университет информатики и радиоэлектроники» Кафедра информатики О.И. Костюкова ИССЛЕДОВАНИЕ ОПЕРАЦИЙ Учебное пособие для студентов специальности 31 03 04 «Инфо...»

«Учебно – методический комплекс “Охрана труда” 1. Учебная программа, для Белорусского государственного университета по всем специальностям факультета прикладной математики и информатики.2. Примерный тематический план.3. Программа курса “Охрана труда” для студентов 5-ого курса ФПМИ.4. Содержание лекционного...»

«Программа по информатике разработана в соответствии с требованиями федерального государственного образовательного стандарта начального общего образования (далее – Стандарт), а также основной образовательной программой начального общего образования (далее – ООП). ПЛАНИРУЕМЫЕ ПРЕДМЕТНЫЕ РЕЗУЛЬТА...»

«Второй (заключительный) этап академического соревнования Олимпиады школьников «Шаг в будущее» по общеобразовательному предмету «Информатика» 10 класс, февраль, 2016 г. Вариант № 2. Задание 1 (12 ба...»

«236 УПРАВЛЕНИЕ, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И ИНФОРМАТИКА УДК 519.21 А.Г. Буймов, Б.А. Буймов Вероятностная модель эффекта повторений в обучении Разрабатывается вероятностная модель принципа повторений и выводится формула обобщенной функции забывания, сформированной в результате произвольного чи...»





















 
2017 www.pdf.knigi-x.ru - «Бесплатная электронная библиотека - разные матриалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.