Integer Programming Formulation for a Teacher Scheduling Problem

Question

I have the following problem im my revision list for my exam next week:

The set of teachers, schedule and classrooms to be used for the application of tests are given by X, Y and Z respectively: $X = \{1,2,3,...,10\}$ , $Y = \{1,2,3,...,15\}$ $Z = \{1,2,3,...,10\}$. Any teacher can apply a test at any time, in any room. The goal is to find the largest set of M combinations of teachers, schedules and classrooms so that each is unique. For example, given $(x, y, z) \in M$, if there exists another $(x', y', z') \in M$, then $x \neq x'$, $y \neq y'$, and $z \neq z'$. Present a linear model that solves this problem.

My solution so far is three binary variables that identify busy or unoccupied rooms, occupied or unoccupied schedules, and teacher busy or not, but I can not seem to get out of it. A friend of mine thought we would have to treat this problem as a three-dimensional space.

So, $$Zb_i = \begin{cases} 1, & \text{if classroom $z_i$ is unoccupied} \\ 0, & \text{if clasroom $z_i$ is busy} \end{cases}$$

$$Yb_i = \begin{cases} 1, & \text{if the hour $y_i$ is free} \\ 0, & \text{if the hour $y_i$ is busy} \end{cases}$$

$$Xb_i = \begin{cases} 1, & \text{if the teacher $x_i$ is free} \\ 0, & \text{if the teacher $x_i$ is busy} \end{cases}$$

And the objective function is:

$$ F(x,y,z) = \sum_{i=0}^n M $$

But I do not know how to leave this point.

Answer 1

I believe that your friend has a point. This is a 3D generalization of the assignment problem.

Variables:

Binary variable $w_{xyz} = 1$ if a test is scheduled for teacher $x$ at hour $y$ in classroom $z$, and zero otherwise.

For your example, there are 10*15*10 such binary variables.

Constraints:

1. Each teacher can only appear in at most one hourly time slot in at most one classroom: $$\sum_y \sum_z w_{xyz} \leq 1, \forall x.$$

2. Each classroom can only be occupied by at most one teacher in at most one hourly time slot: $$\sum_x \sum_y w_{xyz} \leq 1, \forall z.$$

3. In each hourly time slot, there can only be at most one exam: $$\sum_x \sum_z w_{xyz} \leq 1, \forall y.$$

Objective:

We are maximizing such combinations: $$\max \sum_x \sum_y \sum_z w_{xyz}.$$