I'm trying to solve a staffing optimization problem and this is the model I have.
First constraint: a minimum number of employee needs to be scheduled for each shift.
For exemple:
| shift | requirement |
|---|---|
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 2 |
| 5 | 1 |
Second constraint: An employee can work 0 shift, 1 shift, or 2 shift and it can't be whatever shift.
Let me explain, if the employee works 2 shifts, they need exactly 1 shift break between each.
This is the list of the possible combination:
| shift | shift |
|---|---|
| 1 | 3 |
| 2 | 4 |
| 3 | 5 |
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 |
Desired outcome:
Let's assume these are my employees:
This is what a valid solution could look like
| shift | employee |
|---|---|
| 1 | Robin |
| 2 | George |
| 3 | Robin, Mathew |
| 4 | George, Elisa |
| 5 | Mathew |
Robin 1, 3
George 2, 4
Mathew 3, 5
Elisa 4
I have no problem with the first constraint. It's more the second constraint I'm struggling to implement in Pulp. I would appreciate it if you could give me pointers.
Thanks!
Edit: This is the code I have right now, trying to go the way @airsquid suggested
# constraint 1: must schedule someone at shift 1, 2, 5
for shift, patterns in vars_by_shift.items():
if shift == 1 or shift == 2 or shift == 5:
prob += sum(vars_by_shift[shift]) >= 1
elif shift == 4 or shift == 5: # and 2 persons at shift 4 and 5
prob += sum(vars_by_shift[shift]) >= 2
# constraint 2: agent can at most be scheduled 1 time among all patterns
for agent in agent_names:
prob += sum(vars_by_agent[agent]) <= 1
Where vars_by_shift looks like this
{
1: [1_3,1,robin, 1,1,robin, 1_3,1,mathew, 1,1,mathew, 1_3,1,george, 1,1,george, 1_3,1,elisa, 1,1,elisa],
2: [2_4,2,robin, 2,2,robin, 2_4,2,mathew, 2,2,mathew, 2_4,2,george, 2,2,george, 2_4,2,elisa, 2,2,elisa],
3: [3_5,3,robin, 3,3,robin, 3_5,3,mathew, 3,3,mathew, 3_5,3,george, 3,3,george, 3_5,3,elisa, 3,3,elisa],
4: [2_4,4,robin, 4,4,robin, 2_4,4,mathew, 4,4,mathew, 2_4,4,george, 4,4,george, 2_4,4,elisa, 4,4,elisa],
5: [3_5,5,robin, 5,5,robin, 3_5,5,mathew, 5,5,mathew, 3_5,5,george, 5,5,george, 3_5,5,elisa, 5,5,elisa]
}
and vars_by_agent like this:
{
'robin': [1_3,1,robin, 1,1,robin, 2_4,2,robin, 2,2,robin, 3_5,3,robin, 3,3,robin, 2_4,4,robin, 4,4,robin, 3_5,5,robin, 5,5,robin],
'mathew': [1_3,1,mathew, 1,1,mathew, 2_4,2,mathew, 2,2,mathew, 3_5,3,mathew, 3,3,mathew, 2_4,4,mathew, 4,4,mathew, 3_5,5,mathew, 5,5,mathew],
'george': [1_3,1,george, 1,1,george, 2_4,2,george, 2,2,george, 3_5,3,george, 3,3,george, 2_4,4,george, 4,4,george, 3_5,5,george, 5,5,george],
'elisa': [1_3,1,elisa, 1,1,elisa, 2_4,2,elisa, 2,2,elisa, 3_5,3,elisa, 3,3,elisa, 2_4,4,elisa, 4,4,elisa, 3_5,5,elisa, 5,5,elisa]
}
I get an infeasible solution when calling solve() and I'm not sure why.
Final edit:
Thank you so much @AirSquid
Finally got a valid solution.
The key was in making sure I don't duplicate decision variables when storing them in the different dictionaries.
def shift_to_be_sent_to(pattern):
shifts = []
for shift in range(1, 6):
if coverage_map[pattern, shift] == 1:
shifts.append(shift)
return shifts
Final code is available here
I really like the other solution presented, which is great for larger generalizations of this type of problem. For the complexity of the problem presented, I think you could get by with a simpler approach that uses enumeration of the possible shifts in a simple way.
In your problem description, each employee may be assigned only 1 of 8 patterns of work (or no assignment at all). That gives rise to a 2-indexed binary variable:
assign[employee, pattern]
The relationship of the "pattern" to the requirement in each shift is known, so you then have a model parameter that pairs these 2 things:
fulfills[pattern, shift] = {('p1', 's1'): 1, ... }
with a little elbow grease, and some summation constraints, you have a model with that variable, parameter, 3 sets (employees, patterns, shifts) and 3 or 4 constraints
This works fine in the case described because it is possible to enumerate the acceptable patterns fairly easily and the relationship of pattern:outcome is a 1-to-1 pairing.
You are on the right track... kinda... lol. I think your approach can be successful, I had something a little different in mind that is not triple indexed, but yours can work.
2 probs you have: you have typo in your constraint for shifts. You have shift '5' instead of '3' for 2 requirement. Also, if you look at your vars_by_shift you'll note that for shift 3 you are not crediting the 1-3 combo!! You might want to restructure that part a bit. Here is an idea on how you can get the shifts associated with patterns more easily. (Realize there are a bunch of ways to do this):
cov_file = 'coverages.csv'
coverages = dict()
with open(cov_file, 'r') as src:
for line in src:
data = line.strip().split(',')
pattern = data[0]
shifts = [int(t) for t in data[1:]]
coverages[pattern] = shifts
shifts = [1, 2, 3, 4]
patterns = coverages.keys()
coverage_map = dict()
for (p, s) in [(p, s) for p in patterns for s in shifts]:
coverage_map[p, s] = 1 if s in coverages[p] else 0
print(coverage_map)
A,1
B,1,3
C,2,4
D,2,3,4
{('A', 1): 1, ('A', 2): 0, ('A', 3): 0, ('A', 4): 0, ('B', 1): 1, ('B', 2): 0, ('B', 3): 1, ('B', 4): 0, ('C', 1): 0, ('C', 2): 1, ('C', 3): 0, ('C', 4): 1, ('D', 1): 0, ('D', 2): 1, ('D', 3): 1, ('D', 4): 1}