Encyclopedia
Please note this is an old version of this entry, which may differ significantly from the current revision.
Subjects:
Computer Science, Theory & Methods
The university course timetabling problem (UCTP) is a multidimensional assignment problem that involves assigning students and teachers to events (or courses), which are then allocated to appropriate timeslots and rooms. The UCTP can be categorized into two categories: post-enrollment-based course timetabling problems (PE-CTPs) and curriculum-based course timetabling problems (CB-CTPs).
- timetabling
- metaheuristics
- genetic algorithm
- iterated local search
1. Introduction
Timetabling is an important and challenging area of research with diverse applications in education, enterprises, sports, transportation, human resources planning, and logistics. According to [1], timetabling refers to the allocation of given resources, subject to constraints, to objects placed in space–time, aiming to maximize the number of satisfied desirable objectives. These high-dimensional, multi-objective combinatorial optimization problems have received significant attention from the scientific community because manually generating timetables is laborious and time-consuming, often resulting in ineffective and costly schedules. Therefore, the development of automated timetabling systems is crucial to reducing errors, accelerating the creation process, and maximizing desirable objectives. Among the various forms of timetabling problems, the educational timetabling problem stands out as one of the most extensively studied. Finding a universal and effective solution for this problem is challenging due to its complexity, varying constraints, and evolving requirements.
The university course timetabling problem (UCTP) is a multidimensional assignment problem that involves assigning students and teachers to events (or courses), which are then allocated to appropriate timeslots and rooms. The UCTP can be categorized into two categories: post-enrollment-based course timetabling problems (PE-CTPs) and curriculum-based course timetabling problems (CB-CTPs). PE-CTP, sometimes referred to as “event timetabling”, focuses on assigning events to timeslots and resources (rooms and students) to avoid conflicts between events, timeslots, and rooms. The timetable is constructed after student enrollment to ensure all students can attend the events they are enrolled in. On the other hand, CB-CTP was first introduced in the Second International Timetabling Competition (ITC2007) [2] and is a weekly assignment problem that involves scheduling a specific number of lectures for various university courses within a given number of time periods and a set of rooms. Each day is divided into a fixed number of timeslots, and a period refers to a combination of a day and a timeslot. The total number of scheduling periods per week is determined by multiplying the number of days per week by the number of timeslots per day. Each course must be scheduled at different periods. Additionally, a set of curricula consists of groups of courses with shared students, and conflicts between courses are resolved based on the curricula rather than student enrollment data.
The main difference between these two variants of the UCTP is that in the PE-CTP, all objectives and constraints are based on the student’s enrollment in various course events, whereas in the CB-CTP, all objectives and constraints are associated with the curriculum conception, which is a set of courses that form a complete assignment for a group of students. An illustration of a student’s preference in the PE-CTP can be seen in the statement, “A student should have multiple events in a day.” Similarly, for the CB-CTP, a teacher’s preference can be exemplified by the statement, “A teacher prefers to have no more than two consecutive lectures.” These timetabling problems involve two types of constraints: hard and soft. Hard constraints are those that must be satisfied under any circumstances. A timetable is considered feasible if it successfully satisfies all hard constraints. On the other hand, soft constraints are more flexible and can be violated if necessary, but it is desirable to minimize these violations due to associated penalty costs. The lower the total value of the penalty cost, the higher the quality of the timetable. Thus, the main objective is to create a high-quality schedule with minimal penalties for violations of soft constraints.
Educational timetabling has been studied for over 60 years, beginning with Gotlieb [3]. Over the years, many solution approaches have been proposed by researchers. Carter et al. [4] provided an overview of the primary solution approaches for the UCTP and roughly divided them into four categories: constraint-based, sequential, clustered, and metaheuristic methods. In recent years, metaheuristic algorithms have been successfully applied for both variants of the UCTP and are classified into local area-based and population-based approaches. Local area-based algorithms, also called single-point algorithms, focus more on exploitation than exploration [5]. These algorithms work iteratively on a single solution and may not thoroughly explore the entire solution space. Examples of local area-based algorithms include tabu search (TS), iterated local search (ILS), very large neighborhood search (VLNS), and simulated annealing (SA). On the other hand, population-based algorithms, also known as multiple-point algorithms, are good at exploration rather than exploitation [6]. These algorithms maintain multiple solutions within a population and employ a selection process to update the solutions. They extensively search the entire solution space to find a globally optimal solution and are sometimes referred to as global area-based algorithms. Consequently, these algorithms do not focus solely on individuals with good fitness within a population but instead explore the entire solution space to identify potential solutions. However, premature convergence is the main disadvantage of such types of algorithms. Commonly utilized population-based algorithms for timetabling problems include the genetic algorithm (GA), artificial bee colony (ABC), particle swarm optimization (PSO), and ant colony optimization (ACO).
2. PE-CTP
The history of the educational scheduling problem can be traced back over six decades, starting with [3]. Over the years, numerous researchers have proposed different solution approaches and tested them on real-world problem instances. Despite significant progress in this field, researchers have faced difficulties when comparing their algorithms with existing state-of-the-art solutions due to differing problem formulations and instances used by each researcher. To address this issue, the International Metaheuristic Network organized the First International Timetabling Competition (ITC2002) in 2002. The objective was to simulate a realistic scenario where students have priorities when selecting events, and the timetable is constructed based on these preferences. Since then, these artificially generated enrollment-based course timetable problem instances have become the standard in the research community. Various researchers have utilized these instances to demonstrate the effectiveness of their novel techniques.
Socha et al. [7] utilized the same data generator to produce eleven instances of PE-CTP. They proposed the MAX-MIN ant system, which incorporates a local search routine optimized by creating an appropriate construction graph. The pheromone value determined the allocation of events to timeslots within specified bounds. The authors concluded that the MAX-MIN ant system outperformed random restart local search when applied to a set of typical problem instances. Rossi et al. [8] conducted a fair comparison of five different metaheuristic algorithms for solving the PE-CTP by using a common solution representation and standard neighborhood structure. Their empirical investigation revealed that each metaheuristic has distinct capabilities in satisfying hard and soft constraints, and an approach suitable for hard constraints may not be appropriate for optimizing soft constraints. Ref. [9] introduced a TS hyper-heuristic where heuristics compete to be selected by the hyper-heuristic.
Burke et al. [10] introduced an investigation into a simple, generic hyper-heuristic method for solving the PE-UCTP. They employed a set of widely used constructive heuristics, specifically graph coloring heuristics. The main characteristic of their method is to utilize a TS approach to alter the permutations of six graph coloring heuristics before creating a timetable. The outcomes of the approach improved further when a higher number of low-level heuristics were applied. In [11], an adaptive randomized descent algorithm (ARDA), which employs an adaptive criterion to escape from local optimal solutions, is described. Ref. [12] proposed a basic harmony search algorithm (BHSA) that takes advantage of the benefits of population-based algorithms by identifying the promising region in the search space using memory consideration and randomness. The proposed approach also used the benefits of local area-based algorithms by fine-tuning the search space region. They also introduced two modifications to the BHSA and proposed a modified harmony search algorithm (MHSA). The first modification involved considering memory, while the second modification aimed to enhance the functionality of the pitch adjustment operators by replacing the acceptance rule from a ‘random walk’ to a ‘first improvement’ and ‘side walk’ approach.
The approach by Cambazard et al. [13] for PE-CTP utilized constraint programming techniques and LS. They demonstrated the advantages of applying a list-coloring relaxation to the problem. They achieved the best constraint programming approach through various investigations and maintained the original problem decomposition. Additionally, they introduced lower bounds to estimate the costs related to the soft constraints in the problem. Motivated by the perception of a gravitational emulation local search algorithm, ref. [14] proposed a new population-based local search (PB-LS) heuristic for their solution. The authors integrated a multi-neighborhood particle collision algorithm and an adaptive randomized descent algorithm into their proposed approach, aiming to address the constraints of population-based algorithms. Ref. [15] proposed an integer linear programming-based heuristic to solve a real-world PE-CTP arising in an institution in Buenos Aires, Argentina. The algorithm produced high-quality results and provided generalizations to other related problems in the literature. Ref. [16] proposed a two-stage approach for solving the PE-CTP. The first phase focused on obtaining a feasible solution by satisfying all the hard constraints. In the second phase, they aimed to improve the solution quality by minimizing violations of soft constraints. To execute this two-phased approach, they employed an enhanced version of the SA with a reheating algorithm called simulated annealing with improved reheating and learning (SAIRL). Additionally, they introduced a reinforcement learning-based approach to establish an effective neighborhood structure for search operations.
Over the years, many hybrid approaches by hybridizing a local area-based algorithm within a population-based algorithm have gained much interest [17]. Such hybridization aims to achieve an equilibrium between exploration and exploitation of the search space to achieve the benefits of population-based and local area-based approaches. Ref. [18] proposed GA with a repair function and local search for solving PE-CTP. They presented a new repair function capable of transforming an unfeasible timetable into a feasible one. The local search algorithm was employed before the next generation to enhance timetable quality. A hybrid evolutionary algorithm employing hybridization between a memetic algorithm and a randomized iterative improvement local search was given by [19]. They reduced the exploration ability of the search space by excluding the crossover operator from the memetic algorithm. Ref. [20] suggested a guided search genetic algorithm (GSGA) consisting of a guided search strategy and a local search technique for their solution. The guided search strategy introduced offspring into the population based on a data structure that stores information extracted from previous competent individuals. Subsequently, the LS technique is employed to enhance the overall quality of individual outcomes. Ref. [21] further proposed an extended guided search genetic algorithm (EGSGA) by introducing a new local search strategy in addition to the original local search strategy used in GSGA.
Ref. [22] proposed a hybrid metaheuristic algorithm that combines an electromagnetic-like mechanism and the great deluge algorithm for solving both variants of UCTP. The electromagnetic-like mechanism is a population-based stochastic global optimization approach that simulates the attraction, physics, and repulsion of sample points in moving toward optimality. The great deluge algorithm is a local search strategy that allows the worst solutions to be accepted by an upper boundary. The dynamic force estimated from the attraction–repulsion mechanism is used as a declining rate to update the search procedure. Ref. [23] presented a hybrid metaheuristic approach that combines the great deluge and tabu search. They proposed their solution approach for both PE-CTP and CB-CTP. The algorithm is divided into two parts, construction and improvement, and four different neighborhood moves are employed. Ref. [24] proposed a new hybrid algorithm that combines GA with local search and uses events based on groupings of students. Ref. [25] proposed a solution for the PE-CTP that is motivated by particle swarm optimization and implemented in the basic artificial bee colony algorithm. The algorithm was hybridized with the great deluge algorithm to enhance local exploitation capabilities and improve global exploration quality. This approach achieved equilibrium by using a combination of these techniques. Ref. [26] developed a new hybrid method that combines genetic-based discrete particle swarm optimization with local search and tabu search approaches for solving the PE-CTP.
A hybrid approach based on the improved parallel GA and LS (IPGALS) is proposed to solve the PE-CTP by [27]. The GA is enhanced by incorporating LS. IPGALS adopts a timetable representation, guaranteeing the preservation of hard constraints. The proposed approach is run parallel to enhance the GA searching process due to various problem constraints. The algorithm was tested on benchmark PE-CTP problem instances, and the results were compared to other methods previously used to solve PE-CTP, and it was found to be very effective. Ref. [28] proposed a review paper regarding the most recent scientific approaches applied to the UCTP. The study demonstrates different methodologies researchers use to solve the problem based on when they were created and what data they used. The paper also discusses the challenges and opportunities while solving the UCTP. They have found that metaheuristic approaches are widely favored, with hybrid and hyper-heuristic approaches subsequently employed to achieve effective outcomes. They also observed that the most advanced techniques found in the scientific literature are not always used in the real world, probably because they are not adaptable enough.
3. CB-CTP
After successfully organizing ITC2002, the research community in the field of timetabling organized the Second International Timetabling Competition (ITC2007) in 2007 [2]. During this event, they introduced three tracks for educational timetabling problems, with the third track focusing on curriculum-based course timetabling applied to Italian universities. For this track, several datasets were derived from real-world examples provided by the University of Udine. These datasets primarily emphasized lecturers’ preferences rather than students’, as is the case in PE-CTP.
By nature, CB-CTP is a highly constrained and complicated combinatorial optimization problem extensively studied by a large number of researchers [22,29,30,31,32,33]. They classified them first, along with their mathematical formulations, and then proposed several solutions approaches. In general, there is no known efficient deterministic polynomial-time algorithm for their solution, and they are solved by a variety of exact and heuristic approaches. Ref. [4] discussed their main solution approaches and roughly divided them into four categories: constraint-based, sequential, clustered, and generalized search (metaheuristics) methods. In constraint-based approaches [29,34], these problems are represented as constraint satisfaction problems (CSPs) and solved using CSP-solving approaches. Ref. [29] proposed to formulate the timetabling instance of CB-CTP as CSP instances and applied a general-purpose CSP solver to find solutions. The solver effectively handled weighted constraints using a hybrid algorithm combining tabu search and ILS. Ref. [35] introduced a constraint-based solver approach for CB-CTP that included multiple local search approaches working in three stages.
Ref. [31] proposed a two-stage integer linear programming (ILP) model for the solution of CB-CTP. The approach involves decomposing the problem into two stages, each represented by a distinct ILP model. In the first stage, the objective is to assign lectures to time periods, whereas the assignment of lectures to rooms is performed in the second stage by considering room stability. In the first stage, the assignment is performed without considering rooms, minimum working days, curriculum compactness, or minimizing penalties for room capacity. The representation of CB-CTPs as graphs is demonstrated in [36], where vertices and connections correspond to the lectures of courses and the constraints between them. Subsequently, graph coloring algorithms are employed to solve these CB-CTPs. Although this kind of approach (sequential heuristics) has demonstrated greater efficiency in small-sized problem instances, it seems ineffective in large-sized problem instances. Ref. [37] have proposed a satisfiability (SAT) model to solve a real-world CB-CTP at a Mexican university. Ref. [38] proposed a harmony search algorithm for the solution of CB-CTP. In the execution of their algorithm, the process of improvisation consists of memory consideration, random consideration, and pitch adjustment. A high-level object-oriented model called QuikFix has been proposed by [39] for the solution of CB-CTP. A repair-based heuristic is used in their approach, and certain structural constraints and significant neighborhood moves are applied in the problem domain’s search space.
Other extensively explored areas, such as the adaptive approaches, metaheuristics, multi-criteria, and case-based reasoning discussed by [40], are also used to solve these problems. In recent years, metaheuristic approaches and hybrid approaches have been extensively used to solve CB-CTP. These metaheuristic approaches are motivated by nature and apply nature-like processes to obtain optimal or near-optimal solutions. These approaches are generally categorized as local area-based (ILS, TS, SA, and VLNS) and population-based (GA, ACO, ABC, and PSO) algorithms. According to [41], an ABC algorithm has four phases: initialization, the employed bee phase, the onlooker bee phase, and the scout bee phase. Ref. [42] proposed a new swarm intelligence algorithm based on ABC to solve the CB-CTP. Their algorithm works in two phases. The first phase is used to obtain a feasible solution by satisfying all the hard constraints. In contrast, the second phase is used to satisfy as many soft constraints as possible without violating any hard constraints. Ref. [32] proposed an adaptive tabu search (ATS) algorithm for their solution by the hybridization of TS and ILS. The algorithm uses two neighborhood structures, namely SimpleSwap and KampeSwap, and a standard tabu list to prevent the cycling of previously visited solutions for both moves.
Ref. [30] proposed a two-phase approach for resolving the CB-CTP problem in their publication. The first phase involved utilizing a robust single-stage simulated annealing method for problem-solving, while in the second phase, an extensive and statistically sound methodology was designed and applied for the parameter tuning process. This resulted in a methodology that models the relationship between search method parameters and instance features, allowing for the parameters of unseen instances to be set through a simple inspection. In [43], the CB-CTP was modeled as a bi-criteria optimization problem with two objectives: a penalty function and a robustness metric. The problem was resolved using a hybrid multi-objective genetic algorithm that integrates hill climbing and simulated annealing algorithms with the standard GA approach to produce an accurate approximation of the Pareto-optimal front. Ref. [33] explored the use of generational construction hyper-heuristics for automating the process of low-level construction heuristic generation for CB-CTP. Two hyper-heuristics, an arithmetic hyper-heuristic for evolving arithmetic heuristics and a genetic algorithm hyper-heuristic made up of ten problem attributes for generating hierarchical heuristics, were implemented and applied to solve CB-CTP.
Ref. [44] presented an answer set programming-based approach, termed a teaspoon, for solving the CB-CTP. In this approach, the system first reads a CB-CTP instance of a standard input format and converts it into a set of answer set programming facts. These facts are then combined with the first-order encoding for CB-CTP solving, which any off-the-shelf ASP system can subsequently solve.
This entry is adapted from the peer-reviewed paper 10.3390/axioms12080720
This entry is offline, you can click here to edit this entry!
