Staff Scheduling Optimization

[Honcho868]

So im trying to code the following model from the paper in JuMP to determine optimal number of staff for 3 shifts daily for 7 days a week where staff must work atleast 1 shift per day

This is the code:

using JuMP
using HiGHS
Wjk = [
    19 16 22 22 22 22 22
    19 16 22 22 22 22 22
    14 11 16 16 16 16 16
]
J, K = size(Wjk)
Ajk = 8
N = 100  #Upper limit
model = Model(HiGHS.Optimizer)
@variable(model, x[1:N, 1:J, 1:K], Bin)
@variable(model, y[1:N], Bin)
@objective(model, Min, sum(x))
@constraint(model, [i in 1:N], sum(x[i, :, :]) <= J * K * y[i])  # y[i] is 1 if employee i is used
@constraint(model, [i in 2:N], y[i-1] >= y[i])  # Ordering on y[i]. If we don't use y[i-1], then we can't use y[i]
@constraint(model, [i in 1:N, k in 1:K], x[i,1,k] + x[i,2,k] + x[i,3,k] <= 2)  # Constraint (8)
@constraint(model, [i in 1:N, k in 1:K], x[i,2,k] + x[i,3,k] + x[i,1,k%7+1] <= 2)  # Constraint (9)
@constraint(model, [i in 1:N, k in 1:K], x[i,3,k] + x[i,1,k%7+1] + x[i,2,k%7+1] <= 2)  # Constraint (10)
@constraint(model, [j in 1:J, k in 1:K], sum(x[:,j,k]) >= Wjk[j,k])  # Constraint (11)
@constraint(model, [j in 1:J, k in 1:K], sum(x[:,j,k]) <= Wjk[j,k] + Ajk)  # Constraint (12)
@constraint(model, [i in 1:N], sum(x[i,j,(i-1)%7+1] + x[i,j,i%7+1] for j in 1:J) == 0)  # Constraint (13)
@constraint(model, [i in 1:N, k in 1:5], sum(x[i,j,(i+k)%7+1] for j in 1:J) >= y[i])  # Constraint (14)

optimize!(model)
status = termination_status(m)
println("Solution status: ", status)
println("Number of Employees: ", N)
println("Optimal Shift Allocation:")
for i in 1:N, j in 1:J, k in 1:K
    if value(x[i, j, k]) > 0.5
        println("Employee $i, Shift $j on Day $k")
    end
end

Although its producing results, the model is infeasible and the number of employees is always the upper limit of 100

[Honcho868]

This is from the paper

[odow]

Note that you have

status = termination_status(m)

but your model is called model. You’re looking up the termination status of some other JuMP model.

Also note that you’ve asked to minimise the number shifts worked. The objective does not have a component to minimise the distinct number of employees.

Also note that:

println("Number of Employees: ", N)

you’re just printing out the constant N. If you do:

println("Number of Employees: ", sum(value.(y)))

You’ll find that you’re using 48 employees.

[Honcho868]

ahhhhh such a silly error, ok i understand now. Thank you

I just noticed the the status error as well as you mentioned it so thank you for that too.

[odow]

No problem

[Honcho868]

I know the variable y is for whether an employee worked a shift or not. What do the constraints below determine, mainly the second of the 2

@constraint(model, [i in 1:N], sum(x[i, :, :]) <= J * K * y[i])  # y[i] is 1 if employee i is used
@constraint(model, [i in 2:N], y[i-1] >= y[i])  # Ordering on y[i]. If we don't use y[i-1], then we can't use y[i]

[odow]

Where did you get the code from? Did you not write the comments?

The first constraints say that if y[i] == 0 then all of the x[i variables must be zero.

The second is a symmetry breaking constraint that does not change the optimal objective value, but ensures that the y are used in order. Otherwise there would be many more equivalent solutions with different permutations of y.

[Honcho868]

Yeah i adapted the code from the previous thread because i didnt have a y variable originally in mine. I understood the first constraint wrt to the variable created for y, was just a little hazy on the second one but i understand it now. It simply ensures that the model doesnt skip any of the employees when determining an optimal solution so y[i-1] must be equal to 1 (have worked a shift) before y[i] can work a shift.