A Hybrid Meta-Heuristic for Feasible Large-Scale Course Timetables With Instance Decomposition

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. Abstract This work presents a hybrid meta-heuristic for generating feasible course timetables, focusing on large-scale problems. We test it on instances from our university, for which the currently used commercial software takes several hours to find feasible solutions and often fails to comply with some constraints. The methodology includes elements from adaptive large neighbourhood search (ALNS), guided local search (GLS), variable neighbourhood search (VNS), and a novel instance decomposition technique. The constraint violations from different groups of constraints are regarded as objective functions to be minimised. The neighbourhood structures focus the search on the time slots where the most violations are identified. After a certain number of iterations without improvements, the most challenging constraint groups are given new weights, guiding the search towards non-dominated solutions, which improve the performance of these objectives, even if the total sum of the effective violations increases. If this mechanism fails to escape these “local optima”, a shaking phase is conducted. The decomposition mechanism operates as follows: curricula are iteratively introduced to the problem, and new feasible solutions are found considering the increasing set of lectures. The assignments from each iteration can be modified if needed in subsequent iterations. This methodology is tested in real-world instances from our university and in random sub-divisions of those. For sub-divisions with 400 curricula timetables, decomposition reduces the solution times to up to 27%. For real-world instances, with 1288 curricula timetables, the reduction is 18%. The experiments also reveal that clustering curricula with more lectures and professors in common when incrementing the instances improved the solution times by 18% more than a random increment order. Using our methodology, feasible solutions for the real-world instance are found in 21 minutes, on average, whereas the commercial software takes several hours. Keywords: Timetabling, Meta-heuristics, Instance Decomposition, Scheduling 1 Introduction Course timetabling is one of the most studied educational scheduling problems [1], which also include exam scheduling [2] or thesis defence scheduling [3]. Moreover, it is an arduous and time-consuming burden for those tasked with its resolution at the university administration level [4]. The problem can be defined through a 5W framework as follows: we want to schedule What lecture, taught by Who (professors), to Whom (curricula), Where (room) and When (day and hour). A feasible timetable fulfils a particular set of constraints specific to each case [5], such as students, professors, and rooms cannot have more than one lecture scheduled at the same time, some lectures can only be scheduled after another has taken place, or some time-slots are unavailable for certain professors, curricula or rooms [6]. Course timetabling impacts several stakeholders. On the one hand, there are those responsible for the scheduling process who have to do extra corrective work in short amounts of time if the timetabling software does not find satisfactory solutions in an acceptable time frame. On the other hand, there are stakeholders whose daily activities can be affected by the quality of the timetables. They can be students, professors, or managerial stakeholders, who must manage costs or room availability for other purposes. Analysing real-world course timetabling systems shows a variety of concerns and points of view depending on the characteristics of each case. [7] show a case where a campus reorganization led to congestion in the hallways and stairs, frequently causing lectures to start late. To solve this problem, the authors propose a course timetabling solution which minimises the travel times between consecutive classes for students. [5] provide a different perspective. Their solution approach minimises operational costs by rearranging the timetables to reduce, for example, professor hiring costs or cleaning and maintenance costs. [8] contribute with another point of view. Their previous timetabling methodology often failed to schedule all the lectures, leading to extraordinary managerial work to find ways to schedule the remaining lectures. Thus, they propose a solution that aims to maximise the number of scheduled lectures to reduce the burden on the management. Our research is inspired by the course timetabling system of the Instituto Superior T´ecnico of the University of Lisbon (IST), where more than 4000 lectures must be scheduled each semester in two different campi. Comparatively, the largest instances solved by the previously mentioned works have at most 1000 lectures. Moreover, many of the lectures in our instances are shared between different curricula and classes. Additionally, the number of certain types of rooms is considerably limited for the number of lectures that must be scheduled. Thus, it is impossible to schedule the lectures of different departments separately as they compete for the same rooms and are taught simultaneously to multiple groups of students from different courses. Furthermore, IST operates using both semester and trimester academic structures, which poses a unique scheduling challenge. Certain courses span a semester, while others are taught in a single trimester. Due to the size and intricacies of the problem, the commercial timetabling software currently used by IST cannot efficiently find timetables that comply with all the rules. For example, it is not uncommon that, in this initial schedule, a professor ends up with two lectures in different campi without any time in between or that some students cannot enrol in some courses due to juxtaposition with others. These problems must then be resolved by hand. This burdensome process takes several weeks of manually rearranging individual timetables, checking their feasibility with the respective stakeholders, and booking new rooms. This work proposes a new hybrid meta-heuristic for generating feasible course timetables. It integrates elements from adaptive large neighbourhood search (ALNS), guided local search (GLS), and variable neighbourhood search (VNS). Its objective function regards the minimisation of hard constraint violations. In our experiments, all instances were known to be feasible. Thus, no time limit was set, and the metaheuristic stops when the value of the objective function reaches 0. If the feasibility of the instances was not known, a time or iteration limit could be set, and the metaheuristic would still minimise the number of violations. The search is directed toward lectures and time slots with the highest number of violations using novel neighbourhood structures. When there is no improvement after a certain number of iterations, the most challenging constraint groups are assigned new weights. This guides the search towards non-dominated solutions that enhance the performance of these objectives, even if the total sum of violations increases. If this approach fails to move away from these “local optima” a shaking phase is implemented. This work contributes to the literature by proposing a new hybrid meta-heuristic for generating feasible solutions for course timetabling problems tailored to solve large and complex instances. For this purpose, we introduce novel neighbourhood structures for ALNS and features for GLS. The neighbourhood structures target specific lectures which are potentially causing violations. This is exceptionally useful when dealing with large and complex instances where random searches would most likely miss the problematic areas. We also explore the use of new instance decomposition techniques in generating feasible course timetables. Our decomposition mechanism functions as follows: a set of lectures belonging to specific curricula is added to the problem, and the meta-heuristic is used to find a new feasible solution considering the current set of lectures. When we have a feasible solution, we add the next set. Let us note that the assignments of each iteration can be changed if necessary in the following iterations. This mechanism allows us to simplify the problem by dealing with less complex states, with fewer violations, in each iteration. The computational experiments are conducted on real-world instances and random sub-divisions of those. The decomposition mechanism promoted solution time reductions of up to 27% compared to solving the problems without decomposition mechanisms in the sub-divisions and of up to 18% in the real-world instance. The results also imply a significant positive impact if the curricula are added in clusters, i.e., curricula which share classes or professors are included in the problem at similar times. The remainder of this paper is structured in the following manner: in Section 2, we provide a state-of-the-art review of recent developments in course timetabling problems. In Section 3, we define the course timetabling problem for IST. In Section 4, we present the algorithmic framework of our meta-heuristic. In Section 5, we analyse the computational experiments, including the IST instances and adaptions of the 2007 International Timetabling Competition curriculum-based course timetabling instances. Finally, in Section 6, we provide a conclusion and propose several new research paths. The remainder of this paper is structured in the following manner: in Section 2, we provide a state-of-the-art review of recent developments in course timetabling problems. In Section 3, we define the course timetabling problem for IST. In Section 4, we present the algorithmic framework of our meta-heuristic. In Section 5, we analyse the computational experiments, including the IST instances and adaptions of the 2007 International Timetabling Competition curriculum-based course timetabling instances. Finally, in Section 6, we provide a conclusion and propose several new research paths. 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. Abstract This work presents a hybrid meta-heuristic for generating feasible course timetables, focusing on large-scale problems. We test it on instances from our university, for which the currently used commercial software takes several hours to find feasible solutions and often fails to comply with some constraints. The methodology includes elements from adaptive large neighbourhood search (ALNS), guided local search (GLS), variable neighbourhood search (VNS), and a novel instance decomposition technique. The constraint violations from different groups of constraints are regarded as objective functions to be minimised. The neighbourhood structures focus the search on the time slots where the most violations are identified. After a certain number of iterations without improvements, the most challenging constraint groups are given new weights, guiding the search towards non-dominated solutions, which improve the performance of these objectives, even if the total sum of the effective violations increases. If this mechanism fails to escape these “local optima”, a shaking phase is conducted. The decomposition mechanism operates as follows: curricula are iteratively introduced to the problem, and new feasible solutions are found considering the increasing set of lectures. The assignments from each iteration can be modified if needed in subsequent iterations. This methodology is tested in real-world instances from our university and in random sub-divisions of those. For sub-divisions with 400 curricula timetables, decomposition reduces the solution times to up to 27%. For real-world instances, with 1288 curricula timetables, the reduction is 18%. The experiments also reveal that clustering curricula with more lectures and professors in common when incrementing the instances improved the solution times by 18% more than a random increment order. Using our methodology, feasible solutions for the real-world instance are found in 21 minutes, on average, whereas the commercial software takes several hours. Keywords: Timetabling, Meta-heuristics, Instance Decomposition, Scheduling Keywords: 1 Introduction Course timetabling is one of the most studied educational scheduling problems [1], which also include exam scheduling [2] or thesis defence scheduling [3]. Moreover, it is an arduous and time-consuming burden for those tasked with its resolution at the university administration level [4]. The problem can be defined through a 5W framework as follows: we want to schedule What lecture, taught by Who (professors), to Whom (curricula), Where (room) and When (day and hour). A feasible timetable fulfils a particular set of constraints specific to each case [5], such as students, professors, and rooms cannot have more than one lecture scheduled at the same time, some lectures can only be scheduled after another has taken place, or some time-slots are unavailable for certain professors, curricula or rooms [6]. Course timetabling impacts several stakeholders. On the one hand, there are those responsible for the scheduling process who have to do extra corrective work in short amounts of time if the timetabling software does not find satisfactory solutions in an acceptable time frame. On the other hand, there are stakeholders whose daily activities can be affected by the quality of the timetables. They can be students, professors, or managerial stakeholders, who must manage costs or room availability for other purposes. Analysing real-world course timetabling systems shows a variety of concerns and points of view depending on the characteristics of each case. [7] show a case where a campus reorganization led to congestion in the hallways and stairs, frequently causing lectures to start late. To solve this problem, the authors propose a course timetabling solution which minimises the travel times between consecutive classes for students. [5] provide a different perspective. Their solution approach minimises operational costs by rearranging the timetables to reduce, for example, professor hiring costs or cleaning and maintenance costs. [8] contribute with another point of view. Their previous timetabling methodology often failed to schedule all the lectures, leading to extraordinary managerial work to find ways to schedule the remaining lectures. Thus, they propose a solution that aims to maximise the number of scheduled lectures to reduce the burden on the management. Our research is inspired by the course timetabling system of the Instituto Superior T´ecnico of the University of Lisbon (IST), where more than 4000 lectures must be scheduled each semester in two different campi. Comparatively, the largest instances solved by the previously mentioned works have at most 1000 lectures. Moreover, many of the lectures in our instances are shared between different curricula and classes. Additionally, the number of certain types of rooms is considerably limited for the number of lectures that must be scheduled. Thus, it is impossible to schedule the lectures of different departments separately as they compete for the same rooms and are taught simultaneously to multiple groups of students from different courses. Furthermore, IST operates using both semester and trimester academic structures, which poses a unique scheduling challenge. Certain courses span a semester, while others are taught in a single trimester. Due to the size and intricacies of the problem, the commercial timetabling software currently used by IST cannot efficiently find timetables that comply with all the rules. For example, it is not uncommon that, in this initial schedule, a professor ends up with two lectures in different campi without any time in between or that some students cannot enrol in some courses due to juxtaposition with others. These problems must then be resolved by hand. This burdensome process takes several weeks of manually rearranging individual timetables, checking their feasibility with the respective stakeholders, and booking new rooms. This work proposes a new hybrid meta-heuristic for generating feasible course timetables. It integrates elements from adaptive large neighbourhood search (ALNS), guided local search (GLS), and variable neighbourhood search (VNS). Its objective function regards the minimisation of hard constraint violations. In our experiments, all instances were known to be feasible. Thus, no time limit was set, and the metaheuristic stops when the value of the objective function reaches 0. If the feasibility of the instances was not known, a time or iteration limit could be set, and the metaheuristic would still minimise the number of violations. The search is directed toward lectures and time slots with the highest number of violations using novel neighbourhood structures. When there is no improvement after a certain number of iterations, the most challenging constraint groups are assigned new weights. This guides the search towards non-dominated solutions that enhance the performance of these objectives, even if the total sum of violations increases. If this approach fails to move away from these “local optima” a shaking phase is implemented. This work contributes to the literature by proposing a new hybrid meta-heuristic for generating feasible solutions for course timetabling problems tailored to solve large and complex instances. For this purpose, we introduce novel neighbourhood structures for ALNS and features for GLS. The neighbourhood structures target specific lectures which are potentially causing violations. This is exceptionally useful when dealing with large and complex instances where random searches would most likely miss the problematic areas. We also explore the use of new instance decomposition techniques in generating feasible course timetables. Our decomposition mechanism functions as follows: a set of lectures belonging to specific curricula is added to the problem, and the meta-heuristic is used to find a new feasible solution considering the current set of lectures. When we have a feasible solution, we add the next set. Let us note that the assignments of each iteration can be changed if necessary in the following iterations. This mechanism allows us to simplify the problem by dealing with less complex states, with fewer violations, in each iteration. The computational experiments are conducted on real-world instances and random sub-divisions of those. The decomposition mechanism promoted solution time reductions of up to 27% compared to solving the problems without decomposition mechanisms in the sub-divisions and of up to 18% in the real-world instance. The results also imply a significant positive impact if the curricula are added in clusters, i.e., curricula which share classes or professors are included in the problem at similar times. The remainder of this paper is structured in the following manner: in Section 2, we provide a state-of-the-art review of recent developments in course timetabling problems. In Section 3, we define the course timetabling problem for IST. In Section 4, we present the algorithmic framework of our meta-heuristic. In Section 5, we analyse the computational experiments, including the IST instances and adaptions of the 2007 International Timetabling Competition curriculum-based course timetabling instances. Finally, in Section 6, we provide a conclusion and propose several new research paths. The remainder of this paper is structured in the following manner: in Section 2, we provide a state-of-the-art review of recent developments in course timetabling problems. In Section 3, we define the course timetabling problem for IST. In Section 4, we present the algorithmic framework of our meta-heuristic. In Section 5, we analyse the computational experiments, including the IST instances and adaptions of the 2007 International Timetabling Competition curriculum-based course timetabling instances. Finally, in Section 6, we provide a conclusion and propose several new research paths. 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