Students in classroom problem - Flow in network

Question

I have room, which is opened some days in week, in different hours each day.

I have multiple students, each has time some days in week, in different hours.

Each student have to visit the room exactly once in the week, for exactly 50 minutes.

Room is unusable for 20 minutes after 2nd student the day, it means, that after the 2nd student have to be at least 20 minute break before 3rd. So something like this:
7:00-7:50
7:50-8:40
(20 mimutes break)
9:00-9:50
There is no break after 4th, 6th, ... student. Only after 2nd one.

How can I find best solution to this? I want to position all (or the most I can) students.

I've thought of using flow in network (see image). Groups (G1, G2, ...) group times (7:00, 7:05, ...) that are within 50 minutes of each other. Pairing student (S1, S2) with time would instantly disable any groups, that contains the time. But that would require to flow going IN->Student->Time-> to split into multiple groups ->Group1+Group2->OUT. How can I achieve this? How should I modify maximum flow search algorithms to do so?

Or is there better way how to do what I'm trying to accomplish?

Answer 1

The best way I can see to solve this is with integer linear programming. This is not a polynomial-time algorithm, but it might work well enough in practice. (I don't think network flow algorithms will work here.)

In particular, you introduce zero-or-one variables $x_{i,t}$, with the intent that $x_{i,t}=1$ means that student $i$ is scheduled in the room starting at time $t$, or $x_{i,t}=0$ otherwise. Then you add inequalities to ensure that these meet all of your requirements:

• $\sum_t x_{i,t} = 1$: each student is scheduled at a single time.

• $x_{i,t} + x_{j,t'} \le 1$ whenever $i \ne j$ and $t,t'$ are within 50 minutes of each other: no two students may be scheduled at an overlapping time.

Then you feed this to an off-the-shelf ILP solver and ask it for a feasible solution. The result is a valid schedule.

As described above, I have ignored the requirement about the 2nd student of the day. You can fix this by adding some extra variables and inequalities. Let $y_{i,t}=1$ if student $i$ is assigned at time $t$ and is the first student assigned that day, and $z_{i,t}=1$ if student $i$ is assigned at time $t$ and is the second student assigned that day. Then we have additional constraints:

• $y_{i,t} \le x_{i,t}$, $y_{i,t} + \sum_j \sum_{t' < t} x_{j,t'} \le 1$, $x_{i,t} - \sum_j \sum_{t' < t} x_{j,t'} \le y_{i,t}$, and $\sum_i \sum_{t \in D_k} y_{i,t} = 1$ where the last sum is over all $t$ that fall on day $k$ (on the same day). These ensure that the $y$'s are consistent with the $x$'s.

• $z_{i,t} \le x_{i,t}$, $z_{i,t} \le \sum_j \sum_{t' < t} y_{j,t'}$, $x_{i,t} - 2 + \sum_j \sum_{t' < t} (x_{j,t'} - M z_{j,t'}) \le z_{i,t}$, $\sum_i \sum_{t \in D_k} z_{i,t} = 1$ where the last sum is over all $t$ that fall on day $k$ (on the same day) and where $M$ is sufficiently large (e.g., at least the number of students). These ensure that the $z$'s are consistent with the $x$'s.

• $z_{i,t} + x_{j,t'} \le 1$ whenever $i\ne j$ and $t,t'$ are within 110 minutes of each other: this ensures a 20-minute gap after the second student of the day.

This should enforce the additional constraints. Double-check the formulation; I haven't checked it carefully, and there might be small errors in what I wrote. In general, Express boolean logic operations in zero-one integer linear programming (ILP) gives some helpful tips on encoding constraints into linear inequalities for ILP.