Какой алгоритм для назначения смены шаблона

Question

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

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

5-2-5-2 (5 дней работы, 2 бесплатно, 5 дней работы, 2 бесплатно) и т. Д.

5-2-4-3

5-4-5-3

5-3-5-3

В данный момент у нас есть все эти паттерны и разные стартовые числа, то естьшаблон может начинаться в определенную дату в определенной части внутри шаблона, например, шаблон 5-4-5-3 имеет 17 возможных начальных последовательностей, это число равно сумме 5 + 4 + 5 + 3 = 17возможные последовательности.

https://en.wikipedia.org/wiki/Shift_plan

Теперь проблема,

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

Я читал о " проблеме планирования медсестры " с помощью Google Or-Tool , но я не понимаю, как установить последовательность последовательности всоздать решение для этой проблемы.Я прочитал некоторые мнения о GA (генетические алгоритмы) , и все они сказали, что такое решение не подходит для такого рода проблем.

У кого-нибудь есть подобная проблема?Может кто-нибудь дать мне более точный пример с инструментами Google OR, чем пример в GitHub.

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

Answer 1

Я думаю, что это можно смоделировать как модель MIP.

Размышление вслух:

Введите двоичную переменную решения:

δ(i,p) = 1 if pattern i is selected for person p  
         0 otherwise

Это включает в себя текущий шаблон(скажем i=0).Это позволило бы:

• сотрудник не отправляет новый шаблон (тогда у нас есть только i=0 для этого сотрудника)
• сотрудник представляет один или несколько предпочтительных шаблонов

У нас есть ограничения:

sum(i, δ(i,p)) = 1                                    ∀p
sum((i,p), pattern(i,p,t)*δ(i,p)) ≈ requiredlevel(t)  ∀t
δ(i,p) ∈ {0,1} 

здесь pattern(i,p,t) описывает шаблон i: это 1, если период t покрывается, когда используется шаблон (i, p), и0 иначеЗдесь я использую ≈ для обозначения «приблизительно».(Это легко смоделировать, используя слабые места и, возможно, штрафные термины в цели).

Теперь мы максимизируем

maximize sum((i,p), weight(i,p) * δ(i,p))

, где weight(i,p) указывает предпочтение для шаблона (например, weight(0,p)=0, т.е.нет бонусных баллов, если не выбран новый, предпочтительный шаблон).

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

Answer 2

Что такое рабочий процесс?

Если у вас есть фиксированный список, и один человек предлагает новый шаблон. Просто удалите вклад этого человека, проверьте все (17) начальные точки нового шаблона и наберите их.

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

Это ясно?

Answer 3

У кого-нибудь есть подобная проблема?

Похоже на Ростер сотрудника OptaWeb , который является вертикалью поверх OptaPlanner, решателя ограничений. Взгляните на исходный код . Это все с открытым исходным кодом.