# Beginners question: how to formulate this assignment/scheduling problem?
**URL:** https://discourse.julialang.org/t/beginners-question-how-to-formulate-this-assignment-scheduling-problem/39681
**Category:** Optimization (Mathematical)
**Created:** [May 18, 2020, 8:06am UTC](https://discourse.julialang.org/t/beginners-question-how-to-formulate-this-assignment-scheduling-problem/39681 "2020-05-18T08:06:39Z")
**Posts on this page:** 6
**Page:** 1
### Author:  [@scheidan](https://discourse.julialang.org/u/scheidan)
#### Post date: [May 18, 2020, 8:06am UTC](https://discourse.julialang.org/t/beginners-question-how-to-formulate-this-assignment-scheduling-problem/39681/1 "2020-05-18T08:06:39Z")
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):
```Julia
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):
```Julia
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!
---
### Author:  [@odow](https://discourse.julialang.org/u/odow)
#### Post date: [May 18, 2020, 1:18pm UTC](https://discourse.julialang.org/t/beginners-question-how-to-formulate-this-assignment-scheduling-problem/39681/2 "2020-05-18T13:18:36Z")
There is a stackexchange for more modeling type questions: [https://or.stackexchange.com](https://or.stackexchange.com)
You could, for example, add constraints like this which limit the ability to have back-to-back talks:
```nohighlight
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.
---
### Author:  [@miguelraz](https://discourse.julialang.org/u/miguelraz)
#### Post date: [May 18, 2020, 2:45pm UTC](https://discourse.julialang.org/t/beginners-question-how-to-formulate-this-assignment-scheduling-problem/39681/3 "2020-05-18T14:45:19Z")
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.
---
### Author:  [@scheidan](https://discourse.julialang.org/u/scheidan)
#### Post date: [May 18, 2020, 4:06pm UTC](https://discourse.julialang.org/t/beginners-question-how-to-formulate-this-assignment-scheduling-problem/39681/4 "2020-05-18T16:06:25Z")
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 🙂
```nohighlight
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
```
---
### Author:  [@oxinabox](https://discourse.julialang.org/u/oxinabox)
#### Post date: [May 18, 2020, 8:57pm UTC](https://discourse.julialang.org/t/beginners-question-how-to-formulate-this-assignment-scheduling-problem/39681/5 "2020-05-18T20:57:31Z")
I wrote code for this, but never deployed it.
Here it is. Based on Convex.jl
> **[Jupyter Notebook Viewer](https://nbviewer.org/gist/oxinabox/124dd3160ff970ec202283cf564524fc)**
>
> Check out this Jupyter notebook!
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.
---
### Author:  [@kevbonham](https://discourse.julialang.org/u/kevbonham)
#### Post date: [May 19, 2020, 1:38am UTC](https://discourse.julialang.org/t/beginners-question-how-to-formulate-this-assignment-scheduling-problem/39681/6 "2020-05-19T01:38:22Z")
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](https://stackoverflow.com/a/35031350/3742902) that seemed pretty amazing to me at the time (in python). I should go back and try to do it in Julia…