Meta-heuristics and Feasible Solutions in Course Timetabling

Authors: (1) Jo˜ao Almeida, CEGIST, Instituto Superior T´ecnico, Universidade de Lisboa Portugal; (2) Jos´e Rui Figueira, CEGIST, Instituto Superior T´ecnico, Universidade de Lisboa Portugal; (3) Alexandre P. Francisco, INESC-ID, Instituto Superior T´ecnico, Universidade de Lisboa Portugal; (4) Daniel Santos, CEGIST, Instituto Superior T´ecnico, Universidade de Lisboa Portugal. 2 Literature Review In this section, we present a review of the latest developments in course timetabling. In Subsection 2.1, we summarise common problem definitions based on competition tracks and real-world problems. In Subsection 2.2, we present the solution approaches employed to solve such problems. In Subsection 2.3, we analyse other works proposing different methodologies for finding feasible course timetabling solutions. 2.1 Problem definitions The course timetabling problem has some characteristic constraints that, even if differently handled, are globally present in the literature [5, 9]. These general constraints can be divided into two groups. The first group prevents student, professor, and room assignment juxtaposition, and the second group ensures that each lecture is assigned a time slot and room. Moreover, some problems follow other university regulations, leading to the addition of some problem-specific constraints. Contrariwise, objectives tend to be more varied between problems. Standardised benchmark instances for the course timetabling problem have been widely studied [4]. The two most studied benchmark instances were introduced in the 2007 International Timetabling Competition. They are the curriculum-based course timetabling problem [10–19] and the post-enrolment course timetabling problem [20– 22]. However, the 2019 International Timetabling Competition [23] introduced a new set of benchmark instances. The curriculum-based course timetabling problem considers the general constraints and an additional constraint, which states that some curricula and professors are unavailable for certain time slots [24]. Additionally, there are four objectives. Specifically, the adherence to a minimum number of working days for the lectures of a course, the promotion of compact schedules for each curriculum, respecting room capacity, and the minimisation of the number of rooms assigned to the lectures of the same course [24]. Moreover, some works have also considered the robustness of the solutions as an additional objective [15–17, 25]. Besides the general constraints, the post-enrolment course timetabling problem also considers room capacity violations, lecture precedence, and unavailable time slots as constraints [21]. Moreover, three objectives are considered. Specifically, avoiding specific time slots, limiting the number of consecutive lectures for a student, and avoiding days with a single lecture for a student [21]. The major difference between the problem of ITC2019 is the required student sectioning [23]. In this problem, the students or curricula are not already assigned to each lecture, and this assignment is one of the decisions the optimisation algorithms must make. Besides this concern, this problem also includes other constraints, such as maximum consecutive workloads, classes that must be taught on different days, or classes that must precede other classes. Real-world problems are also addressed in the literature. [5] deal with the course timetabling problem at the Faculty of Engineering of Naresuan University, and their largest instances have 1009 lectures and 66 curricula. Besides general constraints, this problem also considers constraints on certain room requirements, professor and student time slot availability, and consecutive lecture assignments. Their objective function aims to minimise operating costs for the faculty. Specifically, its components are the operating costs generated by assigning certain rooms, hiring lecturers for certain time slots, and cleaning and setting up rooms, which should be assigned as compact schedules as possible. [8] addresses the University of Technology of Compi`egne course timetabling problem. Due to the size of their instances, they adopted the approach of including the assignment of lectures as an objective while maintaining the remaining general constraints. Their largest instances include 652 lectures. Additionally, they also include avoiding building changes and minimising the number of necessary time slots. [26] use the problem of the Department of Computer Science and Information Engineering at the National Changhua University of Education as their case study, solving instances with six curricula and 45-50 courses. Besides the general constraints, they also include constraints regarding room requirements and certain time-slot availability concerns. As objectives, they consider some preferred time slots, maximum consecutive and daily assignments, and avoidance of similar time slots for specific optional lectures. [27] solve a problem from a Taiwanese university, with at most 28 curricula. They include general and room requirement constraints, and their objectives include time slot preferences, course time slot distribution preferences, and minimisation of room preferences. [28] address instances from the Department of Statistics at Hacettepe University, with four curricula and 57 lectures. Their problem-specific constraints are room requirements and lectures scheduled on different days. Their objective functions include compactness and workload considerations, time slot preferences, and room capacity violations. 2.2 Solution improvement approaches In course timetabling literature, solution approaches that provide a single solution [5, 8, 11–14, 17–19, 21, 22, 29] are more often addressed than multi-objective methodologies [15, 16, 25, 30],which aim to provide better knowledge about the different possible timetabling options. For finding a single solution, authors have studied meta-heuristic-based approaches [5, 11, 17–19, 21, 22, 25], with the latter also including machine learning in their approach, mixed integer linear programming based approaches [8, 12, 13, 29, 31], and hyper-heuristics based approaches [14]. Some authors use multi-objective approaches [15, 16, 25, 30]. Moreover, all of these address the curriculum-based course timetabling problem and implement bicriteria models. Works that introduced robustness metrics used this methodology to understand the trade-off between the weighted objective function and their respective robustness metrics [15, 16, 25]. Conversely, [30] use bi-criteria optimisation to assess trade-offs between pairs of objective functions already present in the original problem. Employed algorithms were based on meta-heuristics [16, 25] and mixed integer linear programming [15, 30]. 2.3 Finding feasible solutions Most meta-heuristics consider initial solutions to be optimised as their starting points. The algorithms employed to generate these initial solutions can significantly impact the quality of the final solution. This influence can come from both the initial performance and the time required to generate the solutions. Several works have studied the generation of initial feasible solutions in different settings. [32] address the scheduling of energy resources in smart grids and compare the use of different strategies, such as random solutions, ant colony optimisation, naive-scheduling heuristics, pre scheduling heuristics, and mixed integer linear programming. [33] and [34] propose heuristic approaches for transportation problems. [35] uses genetic algorithms to generate feasible and diverse dungeon levels. Regarding course timetabling, [36] proposes an iterated local search algorithm and tackles a problem considering student and room clashes, room requirements, and complete assignment of events as constraints. Their initial solution mechanism attempts to schedule as many lectures as possible without generating student and room clashes and respecting room requirements. They then use a simulated annealing procedure to improve this initial solution. [37] proposes a hyper-heuristic approach. They explore the automatic induction of two construction heuristics types: arithmetic and hierarchical heuristics. Genetic programming is employed to evolve arithmetic heuristics, while a combination of genetic programming, genetic algorithms, and the generation of random heuristic combinations is used to generate hierarchical heuristics. [38] proposes a Monte Carlo tree search methodology. Their problems include similar constraints to the ones present in [36], with the addition of predefined time slots for some lectures and lecture ordering constraints. Besides their simulation approach, they provide several heuristic methods to improve the simulation efficiency by pruning their Monte Carlo trees. Like [36], our work uses a local search based approach but with a few key distinctions. Our initial solution approach schedules all the lectures while respecting student/curriculum-related hard constraints and disregarding professor, room, and lecture ordering constraints. Moreover, our neighbourhood structures specifically focus the search on the lectures which are causing the violations. Their objective function represents the number of violations. In our work, we include weights for different types of constraint violations. These weights are constantly updated during the search to penalise violations identified as the most challenging to overcome. Our largest tested instances include more than 4000 lectures, whereas [36] consider at most 1000. For instances of this dimension, instance decomposition and increment significantly improved solution times. As far as we know, this procedure was never attempted before in course timetabling problems. This paper is available on arxiv under CC 4.0 license. Authors: (1) Jo˜ao Almeida, CEGIST, Instituto Superior T´ecnico, Universidade de Lisboa Portugal; (2) Jos´e Rui Figueira, CEGIST, Instituto Superior T´ecnico, Universidade de Lisboa Portugal; (3) Alexandre P. Francisco, INESC-ID, Instituto Superior T´ecnico, Universidade de Lisboa Portugal; (4) Daniel Santos, CEGIST, Instituto Superior T´ecnico, Universidade de Lisboa Portugal. Authors: (1) Jo˜ao Almeida, CEGIST, Instituto Superior T´ecnico, Universidade de Lisboa Portugal; (2) Jos´e Rui Figueira, CEGIST, Instituto Superior T´ecnico, Universidade de Lisboa Portugal; (3) Alexandre P. Francisco, INESC-ID, Instituto Superior T´ecnico, Universidade de Lisboa Portugal; (4) Daniel Santos, CEGIST, Instituto Superior T´ecnico, Universidade de Lisboa Portugal. 2 Literature Review In this section, we present a review of the latest developments in course timetabling. In Subsection 2.1, we summarise common problem definitions based on competition tracks and real-world problems. In Subsection 2.2, we present the solution approaches employed to solve such problems. In Subsection 2.3, we analyse other works proposing different methodologies for finding feasible course timetabling solutions. 2.1 Problem definitions The course timetabling problem has some characteristic constraints that, even if differently handled, are globally present in the literature [5, 9]. These general constraints can be divided into two groups. The first group prevents student, professor, and room assignment juxtaposition, and the second group ensures that each lecture is assigned a time slot and room. Moreover, some problems follow other university regulations, leading to the addition of some problem-specific constraints. Contrariwise, objectives tend to be more varied between problems. Standardised benchmark instances for the course timetabling problem have been widely studied [4]. The two most studied benchmark instances were introduced in the 2007 International Timetabling Competition. They are the curriculum-based course timetabling problem [10–19] and the post-enrolment course timetabling problem [20– 22]. However, the 2019 International Timetabling Competition [23] introduced a new set of benchmark instances. The curriculum-based course timetabling problem considers the general constraints and an additional constraint, which states that some curricula and professors are unavailable for certain time slots [24]. Additionally, there are four objectives. Specifically, the adherence to a minimum number of working days for the lectures of a course, the promotion of compact schedules for each curriculum, respecting room capacity, and the minimisation of the number of rooms assigned to the lectures of the same course [24]. Moreover, some works have also considered the robustness of the solutions as an additional objective [15–17, 25]. Besides the general constraints, the post-enrolment course timetabling problem also considers room capacity violations, lecture precedence, and unavailable time slots as constraints [21]. Moreover, three objectives are considered. Specifically, avoiding specific time slots, limiting the number of consecutive lectures for a student, and avoiding days with a single lecture for a student [21]. The major difference between the problem of ITC2019 is the required student sectioning [23]. In this problem, the students or curricula are not already assigned to each lecture, and this assignment is one of the decisions the optimisation algorithms must make. Besides this concern, this problem also includes other constraints, such as maximum consecutive workloads, classes that must be taught on different days, or classes that must precede other classes. Real-world problems are also addressed in the literature. [5] deal with the course timetabling problem at the Faculty of Engineering of Naresuan University, and their largest instances have 1009 lectures and 66 curricula. Besides general constraints, this problem also considers constraints on certain room requirements, professor and student time slot availability, and consecutive lecture assignments. Their objective function aims to minimise operating costs for the faculty. Specifically, its components are the operating costs generated by assigning certain rooms, hiring lecturers for certain time slots, and cleaning and setting up rooms, which should be assigned as compact schedules as possible. [8] addresses the University of Technology of Compi`egne course timetabling problem. Due to the size of their instances, they adopted the approach of including the assignment of lectures as an objective while maintaining the remaining general constraints. Their largest instances include 652 lectures. Additionally, they also include avoiding building changes and minimising the number of necessary time slots. [26] use the problem of the Department of Computer Science and Information Engineering at the National Changhua University of Education as their case study, solving instances with six curricula and 45-50 courses. Besides the general constraints, they also include constraints regarding room requirements and certain time-slot availability concerns. As objectives, they consider some preferred time slots, maximum consecutive and daily assignments, and avoidance of similar time slots for specific optional lectures. [27] solve a problem from a Taiwanese university, with at most 28 curricula. They include general and room requirement constraints, and their objectives include time slot preferences, course time slot distribution preferences, and minimisation of room preferences. [28] address instances from the Department of Statistics at Hacettepe University, with four curricula and 57 lectures. Their problem-specific constraints are room requirements and lectures scheduled on different days. Their objective functions include compactness and workload considerations, time slot preferences, and room capacity violations. 2.2 Solution improvement approaches In course timetabling literature, solution approaches that provide a single solution [5, 8, 11–14, 17–19, 21, 22, 29] are more often addressed than multi-objective methodologies [15, 16, 25, 30],which aim to provide better knowledge about the different possible timetabling options. For finding a single solution, authors have studied meta-heuristic-based approaches [5, 11, 17–19, 21, 22, 25], with the latter also including machine learning in their approach, mixed integer linear programming based approaches [8, 12, 13, 29, 31], and hyper-heuristics based approaches [14]. Some authors use multi-objective approaches [15, 16, 25, 30]. Moreover, all of these address the curriculum-based course timetabling problem and implement bicriteria models. Works that introduced robustness metrics used this methodology to understand the trade-off between the weighted objective function and their respective robustness metrics [15, 16, 25]. Conversely, [30] use bi-criteria optimisation to assess trade-offs between pairs of objective functions already present in the original problem. Employed algorithms were based on meta-heuristics [16, 25] and mixed integer linear programming [15, 30]. 2.3 Finding feasible solutions Most meta-heuristics consider initial solutions to be optimised as their starting points. The algorithms employed to generate these initial solutions can significantly impact the quality of the final solution. This influence can come from both the initial performance and the time required to generate the solutions. Several works have studied the generation of initial feasible solutions in different settings. [32] address the scheduling of energy resources in smart grids and compare the use of different strategies, such as random solutions, ant colony optimisation, naive-scheduling heuristics, pre scheduling heuristics, and mixed integer linear programming. [33] and [34] propose heuristic approaches for transportation problems. [35] uses genetic algorithms to generate feasible and diverse dungeon levels. Regarding course timetabling, [36] proposes an iterated local search algorithm and tackles a problem considering student and room clashes, room requirements, and complete assignment of events as constraints. Their initial solution mechanism attempts to schedule as many lectures as possible without generating student and room clashes and respecting room requirements. They then use a simulated annealing procedure to improve this initial solution. [37] proposes a hyper-heuristic approach. They explore the automatic induction of two construction heuristics types: arithmetic and hierarchical heuristics. Genetic programming is employed to evolve arithmetic heuristics, while a combination of genetic programming, genetic algorithms, and the generation of random heuristic combinations is used to generate hierarchical heuristics. [38] proposes a Monte Carlo tree search methodology. Their problems include similar constraints to the ones present in [36], with the addition of predefined time slots for some lectures and lecture ordering constraints. Besides their simulation approach, they provide several heuristic methods to improve the simulation efficiency by pruning their Monte Carlo trees. Like [36], our work uses a local search based approach but with a few key distinctions. Our initial solution approach schedules all the lectures while respecting student/curriculum-related hard constraints and disregarding professor, room, and lecture ordering constraints. Moreover, our neighbourhood structures specifically focus the search on the lectures which are causing the violations. Their objective function represents the number of violations. In our work, we include weights for different types of constraint violations. These weights are constantly updated during the search to penalise violations identified as the most challenging to overcome. Our largest tested instances include more than 4000 lectures, whereas [36] consider at most 1000. For instances of this dimension, instance decomposition and increment significantly improved solution times. As far as we know, this procedure was never attempted before in course timetabling problems. This paper is available on arxiv under CC 4.0 license. This paper is available on arxiv under CC 4.0 license. available on arxiv