Hi there!
I have the following problem: I have n >= 8 people who are supposed to do a “shift” (this is not for a job but for a hobby. I would hope HR people know how to properly do this 
). There is one shift each on Saturday and Sunday, in the morning and in the evening (so 4 each weekend), in teams of 2. I now want to create a plan so that everyone …
- has to be there equally often
- only has to be there once every weekend (that’s why
n >= 8is relevant) - is there the same number of mornings and evenings
- is there the same number of Saturdays and Sundays
- has a new partner every time (until they have to start from the beginning)
- has the same time (in weeks) between each shift (as close as possible)
- a few more parts I’m going to worry about later
I’m trying to use constraints in JuMP and I managed to get the first 5 points working (although I’m sure it’s not very pretty).
using JuMP
using HiGHS
model = Model(HiGHS.Optimizer)
nperson = 14
nteams = sum(1:nperson-1) # Number of possible teams (person with a different person)
nweeks = nteams # So each team can have a shift on Saturday/Sunday, morning/evening each
npersonperteam = 2
sat_sun = 2
morning_evening = 2
nshifts_perperson = (npersonperteam * nweeks * sat_sun * morning_evening) ÷ nperson
# Each bit indicates which two people have a shift, each morning/evening of each
# Saturday/Sunday of each week
# E.g. plan[1, 2, 3, 1, 2] = 1 means person 1 and person 2 have a shift in third week,
# on Sunday (2) morning (1).
@variable(model, plan[1:nperson, 1:nperson, 1:nweeks, 1:morning_evening, 1:sat_sun], Bin)
# I'm mirroring the matrix so I can later sum over whole rows/columns
# This should also work with Symmetric constraints, but I couldn't get it to work
for i1 in 1:nperson, i2 in i1+1:nperson, j in 1:nweeks, k in 1:morning_evening, l in 1:sat_sun
@constraint(model, plan[i1, i2, j, k, l] == plan[i2, i1, j, k, l])
end
# each shift consists of 2 people = 1 Team (= 2 here since I mirrored the matrix)
for j in 1:nweeks, k in 1:morning_evening, l in 1:sat_sun
tst = @constraint(model, sum(plan[:, :, j, k, l]) == 2)
end
# a team can't be the same person twice
for i in 1:nperson, j in 1:nweeks, k in 1:morning_evening, l in 1:sat_sun
tst = @constraint(model, plan[i, i, j, k, l] == 0)
end
# 2) ... only has to be there once every weekend
for i in 1:nperson, j in 1:nweeks
@constraint(model, sum(plan[i, :, j, :, :]) <= 1)
end
# 3) ... is there the same number of mornings and evenings
for i in 1:nperson, k in 1:morning_evening
@constraint(model, sum(plan[i, :, :, k, :]) == nshifts_perperson ÷ 2)
end
# 4) ... is there the same number of Saturdays and Sundays
for i in 1:nperson, l in 1:sat_sun
@constraint(model, sum(plan[i, :, :, :, l]) == nshifts_perperson ÷ 2)
end
# 5) ... has a new partner every time
# implemented here a "has each partner the same amount of times"
for i1 in 1:nperson, i2 in i1+1:nperson
@constraint(model, sum(plan[i1, i2, :, :, :]) == 4nweeks ÷ nteams)
end
@objective(model, Min, 0)
optimize!(model)
p = round.(Int, value.(plan))
display(p)
Now I’m lost at point 6 since I don’t know how to get “distances” between the shifts out of the plan matrix. In normal Julia code I would count the indices between trues for each person in the matrix, but I don’t think this works in JuMP.
I also though about turning everything on its head, and instead modelling the time between each shift instead. However, then I don’t know how to check which people are there the same time (in order to limit them to two, for example).
Is something like this possible in JuMP or should I use a different tool?
