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:

(1)\[\begin{split}X_{ij} = \begin{cases} 1,&\text{ if event }i\text{ is scheduled in slot }j\\ 0,&\text{otherwise} \end{cases}\end{split}\]

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.

(2)\[\sum_{j=1}^{N} X_{ij} = 1\text{ for all }1\leq i\leq M\]

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.

(3)\[\sum_{i=1}^{M} X_{ij} \leq 1\text{ for all }1\leq j\leq N\]

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}\):

(4)\[\begin{split}{C_{s}}_{ij} = \begin{cases} 1,&\text{ if event }i\text{ is available in slot }j\\ 0,&\text{otherwise} \end{cases}\end{split}\]

This gives the following constraint:

(5)\[ X_{ij} \leq {C_{s}}_{ij}\text{ for all }1\leq i\leq M,\,1\leq j\leq N\]

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}\):

(6)\[\begin{split}{C_{e}}_{ii'} = \begin{cases} 1,&\text{ if event }i\text{ is available during event }i'\\ 0,&\text{otherwise} \end{cases}\end{split}\]

Using this, we define the following set for every slot \(j\):

(7)\[S_j = \{1\leq j'\leq N\,|\,\text{ if }j\text{ and }j'\text{ are at the same time}\}\]

Using this we have the following constraint:

(8)\[ X_{ij} + X_{i'j'} \leq 1 + {C_{e}}_{ii'}\text{ for all }j'\in S_j\text{ for all }1\leq j\leq N\text{ for all }1\leq i,i'\leq M\]

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:

(9)\[\sum_{i=1}^{M}\sum_{j=1}^{N}X_{ij}(d_i - c_j)\]

Using this, our optimisation problem to give a desirable schedule is obtained by solving the following problem:

Minimise (9) subject to (2), (3), (5) and (8).

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:

\[\max_{i,j}X_{ij}(d_i - c_j)\]

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:

(10)\[X_{ij}(d_i - c_j) \leq \beta \text{ for all }0\leq i\leq N\text{ for all }1\leq j\leq M\]

The objective function then becomes to minimize:

(11)\[\beta\]

Using this, our optimisation problem to give a desirable schedule is obtained by solving the following problem:

Minimise (11) subject to (2), (3), (5), (8) and (10).

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:

(12)\[\sum_{i=1}^{M}\sum_{j=1}^{N}\delta({X_o}_{ij}, X_{ij})\]

where \(\delta:\{0,1\}^{2}\to\{0,1\}\) is given by:

(13)\[\begin{split}\delta(x_o, x) = \begin{cases} x,&\text{ if } x_o=0\\ 1-x,&\text{ if } x_o=1 \end{cases}\end{split}\]

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:

Minimise (12) subject to (2), (3), (5), and (8).