Математическое моделирование в ORtools: задача планирования расписаний

Приветствую! Я Ложкинс Алексей, консультант и разработчик математических моделей и оптимизационных решений для бизнеса. Это вторая обучающая статья, часть личного образовательного проекта "Make optimization simple". Цель проекта - продемонстрировать доступность технологий и показать на примерах, что моделировать можно без глубокого математического фундамента.

В статье рассмотрим задачу планирования расписаний, в частности, планирование смен сотрудников сети стоматологических клиник. Я покажу, как реализовать программный прототип математической модели посредством Python и библиотеки OR-Tools, а также продемонстрирую, как получить решение задачи всего в одной строке кода.

Материал статьи предназначен для

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

<= Предыдущая статья

Описание задачи

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

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

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

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

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

Сеть из 3 стоматологических клиник имеет в своем ассортименте 5 экспертов. Все клиники сети работают без выходных по одной смене каждый день (8 часов). График работы сотрудников должен иметь недельный цикл (горизонт планирования 7 дней). Необходимо распределить сотрудников по клиникам и сменам при следующих ограничениях:

Каждый эксперт может работать только в одной клинике в смену;
В каждой клинике в любой из дней недели должен работать ровно один эксперт (одно помещение под эксперта);
Эксперты работают 5 смен в неделю (режим труда и отдыха);
В каждой клинике в течение недели должны работать не менее 2 разных экспертов (имитация выбора для клиента).

Построение модели и ее python реализация

Рассматриваемая нами задача состоит из набора ограничений, как и задача планирования расписаний в целом, ее можно представить в виде задачи удовлетворения ограничений (ЗУО). Элементы "языка ЗУО":

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

Представление задачи в формате ЗУО не дает ее решение, а только предлагает вариант формализации в некоторой математической форме. Одним из вариантов для ее решения является парадигма программирование в ограничениях (Constraint Programming, CP). Она представляет собой набор методов и алгоритмов для решения ЗУО.

Конечно, уже разработаны и упакованы библиотеки для решения задач удовлетворения ограничений, в которых реализованы алгоритмы программирования в ограничениях, такие пакеты называются solver или cp-solver.

Из числа open source решений наиболее эффективным является cp-sat solver ORtools. Библиотека также предоставляет функционал для описания ЗУО. На примере данного solver`а будем моделировать и решать задачу планирования расписания смен ведущих стоматологов сети клиник.

Установить библиотеку ORtools в среду python можно с помощью pip:

pip install ortools

Индексы и входные данные

В задаче фигурируют три объекта: клиника, эксперт и смена. Введем для них следующие обозначения:

$k \in K$ - индекс и список клиник, клиника содержится во множестве ;

$e\in E$ - индекс и список экспертов, эксперт содержится во множестве ;

$t \in T$ - индекс и дни недели, день недели содержится во множестве .

Запишем эти множества в виде списков Python:

# Инициализируем множества/списки
K = ["Klinika1", "Klinika2", "Klinika3"]  # Список клиник в сети
E = ["Expert1", "Expert2", "Expert3", "Expert4", "Expert5"]  # Список экспертов
T = ["Smena" + str(t) for t in range(1, 8)]  # Список смен

trudovoy_kodex = 5  # Константа, ограничение кол-ва рабочих смен у эксперта
min_experts_per_clinic = 2  # Минимальное кол-во экспертов, привязанных к клинике

Импорт библиотеки и инициализация модели

ORtools содержит в себе различные обертки для различных классов задач, в том числе для ЗУО. Поэтому импорт нужной нам части находится на четвертом уровне: from ortools.sat.python import cp_model. Переменные, ограничения и целевая функция инициализируются в экземпляре класса CpModel(). Объект модели может содержать только описание одной задачи, но никто не мешает инициализировать несколько экземпляров модели.

# Импорт "редактора" для записи ЗУО
from ortools.sat.python import cp_model
import pandas as pd

# Инициализация модели
model = cp_model.CpModel()

Инициализация переменных

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

Каждую такую комбинацию свяжем с переменной $x_{ket}$ , которая принимает значение 1, если эксперт $e \in E$ работает в смену $t \in T$ в клинике $k \in K$ , 0 - в противном случае. Таким образом, у нас есть 3*5*7 = 105 переменных, соответствующих всем комбинациям.

Например: если переменная для комбинации Klinika1-Expert1-Smena1 равна 1, следовательно, Эксперт 1 должен работать в Клинике 1 в Смену 1. Если значение переменной равно 0, то Эксперт 1 не работает в Клинике 1 в Смену 1.

Кроме допустимых комбинаций введем вспомогательные переменные-индикаторы клиника-эксперт. Значение переменной $y_{ke}$ равное 1, будет означать, что эксперт $e\in E$ работает, по крайней мере, одну смену в клинике $k \in K$ , 0 - эксперт не работает в клинике .

Например: если переменная для комбинации Klinika1-Expert1 равна 1, следовательно, Эксперт 1 должен работать в Клинике 1 хотя бы одну смену. Если значение переменной равно 0, то Эксперт 1 не работает в Клинике 1 вообще.

Добавление переменных в CpModel возможно через метод NewBoolVar, если переменная бинарная (может принимать значения 0 или 1) или с помощью метода NewIntVar для целочисленных переменных. Переменные, соответствующие допустимым комбинациям, будем складировать в словарь X, переменные-индикаторы - в Y.

Важно! Использование cp-sat solver'а возможно только для решения задач с целочисленными переменными.

# Инициализация переменных комбинации
X = {}  # Словарь для хранения ссылок на переменные

for k in K:
  for e in E:
    for t in T:
      var_name = f"x_{k}_{e}_{t}"  # Название переменной
      X[k, e, t] = model.NewBoolVar(name=var_name)

# Инициализация переменных-индикаторов
Y = {}  # Словарь для хранения ссылок на переменные-индикаторы

for k in K:
  for e in E:
    var_name = f"y_{k}_{e}"  # Название переменной-индикатора
    Y[k, e] = model.NewBoolVar(name=var_name)

Ограничение: один эксперт в каждой клинике каждый день

Всего в нашем распоряжении пять экспертов и три клиники. Ровно один из этих пяти экспертов должен работать в Клинике 1 в Смену 1. Это условие можно записать следующим образом:

$x_{\text{Klinika1}, \text{Expert1}, \text{Smena1}} + x_{\text{Klinika1}, \text{Expert2}, \text{Smena1}} + x_{\text{Klinika1}, \text{Expert3}, \text{Smena1}} +$ $x_{\text{Klinika1}, \text{Expert4}, \text{Smena1}} + x_{\text{Klinika1}, \text{Expert5}, \text{Smena1}} = 1.$

Аналогичные ограничения создаем для всех остальных пар клиника-смена. В связи с большим количеством ограничений (3*7=21 шт.), текстовую запись всех ограничений опустим.

Более лаконично ограничения можно записать в математической форме с использованием знака суммы $\sum$ и символа для каждого элемента множества $\forall$ («Для любого...»).

$\sum_{e \in E} x_{ket} = 1, \quad \forall k \in K, \forall t \in T.$

Добавление ограничений в CpModel возможно через метод Add, но наше ограничение подпадает под определенный шаблон ограничений AddExactlyOne (ровно одна переменная равняется 1). Использование таких шаблонов позволяет алгоритмам автоматически подстраиваться под ограничения и работать эффективнее. Добавим ограничения в модель.

# Ограничение: один эксперт в каждой клинике каждый день
for k in K:  # для каждой клиники
  for t in T:   # для каждого дня недели

    # Список экспертов для работы в клинике "k" в смену "t"
    lst_vars = [X[k, e, t] for e in E]  

    # Добавление ограничений в модель: ровно один эксперт в клинике в смену
    model.AddExactlyOne(lst_vars) 
    # model.Add(sum(lst_vars) == 1)  # Альтернативный способ добавления ограничения

Ограничение: эксперт работает не более чем в одной клинике в смену

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

В сети три клиники, в одной из которых может работать Эксперт 1 в Смену 1. Кроме того, Эксперт 1 может вообще не работать в Смену 1 - выходной. Это условие с помощью введенных переменных можно записать как

$x_{\text{Klinika1}, \text{Expert1}, \text{Smena1}} + x_{\text{Klinika2}, \text{Expert1}, \text{Smena1}} + x_{\text{Klinika3}, \text{Expert1}, \text{Smena1}} \le 1.$

Аналогичные ограничения создаем для всех остальных пар эксперт-смена. В связи с большим количеством ограничений (5*7=35 шт.) текстовую запись всех ограничений снова опустим. Лаконичная запись в виде формулы:

$\sum_{k \in K} x_{ket} \le 1, \quad \forall e \in E, \forall t \in T.$

Данное ограничение является шаблонным, задается посредством метода AddAtMostOne (не более чем одна переменная равна 1).

# Ограничение: Каждый эксперт может работать только в одной клинике в смену.
for e in E:  # для каждого эксперта
  for t in T:   # для каждой смены

    # Список клиник для работы эксперта "e" в смену "t"
    lst_vars = [X[k, e, t] for k in K]  

    # Добавление ограничений в модель: у эксперта не более одной клиники в смену
    model.AddAtMostOne(lst_vars) 
    # model.Add(sum(lst_vars) <= 1)  # Альтернативный способ добавления ограничения

Ограничение: связь переменных-комбинаций и переменных-индикаторов

Данный тип ограничений является вспомогательным с целью упростить формализацию других ограничений. Само ограничение связывает переменные-индикаторы с переменными-комбинациями. Смысл ограничения в следующем: если Эксперт 1 работает в Клинике 1 хотя бы одну смену из семи, тогда Эксперт 1 связан (ассоциирован) с Клиникой 1, в противном случае не связан с Клиникой 1. Необходимость этого знания будет описана в следующем ограничении.

С целью формализации ограничения воспользуемся функцией $\max()$ которая возвращает максимальное значение среди набора переменных. В нашем случае переменные могут принимать значения 0 или 1. Поэтому максимальное значение не может быть больше 1, что входит в диапазон допустимых значений переменной $y_{ke}$ . Пример ограничений для Эксперта 1 и Клиники 1:

$\max(x_{\text{Klinika1}, \text{Expert1}, \text{Smena1}}; x_{\text{Klinika1}, \text{Expert1}, \text{Smena2}}; x_{\text{Klinika1}, \text{Expert1}, \text{Smena3}};$ $x_{\text{Klinika1}, \text{Expert1}, \text{Smena4}};x_{\text{Klinika1} \text{Expert1} \text{Smena5}}; x_{\text{Klinika1}, \text{Expert1}, \text{Smena6}};$ $x_{\text{Klinika1}, \text{Expert1}, \text{Smena7}}) = y_{\text{Klinika1}. \text{Expert1}}.$

Если хотя бы одна из переменных $x_{ket}$ в $\max()$ будет иметь значение 1, то результат функции $\max()$ будет равен 1. Тогда переменная-индикатор так же будет равна 1. А это означает, что можно продавать услуги эксперта в клинике .

Эти ограничения гарантируют связь переменных-комбинаций и переменных-индикаторов. Лаконичная форма записи ограничений для клиника-эксперт:

$\max_{t \in T}x_{ket} = y_{ke}, \quad \forall k \in K, \forall e \in E.$

В CpModel() метод AddMaxEquality() позволяет задать ограничения с функцией $\max()$ . В качестве аргументов необходимо передать target и variables, в нашем случае target - это переменная $y_{ke}$ а variables - список переменных $x_{ket}$ соответствующий всем возможным сменам эксперта в клинике .

# Ограничение (вспомогательное): индикатор работы эксперта "e" в клинике "k"
for k in K:
  for e in E:

    # Список смен для работы в клинике "k" и эксперта "e"
    lst_vars = [X[k, e, t] for t in T]  

    # Добавление ограничений в модель: индикатор работы эксперта "e" в клинике "k"
    model.AddMaxEquality(Y[k, e], lst_vars)
    # model.Add(sum(lst_vars) >= Y[k, e])  # Нижняя граница
    # model.Add(sum(lst_vars) <= expert_shift_lim * Y[k, e])  # Верхняя граница

Ограничение: в каждой клинике не менее двух экспертов

Бизнес-ограничение обусловлено спектром сервиса в виде предоставления клиентам возможности выбирать из нескольких экспертов. Запись ограничения для случая Клиника 1:

$y_{\text{Klinika1}, \text{Expert1}} + y_{\text{Klinika1}, \text{Expert2}} + y_{\text{Klinika1}, \text{Expert3}} +$ $y_{\text{Klinika1}, \text{Expert4}} + y_{\text{Klinika1}, \text{Expert5}} \ge 2.$

Заметим, что в ограничении участвуют вспомогательные переменные-индикаторы, которые отражают привязку эксперта к клинике, а само ограничение гарантирует привязку минимум двух разных экспертов.

Математическая запись ограничений для каждой клиники:

$\sum_{e \in E} y_{ke} \ge 2, \quad \forall k \in K.$

# Ограничение: в каждой клинике не менее двух экспертов 
for k in K:

  # Список экспертов, которые могут работать в клинике "k"
  lst_vars = [Y[k, e] for e in E]  

  # Добавление ограничений в модель: минимум 2 разных эксперта должны работать в клинике "k"
  model.Add(sum(lst_vars) >= min_experts_per_clinic)

Ограничение: эксперт может работать пять смен в неделю

Источник ограничения - Трудовой кодекс. Модель должна понимать, что установлено ограничение на кол-во рабочих дней в неделю, обусловленное законом. Каждый эксперт суммарно во всех клиниках не может работать более 5 смен в неделю. Пример ограничения громоздкий, так как содержит 3*7=21 переменную, поэтому запишем его только в математической форме:

$0 \le \sum_{k \in K} \sum_{t \in T} x_{ket} \le 5, \quad \forall e \in E.$

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

# Ограничение: эксперт может работать не более 5 смен
for e in E:

  # Список рабочих смен эксперта "e" во всех клиниках
  lst_vars = [X[k, e, t] for k in K for t in T]

  # Добавление ограничений в модель: 0 <= кол-во смен у эксперта <= 5
  model.AddLinearConstraint(sum(lst_vars), 0, trudovoy_kodex)

Поиск решения

Инициализируем solver и запускаем поиск решения поставленной задачи:

# Инициализация solver
solver = cp_model.CpSolver()

# Решение задачи - та самая одна строчка
status = solver.Solve(model)

# Проверяем статус
if status == cp_model.FEASIBLE:
  print('Найдено решение')

Извлечем полученное решение из модели, для этого запрашиваем у solver значение переменной с помощью метода Value():

# Извлекаем результат (решение)
result = {}
for key, val in X.items():
  sol = solver.Value(val)  # Достаем значение переменной
  if sol > 0:  # Собираем только те переменные, которые имеют значение 1
    result[key] = 1

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

Анализируя результат, можно заметить, что не все эксперты работают 5 смен. Это связано с тем, что объем требуемых смен для экспертов равен 3 * 7=21, а максимальное кол-во смен пяти экспертов 5 * 5 = 25. Таким образом, получаем, что 4 смены экспертов не используются (лишние).

Заключение

Резюмирую содержание обучающего материала: построили математическую модель планирования сменного графика для ведущих специалистов сети стоматологических клиник. Разработали программный прототип на базе Python пакета OR-Tools и решили задачу с помощью cp-sat solver.

Ссылки

Ссылка на расширенный материал в Jupyter Notebook;
Документация Python библиотеки OR-Tools;
Задача планирования расписаний из других уст;
Задача планирования расписаний из примеров OR-Tool;
Задача планирования расписаний в NFL;
Для более углубленного изучения: алгоритм колоночной генерации.

<= Предыдущая статья

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

P.S.S. Есть на примете статьи с моделями в PuLP или ORtools? Присылайте, дополню ссылками.

Источник: https://habr.com/ru/articles/735572/

Вернуться к списку

Интересные статьи

Как мы «уволили» старые процессы планирования и «наняли» новые: опыт разработки собственного инструмента

Привет, Хабр! Меня зовут Анзор Кардан, я руководитель продукта Teamplanner в Х5 Tech. В статье я поделюсь собственным опытом выбора инструмента планирования проектов, через какие стадии мы прошли и с ...

Моделирование ракеты для достижения максимальной высоты

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

«Лучшая задача по математике для школьников, которую я встречал в своей жизни» (Алексей Савватеев)

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

Аналитика vs моделирование. Задача по теории вероятностей

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

Самая сложная задача в Computer Vision

Среди всего многообразия задач Computer Vision есть одна, которая стоит особняком. К ней обычно стараются лишний раз не притрагиваться. И, если не дай бог работает, — не ворошить. У ...