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

1. Introduction

Timetable creation is a recurring and complex problem in any academic institution. The goal is to build a feasible schedule for teaching activities by assigning lectures to rooms and periods (Mühlenthaler and Wanka 2015). This paper presents a comprehensive case study based on a real-world experience that, starting with a relatively simple timetabling scheduling problem, progressively adds new elements to introduce the students to several modeling principles from linear and integer programming.

The use of scheduling problems in an educational setting is not new; see, for example, Trick (2004), Hans and Nieberg (2007), Rao and Beliën (2014), Sauré and Puterman (2014), Winch and Yurkiewicz (2014), and Sharkey et al. (2020). Trick (2004) presented a solution for how to use sports scheduling problems to introduce fundamental concepts of integer programming to students with different backgrounds. The author shows the potential that integer programming techniques have in different application domains, moving beyond the classical production and transportation exercises that are available in textbooks. Hans and Nieberg (2007) proposed the operating room manager game. In this game, students take on the role of management teams in the operations research (OR) department and, in subsequent rounds, follow the actual planning and scheduling process, starting with strategic choices about capacities for an upcoming year and ending with the daily, online planning of actual surgeries in each operating room. Similarly, Sauré and Puterman (2014) introduced the appointment scheduling game. This game simulates a system in which daily patient appointment requests arrive randomly. The daily service capacity is limited. Students assume the role of a scheduling clerk who must assign appointment dates to these requests without knowing the future demand.

Winch and Yurkiewicz (2014) presented a class scheduling problem from the student’s perspective. Kelly, a senior undergrad, must take five courses in the upcoming semester. She has all the information related to the courses, meeting times, and ratings. Her objective is to decide which courses to take to maximize the overall rating while still satisfying all the constraints imposed by the university. Similarly, but in a different domain, Rao and Beliën (2014) proposed the Falcon Die Casting Company production scheduling problem. The aim of this game is the scheduling of the weekly production of five products on five machines, where each product is produced only on a subset of the machines. Although there are no precedence relations between the products and machines, both the setup times and waste ratios affect the problem.

Finally, Sharkey et al. (2020) introduced a workforce scheduling problem for an immigration department located in an anonymous country. Students must analyze the current employee scheduling and propose policy changes to reduce staffing. However, their proposed changes must consider the waiting time of passengers who are standing in the queue at the immigration department. A key element of the case is that it presents an open-ended problem, which means that there is no correct solution. The students must justify why their solution is better than others.

In summary, the scheduling problems reported below cover a wide range of application domains. However, to the best of our knowledge, the school timetabling problem from the institution’s perspective has not been addressed as an optimization application in a teaching case.

2. Teaching Objectives and Pedagogical Benefits

The main teaching objective of the current case study is for students to formulate, implement, and solve a real-world timetabling problem while evaluating different objective functions to measure the quality of the final schedule. More specific objectives include the following:

1. Students should create meaningful integer programming models and propose solution alternatives to the main stakeholders.

2. Students should justify the assumptions made while creating the models and demonstrate that their solution alternatives are valid.

3. Students should research different mechanisms to measure the quality of a schedule in an academic context and select the most appropriate solution for the problem at hand.

4. Students should present a trade-off analysis between the solution alternatives so that the main stakeholder can evaluate the pros and cons to make an informed decision.

As we mentioned in Section 1, to the best of our knowledge, school timetabling problems from the institution’s perspective have not been addressed in a teaching case. This fact makes the current case study novel. However, there are other relevant benefits of the current case.

• The case study allows the instructor and the students to approach the problem by breaking it down into simpler versions and then improving the solution by adding more complex constraints into the previous models. Usually, complex, realistic problems do not have this characteristic, which means that the students have to incorporate almost all the elements and constraints in the prototype to obtain a solution that makes sense.

• Each new model changes the optimal solution. By observing these changes, students can gain greater insight into the nature of the problem and how the added constraints and the objective function affect the optimal schedule.

• This case study provides an opportunity to discuss how to measure the quality of a timetable, which is a critical issue when building them (Mühlenthaler and Wanka 2015). The case allows the instructor and the students to explore various alternatives to evaluate schedules. This enables the instructor to naturally introduce concepts such as hard and soft constraints.

• The case study can serve as a capstone project by reinforcing and connecting many disparate ideas studied over a semester into a single scenario. Each new element introduced in the case study also demonstrates the limitations of the previous models and shows how to improve them.

• A key challenge in teaching linear and integer programming courses is that realistic examples based on specialized applications generally require students to spend a considerable amount of time understanding the background before they can effectively model the decision problem that is under consideration (Rao and Beliën 2014). For example, the operating room manager game (Hans and Nieberg 2007) and the appointment scheduling game (Sauré and Puterman 2014) require some previous knowledge about health service operations. In such cases, students can lose track of aspects of the OR when they are drowning in the details (Trick 2004). This case presents a realistic scenario based on a common knowledge problem for undergraduate and postgraduate students regardless of their major.

• The case study comes with the GAMS and AIMMS source codes implementation facilitating its use for the instructor. In the teaching note, we discuss the pros and cons of alternative software packages that can be used with the case.

3. Case Overview

The main decision problem present in the current case study is the weekly scheduling of 14 subjects in the entry level (first level) of a Catholic high school. The first level is usually divided into four sections. Each section is a cohort of students who share the same classroom and schedule. Note that the classroom assignment is not an issue here because all the students in a cohort are allocated to the same room. Some relevant challenges appear in the problem.

• First, some subjects have to be scheduled in the same time slot for all sections, that is, their lectures must be allocated at the same time for all sections in the entry level. In school timetabling problems, it is not common that lectures cannot conflict with other sections.

• Second, some subjects have to be scheduled in a specific time slot. Therefore, students must deal with fixed variables and evaluate their impact in the other constraints.

• Third, the decision problem is more of a feasibility problem than an optimization problem. Because the quality indicators for class schedules are usually subjective, the students must research some options to formulate the objective function.

One characteristic of the case is that the problem can be broken down into simpler versions, which allows its use with students who have different levels of expertise in linear and integer programming. Another important fact is how we present the problem. Instead of narrating an optimization problem, we introduce the principal’s problem during a conversation with operations research experts. The instructor can highlight how a consultant could guide the conversation in similar situations and which questions to ask the main stakeholders. The aim is to obtain enough information about the problem to develop a prototype to validate in the next meetings. The first task students must complete is to extract the relevant aspects of the problem. Then, they have to structure this information and explain it to their teammates; then with an instructor’s guidance, they must propose an approach to deal with the problem constructively.

4. Possible Uses of the Case

The case can be used in courses that include the topic of integer programming in either undergraduate or graduate programs, such as operations research, industrial engineering, business administration, or computer science. The instructors of such courses have several ways to use the case, depending on the academic and mathematical backgrounds, and interests and needs of the students as well as the focus of the course.

1. In an introductory course on linear and integer programming, model 1¹ can be used for class discussions in order to provide a more advanced introduction to binary variables or as an interesting application of the assignment model in a classroom setting. Based on the students’ mathematical sophistication, model 2 may be used as a concluding capstone example for the course.

2. In a secondary course on linear and integer programming, model 1 can be used to refresh the concepts learned in the introductory course, whereas models 2, 3, and 4 can be used to discuss advanced modeling issues as well as decision making and implementation aspects.

3. Model 5 incorporates all the elements and constraints of the problem, thereby making the case useful in graduate or undergraduate courses in linear and integer programming with a focus on modeling techniques. Usually, based on the major and students’ profiles, introductory linear and integer programming courses may focus on the modeling principles and techniques or the mathematical aspects of the subject. The current case study is well suited for courses that are focused on modeling techniques rather than mathematical theory because the latter do not usually cover complex, realistic problems.

4. Additionally, model 5 can be used as a final capstone project in undergraduate or graduate courses about linear and integer programming that are focused on modeling techniques and implementation issues. The course instructors can request that their students prepare a business case and an executive presentation justifying why the organization must implement their proposed solution.

5. Finally, regardless of the major and students’ level of experience, the case study allows the class discussion to focus on the scheduling issues and challenges for any educational institution and to have a secondary debate about the aspects and benefits of mathematical optimization.

5. Classroom Experience

We used model 5 of the case in two introductory courses on linear/integer programming at the undergraduate level. These experiences took place in Chile and Ecuador. The students in Chile were pursuing a major in logistics, whereas the Ecuadorian students were majoring in computer engineering. In both cases, the focus was on the modeling principles and how to solve the problem using a modeling language, such as AIMMS or GAMS. The mathematical theory behind linear and integer programming was out of the scope of these courses.

We collected the students’ feedback by having informal conversations with them. The students found the problem very interesting and challenging. They liked that we based the case on a real-life scenario that is a current problem in some academic institutions. Because most of the students maintained contact with their high schools, they appreciated that they could adapt the mathematical model to the particular situation of their high schools. Thus, they had a concrete prototype to present to an initial contact in the world of consultancy.

We used the current case as a capstone project in both experiences. In what follows, we explain how we used the case to meet this purpose, the results, and the students’ reactions.

• The students who were pursuing a logistics major in Chile had a better mathematical background than did students in Ecuador. The students formed groups of two to deal with the final project. We set a deadline for three weeks in the future in order to give the students enough time to discuss the case, conduct research on the internet, and bring questions to discuss in class. The students highlighted that the most difficult constraint to manage was the two consecutive class hours within one day that were required for certain subjects, in combination with the break in-between classes. They also found it difficult to convincingly justify the objective function used in the mathematical model. However, all of the students presented a functional solution to the case.

• The students who were pursuing a major in computer engineering in Ecuador had one unusual characteristic; that is, they entered the university halfway through the curriculum instead of at the beginning. Therefore, they did not take elementary courses, such as algebra, calculus, statistics, etc. As a consequence, these students had a poor mathematical background. We solved a few similar scheduling problems over several sessions to give them previous experience working with the case study. Similar to the first case, the students formed groups of three, and we set the deadline for three weeks in the future. Despite the instructor’s efforts, no group presented a functional solution for the case problem. Ultimately, the students highlighted that the case problem was too difficult for them to address.

According to these experiences, we conclude that solving the full case model could be very challenging for students with poor mathematical backgrounds. One possible reason for this is that most of the information available in books and over the internet uses advanced mathematical notations that are not familiar to students with this background. For these groups, we suggest that the instructor use the following learning path to improve the students’ chances of success when assigning case model 5 as a final capstone:

1. Solve some production scheduling problems with inventory flows in one or two class sessions to familiarize the students with algebraic modeling notation.

2. Solve the Falcon Die Casting Company case (Rao and Beliën 2014) with the students over one or two sessions to reinforce the concepts of production problems and the algebraic modeling notation.

3. Solve the Kelly class scheduling case (Winch and Yurkiewicz 2014) with the students over one or two sessions to introduce some basic concepts about course scheduling problems.

4. Present the school timetabling case to students and solve models 1 to 3 with them over two or three sessions.

5. Assign case models 4 and 5 as a final capstone. Reduce the number of students per group to 2 and set the deadline to either one or two weeks based on the students’ performance in the last four stages of the learning path.

6. Alternative Approach

The current case is based on the authors’ real experience, which is not an uncommon experience for the students. If the instructor considers it relevant, they can ask the students to replicate the case in the future; however, at this time, the students have to consider the particularities of the school from which they come. This approach is beneficial to the students for the following reasons:

1. They should resume contact with their schools and make an appointment to obtain information that is relevant to the case problem.

2. They should replicate the conversation held between the principal and the consultants in real time.

3. They will have to formulate and solve a new mathematical model that is adapted to the unique conditions of their schools.

4. They will be able to compare the problems of different institutions and discuss these problems in class to establish similarities and differences.

7. Conclusions

The school timetabling scheduling case lets students apply integer linear programming in a problem that is relevant to their recent life; it also allows them to collect their own data and experience the entire process of quantitative modeling. The problem is easily understood; however, in order to be implemented, the problem requires advanced modeling platforms, such as AIMMS, GAMS, or AMPL.

The undergraduate students who were enrolled in our course appreciated the usefulness of the optimization techniques and gained an understanding of quantitative modeling steps. We believe that other instructors will find the school timetabling scheduling case to be a useful addition to their management science or quantitative modeling course.