Какой алгоритм назначения смен (задача дискретной оптимизации)

Question

Я разрабатываю приложение, которое оптимально назначает смены медсестрам в больнице. Я полагаю, что это проблема линейного программирования с дискретными переменными, и поэтому, вероятно, NP-hard:

• Для каждого дня каждой медсестре (ок. 15-20) назначается смена
• Существует небольшое количество (около 6) различных смен
• Существует значительное количество ограничений и критериев оптимизации, касающихся как дня, так и сотрудника, например:
  • Для каждой смены должно быть назначено минимальное количество людей каждый день
  • Некоторые смены накладываются друг на друга, поэтому нормально, чтобы в раннюю смену было на одного человека меньше, если кто-то делает промежуточную смену
  • Некоторые люди предпочитают раннюю смену, некоторые предпочитают позднюю смену, но для получения более высокой оплаты за смену требуется минимум сменных смен.
  • Нельзя допускать, чтобы один человек работал поздней сменой в один день и ранней сменой на следующий день (из-за минимального времени отдыха)
  • Назначенная продолжительность собрания (разная для разных людей)
  • ...

Таким образом, в основном существует большое количество (около 20 * 30 = 600) переменных, каждая из которых может принимать небольшое количество дискретных значений.

В настоящее время мой план заключается в использовании модифицированного алгоритма минимальных конфликтов

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

Есть идеи получше? Я несколько обеспокоен тем, что он застрянет в локальном оптимуме. Должен ли я использовать какую-либо форму имитации отжига ? Или рассмотреть не только изменения в одной переменной за раз, но и конкретно переключатели смен между двумя людьми (основной компонент в текущем ручном алгоритме)? Я хочу избежать адаптации алгоритма к текущим ограничениям, поскольку они могут измениться.

Редактировать: Нет необходимости искать строго оптимальное решение; реестр в настоящее время делается вручную, и я почти уверен, что результат в большинстве случаев значительно ниже оптимального - не должно быть проблем с этим. Краткосрочные корректировки и ручные изменения также обязательно будут необходимы, но я не верю, что это будет проблемой; Пометка прошлых и ручных заданий как «фиксированных» на самом деле должна упростить задачу за счет уменьшения пространства решения.

Answer 1

Это сложная проблема, которую нужно решить хорошо. Было много научных работ по этому предмету, особенно в области Operations Research - см., Например, документы по составлению списков медсестер за 2007-2008 гг. или просто Google "Исследования по составлению списков медсестер". Сложность также зависит от таких аспектов, как: сколько дней нужно решить; какой тип «запросов» может сделать медсестра; это реестр "циклический"; Является ли это долгосрочным планом или ему необходимо справиться с кратковременным «ремонтом» реестра, таким как болезни, свопы и т. д. и т. д.

Алгоритм, который вы описываете, является эвристическим подходом. Вы можете обнаружить, что можете настроить его так, чтобы он хорошо работал для одного конкретного случая проблемы, но как только «что-то» изменяется, оно может работать не так хорошо (например, локальные оптимумы, плохая конвергенция).

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

Answer 2

Хм, а вы знали, что некоторые ILP-решатели неплохо справляются? Попробуйте AIMMS, Mathematica или GNU! 600 переменных, конечно, намного больше, чем теорема Ленстры, которую легко решить, но иногда эти решатели ILP хорошо справляются, и в AIMMS вы можете немного изменить стратегию ветвления. Кроме того, для ILP существует очень быстрая 100% -ная аппроксимация.

Answer 3

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

Затем мы попробовали генетические алгоритмы (как вы и предлагали), но не смогли найти хорошую фитнес-функцию, которая закрывала бы какое-либо жизнеспособное решение (потому что самое маленькое изменение может сделать весь график ПРАВИЛЬНЫМ или НЕПРАВИЛЬНЫМ - очков практически нет) 1004 *

Наконец мы выбрали следующий метод (который отлично работал!):

1. Рандомизировать набор входных данных (т. Е. Вакансии, смены, персонал и т. Д.).
2. Создайте допустимый кортеж и добавьте его в предварительное расписание.
3. Если недопустимый кортеж может быть создан, выполните откат (и приращение) последнего добавленного кортежа.
4. Передать частичное расписание функции, которая проверяет could_schedule_be_valid, то есть, может ли это расписание быть действительным, если оставшиеся кортежи были заполнены возможным способом
5. Если !could_schedule_be_valid, просто откатить (и увеличить) кортеж, добавленный в (2).
6. Если schedule_is_complete, return schedule
7. Перейти (2)

Таким образом, вы постепенно строите частичный сдвиг. Преимущество состоит в том, что некоторые тесты для правильного расписания можно легко выполнить на шаге 2 (предварительные тесты), а другие должны остаться на шаге 5 (пост-тесты).

Удачи. Мы потратили впустую дни, пробуя первые два алгоритма, но получили рекомендованный алгоритм, генерирующий действительные графики мгновенно за менее чем 5 часов разработки.

Кроме того, мы поддерживали предварительную и последующую фиксацию назначений, которые будут соблюдаться алгоритмом. Вы просто не рандомизируете эти слоты на шаге 1. Вы обнаружите, что решения не должны быть где-то близко к оптимальным. Наше решение как минимум O (N * M), но выполняется на PHP (!) Менее чем за полсекунды для всего завода. Прелесть в том, чтобы быстро исключать плохие графики, используя хороший тест could_schedule_be_valid.

Людям, которые привыкли делать это вручную, все равно, если это займет час - они просто знают, что им больше не нужно делать это вручную.

Answer 4

Майк,

Не знаю, получили ли вы когда-нибудь хороший ответ на этот вопрос, но я почти уверен, что программирование с ограничениями - это билет. В то время как GA может дать вам ответ, CP предназначен для того, чтобы дать вам много ответов или сказать, нет ли реального решения. Поиск по «программированию ограничений» и календарному планированию должен вызвать много информации. Это относительно новая область, и методы CP хорошо подходят для решения многих типов задач, в которых традиционные методы оптимизации не работают.

Answer 5

Метаэвристика очень хорошо прошла на Международном конкурсе медсестер-ростеров 2010 .

Для реализации, смотрите это видео с непрерывным списком медсестер (java) .

Answer 6

Используя программирование CSP, я создал программы для автоматического внесения изменений в списки. например:

1. 2-сменная система - проверено на 100+ медсестер, 30 дней, 10+ правила
2. 3-сменная система - проверено на 80+ медсестер, 30 дней, 10+ правил
3. 3-сменная система, 4 команды - проверено на горизонте 365 дней, 10+ правил,

и пара похожих систем. Все они были протестированы на моем домашнем ПК (1,8 ГГц, двухъядерный). Время исполнения всегда было приемлемым, т.е. для 3 / это заняло около 5 минут и 300 МБ ОЗУ.

Самой сложной частью этой проблемы был выбор правильного решателя и правильной стратегии решения.

Answer 7

Я думаю, вы должны использовать генетический алгоритм, потому что:

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

• Качество решения зависит от того, сколько времени вы собираетесь потратить на решение программы.

  Определение генетических алгоритмов

  Учебник по генетическим алгоритмам

  Планирование класса проекта с GA

Также взгляните на: аналогичный вопрос и еще один

Answer 8

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

Answer 9

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