Mathematical model¶
The scheduler works by solving a well understood mathematical problem called an integer linear program [Dantzig1963], [Schaerf1999].
If we assume that we have \(M\) events and \(N\) slots, then the schedule is mathematically represented by a binary matrix \(X\in\{0, 1\}^{M\times N}\). Every row corresponds to an event and every column to a slot:
From that we can build up various constraints on what is a valid schedule.
The constraints¶
All events must be scheduled¶
For every row (event), we sum over every column of \(X\) and must have total sum 1.
All slots cannot have more than one event¶
For every column (slot), we sum over every row of \(X\) and must have total sum at most 1.
This in itself would give a basic schedule for a conference however things can be a bit more complicated:
- Some slots can be in parallel with each other (for example because of multiple rooms);
- Slots and events might have different duration;
- It might be desirable to have some common thread for talks in a collections of slots (for example: the morning session)
The mathematical representation for these constraints will be described below.
Events are only scheduled in slots for which they are available¶
There are multiple reasons for which an event might not be available in a given slot: perhaps the speaker is unavailable on a given day.
These constraints can be captured using a matrix \(C_s\in\{0, 1\}^{M\times N}\):
This gives the following constraint:
Two events are scheduled at the same time only if they are available to do so¶
Any two given events might not be able to occur concurrently: two events could be delivered by the same speaker, or they could be about a similar topic.
This constraint is captured using a matrix \(C_{e}\in\{0, 1\}^{M\times M}\):
Using this, we define the following set for every slot \(j\):
Using this we have the following constraint:
We see that if \({C_{e}}_{ii'}=0\) then at most one of the two events can be scheduled across the two slots \(j,j'\).
Expressions (2), (3), (5), and (8) define a valid schedule and can be used by themselves.
However, it might be desirable to also optimise a given objective function.
Objective functions¶
Efficiency: Optimising to avoid total room overflow¶
Demand for events might be known: this will be captured using a vector \(d\in\mathbb{R}_{\geq 0}^{M}\). Similarly capacity for rooms might be known, captured using another vector \(c\in\mathbb{R}_{\geq 0}^{N}\). Whilst it might not be possible to stick to those constraints strongly (when dealing with parallel sessions delegates might not go where they originally intended) we can aim to minimise the expected overflow given by the following expression:
Using this, our optimisation problem to give a desirable schedule is obtained by solving the following problem:
Equity: Optimising to avoid worse room overflow¶
Minimising (9) might still leave a given slot with a very large overflow relative to all over slots. We can aim to minimise the maximum overflow in a given slot given by the following expression:
Note that it is not possible to use \(\max\) in the objective function for a linear program (it is none linear). However, instead we can define another variable: \(\beta\) as the upper bound for the overflow in each slot:
The objective function then becomes to minimize:
Using this, our optimisation problem to give a desirable schedule is obtained by solving the following problem:
Consistency: Minimise change from a previous schedule¶
Once a schedule has been obtained and publicised to all delegates, a new constraint might arise (modifying (2), (3), (5) and (8). At this point the original optimisation problem can be solved again leading to a potentially completely different schedule. An alternative to this is to use distance from an original schedule \(X_o\) as the objective function. Norms on matrix spaces are usually non linear however, given the boolean nature of our variables, the following function can be used to measure the number of changes:
where \(\delta:\{0,1\}^{2}\to\{0,1\}\) is given by:
Using this it is possible to obtain a schedule that is least disruptive from another schedule when presented with new constraints by solving the following problem: