Problem: Hard constraints have the effect of soft constraints
Ongoing
Hello, this is a staff scheduling model.
1. The maximum continuous working time, the constraint 3 has almost no effect on the model. But if I use the "range (sD1,
sD1 + MAX) " to " range (nD) ", it will have a big impact on the result and I will get the result that should get when using" range (sD1, sD1 + MAX) ".
2. The minimum continuous working time, the constraints 4 will have a greater impact on the model than the maximum, but nonetheless violations of the restriction can be observed in the results.
3. The "prohibited sequence" restriction affects the model, but cannot completely prohibit this "sequence".
After each run there will be a "violation". Without changing any other parameters, removing this restriction will result in a large number of "violations". This restriction appears to be a "soft restriction"
The constraints mentioned above are all hard constraints.
How should I solve these problems?
Following is code:
import gurobipy
# Development of model
from gurobipy import Model
nE = 9 #number of employees
EMPLOYEE = ["SMITH", "JOHNSON", "WILLIAMS", "JONES", "BROWN","DAVIS", "MILLER", "WILSON", "MOORE",]
nS = 3 #number of types of shifts
nD = 7 #number of days in the planning cycle 7
MIN = 1 #minimum number of consecutive working days 4
MAX = 5 #maximum number of consecutive working days 7 (LV:5)
aS = 2 # object of allowable sequence: N(2)-N(2), N(2)-B
uaS = range(2) # unallowable sequence
Dem = [[2, 2, 2, 2, 2, 2, 2], [2, 2, 2, 3, 3, 3, 2], [2, 2, 2, 2, 2, 2, 2]] #daily demand for each working shift s
MODEL: Model = gurobipy.Model("TSP")
# Decision variables
# Variables x are decision variables. Variables b, aux, z are auxiliary variables.
x = MODEL.addVars(EMPLOYEE, range(nS), range(nD), vtype=gurobipy.GRB.BINARY)
b = MODEL.addVars(EMPLOYEE, range(nS), range(nD), vtype=gurobipy.GRB.BINARY)
# Update
MODEL.update()
# Objective function
MODEL.setObjective(gurobipy.quicksum(x[d, i, j]
for d in EMPLOYEE
for i in range(nS)
for j in range(nD)),
sense = gurobipy.GRB.MINIMIZE)
# Constraints
# Constraints1:Assigned only one shift or day off a day
MODEL.addConstrs(gurobipy.quicksum(x[e, i, j]
for i in range(nS)) <= 1
for e in EMPLOYEE
for j in range(nD))
# Constraints2:Daily demand must be met
MODEL.addConstrs(gurobipy.quicksum(x[e, i, j]
for e in EMPLOYEE) >= Dem[i][j]
for i in range(nS)
for j in range(nD))
# Constraints3:Maximum number of consecutive working days TODO
MODEL.addConstrs(gurobipy.quicksum(x[e, i, j]
for i in range(nS)
for j in range(sD1, sD1 + MAX)) <= MAX
for sD1 in range(nD - MAX)
for e in EMPLOYEE)
# Auxiliary variables
MODEL.addConstrs(b[e, i, j] >= x[e, i, j]
for e in EMPLOYEE
for i in range(nS)
for j in range(nD))
# Constraints4:Minimum number of consecutive working days TODO
MODEL.addConstrs(gurobipy.quicksum(x[e, i1, j]
for i1 in range(nS)
for j in range(sD2, sD2 + MIN)) >= MIN * b[e, i2, sD2] for i2 in range(nS)
for e in EMPLOYEE
for sD2 in range(nD - MIN) )
# Constraints5: Recommended sequences TODO
MODEL.addConstrs(x[e, aS, j] * x[e, i, j+1] == 0
for e in EMPLOYEE
for i in uaS
for j in range(1, nD - 1))
# optimize
MODEL.optimize()
# output the optimal solution
if MODEL.status == gurobipy.GRB.Status.OPTIMAL: # Status codes: 2
solution = [k for k, v in MODEL.getAttr('x', x).items() if v == 1]
for e, i, j in solution:
print(f"{e} works the {i} shift on {j}")
for we in range(nD):
member = [e for e, i, j in solution if we == j ]
print(f'The member of staff who works the shift on {we} : {",".join(member)}')
-
Official comment
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?. -
Hi Zeyang,The real issue is that the constraints do not accurately model the requirements such as maximum and minimum limits on the number of consecutive working days for each employee.To ensure the accurate implementation of the constraints, it is recommended to first represent each mathematically.Following your notation, we have:
- \(x_{eij}\) equals 1 if employee \(e\) is assigned to shift \(i\) on day \(j\) and 0, otherwise
- \(y_{ej}\) equals 1 if employee \(e\) is working on day \(j\) and 0, otherwise [this is a new variable to use instead of \(b\)]
Before implementing the constraints enforcing the maximum and minimum limits on the number of consecutive working days, let us formulate the relationship between the variables \(x_{eij}\) and \(y_{ej}\).- If \(\sum_i x_{eij} = 1\) \(\Rightarrow\) \(y_{ej} = 1\) \(\forall e, j\)
- If \(\sum_i x_{eij} = 0\) \(\Rightarrow\) \(y_{ej} = 0\) \(\forall e, j\)
Note that we already know that each employee can be assigned to at most one shift per day (\(\sum_i x_{eij} \leq 1, \forall e, j\)). The above constraints are logically equivalent to:- If \(y_{ej} = 0\) \(\Rightarrow\) \(\sum_i x_{eij} = 0\) \(\forall e, j\)
- If \(y_{ej} = 1\) \(\Rightarrow\) \(\sum_i x_{eij} = 1\) \(\forall e, j\)
Since the indicator variable is binary, we can implement these two constraints using the Model.addGenConstrIndicator() method.
Using the auxiliary variables \(y_{ej}\), it is now easier to implement the maximum and minimum limits on the number of consecutive working days:
- Maximum Limit
- If \(y_{ej} = 1\) \(\Rightarrow\) \(\sum_{k \in S_j} \sum_i x_{eik} \leq \mbox{MAX}\) \(\forall e, j\) where \(S_j=\{k | j -\mbox{MAX} < k < j + \mbox{MAX}\}\)
- Minimum Limit
- If \(y_{ej} = 1\) \(\Rightarrow\) \(\sum_{k \in S_j} \sum_i x_{eik} \geq \mbox{MIN}\) \(\forall e, j\) where \(S_j=\{k | j -\mbox{MIN} < k < j + \mbox{MIN}\}\)
Note that the set \(S_j\) should include all days before and after day \(j\) because variables \(x_{eij}\) do not represent the start working day for employee \(e\). This was the main issue with your implementation.
See the snippet attached for the implementation of the above. The indicator constraints are implemented using the overload form. The constraints associated with the "prohibited sequences" are removed because I could not fully understand what they mean. Hopefully, you can implement them given the above changes. If not, please clarify what this set of constraints does.
I did run the snippet below using your data and the maximum and minimum limits are now enforced.
m = gp.Model("employee_scheduling")
# Decision variables
x = m.addVars(EMPLOYEE, range(nS), range(nD), vtype=gp.GRB.BINARY, name="x")
y = m.addVars(EMPLOYEE, range(nD), vtype=gp.GRB.BINARY, name="y")
# Objective function
m.setObjective(x.sum(), sense=gp.GRB.MINIMIZE)
# Constraints 1: Each employee is assigned to at most on one shift per day
m.addConstrs(x.sum(e, "*", j) <= 1 for e in EMPLOYEE for j in range(nD))
# Constraints 2: Demand
m.addConstrs(x.sum("*", i, j) >= Dem[i][j] foriinrange(nS) forjinrange(nD))
# New Constraints enforcing the relationship between x and y
m.addConstrs(
((y[e, j] == 1) >> (x.sum(e, "*", j) == 1)) for e in EMPLOYEE for j in range(nD)
)
m.addConstrs(
((y[e, j] == 0) >> (x.sum(e, "*", j) == 0)) for e in EMPLOYEE for j in range(nD)
)
# Constraints 3: Maximum limit on the number of consecutive working days
m.addConstrs(
(
(y[e, sD1] == 1)
>> (
gp.quicksum(
x.sum(e, "*", j)
for j in range(max(0, sD1 - MAX + 1), min(sD1 + MAX, nD))
)
<= MAX
)
)
for sD1 in range(nD)
for e in EMPLOYEE
)
# Constraints 4: Minimum limit on the number of consecutive working days
m.addConstrs(
(
(y[e, sD1] == 1)
>> (
gp.quicksum(
x.sum(e, "*", j)
for j in range(max(0, sD1 - MIN + 1), min(sD1 + MIN, nD))
)
>= MIN
)
)
for sD1 in range(nD)
for e in EMPLOYEE
)
m.optimize()Best regards,
Maliheh
0 -
Hello Maliheh,
Thank you for your help.
Would you like to explain it, "Note that the set should include all days before and after day j.... "? Why do I need to consider both parts, before and after the time point, , that means the width of the time window is 2*MAX instead of MAX?
0 -
Hi Zeyang,
Would you like to explain it, "Note that the set Sj should include all days before and after day j.... "? Why do I need to consider both parts, before and after the time point, xeij, that means the width of the time window is 2*MAX instead of MAX?
Maybe my previous explanation was not clear enough. The decision variable \(x_{eij}\) only tells us whether employee \(e\) is working on day \(j\) or not. We do not know if day \(j\) is the first working day of employee \(e\), it is the second day, or the final day, for example. Since we do not know employee \(e\)'s first working day, we need to account for the sum of all consecutive days where day \(j\) might be the first or the last working day of employee \(e\). That's why the width of the time window considered here is 2*MAX and 2*MIN. Hope it is clear now.
Best regards,
Maliheh
0 -
Hello Maliheh,
Thanks for the explanation. Now I understand why the boundarys are set like this. Your solution solved all my problems.
Best regards,
Zeyang
0
Post is closed for comments.
Comments
5 comments