Case—School Timetabling Problem: A Scheduling Problem for High-School Institutions

1. Introduction

Johanna is the principal of a large Catholic academic institution located in the city of Guayaquil, Ecuador. This academic institution provides high-quality, low-cost education to almost 2,000 students from different socioeconomic backgrounds. To provide access to more students in the city, the institution operates using two schedules, namely, a morning schedule and an afternoon schedule. As in all academic institutions in Ecuador, the students are divided into two main groups, namely, primary and secondary education. In secondary education, students must pass six levels to reach graduation and to be able to advance to a university.

One of the biggest problems faced each year by Johanna’s institution is the construction of class schedules for each academic level. Because many institutions look to reduce costs, teachers usually give lectures to more than one section per level and more than one level per academic year. In the scientific literature, this problem is known as the school timetabling scheduling problem, which is one of the most challenging problems to solve computationally.

2. The Scheduling Problem

Johanna used to build class schedules by hand using heuristic methods. However, as she has recently been promoted to principal, she no longer has enough time to invest in the class scheduling problem. For this reason, she called on Gabriela and Javier, the institution’s alumni experts in operations research (OR), for help. In a recent meeting, Gabriela and Javier highlighted some critical issues about the problem at hand. Afterward, Johanna shared data about the number of weekly hours that each subject must be allocated. These data are available in Table 1.

Table 1. Data About the Subjects

Below is an excerpt from the conversation between Johanna and the OR experts that describes the problem to be solved:

• Johanna: Hi, Gabriela and Javier. It is nice to see you again. It has been a long time since you graduated from this school.

• OR experts: Hi, Johanna. Yes. We used to compete in math and chess tournaments many years ago. We won many of them.

• Johanna: Exactly. Currently, I am the principal of the high school, so I do not have enough time to prepare the chess and math teams and build the class schedules as I used to do. I know you hold a bachelor’s and a master’s degree in operations research, so I think you can help me with this problem.

• OR experts: Sure. Tell us more about your problem.

• Johanna: As may you remember, in the high school, we have six levels. The first three levels share the same subjects and occasionally the same teachers between levels, whereas the last three levels have different subjects and teachers; however, some subjects are shared between them, although the study plans of these subjects are different.

• OR experts: Yes, we remember that. Do the first three levels share teachers with the last three levels?

• Johanna: No, they don’t.

• OR experts: So, if they don’t share teachers, then we can deal with them as separate but similar problems.

• Johanna: I suppose that is correct.

• OR experts: Let us focus on the first three levels. How many sections¹ per level are there?

• Johanna: There are four sections per level. For each subject, the teacher is the same for each of the four sections.

• OR experts: Do the teachers share subjects with the other levels?

• Johanna: Usually not. Only in special cases or for few hours² every week do subjects require the teacher to give lectures to the other levels. For example, the subject of music consists of only a few hours per week. Therefore, the teacher is assigned to more than one level during the academic year.

• OR experts: For the sake of simplicity, we will assume that the teachers do not give lectures to other levels. Therefore, we can focus only on one level. This will allow us to build a simple prototype; later, we can drop this assumption to obtain a more realistic solution approach.

• Johanna: Okay.

• OR experts: For each section within a level, which conditions or limitations do you consider when building the class schedule?

• Johanna: There are many limitations we have to consider. First, we can allocate any subject up to two hours per day. If we allocate these two hours to a subject, then they must be consecutive hours either before or after the break.

• OR experts: So, if you allocate one hour before the break and one hour immediately after the break, this does not count as two consecutive hours, does it?

• Johanna: Exactly.

• OR experts: Let’s continue.

• Johanna: We have a new system for English classes. The students of all sections in the same level go to the English laboratory simultaneously. For this reason, English classes must be scheduled for the same hour in all sections.

• OR experts: Oh! That’s new! Therefore, if we schedule the English class for one section for the first hour on Tuesday, then all the other sections in the same level must also have English scheduled for the first hour on Tuesday.

• Johanna: Yes!

• OR experts: Can you vary the hour on other days or must it remain the same?

• Johanna: You can vary the hour between days as long as it is the same for all sections on that day.

• OR experts: Okay.

• Johanna: Some special subjects have to be allocated two consecutive hours on the day they are scheduled. These subjects are music, sports, and computing.

• OR experts: That’s because these subjects are given for only two hours per week, right?

• Johanna: Yes. Additionally, it is done this way because the students have to go to the coliseum, the computer laboratory, or the music room to take these classes. We try to minimize the flow of students inside the buildings.

• OR experts: What about Mass? We remember it used to be on Mondays during the first hour for the first level.

• Johanna: That has not changed. Mass must always be allocated to the first hour on Monday for the first level, on Tuesday for the second level, and on Wednesday for the third level.

• OR experts: What about the number of hours per week and per subject?

• Johanna: I will share with you a table that contains that information.

• OR experts: Great! Is there anything else we need to know?

• Johanna: There are some common-sense constraints. For example, since the same teacher teaches math to all sections at the same level, it is obvious that the schedule must allocate different hours within the day to allow the teacher to attend all his or her lectures. The exceptions to this are Mass and English.

• OR experts: Of course; don’t worry about common sense constraints. We will deal with them.

• Johanna: Please remember that we operate five days per week with eight academic hours per day. Additionally, the students have a 20-minute break after the fourth hour.

• OR experts: Thank you for the reminder. We will wait to receive the subject data. In the meantime, we will start working on a prototype for the first level. If this prototype makes sense to you, we can scale it to the other levels.

• Johanna: Don’t worry about the data. I will send it to you by the end of the day.

• OR experts: Great. Changing the topic, how is the institution doing in chess and mathematics competitions?

• Johanna: Oh, that is a long story…

As a result of the meeting, the OR experts were tasked with formulating and implementing an optimization model to help Johanna solve her operational problem.