Статья описывает алгоритм автоматизированного построения расписаний, использованный при разработке специализированной информационной системы. Он основан на взвешенной SPT модели и дополнен идеями построения расписаний для многопроцессорных работ. (SPT = Shortest — processing — time sequencing — упорядочение по минимуму длительностей работ). В статье описываются условия, в которых необходимо создавать расписание, и алгоритм, позволяющий выполнить эти условия.
Ключевые слова: теория расписаний, информационные системы, алгоритмы, SPT модель
Целью нашей работы является создание медицинской информационной системы, позволяющего систематизировать текущий рабочий процесс психотерапевтического центра для упрощения оформления и обслуживания клиентов. Важной особенностью данной разработки является автоматизация построения расписаний с возможностью его дальнейшей корректировки. В данной статье описывается алгоритм, позволяющий получить расписание работы сотрудников медицинского центра, удовлетворяющее входным критериям
Описание рабочего процесса.
На текущий момент в центре работают сотрудники с различными профессиональными обязанностями. В течение рабочего дня у сотрудников происходят события:
− индивидуальный прием пациента;
− групповая терапия (групповой прием);
− собрания, совещания, планерки и т. д.
События третьего типа, как правило, назначаются в фиксированное, редко изменяемое время. Для событий первого и второго типов каждый месяц строится расписание, которое зависит от различных нормативов, а также, к примеру, фактического участия сотрудника в рабочем процессе в данном месяце.
Индивидуальный прием — это обычный прием пациента «врач-пациент». Групповой прием сложнее. Его можно описать, как отношение «врачи-пациенты». Основная идея заключается в том, что проводить групповой прием могут одновременно один или сразу два сотрудника. Поэтому при составлении индивидуальных расписаний сотрудников необходимо постоянно контролировать их согласованность. Также все другие события расписания не имеют «содержимого» на момент построения (не указывается пациент, для которого проходит прием) и поэтому между ними нет различий, а групповые приемы известны заранее, поэтому при их добавлении в расписание им приходится уделять большое внимание.
Описанные особенности приводят к тому, что специалисту по расписанию требуется несколько часов для построения расписания работы центра вручную. В этой работе используется идея применения алгоритмов теории расписаний для автоматизации их построения.
Основные понятия теории расписаний.
Определение: «Теория расписаний (ТР) — это раздел исследования операций, в котором строятся и анализируются математические модели календарного планирования (т. е. упорядочивания во времени) различных целенаправленных действий с учетом целевой функции и различных ограничений» [2].
Определение: Работой называется некоторое действие, которое необходимо обслужить. Работы состоят из операций — элементарных нераздельных частей. В силу того, что событие в расписании сотрудника рассматривается как неделимое, то термины операции и работы для этой задачи эквивалентны.
Рассматриваемый здесь пример можно определить, как детерминированную задачу упорядочивания календарного планирования с суммарными критериями оптимизации. Детерминированной называется задача теории расписаний, в которой все начальные данные поступают одновременно, перед решением задачи.
В качестве суммарного критерия применим суммарную взвешенную длительность прохождения работы в системе.
Обозначим 
— длительность выполнения работы i; 
— аналогично, но [i] — индекс после упорядочения;
— длительность ожидания начала работы. Тогда 
— длительность прохождения работы i в системе.
Суммарная длительность прохождения работ в системе 
Если в системе определить вес работы (
), обозначающий приоритетность одной работы перед остальными, то можно определить суммарную взвешенную длительность прохождения работы:
Выбранная математическая модель называется SPT (Shortest — processing — time sequencing) — упорядочением по минимуму длительностей работ [1]. Для решения данной задачи эта модель дополняется учетом веса работы — условной единицы, обозначающей приоритет работы над остальными.
Теорема[1]: Минимальное значение суммарной взвешенной длительности прохождения (1) в системе достигается при расписании, для которого
.
Графически этот метод представлен на рис. 1. Каждый прямоугольник — работа, а его ширина — длительность, высота — вес. Суммарная взвешенная длительность является суммой площадей прямоугольников и площади под ними, поэтому для минимизации F необходимо упорядочить работы в порядке уменьшения модуля угла вектора, лежащего на диагонали прямоугольника, к горизонтальной оси. Коэффициент угла равен 
.
Рис. 1. Геометрическое представление
Для решения проблемы групповых занятий используем теорию, описанную Brucker’ом [4]. Для решения мультипроцессорных задач (т. е. задач, требующих одновременного выполнения на нескольких процессорах) он вводит следующую модификацию начальных данных.
Пусть в системе с m процессорами задано n мультипроцессорных задач 
. Сопоставим задаче i множество 
процессоров, необходимых для её выполнения. Это множество определяет тип задачи i. Выделим 
типов задач и сгруппируем все задачи по этим типам [4]. Здесь под типом задачи понимается характеристика взаимно однозначная структуре порождающего множества процессоров. Тип может быть порожден как отдельным сотрудником, так и парой сотрудников.
В итоге получился набор «сущностей» (множеств, порождающих типы). Для этих «сущностей» нет требования на одновременное выполнение задачи. Есть только требования предшествования вида: групповой прием, исполняемый составной «сущностью», должен стоять после (или до) первичного приема, исполняемого одним из сотрудников, состоящим в этой «сущности». Можно использовать ту же теорию, что и в классической задаче по множеству независимых исполнителей с ограничением на последовательность выполнения.
Описание алгоритма построения расписания сотрудников.
Опишем алгоритм составления шаблона расписания на одну неделю.
Входными параметрами для алгоритма являются:
− таблица нагрузок сотрудника на неделю по всем видам события расписания, кроме групповых приемов (данные указываются на примере одного события, для остальных событий этого типа данные аналогичны);
− данные по групповым приемам с указанием ведущих и необходимых нагрузок на неделю (данные указываются для каждой группы);
− данные о весе событий расписания.
Предполагается, что суммарная длительность работ не превышает ограничений длительности рабочего времени. Для упорядочивания применяется взвешенная SPT модель, описанная выше.
На первом этапе создаются «сущности» − пары сотрудников. Создание расписания для них сложнее, чем для отдельных сотрудников, поэтому начнем с них.
Для каждой пары сотрудников упорядочим групповые приемы и добавим их в личное расписание обоих сотрудников с учетом сохранения условия, указанного в теореме. Причем начинать стоит с групповых приемов с наибольшим коэффициентом , чтобы не возникало конфликтов. На данном этапе строится только порядок групповых приемов, без указания времени начала. В конце этого этапа проводится разбиение всего списка на дни недели.
На втором этапе для разбитых на дни групповых приемов устанавливается время начала с учетом согласованности расписаний связанных сотрудников. Свободное время заполняется оставшимися событиями других типов. При необходимости, для соблюдения правила упорядочивания, можно изменить начало групповых приемов.
Далее каждому событию назначается доступный кабинет.
В итоге получаем расписание, не всегда оптимальное, но допустимое и близкое к оптимальному.
Реализация:
Описанный подход был реализован в многопользовательском приложении, имеющем всю необходимую функциональность. Для разработки применялись следующие инструменты: C#(.NET Framework 4.5), WPF-технология с шаблоном проектирования MVVM (см. [3]), MS SQL Server 2012 (с Entity Framework 6.1.3).
Результаты.
В итоге была создана медицинская информационная система, содержащая набор функций, полностью удовлетворяющих работу данного психотерапевтического центра.
Реализован описанный алгоритм автоматизированного построения расписаний.
В процессе тестирования были настроены веса для каждого вида работ.
Этот алгоритм не отменяет необходимость проверки и корректировки готового расписания специалистом по составлению расписаний. Но большая часть работы теперь производится системой, освобождая сотрудника от необходимости подготовки начального варианта расписания. В связи с этим процесс, занимавший больше половины рабочего дня, стал проходить за час-полтора.
Литература:
- Конвей Р. В., Максвелл В. Л., Миллер Л. В. Теория расписаний / пер. с англ. Кокотушкина В. A., Михалева Д. Г., под ред. Башарина Г. П. М.: Наука, 1975.
- Лазарев А. А., Гафаров Е. Р. Теория расписаний. Задачи и алгоритмы. М.: МГУ, 2011.
- Smith J. Patterns — WPF Apps With The Model-View-ViewModel Design Pattern // MSDN Magazine. 2009. February.
- Brucker P. Scheduling Algorithms. // Springer Verlag, 2007.
