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

Specific Domains Optimization (Mathematical)
1

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
2

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.

3

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
4

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 :slight_smile:

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);

# Add constrains of speakers
@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
5

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.

6

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…