Mixed Integer Programming for time table scheduling

Using Python and mathematical modeling to solve scheduling problems

Back to school, one of the most time-consuming tasks for the academic year is to create a schedule that suits all teachers’ preferences, constraints, and can also take into account other requirements such as the maximum number of hours per subject and day or the capacity of the classrooms.

Wouldn’t be great if Maths could help us achieve this quickly, reliably, and efficiently?

In this article, we will explore how Mixed Integer Programming (or MIP) can help us create a class schedule, using the python library Pyomo, and the open-source solver CBC.

You can see the original article in Spanish here

Setting up the environment

My recommendation for installing Pyomo and CBC is to use pip and Conda. There are other methods to achieve this, but in my experience, the commands below are the most efficient and seamless route.

!pip install pyomo
!conda install -c conda-forge coincbc

Modeling

Now it is time to think about the decision that we want to make. If we think of a schedule as a grid of days and hours, then the decision would be to fit on each of those cells in the table the subject given in that particular day and hour.

Mathematically, we could think about this choice from a different perspective, adding a third dimension, all the possible subjects to be given and framing the problem not as an integer decision (assigning to each pair Day x Hour a subject index) but as a binary decision, where the variable vbSubjectSchedule[d, h, s] takes the value 1 when the subject s is given that (day x hour) and 0 otherwise.

In addition to the binary decision variable, we already have three different sets:

• sHours: hours of the day when a class can be given.
• sDays: days of the week for the schedule.
• sSubjects: the subjects to be scheduled.

Parameters

Parameters in a MIP model are taken as constants by the solver, meaning that none of the decisions will affect their values.

In our model, we will consider the following parameters:

• pHoursPerSubject: how many hours per week the subject has.
• pMinDaysPerSubject: least amount of days for a certain subject. This takes into account the direct constraint of the maximum daily hours for a subject.
• pMaxDaysPerSubject: maximum days for a particular subject. The default is as many as hours it has, but we can constrain that prior to modeling, for any particular subject, as it is indexed individually on each.
• pPreferences: particular preferences of the teachers of every subject. E.g. teacher of subject 1 prefers 5 times more giving their course on Monday at 10:30, then pPreferences[‘Mon’,’10:30',’SBJ_1'] = 5.

Helper variables

Helper or auxiliary variables are not decision variables per se but make the modeling process easier and clearer and help us store values that can then be easily accessed after solving the mathematical model.

We will use these in our model:

• vbSubjectDaysFlags: takes the value 1 if the subject is scheduled for that day.
• vIcumulatedHours: cumulative number of hours for a subject in a day x hour. This will help us with modeling the constraints.
• vIsubjectTotalDays: total number of days for all subjects. We will use this variable as a penalty
• vbSubjectSwitches: to control if the same subject is given the previous hour. Also used to model some of the constraints.

Objective function

The objective function in our problem is easy, we want to maximize the total welfare of the teachers, so we will sum the product of their preferences across the different day x hour multiplied by the decision variable vbSubjectSchedule[d, h, s].

Moreover, we will subtract from the total welfare a penalty M multiplied times the total number of days for the subjects, gathered in the variable vIsubjectTotalDays, as we are interested in having the least amount of days per subject possible .

Constraints

If we now try to solve the model, all the binary variables will be set to 1, in order to maximize the sum of the preferences. We need to constrain our model to bring the reality of the business use case to live.

• Single assignment constraint: only one subject can be given at the same day and hour.

single assignment constraint

• Cover all subject hours: the number of hours scheduled for a subject must be the total weekly hours.

Schedule all weekly hours

• The total amount of daily hours per subject must respect the maximum possible. This is controlled using two different constraints, the first one is imposed as a hard constraint, with the total scheduled hours always being lower than or equal to maxHoursPerDay whereas the second one is used to activate the flag vbSubjectDaysFlags.

Activate the flag helper variable if the subject is given that day

• If there are any constraints regarding the minimum / maximum number of days for a particular subject, this can also be controlled with an additional set.

control the minimum and maximum days per subject

Now, solving the problem will provide us with a schedule that maximizes the preferences but we will find that a subject is scheduled in arbitrary hours of the day, for instance, the first and the fourth.

We want to avoid this behavior, as it will be impractical in the real world. Using some mathematical tricks to achieve this goal:

• We log in the variable vbSubjectSwitches every time the assignment for that subject and day differs from the previous hour, to identify when a subject starts or ends. This is controlled using the constraint group ctSubjectSwitches and modelling it as an absolute value, that way, the value of vbSubjectSwitches will be 1 regardless of being the first or last hour of the subject.
  Mathematically, we can model an absolute value linearly this way:

absolute value modeling to capture schedule changes

• Moreover, in the code we can see that the set of hours is circular, to be able to control subjects starting or ending at the beginning or end of day, respectively.
• The sum of vbSubjectSwitches, assuming that they are given in consecutive blocks can be either 2, if the subject is scheduled for that day or 0 otherwise. This is controlled using the constraint:

Lastly, we add the variable that we will use as an accumulator for the penalty of the objective function, which will try to find a solution with the least amount of days per subject possible.

penalty accumulator for the objective function

Testing the model

In my github repository you have access to the scheduler model and a test. In our example:

• Days: l (Monday) to v (Friday).
• Hours: 10:00 to 14:00.
• Subjects: SB_0 to SB_7.
• All subjects with 2 hours per week and 4 hours to be added at random.
• Maximum of 2 hours per subject per day.
• Preferences: subject 3 preferably scheduled Mondays at 11, with a weight of 4.
• Constraints: subject 1 must be scheduled on Mondays at 12.

After solving the model, we can check in the solution that:

• The subjects are scheduled with a maximum of 2 hours per day.
• In consecutive blocks.
• Subject 3 is scheduled on Monday at 11.
• Subject 1 is scheduled on Monday at 12.

Conclusions

• In this article we have used mathematical modeling to create the best schedule possible given a set of constraints.
• Pyomo and python provide a clean way to translate the mathematical model into code.
• This model has been tailored for a base use-case, but could be adapted to other scenarios by deactivating some of the constraints or expanding them.