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

Question

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

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

Есть ли у кого-нибудь советы по хорошему алгоритму для этой цели? Благодаря!

Answer 1

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

Два подхода основаны на использовании жадный алгоритм.

Первый - использовать полуслучайный жадный алгоритм; если у вас есть два варианта, то обычно вы всегда выбираете локально оптимальный выбор, но с полузависимым жадным подходом вы вводите возможность выбора выбора, который не является локально оптимальным. Например, выбор имеет вес 5, а второй выбор имеет вес 2; обычно вы выбираете вариант выбора, но в этом случае вы использовали бы генератор случайных чисел и выбираете один вариант, если rand (5 + 2) меньше 5, иначе выберите второй выбор. Теперь запустите алгоритм несколько раз и возьмите «лучшее» решение.

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

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