Оптимальный алгоритм планирования смен

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

В бассейне работают X многих спасателей, и у каждого есть определенное количество часов, которое они хотели бы отработать. Мы надеемся сделать так, чтобы среднее количество часов от каждого спасателя было минимальным и справедливым для всех. Каждый спасатель также является студентом колледжа, поэтому у него будет разный график работы.

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

В течение каждого дня требуется определенное количество спасателей на определенные промежутки времени (например: 3 охранника с 8:00 до 10:00, 4 охранника с 10:00 до 15:00 и 2 охранника с 15:00 до 22:00). Вот здесь-то и начинается самое сложное. Нет четко определенных смен (слотов) для размещения каждого из спасателей (из-за того, что создание расписания может быть невозможно при наличии спасатели плюс изменяющееся еженедельное расписание мероприятий в бассейне).

Поэтому расписание нужно создавать с чистого листа, на котором есть только ...

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

Проблема теперь может быть четко определена как «Создайте возможное расписание, которое охватывает необходимое количество охранников в любое время каждый день недели, И будьте как можно более справедливыми по отношению ко всем спасателям при составлении расписания».

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

Изменить. Один из наиболее часто предлагаемых алгоритмов, который я нахожу, - это «Проблема больниц / резидентов», однако я не верю, что это применимо, поскольку нет четко определенных слотов для размещения рабочих.


optimization scheduling algorithm approximation
person yiati    schedule 17.06.2013    source источник
comment
Спустя 6 лет эта статья Google OR-Tools чрезвычайно актуальна developers.google.com/optimization / scheduling /   -  person yiati    schedule 05.09.2019

Ответы (2)


arrow_upward
10
arrow_downward

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

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

person Zim-Zam O'Pootertoot    schedule 17.06.2013
comment
Программирование с ограничениями кажется мне сейчас лучшим решением (по крайней мере, после прочтения этого сейчас в течение пары минут). Кажется, что люди в бассейне каждую неделю вырывают себе волосы, пытаясь составить рабочий график, при этом охранники будут довольны. Кажется, что проблемы с ограничениями обычно NP-Hard. - person yiati; 17.06.2013
comment
@yiati Это обобщенная задача присваивания, что означает, что она NP-трудна, если только функция стоимости не является тривиальной. - person Zim-Zam O'Pootertoot; 17.06.2013
comment
@ Zim-ZamO'Pootertoot У меня аналогичная проблема с планированием ресурсов в соответствии с шаблоном работы, у меня 5 сотрудников, все они работают по фиксированному циклическому шаблону 4 3 3 4, что означает 4 дня работы, 3 выходных, 3 дня работы, 4 выходных, теперь ограничение - каждый день работает минимум 3 сотрудника. Несколько дней у меня болела голова, но я все еще не знаю, с чего начать. Не могли бы вы дать руководство, спасибо. - person Saorikido; 21.01.2016
comment
@ Z.Neeson Я не знаю, удастся ли удовлетворить ваше ограничение с помощью этого графика - у вас 5 сотрудников, и каждый сотрудник работает 50% времени, поэтому в среднем в течение каждого 14-дневного цикла у вас будет только 2,5 сотрудника работают. Можно ли назначить сотруднику дополнительные дни / меньше выходных или что-то в этом роде? - person Zim-Zam O'Pootertoot; 21.01.2016
comment
@ Zim-ZamO'Pootertoot Да, вы правы, я не прояснил проблему, ресурсов явно недостаточно для одного цикла, на самом деле это проблема, с которой мы сталкиваемся, шаблон исправлен (я не знаю, почему они предпочитают этот шаблон ...), так что теперь у нас есть два варианта для удовлетворения минимальных ежедневных рабочих ресурсов: либо нанять больше сотрудников для работы по той же схеме (4334), либо нанять нескольких сотрудников, работающих неполный рабочий день, для заполнения вакансии, зарплаты все дневная заработная плата, так как же потратить минимум денег, чтобы получить оптимальное решение / комбинацию? - person Saorikido; 22.01.2016
comment
@ Zim-ZamO'Pootertoot Текущий отдел - это небольшой отдел, всего несколько человек, в худшем случае мы можем перебрать все случаи, чтобы найти оптимальное решение, но для других отделов (у них есть свой рабочий шаблон) у некоторых из них есть больше более 60 человек работают в смену, поэтому мы должны найти способ решить эту проблему выдергивания волос. - person Saorikido; 22.01.2016
comment
@ Zim-ZamO'Pootertoot На мой взгляд, эта проблема будет заключаться в том, что у каждого сотрудника будет различное начальное смещение последовательности шаблонов, поэтому какая комбинация смещений лучше всего подходит для получения второстепенных вакансий? Я не уверен, верна ли гипотеза ... - person Saorikido; 22.01.2016
comment
@ Z.Neeson Я подозреваю, что с учетом 14-дневного рабочего периода лучшим решением будет, чтобы N / 14 сотрудников начинали свой рабочий период в любой день, например с 28 сотрудниками у вас будет 2 начала рабочего периода в первый день, 2 - во второй день и т. д. Я предлагаю вам написать простой жадный алгоритм, который назначает равное распределение, а также алгоритм, который назначает случайное распределение, запускайте случайный алгоритм несколько тысяч раз, и посмотрите, превзойдет ли он когда-нибудь равное распределение; если это не так, тогда используйте равное распределение, если это так, то может потребоваться более умное решение - person Zim-Zam O'Pootertoot; 22.01.2016
comment
@ Zim-ZamO'Pootertoot хм ... имеет смысл, позвольте мне сначала попробовать, большое вам спасибо. - person Saorikido; 22.01.2016

arrow_upward
4
arrow_downward

Вам нужно превратить свой критерий честности в целевую функцию. Затем вы можете выбрать из любого количества инструментов планирования рабочего места. Например, вы описываете желая минимизировать среднюю разницу между желаемыми и назначенными часами. Однако я бы посоветовал вам подумать о минимизации максимальной разницы. Это кажется более справедливым (мне) и обычно приводит к другому графику.

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

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

person Ted Hopp    schedule 17.06.2013
comment
Я согласен с тем, что я обязательно должен стремиться минимизировать максимальную разницу. Теперь я также понимаю, что их взвешивание определенно могло быть важным фактором, который я не учел. - person yiati; 17.06.2013
comment
Какие виды инструментов планирования уже имеют эти возможности и / или как они называются, чтобы я не воссоздавал здесь колесо, если в этом нет необходимости? - person yiati; 17.06.2013
comment
@yiati - я не очень разбираюсь в существующих инструментах и, конечно же, не могу рекомендовать один перед другим. Из этого обсуждения кажется, что whentowork.com делает большую часть того, что вы хотите . Некоторые другие инструменты перечислены здесь (обычно это более мощные пакеты управления персоналом) и вы можете составить расписание спасателей Google, чтобы найти больше ресурсов. - person Ted Hopp; 17.06.2013