Determine allocation of values - Python
Note: This is an answer to an earlier version of the question.
I think the solution returned by the solver is correct; each person is working their MinHours
, they're just not consecutive. I ran your code, then said
for person in persons:
print("{}: {}".format(person, sum([staffed[(timeslot, person)].value() for timeslot in timeslots])))
and got:
C1: 12.0
C2: 12.0
C3: 12.0
C4: 20.0
C5: 23.0
C6: 18.0
C7: 22.0
C8: 29.0
C9: 22.0
C10: 27.0
C11: 32.0
So everyone is working at least 12 shifts, i.e., 3 hours.
If you want the shifts to be consecutive (i.e., a person can't work slot 1 and then slot 3), then the typical way to handle this is to use a decision variable that says what time each employee starts their shift, rather than a variable that specifies every time period they are working. Then, introduce a parameter like a[j][t]
, which equals 1
if an employee who starts a shift at slot j
is working in slot t
. From there, you can calculate who is working during which slots.
The reason the problem is infeasible when you set MinHours
to 5 is that it forces too many people to be working during certain hours. For example, 6 people have to complete their shifts before time slot 41. That means 6 x 4 x 5 = 120 person-slots need to be worked before slot 41. But only 97 person-slots are required between slots 1 and 41.
This problem can be fixed by changing the "Staff the right number of people" constraint to >=
instead of ==
, assuming that is allowable for the staffing system. (If it's not, then you just have an infeasible instance on your hands.)
(By the way -- you might be interested in the proposed new Stack Exchange site on Operations Research and Analytics. We'll be all over questions like this one over there. :-) )
Here's an answer to your revised question, i.e., how to add a constraint that requires each employee to work consecutive time periods.
I suggest that you add the following constraint (written here algebraically):
x[t+1,p] <= x[t,p] + (1 - (1/T) * sum_{s=1}^{t-1} x[s,p]) for all p, for all t < T
where x
is your staffed
variable (written here as x
for compactness), t
is the time index, T
is the number of time periods, and p
is the employee index.
The logic of the constraint is: If x[t,p] = 0
(the employee is not working in period t
) and x[s,p] = 1
for any s < t
(the employee was working in any prior period), then x[t+1,p]
must = 0
(the employee cannot be working in period t+1
. Thus, once the employee stops working, they can't re-start. Note that if x[t,p] = 1
or x[s,p] = 0
for every s < t
, then x[t+1,p]
can equal 1
.
Here's my implementation of this constraint in pulp
:
# If an employee works and then stops, they can't start again
num_slots = max(timeslots)
for timeslot in timeslots:
if timeslot < num_slots:
for person in persons:
prob += staffed[timeslot+1, person] <= staffed[timeslot, person] + \
(1 - (1./num_slots) *
sum([staffed[(s, person)] for s in timeslots if s < timeslot]))
I ran the model and got:
Optimal
Staffed
Timeslot Staffmember
1 C2 1.0
2 C2 1.0
3 C2 1.0
4 C2 1.0
5 C2 1.0
6 C2 1.0
7 C2 1.0
8 C2 1.0
9 C2 1.0
C6 1.0
10 C2 1.0
C6 1.0
11 C2 1.0
C6 1.0
12 C2 1.0
C6 1.0
13 C3 1.0
C6 1.0
14 C3 1.0
C6 1.0
etc. So, employees are working in consecutive time periods.
Note that the new constraints slow down the model a bit. It still solves in <30 seconds or so. But if you are solving much larger instances, you might have to re-think the constraints.