Scheduling Algorithm with contiguous breaks

I'm lost here. Here's the problem and I think it's NP-hard. A center is staffed with a finite number of workers with the following conditions:

1. There are 3 shifts per day with 2 people in each shift
2. Each employee works for 5 days straight and then 2 days off with only one shift per day

So the problem is: how many workers do we need if the center remains active every day and a feasible schedule?

Update:

Thanks for all the great answers. The closest I've come to (with a randomized brute-force algorithm) is the following:

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

I've simplified the problem into batches of 2 people (0-3 repres开发者_Python百科ent 4 batches) in the hopes of getting a feasible solution. X refers to a shift which has not been assigned (which was not the initial goal but it looks like there may not be an alternative).

---

The constraints cannot be respected exactly as expressed in the question.
That's because the numbers don't add up (or rather "divide up").

Consequently, the problem should be reworded to require

• exactly 3 shifts per day
• exactly 2 workers per shift
• workers work a maximum of 5 consecutive days
• workers rest a minimum of 2 consecutive days

With the introduction of the minimum and maximum qualifiers, the minimum number of workers required is 9 (again assuming no part-time worker).
Note that although 9 appears to be a absolute minimum, given the need to cover 42 shifts per week (3 * 2 * 7) with workers who can cover a maximum of 5 shifts per week (5 work days 2 rest days = a week), there is no assurance that 9 would be sufficient given the consecutive work and/or rest day requirements.

This is how I figure...
8 workers isn't enough, and the following 9 workers line-up, is an example of such a schedule.
To make things easy, I assigned all workers except for worker #1 and #9, to an optimal schedule of exactly a 5 days-on and 2 days-off schedule; #1 and #9 work less. Of course many other arrangements would work (maybe this is what the OP sensed when he hinted at an NP-complete problem). Also, the schedule is such that each week's schedule is exactly the same for everyone, but that could also be changed (maybe introducing some fairness, by having all workers have a lighter week every once in a while, but this BTW can lead to some difficulties of respecting the requirement of 5 maximum work days).
The sample schedule shows two consecutive weeks to help see the consecutive work or rest days, but as said, all weeks are the same for every one.

                              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

The tally at the bottom shows exactly 6 workers per day (respecting the need to cover 3 shifts with 2 workers each), the max and min columns on the right show that the maximum consecutive work and minimum consecutive rest requirements are respected.

---

3 shifts per day * 2 people per shift * (7 days per week / 5 working days per person) = 8.4 people (9 if part time is not an option).

---

3 shifts x 7 days = 21

this does not divide evenly by 5 nor 2 - so your constraints will not allow a complete filling of the slots.

---

OK - even though you have an answer, let me take a shot.

Let's take the general problem: 7 days x 3 shifts = 21 different shifts to fill There are 7 possible employee schedules expressed as days on (1) & days off (0)

MTWTFSS 0011111 1001111 1100111 1110011 1111001 1111100 0111110

We want to minimize the number of scheduled employees that matches the number of required hours.

I have a matrix of number of employees of each type per shift and that number is an integer variable. My optimization model is:

Min (number of employees)

Subject to: sum of (# of emp sched * employee schedule) = staff required for each shift

and

number of employees scheduled is integer

You can change the = sign in the first constraint to a >=. Then you'll get a feasible solution with extra staff. You can solve this in Excel with the basic SOLVER addin.

Let's say I need four employees for each day on a shift but I'm willing to tolerate extra staff.

A solution using the schedules above is:

Number of staff by schedule type: 0,2,0,2,0,2,0

Schedule types 0011111,1001111,1100111,1110011,1111001,1111100,0111110

(In other words 2 with schedules 1001111, 2 with schedules 1111001, and 2 more with schedules 1111100)

This results in one day (Monday) with two extra staff and 4 employees on all the other days.

Of course, this isn't a unique solution. There are at least 6 other solutions with two extra staff members. Constraint programming would be a better and much faster approach since there will often be many feasible schedules.