# Modelling problem with JuMP

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 …

1. has to be there equally often
2. only has to be there once every weekend (that’s why `n >= 8` is relevant)
3. is there the same number of mornings and evenings
4. is there the same number of Saturdays and Sundays
5. has a new partner every time (until they have to start from the beginning)
6. has the same time (in weeks) between each shift (as close as possible)
7. 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 `true`s 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?

Solving this with JuMP and a MIP solver like e.g. HiGHS should be doable. Since you are only looking for a feasible solution, constraint programming could also be a viable approach.

The distance between shifts could be modelled by requiring just a single shift for every M consecutive weeks. Something along these lines should work (but I have not tested)

``````# 6) ...only one shift per M consecutive weeks
M = nweeks ÷ nshifts_perperson
for i in 1:nperson, j in 1:nweeks-M
@constraint(model, sum(plan[i, i2, jj, k, l] for i2 in i+1:nperson, jj in j + M, k in 1:morning_evening, l in 1:sat_sun) <= 1)
end
``````
2 Likes

Thank you, this idea worked!

It takes quite long now to generate a solution (like ~9h) but at least I’m getting one.