WorkForce Scheduling Error
AnsweredHi,
I have an issue with one of the constraints for workforce scheduling optimization problems in gurobi. Below is the info.
The parttime staffing requirements are not being met. There is a need for 3 parttime employees from Monday to Thursday and 6 parttime employees from Friday to Sunday. This requirement should be fulfilled for every shift / hour, and there should be no overlapping of shifts. However, the same parttime employee can work for two different shifts on the same day. Just to provide an example, parttime employee 1 can work from 7 am to 11 am and from 11 am to 3 pm on any given day in 4hour blocks. They can also take on additional shifts on the same day.The model shouldn’t give an O/P showing employee 2 working from 7am to 11am and from 10 am to 2 pm i.e. no overlapping of shifts.
PT_REQ_FALL_SPRING = {"Mon": {"Morning": 3, "Evening": 3},
"Tue": {"Morning": 3, "Evening": 3},
"Wed": {"Morning": 3, "Evening": 3},
"Thu": {"Morning": 3, "Evening": 3},
"Fri": {"Morning": 6, "Evening": 6},
"Sat": {"Morning": 6, "Evening": 6},
"Sun": {"Morning": 6, "Evening": 6}}
# Parttime staffing requirements for overall coverage
for day in DAYS:
model.addConstr(sum(work_pt[j, day, shift] for j in range(PT_EMPLOYEES) for shift in PT_SHIFT_TIMES[:6]) >= PT_REQ_FALL_SPRING[day]["Morning"], f"pt_morning_coverage_{day}")
model.addConstr(sum(work_pt[j, day, shift] for j in range(PT_EMPLOYEES) for shift in PT_SHIFT_TIMES[6:]) >= PT_REQ_FALL_SPRING[day]["Evening"], f"pt_evening_coverage_{day}")
# Prevent overlapping shifts for parttime employees
for j in range(PT_EMPLOYEES):
for day in DAYS:
for i inrange(len(PT_SHIFT_TIMES)  3): # Prevent index out of range
model.addConstr(work_pt[j, day, PT_SHIFT_TIMES[i]] + work_pt[j, day, PT_SHIFT_TIMES[i + 1]] + work_pt[j, day, PT_SHIFT_TIMES[i + 2]] + work_pt[j, day, PT_SHIFT_TIMES[i + 3]] <= 1, f"no_overlap_pt_{j}_{day}_{i}")
How can we modify such that we get a feasible solution and the requirements for part timers are met.

Hi Sai,
It looks like you are missing the nonoverlapping shifts constraints for \(i = len(Pt\_Shift\_Times)1, len(Pt\_Shift\_Times)2 \) and \(len(Pt\_Shift\_Times) 3\).
For each \(i \in len(Pt\_Shift\_Times)\), you can create the set of shifts overlapping with shift \(i\), say \(overlappint\_shifts[i]\), and then add the constraint
\[ \sum_{j \in overlapping\_shifts[i]}work\_pt_{e,d,j} \leq 1 \quad \forall \ e \in Pt\_Employees, d \in days, i \in len(Pt\_Shift\_Times)\]
Best regards,
Simran0 
Hi Simran,Would the model work with the below objective function? Do we need to change it?
# Objective Function: Minimize total wage costs
total_wages_ft = sum(work_ft[i, day, shift] * FT_HOURLY_WAGE * FT_SHIFT_LENGTH for i in range(FT_EMPLOYEES) for day in DAYS for shift in FT_SHIFT_TIMES)
total_wages_pt = sum(work_pt[j, day, shift] * PT_HOURLY_WAGE * PT_SHIFT_LENGTH for j in range(PT_EMPLOYEES) for day in DAYS for shift in PT_SHIFT_TIMES)
model.setObjective(total_wages_ft + total_wages_pt, GRB.MINIMIZE)
Or just adding the above mentioned constraint will work?Thanks and RegardsSai Arvind Atluri0 
Hi Sai,
There is no need to change the objective function. It is just minimizing the total wages paid to the fulltime and parttime employees.
Adding the constraint will make sure that a parttime employee is not assigned to overlapping shifts in a day.
Best regards,
Simran0 
Hi Simran,
I understand that but we're having troubles in meeting the requirements of the part timers.
For the existing code we do not have any overlapping shifts but the requirements are not met. How can we make changes to the existing code so that the part time employee constraint requirements are met?
It's like we have a shifts for part timers assigned as below and during the 7am3pm there should be 3 part timers working at all times and the same applies for 3pm11pm. The requirements on each day are mentioned above in the initial question.PT_SHIFT_TIMES = ["7am11am", "8am12pm", "9am1pm", "10am2pm", "11am3pm", "12pm4pm", "1pm5pm", "2pm6pm", "3pm7pm", "4pm8pm", "5pm9pm", "6pm10pm", "7pm11pm"]
It would be of great help if you can help me in balancing this particular constraint. If i'm trying to make a change i'm getting infeasible solution.
Thanks and RegardsSai Arvind Atluri0 
Hi Sai,
The overlapping_shifts[i] in my previous comment represented the set of shifts that overlap with the time of shift i. For example,
overlapping_shifts["7am11am"] will be [ "7am11am", "8am12pm", "9am1pm", "10am2pm" ],
overlapping_shifts["8am12am"] will be [ "7am11am", "8am12pm", "9am1pm", "10am2pm", "11am3pm" ], and
overlapping_shifts["9am1pm"] will be [ "7am11am", "8am12pm", "9am1pm", "10am2pm", "11am3pm", "12pm4pm" ]i.e., in terms of indexes, we will have
overlapping_shifts[0] = [ 0, 1, 2, 3]
overlapping_shifts[1] = [ 0, 1, 2, 3, 4 ]
overlapping_shifts[2] = [ 0, 1, 2, 3, 4, 5 ] and so on...Please modify your code to construct these sets and add the nonoverlapping constraint discussed in the previous comment. I hope this helps!
Best regards,
Simran0 
Hi Siman,
I have implemented this in the Colab but the daily and hourly requirements of the parttime employees aren't met and that's my main concern. When i'm printing the O/P for part time employees the no. of employees working on Monday from 7am3pm has to be 3 at all times and that isn't satisfied. This condition has to be satisfied for everyday based on the requirements.
There's no overlap of shifts after implementing the above suggestion but how can i fix the hourly requirements.Just to give you an idea we have 19 part time employees and each of them will be working in 4hour blocks.
Can you help with it? I hope you're understanding on what I'm trying to explain.Thanks and RegardsSai Arvind Atluri0 
Hi Sai,
If I understand correctly, your requirement is "for each day and each morning/evening shift, there should be at least PT_REQ_FALL_SPRING[day]["Morning"] / PT_REQ_FALL_SPRING[day]["evening"] parttime employees."
For this, we must create a constraint for each day and shift. Please replace the following constraints in your code:
for day in DAYS: model.addConstr(sum(work_pt[j, day, shift] for j in range(PT_EMPLOYEES) for shift in PT_SHIFT_TIMES[:6]) >= PT_REQ_FALL_SPRING[day]["Morning"], f"pt_morning_coverage_{day}") model.addConstr(sum(work_pt[j, day, shift] for j in range(PT_EMPLOYEES) for shift in PT_SHIFT_TIMES[6:]) >= PT_REQ_FALL_SPRING[day]["Evening"], f"pt_evening_coverage_{day}")
with
for day in DAYS:
for shift in PT_SHIFT_TIMES[:6]:
model.addConstr(gp.quicksum(work_pt[j, day, shift] for j in range(PT_EMPLOYEES) ) >= PT_REQ_FALL_SPRING[day]["Morning"], f"pt_morning_coverage_{day}_{shift}")
for shift in PT_SHIFT_TIMES[6:]
model.addConstr(gp.quicksum(work_pt[j, day, shift] for j in range(PT_EMPLOYEES) ) >= PT_REQ_FALL_SPRING[day]["Evening"], f"pt_evening_coverage_{day}_{shift}")Please change the sense of the above constraints to equality if the requirement is to have exactly PT_REQ_FALL_SPRING[day]["Morning"] or PT_REQ_FALL_SPRING[day]["Evening"] number of constraints working in a shift.
Best regards,
Simran0 
Hi Simran,
Yes that's correct. 3 part time employees in the morning and 3 in the evening at every hour in a day during the mentioned hours 7am11pm.
Is there a possibility to connect in a different way? I'm getting a infeasible solution when i try to replace this constraint.
How can we can balance this particular constraint with a feasible solution by taking everything into consideration?Thanks and RegardsSai Arvind Atluri0 
Hi Sai,
The infeasibility in your model could be due to the input data, i.e. there is no feasible solution possible with the given data, or a bug in the code. To troubleshoot this, I would suggest the following:
 check if you can create a feasible solution for your problem by hand or with a heuristic for the given input data
 export the model in readable form to an LP file, with model.write("model.lp") immediately before calling optimize(). inspect this LP file to see if the model is built as per your expectations.
 run the Model.ComputeIIS() method on the infeasible model. It will let you know the smallest set of variables and constraints that make your model infeasible. Have a look at the article How do I use 'compute IIS' to find a subset of constraints that are causing model infeasibility?
Best regards,
Simran0 
Hi Simran,
I ran the following and generated the ILP file.My question might be stupid as I'm still new to working on Optimization models but how can we be troubleshoot from the file generated?
Please advise. Thanks a lot for helping so far!.Thanks and RegardsSai Arvind Atluri0 
Hi Sai,
You should be able to open the LP file with any text editor. You can crosscheck that the constraints are built as you would have expected logically. This will help to rule out any obvious bugs in the code.
Running the run Model.ComputeIIS() method on the infeasible model will also help to point to the constraints that cause the infeasibility. The article How do I use 'compute IIS' to find a subset of constraints that are causing model infeasibility? has a good example on how to use the computeIIS method.
Best regards,
Simran0 
Hi Simran,
Yes i did check the LP file just now. However, it looks like the part time constraint isn't working as expected. It's just showing the subject to for the morning and evening coverage from FriSun only and the no. of working hours less than or equal to 20 and bounds isn't set to anything.
Is there a way i can share the file with you so you can have a look? Unfortunately, this is something urgent and we need to fix it rightaway.Thanks and RegardsSai Arvind Atluri0 
Hi Sai,
Now that you have identified the constraints that are not built correctly, please debug the part of your code that builds these constraints.
Best regards,
Simran0
Please sign in to leave a comment.
Comments
13 comments