Алгоритм планирования с непрерывными перерывами

Question

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

1. 3 смены в день с двумя людьми в каждой смене
2. Каждый сотрудник работает 5 дней подряд изатем 2 выходных с одной сменой в день

Итак, проблема в том, сколько рабочих нам понадобится, если центр будет работать каждый день и выполнимый график?

Обновление:

Спасибо за все великолепные ответы.Самое близкое, с чем я столкнулся (с рандомизированным алгоритмом грубой силы), это следующее:

X       3       0
1       0       3
2       3       1
2       1       3
0       1       2
0       2       1
3       0       2

Я упростил задачу до 2 человек (0-3 представляют 4 партии) внадеется получить выполнимое решение.X относится к смене, которая не была назначена (которая не была первоначальной целью, но похоже, что альтернативы не может быть).

Answer 1

Ограничения не могут быть соблюдены точно , как указано в вопросе.
Это потому, что числа не складываются (или, скорее, «делятся»).

Следовательно, проблему следует переформулировать так, чтобы она требовала

• ровно 3 смены в день
• ровно 2 рабочих в смену
• рабочие работают максимум 5 дней подряд
• рабочий отдых минимум 2 дня подряд

С введением минимальных и максимальных квалификаторов, минимальное количество требуемых работников составляет 9 (опять же, при условии отсутствия работника, занятого неполный рабочий день).
Обратите внимание, что хотя 9 представляется абсолютным минимумом, учитывая необходимость покрывать 42 смены в неделю (3 * 2 * 7) с работниками, которые могут покрывать максимум 5 смен в неделю (5 рабочих дней 2 выходных дня = неделя) , нет уверенности в том, что 9 будет достаточно с учетом требований к работе и / или выходному дню.

Вот как я понимаю ...
8 рабочих недостаточно, и следующий состав 9 рабочих является примером такого графика.
Чтобы упростить задачу, я назначил всем работникам, за исключением рабочих № 1 и № 9, оптимальный график работы с графиком точно 5 дней и 2 дня; № 1 и № 9 работают меньше. Конечно, многие другие механизмы будут работать (возможно, это то, что ОП почувствовал, когда намекнул на NP-полную проблему). Кроме того, график таков, что график на каждую неделю одинаков для всех, но его также можно изменить (возможно, введя некоторую справедливость, если время от времени у всех работников будет светлая неделя, но это, кстати, может привести к некоторым трудности соблюдения требования 5 максимальных рабочих дней).
Примерный график показывает две недели подряд, чтобы увидеть последовательные дни работы или отдыха, но, как уже говорилось, все недели одинаковы для всех.

                              Max Conseq Ws   Min Conseq Rs
Worker #1   RRWWWRW RRWWWRW         3              2
Worker #2   WWWWWRR WWWWWRR         5              2
Worker #3   WWWRRWW WWWRRWW         5              2
Worker #4   WWWRRWW WWWRRWW         5              2
Worker #5   WRRWWWW WRRWWWW         5              2
Worker #6   WRRWWWW WRRWWWW         5              2
Worker #7   RWWWWWR RWWWWWR         5              2
Worker #8   RWWWWWR RWWWWWR         5              2
Worker #9   WWRRRRW WWRRRRW         3              3

Nb of Ws    6666666 6666666

Подсчет внизу показывает ровно 6 рабочих в день (с учетом необходимости покрывать 3 смены по 2 рабочих в каждой), столбцы «Макс» и «Мин» справа показывают, что соблюдаются требования к максимальной продолжительности последовательной работы и минимальному количеству последовательного отдыха.

Answer 2

3 смены в день * 2 человека в смену * (7 дней в неделю / 5 рабочих дней на человека) = 8,4 человека (9, если неполный рабочий день не предоставляется).

Answer 3

ОК - хотя у вас есть ответ, позвольте мне сделать снимок.

Давайте возьмем общую проблему: 7 дней х 3 смены = 21 разные смены для заполнения Существует 7 возможных расписаний сотрудников, выраженных в днях (1) и выходных (0)

ПВСЧПСВ 0011111 1001111 1100111 1110011 1111001 1111100 0111110

Мы хотим минимизировать количество запланированных сотрудников, которое соответствует количеству требуемых часов.

У меня есть матрица числа сотрудников каждого типа в смену, и это число является целочисленной переменной. Моя модель оптимизации:

Мин (количество сотрудников)

В зависимости от: суммы (# emp emphed * расписание сотрудников) = персонал, необходимый для каждой смены

и

количество сотрудников запланировано целым числом

Вы можете изменить знак = в первом ограничении на>>. Тогда вы получите реальное решение с дополнительным персоналом. Вы можете решить эту проблему в Excel с помощью основного надстройки SOLVER.

Допустим, мне нужно по четыре сотрудника на каждый день в смену, но я готов терпеть дополнительный персонал.

Решение с использованием приведенных выше графиков:

Численность персонала по типу расписания: 0,2,0,2,0,2,0

Типы расписаний 0011111,1001111,1100111,1110011,1111001,1111100,0111110

(Другими словами, 2 с графиками 1001111, 2 с графиками 1111001 и еще 2 с графиками 1111100)

В результате получается один день (понедельник) с двумя дополнительными сотрудниками и 4 сотрудниками во все остальные дни.

Конечно, это не уникальное решение. Есть как минимум 6 других решений с двумя дополнительными сотрудниками. Программирование с ограничениями будет лучшим и более быстрым подходом, поскольку часто будет много выполнимых расписаний.

Answer 4

3 смены x 7 дней = 21

это делится неравномерно на 5 и 2 - поэтому ваши ограничения не позволят полностью заполнить слоты.