ЦЕЛОЧИСЛЕННАЯ ЛИНЕЙНАЯ МОДЕЛЬ РАСПРЕДЕЛЕНИЯ ПАЦИЕНТОВ ПО КАБИНЕТАМ И ВРЕМЕННЫМ СЛОТАМ ДЛЯ СНИЖЕНИЯ ВРЕМЕНИ ОЖИДАНИЯ

​INTEGER LINEAR MODEL FOR ASSIGNING PATIENTS TO ROOMS AND TIME SLOTS TO REDUCE WAITING TIME

Uteuliev Nietbay Uteulievich

Doctor of Physical and Mathematical Sciences, Professor, Head of the Department of Mathematical Modeling Nukus State Technical University,

Uzbekistan, Nukus

Sagidullaev Nursultan Ibadullaevich

PhD student, Tashkent University of Information Technologies, assistant teacher of the Department of Software Engineering, Nukus State Technical University,

Uzbekistan, Nukus

АННОТАЦИЯ

Предлагается целочисленная линейная модель распределения пациентов по кабинетам и временным слотам для снижения времени ожидания в амбулаторном звене. В модели учитываются интервалы доступности пациентов, пропускная способность кабинетов, ограничения совместимости по врачу или оборудованию и приоритет обращения. Критерием оптимальности является минимум суммарного взвешенного ожидания. На модельном примере с 12 пациентами, 3 кабинетами и 8 слотами по 15 минут получено сокращение среднего времени ожидания с 17,5 до 6,25 мин и суммарного взвешенного ожидания с 390 до 90 мин относительно базового правила FCFS. Модель пригодна как для анализа качества расписания, так и для последующей интеграции в прикладные медицинские информационные системы.

ABSTRACT

The paper proposes an integer linear model for assigning patients to rooms and time slots in order to reduce waiting time in outpatient care. The model considers patient availability windows, room capacities, compatibility constraints related to physicians or equipment, and patient priority. The optimization criterion is the minimum total weighted waiting time. On a test instance with 12 patients, 3 rooms, and 8 fifteen-minute slots, the average waiting time was reduced from 17.5 to 6.25 minutes and the total weighted waiting time from 390 to 90 minutes compared with an FCFS rule. The model is suitable both for formal schedule quality analysis and for later integration into practical medical information systems.

Ключевые слова: математическое моделирование; расписание приема; пациенты; временные слоты; кабинеты; целочисленное программирование.

Keywords: mathematical modeling; appointment scheduling; patients; time slots; rooms; integer programming.

Введение

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

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

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

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

Пусть P - множество пациентов, R - множество кабинетов, T = {0, 1, 2, ..., |T|-1} - множество временных слотов рабочего дня. Для каждого пациента p задаются: ранний допустимый слот , поздний допустимый слот , длительность обслуживания , приоритет  и множество допустимых назначений, определяемое параметром . В базовом варианте рассматривается случай , то есть один прием занимает один слот.

Необходимо выбрать для каждого пациента ровно одну пару «кабинет - временной слот» так, чтобы не превысить пропускную способность кабинетов и минимизировать суммарное ожидание. Если пациент приходит в момент a_p, а запись производится на слот t, то его ожидание составляет , где  - продолжительность слота в минутах.

Таблица 1.

Основные параметры постановки

Математическая модель

Введем бинарную переменную , равную 1, если пациент p назначен в кабинет r на слот t. Тогда математическая модель записывается следующим образом.

                                                                   (1)

                              (2)

                    (3)

          (4)

            (5)

Ограничение (2) обеспечивает единственность назначения каждого пациента. Ограничение (3) контролирует загрузку кабинетов по слотам. Ограничение (4) исключает недопустимые назначения, связанные с отсутствием врача, оборудования или требуемой специализации. Целевая функция (5) минимизирует суммарное взвешенное ожидание, поэтому при прочих равных условиях более срочные пациенты получают более ранние слоты.

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

Вычислительный эксперимент

Для иллюстрации работы модели рассмотрен пример с 12 пациентами, 3 кабинетами и 8 слотами по 15 минут. Пациенты различаются по приоритету и множеству допустимых кабинетов: часть обращений может быть направлена в альтернативный кабинет, тогда как часть жестко связана с конкретным ресурсом. В качестве базового алгоритма использовано правило FCFS, при котором запись формируется последовательно без глобальной переоценки последствий для всего дня.

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

Таблица 2.

Сравнение результатов для FCFS и ILP

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

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

Таблица 3.

Фрагмент сравнения ожидания по отдельным пациентам

Заключение

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

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

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

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

1. Apergi L.A., Baras J.S., Golden B.L., Wood K.E. An optimization model for multi-appointment scheduling in an outpatient cardiology setting // Operations Research for Health Care. 2020. Vol. 26. Art. 100267.
2. Cayirli T., Veral E. Outpatient scheduling in health care: A review of literature // Production and Operations Management. 2003. Vol. 12, no. 4. P. 519-549.
3. Gupta D., Denton B. Appointment scheduling in health care: Challenges and opportunities // IIE Transactions. 2008. Vol. 40, no. 9. P. 800-819.
4. Reihaneh M., Ansari S., Farhadi F. Patient appointment scheduling at hemodialysis centers: An exact branch and price approach // European Journal of Operational Research. 2023. Vol. 309, no. 1. P. 35-52.
5. Bekker R., Bharti B., Lan L., Mandjes M. A queueing-based approach for integrated routing and appointment scheduling // European Journal of Operational Research. 2024. Vol. 318, no. 2. P. 534-548.