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

StackOverflow https://stackoverflow.com/questions/573670

Вопрос

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

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

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

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

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

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

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

Это было полезно?

Решение

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

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

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

Другие советы

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

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

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

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

  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 тест.

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

Майк,

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

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

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

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

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top