#python #runtime #scheduling #or-tools
#python #время выполнения #планирование #или-инструменты
Вопрос:
Я разрабатываю программу планирования медсестер для одного из отделений больницы, с которой я работаю, на Python. Различные примеры таких программ уже существуют и публикуются в Интернете. Один из них следующий:https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py
На данный момент мне удалось адаптировать код по ссылке выше, чтобы включить различные типы трудовых норм, а также индивидуальные предпочтения медсестры. Однако я продолжаю изо всех сил пытаться реализовать следующее правило:
- Сотрудники не могут работать более 5 дней подряд.
Код изначально поддерживает ограничения на длину серий одного и того же типа смен (например, запретить n последовательных утренних или ночных смен). Однако нет никакого способа ограничить продолжительность серий последовательных смен, если они не одного типа (например, ночь / night / morning/night/morning).
Мне удалось реализовать это правило, добавив следующий фрагмент кода:
for e in range(num_employees):
for d in range(num_days):
model.Add(work[e, 0, d] == 1).OnlyEnforceIf( (work[e, 1, d-5] or work[e, 2, d-5] or work[e, 3, d-5] or work[e, 4, d-5] )
and (work[e, 1, d-4] or work[e, 2, d-4] or work[e, 3, d-4] or work[e, 4, d-4] )
and (work[e, 1, d-3] or work[e, 2, d-3] or work[e, 3, d-3] or work[e, 4, d-3] )
and (work[e, 1, d-2] or work[e, 2, d-2] or work[e, 3, d-2] or work[e, 4, d-2] )
and (work[e, 1, d-1] or work[e, 2, d-1] or work[e, 3, d-1] or work[e, 4, d-1] ))
Однако эта реализация резко увеличивает время выполнения программы (с 30 секунд без ограничений, примерно до 15 минут с учетом этого). Поэтому я ищу способ запретить сотрудникам назначаться на 5 или более дней подряд, что не так сильно увеличивает время выполнения.
Ответ №1:
ОТВЕТ
Я внедрил изменения, предложенные @LaurentPerron ниже, используя следующие строки кода:
max_seq_length = 5
for e in range(num_employees):
works = [work[e, 0, d].Not() for d in range(num_days)]
variables, coeffs = add_soft_sequence_constraint(
model, works, 0, 0, 0, max_seq_length, max_seq_length, 0,
'shift_constraint(employee %i, shift %i)' % (e, 0))
obj_bool_vars.extend(variables)
obj_bool_coeffs.extend(coeffs)
Комментарии:
1. Эй, не могли бы вы рассказать нам, как вела себя среда выполнения? Было ли это в основном таким же, как до этого ограничения?
2. @CjojureMostly, при добавлении этого ограничения время выполнения резко увеличивается. При моей настройке программы компьютеру потребовалось примерно 5-10 минут, чтобы найти решение. Поэтому я бы посоветовал максимально сократить время выполнения перед его внедрением (однажды мне пришлось ждать завершения моего расписания более 24 часов)
Ответ №2:
Вы можете адаптировать код, ограничив длину литералов off_shift.not().
Комментарии:
1. Привет, Лоран, не могли бы вы немного конкретнее объяснить, что вы подразумеваете под литералами off_shift? Если я не ошибаюсь, они не были реализованы. Как мне это сделать?
2. В приведенном выше примере O — выходной, M — утро, A — день, N — ночь. Таким образом, нерабочим является O. Таким образом, для данного дня
dи сотрудникаe` work[e, 0, d]` является истинным, если этот сотрудник не работает в этот день. Таким образом,work[e, 0, d].not()верно, если этот сотрудник работает. Вы можете ограничить максимальную длину этих литералов.
Ответ №3:
не могли бы мы просто добавить ограничение AddBoolOr для последовательных отключенных смен вместо функции ‘add_soft_sequence_constraint’ и литералов .Not()? т.Е. мы следим за тем, чтобы не было последовательности длиной hard_max, в которой не было бы off-shift. пример кода, измененный из файла примера:
max_seq_length = 5
for e in range(num_employees):
works = [work[e, 0, d] for d in range(num_days)]
for start in range(len(works) - hard_max):
model.AddBoolOr([works[i] for i in range(start, start hard_max 1)])
Интересно, поможет ли это ускорить работу решателя.