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

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

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

17.05.2023 09:30

Lozkins 2 662 Источник

Математическое моделирование, оптимизация, исследование операций, программирование в ограничениях … Продолжим двигаться в этом направлении.

Статья выполнена в рамках проекта “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;
Для более углубленного изучения: алгоритм колоночной генерации.