# Beginners question: how to formulate this assignment/scheduling problem?

Hi all,
I’m quite new to mathematical programming. I try to solve this seemingly simple problem:

I have `N` speakers and `M > N` slots for talks. Each slot can hold a single talk. Other constrains may be added. How should I distribute the slots so that the time a speaker has to wait between each of her talks is “as regular as possible”?

I thought that would be an easy MIP problem. I could expressed the assignments in a matrix with binary variables and defining the constrains. However, I’m completely lost how to formulate a objective function that gives “regular intervals”.
For example, if we have 3 speakers and 6 slots, this would be a good assignments (everybody has to way 3 slots):

``````A1 = [ 1 0 0;
0 1 0;
0 0 1;
1 0 0;
0 1 0;
0 0 1]
``````

but this not (because the third speaker gives two talks in a row):

``````
A2 = [1 0 0;
0 1 0;
0 0 1;
0 0 1;
0 1 0;
1 0 0]
``````

I know that is not really a Julia question, but I’d be very grateful for every hint!

1 Like

There is a stackexchange for more modeling type questions: https://or.stackexchange.com

You could, for example, add constraints like this which limit the ability to have back-to-back talks:

``````for m in 2:(M - 1)
@constraint(model, sum(x[(m - 1):(m + 1)]) <= 1)
end
``````

Otherwise a common approach to this is to generate a bunch of columns in your matrix a priori, assign a binary variable for each column/speaker pair (indicating if the speaker has talks for the column) and then have constraints saying that the sum across the row has to be <= 1 (at most one talk per slot) and that each speaker has to pick one column. Then your objective coefficients can measure how “regular” the talks in a particular column are. But a naive implementation can scale poorly as M gets large.

This is a perfect Julia question because people like @oxinabox have had to slot M speakers for N slots for JuliaCon (with even more constraints) and they can probably share what software they use.

1 Like

Thank a lot @odow for the link and the ideas!

I finally came up with this solution. The key insight was that we already know an optimal solution as long we don’t have any constrains (e.g. matrix `A1` in the post above). Then we can permutate the rows until all constrains are met. The objective function measures how many and how large the permutations are. This was a fun little exercise

``````using JuMP
using GLPK

N = 3                           # number of speaker
M = 5                           # number of slots

# Optimal assignment matrix of talks *ignoring the constrains*
A0 = [rem(i-1, N)+1 == j for i in 1:M, j in 1:N]

model = Model(GLPK.Optimizer)

# Permutation matrix to swap rows, hence assignments matrix = P*A0
@variable(model, P[1:M, 1:M], Bin);
@constraint(model, sum(P, dims=1) .== 1);
@constraint(model, sum(P, dims=2) .== 1);

@constraint(model, speaker1, (P*A0)[1,1] == 0) # speaker 1 cannot talk at slot 1
@constraint(model, speaker2, (P*A0)[4,2] == 1) # speaker 2 must talk at slot 4

# Cost matrix for permutation matrix. Penalizes off diagonal elements (i.e. wide swaps).
C = [abs(i-j) for i in 1:M, j in 1:M];
@objective(model, Min, sum(C .* P));

# Optimize
optimize!(model)
termination_status(model)

# Final assignment matrix with constrains
Popt = Int.(value.(P));
Popt*A0
``````

I wrote code for this, but never deployed it.

Here it is. Based on Convex.jl

Its been a while since i looked at it.

I have been doing schedulling by hand as collecting the data to decide it is hard.

I had to do something like this in real life and I asked a question on stack overflow. One responder really went above and beyond and coded up a solution that seemed pretty amazing to me at the time (in python). I should go back and try to do it in Julia…