# An Assignment Problem and Its Application in Education Domain: A Review and Potential Path

Authors: Syakinah Faudzi; Syariza Abdul-Rahman; Rosshairy Abd Rahman
Journal: Advances in Operations Research
 (2018)

---

## Abstract

This paper presents a review pertaining to assignment problem within the education domain, besides looking into the applications of the present research trend, developments, and publications. Assignment problem arises in diverse situations, where one needs to determine an optimal way to assignn subjects to m subjects in the best possible way. With that, this paper classified assignment problems into two, which are timetabling problem and allocation problem. The timetabling problem is further classified into examination, course, and school timetabling problems, while the allocation problem is divided into student-project allocation, new student allocation, and space allocation problems. Furthermore, the constraints, which are of hard and soft constraints, involved in the said problems are briefly elaborated. In addition, this paper presents various approaches to address various types of assignment problem. Moreover, direction and potential paths of problem solving based on the latest trend of approaches are also highlighted. As such, this review summarizes and records a comprehensive survey regarding assignment problem within education domain, which enhances one’s understanding concerning the varied types of assignment problems, along with various approaches that serve as solution.


---

## Body

## 1. Introduction

Problems related to assignment arise in a range of fields, for example, healthcare, transportation, education, and sports. In fact, this is a well-studied topic in combinatorial optimization problems under optimization or operations research branches. Besides, problem regarding assignment is an important subject that has been employed to solve many problems worldwide [1]. This problem has been commonly encountered in many educational activities all over the world. Within the education domain, this review classified the assignment problem into two: timetabling problem and allocation problem.Assignment problem refers to the analysis on how to assignn objects to m objects in the best possible way (optimal way) [2, 3]. The two components of assignment problem are the assignments and the objective function. The assignment signifies underlying combinatorial structure, while the objective function reflects the desires to be optimized as much as possible. Nonetheless, the question is, “how to carry out an assignment with optimal objective, and at the same time, fulfilling all the related constraints?” In order to address the question, several diverse methods have been proposed [1, 2], such as the exact method [4], the heuristics method [5], the local search-based [6], the population search-based [7], and the hybrid algorithm [8].The aim of looking into assignment problem is to discover an assignment among two or more sets of elements, which could minimize the total cost of all matched pairs. Relying on the specific structure of the matched sets and the cost function form, the allocation problems can be categorised into quadratic, bottleneck, linear, and multidimensional groups [9]. Hence, every assignment problem has a table or matrix. Normally, the rows are comprised of objects or people to assign, while the columns consist of the things or tasks to be assigned. Meanwhile, the numbers in the table refer to the costs related to every particular assignment. With that, this study presents a review of assignment problem within educational activities, where the problems were classified into timetabling and allocation problems. In fact, studies within this area have commonly displayed substantial progress with diverse methodologies.The organization of this paper is given as follows: Section2 discusses the definition and the mathematical formulation of general assignment problem. Next, the types of assignment problem within the education domain, along with their approaches, are presented in Section 3. In fact, this section is divided into subsections that elaborate in detail the two types of problem: (i) timetabling problem and (ii) allocation problem. Finally, the conclusion, future direction, and potential path of solution approach are presented in Section 4.


## 2. Definition and Mathematical Formulation of General Assignment Problem

The general aim of assignment problem is to optimize the allocation of resources to demand points where both resources and demand point share equal number [1]. The problem, hence, can be mathematically presented as follows:Optimize(1)∑i=1n∑j=1ncijxijsubject to(2)∑j=1nxij=1,i=1,…,n(3)∑i=1nxij=1,j=1,…,n(4)xij=0or1,i=1,…,n,j=1,…,nwhere cij is the cost or effectiveness of assigning ith resource to jth demand, xij is 0 or 1 (as presented in (4)), and n is the number of resources or demands. The constraints of the problem are defined as (2) and (3). Equation (2) indicates that each resource i needs to be assigned to only one demand j, while (3) shows that each demand j needs to be assigned to only one resource i.In relation to every assignment problem, there is a matrix named cost or effectiveness matrixcij, where cij is the assigning cost of ith resource to jth demand. In this paper, it is called an assignment matrix, where every resource can be assigned to only one demand and signify it, as given in the following:(5)c11c12c13⋯c1nc21c22c23⋯c2n⋮⋮⋮⋮⋮cn1cn2cn3⋯cnnMoreover, in solving assignment problem, some constraints need to be fulfilled under certain conditions. These constraints are recognized as “hard” constraints as they must adhere to any condition, in which satisfying the condition(s) could generate feasible solution. On the other hand, “soft” constraints are considered as needed, but not crucial. In reality, it is very rare to fulfil all the soft constraints. Usually, the violated soft constraints assessed the solution quality as the objective function (cost function or “fitness” or “penalty”) [10]. When the soft constraints are adhered, they will not affect the solution feasibility, but they have to be fulfilled as much as possible to gain a solution with high quality. Besides, handling a great range of constraints is a pretty tough task. Each added constraint will increase the difficulty and the complexity of the problem, thus making the solution extra resource consuming. Some instances of constraints involved within assignment problem are as follows: the number of students in a room may not surpass the capacity of the room, and a lecturer may prefer to teach in a specific room or an exam should take place in a specific building.


## 3. Types of Assignment Problems and Their Approaches

In this review, assignment problem within the education domain is classified into two problems, which are timetabling and allocation problems. As such, this section discusses these two problems, along with the approaches on solving the problems. Furthermore, varied methods have been used in prior studies to solve assignment problem. In fact, there are countless number and a diverse of complex problems that appear in real-life applications that need to be solved. Eventually, this has served as motivation to encourage the development of well-organized procedures to produce good solutions, even if not optimal. Therefore, choosing an appropriate solution is the key of success factor to achieve optimized results. The discussion on approaches in allocation problem is divided into exact method, heuristic and metaheuristic (local search- and population search-based), hybrid, and other techniques.In fact, according to Martí et al. [11], exact methods assure to provide an optimum solution, while heuristic methods simply try to produce a good but not certainly optimum solution. Nevertheless, the duration to find an optimum solution of a complex problem of exact method is more complicated than that of the heuristic (due to incorporation of many irrelevant cases). Besides, there are several exact methods, for example, dynamic programing, integer programming, and linear programming. Moreover, the exact method guarantees to produce an optimum solution and assesses its optimality [12]. Heuristics and metaheuristics, on the other hand, are often used when the problem becomes too large for exact methods. Heuristic methods attempt to produce a good but not certainly optimal solution. Meanwhile, metaheuristic can be categorised into two, which are local search-based and population search-based techniques. The local search techniques iteratively employ single candidate solution for improvement and the examples are simulated annealing (SA), Tabu search (TS), and great deluge (GD), whereas the population-based techniques employ a population of candidate solutions throughout the iterative search process for further improvement, such as Fly Algorithm, genetic algorithm (GA), and Ant Colony Optimization. Furthermore, hybrid algorithms have also been applied in solving assignment problem, where it unites a few algorithms to solve a problem. The hybridization can be done by either selecting one or switching the algorithms. The next subsections discuss these problems.


### 3.1. Timetabling Problem

Timetabling problem is considered as a type of assignment problem. A timetable usually provides information about the time for particular events to occur and eventually relates to the resources allocation [13]. Besides, timetabling is described as an assignment of events to a limited number of timeslots and rooms subject to prescribed constraints [12]. In reality, allocation of resources at a specified time is indeed necessary. The problem is challenging because one has to schedule a large number of entities and satisfy a number of constraints and preferences. According to Burke et al. [14], “a timetabling problem is a problem with four parameters: T, a finite set of times; R, a finite set of resources; M, a finite set of meetings; and C, a finite set of constraints. The problem is to assign time and resources to the meetings so as to satisfy the constraints as much as possible.” As such, timetabling problem is classified into three subproblems, which are examination timetabling problem (ETP), course timetabling problem (CTP), and school timetabling problem (STP). They are further discussed in the following subsections.


#### 3.1.1. Examination Timetabling Problem

The examination timetabling problem (ETP) is defined as an assignment of a set of examinations to a set of timeslots while simultaneously satisfying several problem constraints. According to Carter and Laporte [15], ETP is defined as a process of assigning examinations to a limited number of timeslots with the aim of producing high quality timetable subject to constraints. In fact, the main objective of this problem is to produce timetable that optimizes certain objective functions. A set of examinations, E=e1,e2,…,en, needs to be assigned to a limited number of timeslots, T=t1,t2,…,tn, subject to certain restricted constraints. In fact, Even et al. [16] claimed that ETP is considered as an NP-hard real-world problem, which is rich and diverse, besides involving some significant levels of information from the connected problems. Meanwhile, according to McCollum [17], the complexity of the problem in recent years is related to the increasing number of student enrolments, course flexibility, and various preferences. The manual solution proposed by institution is usually time-consuming and lacks feasibility, thus requiring advanced techniques so as to satisfy both institutional and personal preferences.Hence, in considering the problem solution, the hard constraints have to be strictly obeyed under any condition to ascertain solution feasibility. On the other hand, although the soft constraints do not affect the solution feasibility, they must be satisfied as much as possible in order to produce a solution with high quality. In assessing timetable quality, both hard and soft constraints in ETP are described in Table1.Table 1
The hard and soft constraints within the ETP adopted from Qu et al. [18].
Constraint type Descriptions Hard constraints (i) Student should not sit two examinations at one time. (ii) The total number of students in the examination room should not exceed the room capacity.  Soft constraints (i) Examinations that are in conflict should be distributed within the timetable as evenly as possible. (ii) Some examinations are required to be scheduled at a particular location or on the same day. (iii) Examinations should be scheduled consecutively. (iv) Examinations with large enrolment size should be scheduled as early as possible. (v) Examinations with limited enrolment should be scheduled into a particular timeslot. (vi) Some examinations are required to be scheduled within a particular timeslot. (vii) Examinations in conflict on the same day should be located nearby. (viii) Examinations should be split over similar locations. (ix) Examinations with the same duration should be allocated the same room. (x) Resource requirements for certain examinations should be met.With that, Burke et al. [18] performed a survey that discovered the diverse real-life constraints within several academic institutions located in Britain. The constraints were imposed on the needs of the institutions, which were categorised as time- and resource-related.Moreover, a broad range of real-world datasets have been introduced in the literature with various practical constraints (see Table2). In addition, these varied approaches have been tested on the proposed dataset for verification. The most frequently tested datasets are Toronto [27], Nottingham [28], and Melbourne [19]. Meanwhile, the dataset from the Second International Timetabling Competition [29] has also been used for verification purpose. Moreover, by using the benchmark dataset, varied advanced approaches had been developed to further encourage advanced scientific researches.Table 2
Summary of real-world examination timetabling datasets from different institutions.
Reference Institution (s) Ayob et al. [5] Universiti Kebangsaan Malaysia  Carter et al. [15] Carleton University, Ottawa; Earl Haig Collegiate Institute, Toronto; Ecole des Hautes Etudes Commercials, Montreal; King Fahd University, Dharan; London School of Economics; Ryeson University, Toronto; St. Andrew's Junior High School, Toronto; Trent University, Peterborough, Ontario; Faculty of Arts and Sciences, University of Toronto; Faculty of Engineering, University of Toronto; York Mills Collegiate Institute, Toronto  Burke et al. [18] University of Nottingham  Merlot et al. [19] University of Melbourne  Ergül [10] Middle East Technical University  Wong et al. [20] Ecole de Technologie Superieure  Kendall and Hussin [21] University of Technology MARA  Tounsi [22] Prince Sultan University  Kahar and Kendall [23] Universiti Malaysia Pahang  Yong and Yi [24] Hubei University of Technology  Innet [25] University of the Thai Chamber of Commerce  Abdul-Rahman et al. [26] Universiti Utara MalaysiaReal-world timetabling problems are normally complex as they involve various constraints and require significant computational effort. In many practical situations, obtaining a good quality timetable by using the exact method is very challenging, thus leading researchers to opt heuristic approaches. Meanwhile, in academic literature, a variety of timetabling problems and solution methodologies that focus on difficulty and efficiency of the problem solving have been discussed (see Table3).Table 3
Summary of related studies in ETP.
Approach Reference (s) Exact method Integer programming Qu et al. [30] Column generation Woumans et al. [31]  Heuristic Technique Graph colouring heuristics Ayob et al. [5]; Abdul-Rahman et al. [26]; Abdul-Rahman et al. [33]; Kahar and Kendall [23]; Kahar and Kendall [37]; [34] Abdul-Rahman et al.; [35] Abdul-Rahman et al.; [36] Abdul-Rahman et al. Hyper-heuristics Burke et al. [38]; Sabar et al. [39]; Muklason et al. [40]  Metaheuristic technique Local search based Hill climbing Caramia et al. [6] Tabu search Sabar et al. [41]; Amaral and Pais [42] Variable neighbourhood search Abdul-Rahman et al. [43] Great Deluge Kahar and Kendall [23] Population search based Memetic algorithm Ersoy et al. [7] Genetic algorithm Pillay and Banzhaf [44]; Innet [25]  Hybrid Great Deluge + electromagnetic-like mechanism Turabieh and Abdullah [8] Hyper-heuristics + estimation distribution algorithm Qu et al. [45] Harmony search hyper-heuristics Rankhambe and Kavita [46] Bee colony optimization + late acceptance hill climbing + simulated annealing Alzaqebah and Abdullah [47]The exact approaches have been used to solve examination timetabling, which evokes mathematical procedures, such as objective function and related constraints. The approaches required to develop a mathematical model should be wisely developed and treated. In fact, the aim of the exact approaches is to obtain an optimal solution, but solving complex problems is computationally expensive. As such, Qu et al. [30] proposed integer programming in order to solve the intricacy of examination timetabling by dividing the problem into two subproblems, which are “easy” and “difficult”. Woumans et al. [31], on the other hand, solved the ETP by using column generation approach that considered student-centric to improve the spread of exam by dynamically allowing more versions of exams.In solving this problem, the constructive approach is one that is popular as it incrementally forms a complete solution using construction heuristics [28]. The graph colouring heuristics as a constructive approach presents the vertices as the examinations, the edges as the conflict between two examinations, and the vertices colour as varying timeslots in the timetable.Additionally, the concept of “squeaky wheel optimization” was initiated by Burke and Newall [32] to assist heuristic modifier based on basic graph colouring heuristic technique to promote difficult examinations to be scheduled first iteratively based on ordering. The study was further investigated by Abdul-Rahman et al. [26] by integrating shuffling strategies to different graph colouring heuristics. Another recent study by Abdul Rahman et al. [33] considered a linear combination of graph colouring heuristics with a heuristic modifier to calculate the difficulty score of each examination. The examinations were ordered based on new difficulty score and the examination with the highest difficulty score was scheduled first. The experiment on two benchmark datasets of ETP showed that the proposed approach generated competitive results among other examination timetable approaches.In another study, Abdul-Rahman et al. [34] considered nonlinear heuristic modifier of graph coloring heuristics to construct solutions for examination timetabling problem. A nonlinear range was proposed using nonlinear heuristic modifier to estimate a difficulty value of an examination so that an effective estimation of examination’s difficulty could be obtained. A web-based examination timetabling system was introduced in Abdul-Rahman et al. [35] by incorporating a multiobjective approach based on graph colouring heuristics. The web-based system was developed for Universiti Utara Malaysia. The study also emphasizes the graphical user interface (GUI) of the system that enables the user to participate in the input, construction, and modification of a timetable. Abdul-Rahman et al. [36] developed an adaptive decomposition and ordering strategy that automatically divides examinations into difficult and easy sets based on graph colouring heuristics for constructing an examination timetable. The examinations in the difficult set are considered to be hard to place by referring to their number of conflict examinations and hence are listed before the ones in the easy set in the construction process.Meanwhile, in solving the ETP at Universiti Malaysia Pahang (UMP), Kahar and Kendall [23] presented a solution by using constructive heuristics, which was compared with a manual solution. The study introduced predetermined room grouping, room searching, and room selection. Based on the graph colouring heuristics, an algorithm was developed to produce a greater solution for the present software. The problem was further investigated by Kahar and Kendall [37] by incorporating invigilator requirement in the timetable using graph colouring approach. Other than that, Burke et al. [38] investigated Monte Carlo hyper-heuristics as a learning mechanism, which was incorporated in search process for ETP. It was found that the choice function appeared to be the best alternative for SA with reheating move acceptance within the hyper-heuristics approach. Next, Sabar et al. [39] introduced a measurement of difficulty index to measure examination difficulty within a hybridization of hierarchical low-level graph colouring heuristics approach, whereas Muklason et al. [40] investigated the fairness in examination timetabling by introducing multiobjective solution, also using the hyper-heuristics approach.Additionally, the local search-based algorithms have successfully solved ETPs. Caramia et al. [6] proposed a hill climbing algorithm as a penalty-decreaser in improving the quality of the timetable. The iterative process by the penalty-decreaser continued to search until no improvement was detected and the penalty-trader, i.e., hill climbing, took over the process. Later, Sabar et al. [41] proposed a hybrid tabu search with exponential Monte Carlo procedure to solve ETP. The work is an extension from Ayob and Kendall’s [48]. A counter-strategy was incorporated to calculate the successive nonimproving iterations to control the acceptance of worse solution. Meanwhile, Amaral and Pais [42] proposed a multiobjective tabu search approach with two new features to increase the algorithm automation. The approach, which was tested on ETP, exhibited that human interference could be avoided by combining weighting functions and compromise ratios.Moreover, Abdul-Rahman et al. [43] investigated the methods of ordering neighbourhood structures within a Variable Neighbourhood Search. The proposed approach hybridized a great deluge algorithm as a move acceptance method to vary the acceptance level. As a result, the empirical findings of a well-known examination timetabling benchmark displayed that the performance of Variable Neighbourhood Search great deluge had been reasonably well, ranking second among previously proposed approaches, with the right choice of initialisation and neighbourhood ordering methods. Next, a modified great deluge approach was proposed by Kahar and Kendall [23] to solve an ETP at Universiti Malaysia Pahang. The study concluded that the iterative process, neighbourhood, and starting solution were important factors that significantly affected the search for solution.On top of that, the population search-based algorithms were applied in solving ETPs. A hyper-heuristic methodology, known as “hyperhill-climber”, was proposed by Ersoy et al. [7]. The proposed approach employed an adaptive memetic algorithm to select the best hill climber. The hill climber determined the best ordering for the successive application of hill-climbers. Meanwhile, Pillay and Banzhaf [44] proposed a two-phased GA that was employed to induce a solution for ETP so as to cater to both hard and soft constraints. The findings showed that the proposed solutions outperformed other evolutionary approaches on some benchmark instances. Next, Innet [25] proposed a GA model in order to solve ETPs by using three genetic operators: crossover, mutation, and selection, in order to improve the effectiveness of automatic arranging examination timetable.Other than that, Turabieh and Abdullah [8] proposed a hybrid approach that considered a great deluge algorithm and an “electromagnetic-like mechanism” heuristics within timetabling approaches. An Estimation Distribution Algorithm-based hyper-heuristic was developed by Qu et al. [45] to solve ETP. The proposed approach is comparable with other hyper-heuristic approaches and was found suitable for specific problem solving situations. On top of that, Rankhambe and Kavita [46] developed harmony search hyper-heuristics, where the harmony search algorithm was based on heuristic harmony memory as low-level heuristics. The findings showed that the approach performed well on University of Nottingham benchmark datasets. Besides, Alzaqebah and Abdullah [47] hybridized bee colony optimization with late acceptance hill climbing and SA algorithms to solve the problem. As such, special selection strategies and self-adaptive neighbourhood mechanism were introduced to maintain the population diversity in backward pass, as well as to enhance the neighbourhood search. An extensive compilation of methodologies for ETP can be viewed in [49].


#### 3.1.2. Course Timetabling Problem

Course timetabling refers to the process of assigning courses, rooms, students, and lecturers to a fixed time period, typically a working week, while satisfying a given set of constraints [50]. According to Obit [51], university course timetabling is considered as a weekly schedule of all university lecturers to a set of courses and at the same time to prevent the lecturers to have students in common at two different timeslots. Moreover, Obit [51] stated that, in reality, examination and course timetabling problem are about the same in some attributes but portray some variances. For instance, in examination timetabling, the room may have more than one examination scheduled at the same time, providing that the room seating capacity is not exceeded, while this is impossible for course timetabling, where the assignment normally allows one course per room, per timeslot.Typically, while constructing a feasible timetable for a course timetabling problem to satisfy all the hard constraints, the objective function of the problem has to be minimized, which usually reflects the violation of soft constraints. Some instances of the hard and soft constraints of course timetabling problem are presented in Table4. Other examples of constraints involved in course timetabling are that each course should be composed of the correct number of lecturers, no student can attend more than one lecture at the same time, and one lecturer has to be scheduled in exactly one room [52, 53].Table 4
The hard and soft constraints within the CTP adopted from Obit [51].
Constraint type Descriptions Hard constraints (i) The room capacity must be equal to or greater than the number of students attending the event in each timeslot. (ii) A student cannot attend two events simultaneously. (iii) Only one event is allowed to be assigned per timeslot in each room. (iv) The room assigned to an event must satisfy the features required by the event.  Soft constraints (i) Students should not have only one event timetabled on a day. (ii) Students should not attend more than two consecutive events on a day. (iii) Students should not attend an event in the last timeslot of a day.The real-world datasets employed in solving course timetabling problem from various institutions are depicted in Table5. There are also benchmark datasets for the CTP, commonly used as test bed such as Socha et al. [53], International Timetabling Competition 2002 and 2007 [29].Table 5
Summary of real-world course timetabling datasets from different institutions.
Reference Institution (s) Gunawan [54] University in Indonesia Oladokun & Badmus [55] University of Ibadan Thongsanit [56] Silpakorn University Borchani et al. [57] Tunisian University Méndez-Díaz et al. [58] A private university in Buenos Aires, Argentina Wahid and Hussin [59] Universiti Utara MalaysiaA number of solutions for course timetabling problems have been discussed in the academic literature (see Table6). An exact approach was proposed by Oladokun and Badmus [55] in optimizing the allocation of limited resources available for lecturing. As a test case, the study modeled and solved course timetabling problem for University of Ibadan. Furthermore, the integer linear programming (ILP) was applied in solving the problem. Next, Thongsanit [56] solved the course-classroom assignment problem for Silpakorn University within a short time and at a minimum cost. In solving the problem, the aim was to develop a mathematical model and to design the related methods. The study presented a guide to improve the solutions for classroom allocation problem with the aim of assigning courses to classrooms at a minimal cost. Meanwhile, Vermuyten et al. [60] investigated the flow of students within a course timetable problem by minimizing the travel time between consecutive lectures based on pedestrian traffic models. The problem was solved by using the decomposition approach as two-stage IP exhibited rather exceptional solutions.Table 6
Summary of studies related to CTP.
Approach Reference (s) Exact method Integer linear programming Oladokun and Badmus [55]; Thongsanit [56] Decomposition approach Vermuyten et al. [60]  Heuristic technique Integer linear programming based heuristics Méndez-Díaz et al. [58]  Metaheuristic technique Local search based Simulated annealing Ceschia et al. [61] Hyper-heuristics iterated local search Soria-Alcaraz et al. [62] Two stage metaheuristics Lewis and Thompson [63] Local search-based algorithm with adaptive mechanism Nagata [64] Variable neighborhood descent Borchani et al. [57] Tabu search with sampling and perturbation + SA with reheating Goh et al. [65] Nonlinear great deluge hyper-heuristics with reinforcement learning Obit et al. [66] Population search based Ant colony optimisation Nothegger et al. [67] Genetic algorithm Song et al. [68]  Hybrid Integer programming + greedy heuristics + modified simulated annealing Gunawan et al. [54] Genetic algorithm + local search Badoni et al. [69] Artificial bee colony algorithm + hill climbing optimizer Bolaji et al. [70] Integer programming + greedy heuristics Ghiani et al. [71] Hybrid multi-objective genetic algorithm + hill climbing + simulated annealing Akkan and Gülcü [72] Harmony search with great deluge Wahid and Hussin [59]Other than that, by using the ILP-based heuristics, a post-enrolment course timetabling problem at a private university in Buenos Aires, Argentina, was solved by Méndez-Díaz et al. [58]. The study produced good quality results and generalized other problems from the related literature.Meanwhile, Ceschia et al. [61] proposed a metaheuristic approach based on SA in solving post-enrolment course timetabling. The proposed approach was tested on benchmark dataset, which showed that the proposed approach was appropriately developed and adjusted. This is because the proposed approach worked well on all datasets and produced new best solution for most of the instances. Next, Soria-Alcaraz et al. [62] developed a constraints’ generic structure of a course timetabling problem, in which the problem was solved by using hyper-heuristics iterated local search. Furthermore, online learning showed that the proposed approach generated competitive results compared to other approaches presented in the literature and produced a number of new best-known solutions.Accordingly, Nagata [64] developed a local search-based algorithm with adaptive mechanism in varying neighbourhood sizes for a post-enrolment-based course timetabling problem. The study found that the recommended approach produced competitive results for well-known benchmark dataset of the problem and foresaw the trade-off between exploration and exploitation by adjusting the neighbourhood size. Similarly, Borchani et al. [57] investigated a university course timetabling problem in Tunisia by using Variable Neighbourhood Descent, which successfully removed an average of 52.47% of holes and isolated sessions with the introduction of 11 specific neighbourhood structures. Meanwhile, Goh et al. [65] solved a post-enrolment course timetabling problem by using a two-phase algorithm. The tabu search with sampling and perturbation was introduced to efficiently find feasible solution, while the SA with reheating eliminated the extensive tuning and scalability of runtime. The proposed algorithm produced new best solution for many instances. Obit et al. [66] investigated reinforcement learning with static and dynamic memory within nonlinear great deluge hyper-heuristics. The study showed that the static one performed better than the dynamic when solving CTP.Moreover, in the course timetabling problem domain, some researchers proposed population-based metaheuristic approaches. For instance, Nothegger et al. [67] applied Ant Colony Optimization to tackle the post-enrolment course timetabling problem, which was specified in the competition, namely, International Timetabling Competition 2007. Next, Song et al. [68] developed an energy efficiency-based course timetabling algorithm that optimized the constructed timetable based on energy consumption using GA. The study found that the proposed algorithm saved up to 4% of energy during cooling and heating seasons, when compared to the existing timetable. In addition, more energy saving up to 5.0% was achieved by mitigating hard constraints.Additionally, Gunawan et al. [54] proposed a hybrid algorithm that combined IP, a greedy heuristic, and a modified SA algorithm to solve a teacher assignment-course scheduling problem. The problem mixed both teacher assignment and course scheduling problems as mathematical programming model. Later, Badoni et al. [69] developed a hybrid approach that combined GA and local search approach by using events based on groupings of students. The hybrid approach produced better results on benchmark datasets, in comparison to other approaches found in the literature pertaining to course timetabling problem. After that, Bolaji et al. [70] employed artificial bee colony algorithm and hill climbing optimizer as a hybrid method to solve a university course timetabling problem. The study showed that a well-designed hybrid technique appeared to be a good alternative to tackle the problem, as the results displayed better performance than the other techniques. Next, a study on a course timetabling problem related to remedial education was introduced by Ghiani et al. [71] who employed both IP and greedy heuristics. The study introduced the selection of remedial courses while considering budgets and operational constraints that helped the students to achieve particular competencies in several skills at varied levels. Besides, Akkan and Gülcü [72] proposed a hybrid multiobjective genetic algorithm that was tested on benchmark dataset of course timetabling problem. The hybrid approach employed hill climbing and SA, which produced highly robust solution close to the best-known results. Wahid and Hussin [59] employed hybrid harmony search with great deluge for solving a real case of CTP.


#### 3.1.3. School Timetabling Problem

The school timetabling problem (STP) is about generating school timetable that usually follows a cycle every week for all classes, in which the objective is to avoid teachers from attending two classes at the same time. In school timetabling, students are normally preassigned, while only teachers and rooms need to be assigned in the timetabling problem. As such, Cerdeira-Pena et al. [73] stated that STP is aimed at assigning period for teacher to certain subject in a specified group by considering groups of students and teachers in a fixed period scheduling. According to Pillay [74], STP is considered as NP-complete or NP-hard problem that depends on the intricacy of the problem in relation to various constraints. Moreover, studies on STP, along with its difficulty, had been investigated as early as 1976 by Even et al. [16] and more current analysis was undertaken by Carter and Tovey [75], Kingston [76], and Eikelder and Willemen [77], to name a few.In fact, the two types of constraints, which are hard and soft constraints, had been used to solve STP. With that, the fact that a teacher can only teach a lesson to one group at a time and the fact that a group cannot accept more than one lesson at a time by different teachers are examples of hard constraints. Usually, soft constraints depend on preferences by the teacher or are based on school policies, such as to minimize the number of periods for the teacher, to minimize the gaps within the timetable, and to avoid some subjects restriction at a prescribe time. Furthermore, Santos et al. [78] proposed that the basic hard constraints that need to be satisfied in school timetabling are that no teachers should be assigned to more than a class in the same timeslot, taking into account the teacher’s availability for each timeslot, and allocating the right number of timeslots for each teacher-class pair. Table 7 depicts the constraints proposed by Cerdeira-Pena et al. [73] in relation to STP.Table 7
The hard and soft constraints related to STP adopted from Cerdeira-Pena et al. [73].
Constraint type Descriptions Hard constraints (i) Overlaps: avoid the possibility of a class been taught by more than one teacher in the same period and avoid classes sharing resources (i.e., a classroom, lab, etc.), where classes which involved the same group could be assigned to the same period. (ii) Simultaneity: two classes are defined as simultaneous classes if they are taught by different teachers at the same time. (iii) Unavailability: it considers periods when a class cannot be given or when a teacher cannot teach. (iv) Consecutiveness: this constraint checks whether a distribution of hours for a pair teacher-class is followed. For example, some practical lessons should be taught in two consecutive periods of time.  Soft constraints (i) Overuse: it refers to the number of periods per day in which a teacher gives its lessons, over its specified maximum of periods per day. (ii) Underuse: when teachers have preferences on their minimum number of periods per day, it indicates the number of periods under such minimum. (iii) Holes: consider the number ofemptyperiods between two consecutive periods where a teacher is assigned a class. Breaks and free-time periods are not considered holes. (iv) Splits: consider the number of periods between two nonconsecutive assignments to the same class in the same day. (v) Groups: assuming a specified maximum of periods per day for an association teacher-class, it considers the number of exceeding periods in such day. This constraint is only considered if a maximum number of consecutive periods (related withconsecutiveness) for the pair class-teacher are not specified. (vi) Undesired: assuming that there are periods in which a teacher would prefer not to teach, this constraint indicates the number of such periods where that teacher is assigned a class. This constraint is thesoftversion of the mandatory unavailabilityconstraint (referring to teachers).The real-world datasets that had been used in solving STP are shown in Table8. Besides, the benchmark problems of STP are also available from Beligiannis et al. [79], Smith et al. [80], and International Timetabling Competition 2011 of High School Timetabling Archive XHSTT-2011 with 21 instances from 8 countries [81].Table 8
Summary of real-world school timetabling datasets from different institutions.
Reference Institution (s) Cerdeira-Pena et al. [73] Secondary school (I.E.S. Menendez Pidal) in A Coruna-Spain Santos et al. [78] Brazilian high schools Boland et al. [82] Australian high school Beligiannis et al. [79] Greek high schools Birbas et al. [83] Hellenic secondary school Ribić and Konjicija [84] Croatian secondary school Moura and Scaraficci [85] Brazilian high school Minh et al. [86] Vietnam high schoolsAs for the school timetabling field, several solutions were retrieved from the literature as described in Table9. Some approaches and new algorithms were applied and derived frequently over the years since school timetabling has further developed with SA, evolutionary algorithms, tabu search, IP, constraint programming, GRASP (Greedy Randomized Search Procedure), and so forth. Hybridizations are also some popular approaches in solving STP, which combine two or more methodologies. Comparative studies in STP were also conducted to compare the performance of several techniques. Normally, solving STP is computationally expensive and in order to reduce the running time, distributed methods have been suggested in association with the proposed approach.Table 9
Summary of studies related to STP.
Approach Reference (s) Exact method Integer Linear Programming Boland et al. [82]; Birbas et al. [83]; Ribić and Konjicija [84] Mixed Integer Programming Santos et al. [78]  Heuristic technique Hyper-heuristics Pillay [87]; Ahmed et al. [88]  Metaheuristic technique Local search based Simulated annealing Zhang et al. [89] Greedy Randomized Adaptive Search Procedure (GRASP) Moura and Scaraficci [85] Tabu search Minh et al. [86] Population search based Evolutionary algorithm Beligiannis et al. [79] Particle Swarm Optimization Tassopoulos et al. [90]  Hybrid Random Non-Ascendent Method (RNA) + genetic algorithm Cerdeira-Pena et al. [73] Simulated annealing + Tabu search Yongkai et al. [91]  Others Neural network Smith et al. [80]; Carrasco and Pato [92]For example, Boland et al. [82] proposed the exact approach by using two ILP models to solve STP. The ILP was applied in solving the problem of class blocking. Next, Birbas et al. [83] employed a hybrid approach to solve STP at the secondary Hellenic school where IP was applied in both phases. In the first phase, the shift assignment was catered by allocating teachers to shifts, while the second phase solved the whole STP, where the algorithm applied Fenchel cuts. After that, Ribić and Konjicija [84] employed IP with two-phase strategy to solve STP. The first phase focused on allocations, which later continued to solve the whole problem in the second phase. Meanwhile, Santos et al. [78] used mixed IP in solving Brazilian high schools as STP. The study proposed a cut and column generation algorithm as the solution methodology.Other than that, the hyper-heuristic based evolutionary algorithm (EA) method was employed by Pillay [87] in 2010 as the initial attempt at applying hyper-heuristics to STP. The study differentiated the performance of different low-level construction heuristics for this area. The study discovered that the use of mutation and crossover operators, which incorporated hill climbing, improves the EA-based hyper-heuristic performance. Ahmed et al. [88] in 2015 solved STP using hyper-heuristic based on the various selection of hyper-heuristics combining with different reusable components of STP. The hyper-heuristic approach combined with adaptive great deluge move acceptance method performed well on the tested ITC 2011 benchmark datasets.Similarly, Yongkai et al. [91] and Zhang et al. [89] solved a real-world STP by using SA algorithm that incorporated new neighbourhood structures in their studies. Yongkai et al. [91] proposed moves with a sequence structure, while Zhang et al. [89] performed swaps between pairs of timeslots, which had been carried out in sequence. Meanwhile, Moura and Scaraficci [85] applied path-relinking strategy with Greedy Randomized Adaptive Search Procedure (GRASP) to solve STP in three Brazilian high schools. Next, Minh et al. [86] solved STP at three Vietnamese high schools using tabu search. In the first phase, greedy search was employed to generate initial timetable, while tabu search was implemented in the second phase to improve the generated solution. The neighbourhood structures used in the study were single moves, swaps, and block moves.Other than that, Beligiannis et al. [79] employed EA technique to solve real STP in a Greek high school. Based on several comparisons made, this EA technique was found to be efficient in producing timetable more easily and quickly. On the other hand, Tassopoulos and Beligiannis [90] solved STP in a high school by using the Particle Swarm Optimization (PSO) method. This PSO method could also produce feasible and efficient timetables that outperformed four other existing techniques.Meanwhile, the hybrid algorithm was also applied in STP. Cerdeira-Pena et al. [73] recommended a new approach to solve STP, where Random Non-Ascendent Method (RNA) functioned as a local search technique and two variants of GA were hybridized to solve STP. Next, Yongkai et al. [91] proposed a two-phase approach to solve STP, where the first phase applied SA in order to get a feasible timetable. The first approach was developed by using new neighbourhoods, which swapped between timeslots in series while maintaining the timetable feasibility. Next, a tabu search was employed in the second phase to minimize the soft constraint.The study using machine learning such as neural network within education domain also appears in the literature. Example of a previous study on neural network was proposed by Smith et al. [80]. The study developed two discrete Hopfield neural network models for solving school timetabling problems. The approaches have shown competitive results when compared with other metaheuristics approaches, namely, greedy search, simulated annealing, and tabu search in terms of solution quality and computational effort.Carrasco and Pato [92] in 2004 employed the neural network-based heuristics to the class/teacher timetabling problem. Two models were introduced which are Potts mean-field annealing simulation and discrete neural network simulation. Test on a real problem showed that the discrete approach produced better performance in terms of solution quality and computation time. Comparison with multiobjective genetic algorithm also showed that the proposed neural network-based heuristics is competitive.


### 3.2. Allocation Problem

Allocation problem has been considered as a type of assignment problem. In fact, the allocation problem has been cited widely as a fundamental combinatorial optimization problem under optimization or operation research branch. The allocation problem is a famous problem discussed in the literature with various types of applications, especially within the education domain. This problem is categorised into three subproblems, which are (Section3.2.1) student-project allocation problem (SPAP), (Section 3.2.2) new student allocation problem (NSAP), and (Section 3.2.3) space allocation problem (SAP). The next subsections discuss these problems.


#### 3.2.1. Student-Project Allocation Problem

The student-project allocation problem (SPAP) is related to assigning a person to a particular project or cases based on preference or interest of student and lecturer [13]. SPAP includes a set of projects, students, and lecturers, whereby every unique lecturer is offered a project and both the lecturers and projects have some capacity constraints. Students have preference towards project, while lecturers have preference towards student(s). Hence, SPAP is considered as an application of a stable matching problem, where the members of two entity sets, students and lecturers, have their own preferences on the projects. As such, Manlove and O’Malley [95] stated that the previous formulation of SPAP considered two conditions, either not to permit lecturer preferences [93] (where stability is not applicable in this case) or to include the preferences of lecturer [94].Thus, in order to solve the problem, both hard and soft constraints need to be considered. Table10 presents the constraints within SPAP highlighted by various researchers. In most cases of SPAP, the similar constraints involved were preference lists and capacity constraints.Table 10
The hard and soft constraints related to SPAP.
Constraint type Descriptions Reference (s) Hard constraints (i) Preference lists. Teo and Ho [93]; Abraham et al. [94]; Manlove and O’Malley [95]; Abu El-Atta and Moussa [96] (ii) Capacity constraints. Anwar and Bahaj [97]; Ramli and Bakar [98]; Harper et al. [99]; Abraham et al. [94]; Abu El-Atta and Moussa [96] (iii) Every student must be allocated one and only one project. Anwar and Bahaj [97] (iv) A project can be allocated to at most one student. Anwar and Bahaj [97] (v) Total number of cases available must not be more than the total number of students. Ghazali and Abdul-Rahman [100] (vi) Maximum number of students in handling a case. Ghazali and Abdul-Rahman [100] (vii) Maximum number of cases that can be handled by certain students. Ghazali and Abdul-Rahman [100]  Soft constraints (i) Assigning a number of students to many cases. Ghazali and Abdul-Rahman [100]Furthermore, numerous real-world SPAPs have been broadly introduced in the literature with variants of measurement and more real-world constraints, as presented in Table11.Table 11
Summary of real-world SPAP from different institutions.
Reference Institution (s) Anwar and Bahaj [97] University of Southampton Ramli and Bakar [98] Universiti Utara Malaysia Ghazali and Abdul-Rahman [100] Internship students at Law Firm in Malaysia Dye [101] University of YorkThe methodologies that have solved SPAP have been discussed in the academic literature (see Table12). The exact approaches were proposed by Anwar and Bahaj [97], where the IP approach was used to solve SPAP. The paper proposed how two models of IP were used in solving the project allocation problem based on criteria and constraints. Next, Li et al. [102] attempted to maximize the number of assigned projects by using goal programming model. The student’s preference was successfully increased by giving higher weightage to the higher preference. Meanwhile, a mix-integer programming model was developed by Calvo-Serrano et al. [103] by incorporating ranking of lecturers and research areas in the allocation process. This approach increased student satisfaction and decreased computation time for a large dataset.Table 12
Summary of related studies to SPAP.
Approach Reference (s) Exact method Integer programming Anwar and Bahaj [97] Goal programming Li et al. [102] Mixed integer linear programming Calvo-Serrano et al. [103]  Metaheuristic technique Local search based Simulated annealing Ghazali and Abdul-Rahman [100] Population search based Genetic algorithm Harper et al. [99]  Hybrid 0-1 integer programming + AHP Ramli and Bakar [98]  Other techniques Constraint Logic Programming Dye [101] Linear time algorithm Abraham et al. [94] Maximum stable matching to preferences over pair Abu El-Atta and Moussa [96] Maximum stable matching to preferences over projects Manlove and O’Malley [95]; Iwama et al. [104]Other than that, the local search-based and population search-based algorithms were applied in solving SPAP as well. A study carried out by Ghazali and Abdul-Rahman [100] focused on solving chambering student-case assignment problem with SA algorithm, where this problem was categorised under SPAP. The aim was to minimize all the students’ completion time in order to solve the given cases. Next, Harper et al. [99] proposed population-based metaheuristic approaches by applying GA for the project assignment problem. They developed an algorithm and then compared it to an optimal integer programming approach.Next, a hybrid algorithm was used in solving SPAP. Ramli and Bakar [98] discussed how 0-1 IP model and Analytical Hierarchy Process (AHP) technique had been employed to assign projects to the students. The model dismissed student preference for team members, since by doing so, the total constraints and variables increased significantly.Meanwhile, Dye [101] applied a Constraint Logic Programming to improve project allocation problem in University of York. Good solution arrived for small dataset but was proven to be inefficient for large data. Abraham et al. [94] proposed linear-time algorithms to determine a stable matching for student-project. Stability is defined as a natural stability generalization to construct an optimal and stable matching for both students and lecturers. Meanwhile, Abu El-Atta and Moussa [96] presented a visual implementation to construct a SPA model with preference over pairs. A java-applet program was implemented to visualize the SPA since java is a web-oriented and object-oriented language. In addition, Manlove and O’Malley [95] proposed a SPAP with projects preferences. They studied how to allocate students to projects and fulfilled the preferences from both students and lecturers, as well as capacity requirement for both projects and lecturers. The process required a complex coding and implementation of the algorithm. The results showed that the problem of finding a maximum stable matching in SPAP was very hard that gave a polynomial-time 2-approximation algorithm. Then, in 2012, Iwama et al. [104] improved the upper bound to 1.5 and the lower bound to 21/19.


#### 3.2.2. New Student Allocation Problem

The new student allocation problem (NSAP) is a clustering problem in allocating new students to their corresponding class with minimum intelligence gap by sorting method: a group of new students with similar ranking and assigned into the same class. Table13 presents the constraints involved in NSAP highlighted by different researchers. In fact, studies performed by Zukhri and Omar [105] and Hassim et al. [106] allocated new students into certain classes in order to keep the optimum students’ capacity in each class. The number of students in every class should not surpass the maximum capacity.Table 13
The hard constraints within the NSAP adopted from Zukhri and Omar [105] and Hassim et al. [106].
Constraint type Descriptions Hard constraints (i) Capacity of students in each class. (ii) A group of new students with similar ranking assigned to the same class.The real-world datasets broadly introduced to NSAP and some real-world NSAP from various institutions are presented in Table14. The studies present various measurements and practical constraints.Table 14
Summary of real-world NSAP from different institutions.
Reference Institution (s) Zukhri and Omar [105] Islamic University of Indonesia Hassim et al. [106] Politeknik Ungku Omar Rad et al. [107] 177 existing university majors in Iran Ma et al. [108] Singaporean Ministry of EducationTable15 presents the summary within NSAP highlighted by various researchers. The study by Zukhri and Omar [105] and Hassim et al. [106] shared similar aim, which was to solve NSAP so as to keep the optimum capacity of students in each class, besides helping the management in a manner and fair way in selecting new students into their classes to ensure that they can perform in their studies. However, different solution methodologies of NSAP are discussed in the academic literature. The study by Zukhri and Omar [105] explored the NSAP by using GA to allocate new students to classes subject to satisfy both students and rooms requirement.Table 15
Summary of studies related to NSAP problem.
Approach  Reference (s) Metaheuristic technique Population search-based Genetic algorithm Zukhri and Omar [105]  Hybrid  K-means algorithm + AHP Rad et al. [107]  Other techniques  Data mining Ma et al. [108] FuzzyC-means algorithm Susanto [109] Subtractive ClusteringTechnique (SCT) Yadav and Ahmed [110] Analytical Hierarchy Process Hassim et al. [106] Bayesian approach Yadav [111]Besides, by using data mining, Ma et al. [108] aimed to award Gifted Education Programme (GEP) by the Singaporean Ministry of Education (MOE) to the right students. The targeted students for remedial classes were selected in a precise manner by using the proposed approach. On the other hand, Susanto [109] proposed fuzzy C-means algorithm (FCM) to allocate students from certain subjects into different classes. Students of various subjects were clustered based on their prerequisite subject scores. In the study, students with similar achievements were pooled into the same class, while students with slightly dissimilar achievement levels were combined in different classes.Next, Yadav and Ahmed [110] explored the applicability of Subtractive Clustering Technique (SCT) to solve NSAP that allocated new students to similar groups of specified maximum capacity and analysed the impact of allocations upon students’ academic performance. Meanwhile, Hassim et al. [106] proposed AHP to solve NSAP. The paper focused on minimizing the intelligence gap in each class. Meanwhile, Yadav [111] applied the Bayesian approach in classifying new students into their classes based on their intelligence based on academic achievements.However, some researchers proposed the hybrid algorithm to solve NSAP. For example, Rad et al. [107] proposed a hybrid model to cluster and rank university majors in Iran. In fact, a total of 177 existing university majors were compared on various criteria. The university majors were clustered based on similarities and differences by using K-means algorithm and were later ranked by using AHP.


#### 3.2.3. Space Allocation Problem

The space allocation problem (SAP) refers to a problem to allocate resources to space areas, for example, allocating rooms and at the same time satisfying several requirements and constraints [112]. Besides, Burke and Varley [125] described SAP as an allocation of rooms or areas of space for detailed function. Since space is limited, availability should be managed properly by assigning rooms to suitable users. With that, this subsection focuses on classroom space allocation that discusses the assignment of available classroom to a number of courses subject to room requirements and student population sizes. The aim of SAP is to ensure maximum space utilization and to satisfy all requirements and/or constraints as much as possible. In this case, all entities need to be allocated, where no wastage or overused space should occur, and any additional requirements and constraints should be satisfied. An important condition exists in this case, where the available space areas and special requirements by entities are not subject to amendment.As such, several sets of constraints had been involved in SAP, as highlighted in past studies (see Table16).Table 16
The hard and soft constraints within the SAP.
Constraint type Descriptions Reference (s) Hard constraints (i) Classroom capacity. Frimpong and Owusu [112]; Constantino [113]; Bagger et al. [114]; Navuduri [115] (ii) Room’s availability at different time of the day and room request. Gosselin and Truchon [116]  Soft constraints (i) Events from the same course occurring the same day must be allocated as close to each other as possible with respect to their geographical location. Bagger et al. [114] (ii) If an event is split into multiple rooms, these must also be as close to each other as possible in the geographical senseSome real-life datasets that have been broadly introduced to SAP are presented in Table17.Table 17
Summary of real-world SAP from different institutions.
Reference Institution (s) Burke et al. [117]; Landa-Silva [11] University of Nottingham, Nottingham Trent University and University of Wolverhampton  Beyrouthy et al. [118]; Beyrouthy et al. [119] University in Sydney Australia  Adewumi and Ali [120] Nigeria Universities  Bagger et al. [114] Technical University of Denmark (DTU)  Frimpong and Owusu [112] Premier Nurse’s Training College, Kumasi  Phillips et al. [121] University of Auckland, New Zealand  Abdullah et al. [122] Universiti Teknologi MalaysiaVarying solution approaches have been proposed in the academic literature (see Table18), where some studies proposed the exact approaches in solving SAP. For example, Gosselin and Truchon [116] proposed an allocation of classrooms in an educational institution by using the LP model to minimize penalty function. First, the model satisfied all the requested rooms as possible and then attempted to spread this departure uniformly among the requests. Meanwhile, in order to solve classroom allocation of Premier Nurse’s Training College, Kumasi, Frimpong, and Owusu [112] formulated an LP model with the aim of maximizing classroom space usage using POM-QM model for windows. Next, Phillips et al. [121] solved a classroom assignment problem of university course timetabling based on a novel formulation of IP. The proposed approach simplified the previous models and preserved tractability even when tested with large instancesTable 18
Summary of studies related to SAP.
Approach Reference (s) Exact method Linear programming Gosselin and Truchon [116]; Frimpong and Owusu [112] Integer programming Phillips et al. [121]  Metaheuristic technique Local search based Tabu search Burke et al. [123] Variable neighbourhood search Constantino [113] Population search based Genetic algorithm Adewumi and Ali [120]  Hybrid Hill climbing + SA + Tabu search + GA Burke et al. [117] Iterative improvement + SA + Tabu search + GA) Landa-Silva Dario [124] Hill climbing + SA Beyrouthy et al. [118] IP + SA Beyrouthy et al. [119] Mixed Integer Program (MIP) + C# Bagger et al. [114]  Other techniques MS EXCEL + SPSS Abdullah et al. [122] Web-based system Navuduri [115]Meanwhile, Burke et al. [123] presented multiobjective hyper-heuristic approaches to solve SAP. A tabu search hyper-heuristic technique was proposed. Next, Constantino [113] solved a classroom assignment problem in a large university by using two iterated heuristic algorithms to minimize the total distance of teaching activities between classrooms. Instead, other added requests that need to be satisfied were generating efficient space utilization, satisfying preferences of the room, and fulfilling other administrative requests. Later, Adewumi and Ali [120] presented a hierarchical-based heuristics solution in solving a hostel SAP. An interrelated heuristics was applied at different allocation process levels in order to achieve constraints and objectives. Then, GA was applied at the lowest level in order to drive the final allocation distribution.Besides, some researchers applied the hybrid technique in solving SAP. Burke et al. [117] proposed hybrid population-based metaheuristic approaches for SAP, where a series of techniques, such as hill climbing, SA, tabu search, and GA, were applied. Meanwhile, Landa-Silva Dario [124] applied metaheuristic and multiobjective approaches to solve SAP. An iterative improvement, SA, tabu search, and GA were adapted for problem application. Next, Beyrouthy et al. [118] applied hill climbing and SA to solve a teaching SAP with slipping. Later, Beyrouthy et al. [119] combined IP and SA approaches in utilizing university teaching space of University in Sydney Australia. Besides, Bagger et al. [114] proposed a Mixed Integer Program (MIP) solver within the constructive heuristic in solving a room allocation optimization problem. The heuristic and metaheuristic methods were applied to the problem for comparison and tested on five real-life data sets derived from Technical University of Denmark (DTU).Moving on, Abdullah et al. [122] employed both qualitative and quantitative techniques to measure the usage of teaching and learning space in Universiti Teknologi Malaysia (UTM). Besides, some researchers proposed a computer-assisted system in solving classroom allocation problem. Meanwhile, Navuduri [115] proposed a web-based system that helped university staff to assign classrooms for a given semester, where the system weighed in several elements, such as classroom size, course capacity, and preferred building of a department.


## 3.1. Timetabling Problem

Timetabling problem is considered as a type of assignment problem. A timetable usually provides information about the time for particular events to occur and eventually relates to the resources allocation [13]. Besides, timetabling is described as an assignment of events to a limited number of timeslots and rooms subject to prescribed constraints [12]. In reality, allocation of resources at a specified time is indeed necessary. The problem is challenging because one has to schedule a large number of entities and satisfy a number of constraints and preferences. According to Burke et al. [14], “a timetabling problem is a problem with four parameters: T, a finite set of times; R, a finite set of resources; M, a finite set of meetings; and C, a finite set of constraints. The problem is to assign time and resources to the meetings so as to satisfy the constraints as much as possible.” As such, timetabling problem is classified into three subproblems, which are examination timetabling problem (ETP), course timetabling problem (CTP), and school timetabling problem (STP). They are further discussed in the following subsections.


### 3.1.1. Examination Timetabling Problem

The examination timetabling problem (ETP) is defined as an assignment of a set of examinations to a set of timeslots while simultaneously satisfying several problem constraints. According to Carter and Laporte [15], ETP is defined as a process of assigning examinations to a limited number of timeslots with the aim of producing high quality timetable subject to constraints. In fact, the main objective of this problem is to produce timetable that optimizes certain objective functions. A set of examinations, E=e1,e2,…,en, needs to be assigned to a limited number of timeslots, T=t1,t2,…,tn, subject to certain restricted constraints. In fact, Even et al. [16] claimed that ETP is considered as an NP-hard real-world problem, which is rich and diverse, besides involving some significant levels of information from the connected problems. Meanwhile, according to McCollum [17], the complexity of the problem in recent years is related to the increasing number of student enrolments, course flexibility, and various preferences. The manual solution proposed by institution is usually time-consuming and lacks feasibility, thus requiring advanced techniques so as to satisfy both institutional and personal preferences.Hence, in considering the problem solution, the hard constraints have to be strictly obeyed under any condition to ascertain solution feasibility. On the other hand, although the soft constraints do not affect the solution feasibility, they must be satisfied as much as possible in order to produce a solution with high quality. In assessing timetable quality, both hard and soft constraints in ETP are described in Table1.Table 1
The hard and soft constraints within the ETP adopted from Qu et al. [18].
Constraint type Descriptions Hard constraints (i) Student should not sit two examinations at one time. (ii) The total number of students in the examination room should not exceed the room capacity.  Soft constraints (i) Examinations that are in conflict should be distributed within the timetable as evenly as possible. (ii) Some examinations are required to be scheduled at a particular location or on the same day. (iii) Examinations should be scheduled consecutively. (iv) Examinations with large enrolment size should be scheduled as early as possible. (v) Examinations with limited enrolment should be scheduled into a particular timeslot. (vi) Some examinations are required to be scheduled within a particular timeslot. (vii) Examinations in conflict on the same day should be located nearby. (viii) Examinations should be split over similar locations. (ix) Examinations with the same duration should be allocated the same room. (x) Resource requirements for certain examinations should be met.With that, Burke et al. [18] performed a survey that discovered the diverse real-life constraints within several academic institutions located in Britain. The constraints were imposed on the needs of the institutions, which were categorised as time- and resource-related.Moreover, a broad range of real-world datasets have been introduced in the literature with various practical constraints (see Table2). In addition, these varied approaches have been tested on the proposed dataset for verification. The most frequently tested datasets are Toronto [27], Nottingham [28], and Melbourne [19]. Meanwhile, the dataset from the Second International Timetabling Competition [29] has also been used for verification purpose. Moreover, by using the benchmark dataset, varied advanced approaches had been developed to further encourage advanced scientific researches.Table 2
Summary of real-world examination timetabling datasets from different institutions.
Reference Institution (s) Ayob et al. [5] Universiti Kebangsaan Malaysia  Carter et al. [15] Carleton University, Ottawa; Earl Haig Collegiate Institute, Toronto; Ecole des Hautes Etudes Commercials, Montreal; King Fahd University, Dharan; London School of Economics; Ryeson University, Toronto; St. Andrew's Junior High School, Toronto; Trent University, Peterborough, Ontario; Faculty of Arts and Sciences, University of Toronto; Faculty of Engineering, University of Toronto; York Mills Collegiate Institute, Toronto  Burke et al. [18] University of Nottingham  Merlot et al. [19] University of Melbourne  Ergül [10] Middle East Technical University  Wong et al. [20] Ecole de Technologie Superieure  Kendall and Hussin [21] University of Technology MARA  Tounsi [22] Prince Sultan University  Kahar and Kendall [23] Universiti Malaysia Pahang  Yong and Yi [24] Hubei University of Technology  Innet [25] University of the Thai Chamber of Commerce  Abdul-Rahman et al. [26] Universiti Utara MalaysiaReal-world timetabling problems are normally complex as they involve various constraints and require significant computational effort. In many practical situations, obtaining a good quality timetable by using the exact method is very challenging, thus leading researchers to opt heuristic approaches. Meanwhile, in academic literature, a variety of timetabling problems and solution methodologies that focus on difficulty and efficiency of the problem solving have been discussed (see Table3).Table 3
Summary of related studies in ETP.
Approach Reference (s) Exact method Integer programming Qu et al. [30] Column generation Woumans et al. [31]  Heuristic Technique Graph colouring heuristics Ayob et al. [5]; Abdul-Rahman et al. [26]; Abdul-Rahman et al. [33]; Kahar and Kendall [23]; Kahar and Kendall [37]; [34] Abdul-Rahman et al.; [35] Abdul-Rahman et al.; [36] Abdul-Rahman et al. Hyper-heuristics Burke et al. [38]; Sabar et al. [39]; Muklason et al. [40]  Metaheuristic technique Local search based Hill climbing Caramia et al. [6] Tabu search Sabar et al. [41]; Amaral and Pais [42] Variable neighbourhood search Abdul-Rahman et al. [43] Great Deluge Kahar and Kendall [23] Population search based Memetic algorithm Ersoy et al. [7] Genetic algorithm Pillay and Banzhaf [44]; Innet [25]  Hybrid Great Deluge + electromagnetic-like mechanism Turabieh and Abdullah [8] Hyper-heuristics + estimation distribution algorithm Qu et al. [45] Harmony search hyper-heuristics Rankhambe and Kavita [46] Bee colony optimization + late acceptance hill climbing + simulated annealing Alzaqebah and Abdullah [47]The exact approaches have been used to solve examination timetabling, which evokes mathematical procedures, such as objective function and related constraints. The approaches required to develop a mathematical model should be wisely developed and treated. In fact, the aim of the exact approaches is to obtain an optimal solution, but solving complex problems is computationally expensive. As such, Qu et al. [30] proposed integer programming in order to solve the intricacy of examination timetabling by dividing the problem into two subproblems, which are “easy” and “difficult”. Woumans et al. [31], on the other hand, solved the ETP by using column generation approach that considered student-centric to improve the spread of exam by dynamically allowing more versions of exams.In solving this problem, the constructive approach is one that is popular as it incrementally forms a complete solution using construction heuristics [28]. The graph colouring heuristics as a constructive approach presents the vertices as the examinations, the edges as the conflict between two examinations, and the vertices colour as varying timeslots in the timetable.Additionally, the concept of “squeaky wheel optimization” was initiated by Burke and Newall [32] to assist heuristic modifier based on basic graph colouring heuristic technique to promote difficult examinations to be scheduled first iteratively based on ordering. The study was further investigated by Abdul-Rahman et al. [26] by integrating shuffling strategies to different graph colouring heuristics. Another recent study by Abdul Rahman et al. [33] considered a linear combination of graph colouring heuristics with a heuristic modifier to calculate the difficulty score of each examination. The examinations were ordered based on new difficulty score and the examination with the highest difficulty score was scheduled first. The experiment on two benchmark datasets of ETP showed that the proposed approach generated competitive results among other examination timetable approaches.In another study, Abdul-Rahman et al. [34] considered nonlinear heuristic modifier of graph coloring heuristics to construct solutions for examination timetabling problem. A nonlinear range was proposed using nonlinear heuristic modifier to estimate a difficulty value of an examination so that an effective estimation of examination’s difficulty could be obtained. A web-based examination timetabling system was introduced in Abdul-Rahman et al. [35] by incorporating a multiobjective approach based on graph colouring heuristics. The web-based system was developed for Universiti Utara Malaysia. The study also emphasizes the graphical user interface (GUI) of the system that enables the user to participate in the input, construction, and modification of a timetable. Abdul-Rahman et al. [36] developed an adaptive decomposition and ordering strategy that automatically divides examinations into difficult and easy sets based on graph colouring heuristics for constructing an examination timetable. The examinations in the difficult set are considered to be hard to place by referring to their number of conflict examinations and hence are listed before the ones in the easy set in the construction process.Meanwhile, in solving the ETP at Universiti Malaysia Pahang (UMP), Kahar and Kendall [23] presented a solution by using constructive heuristics, which was compared with a manual solution. The study introduced predetermined room grouping, room searching, and room selection. Based on the graph colouring heuristics, an algorithm was developed to produce a greater solution for the present software. The problem was further investigated by Kahar and Kendall [37] by incorporating invigilator requirement in the timetable using graph colouring approach. Other than that, Burke et al. [38] investigated Monte Carlo hyper-heuristics as a learning mechanism, which was incorporated in search process for ETP. It was found that the choice function appeared to be the best alternative for SA with reheating move acceptance within the hyper-heuristics approach. Next, Sabar et al. [39] introduced a measurement of difficulty index to measure examination difficulty within a hybridization of hierarchical low-level graph colouring heuristics approach, whereas Muklason et al. [40] investigated the fairness in examination timetabling by introducing multiobjective solution, also using the hyper-heuristics approach.Additionally, the local search-based algorithms have successfully solved ETPs. Caramia et al. [6] proposed a hill climbing algorithm as a penalty-decreaser in improving the quality of the timetable. The iterative process by the penalty-decreaser continued to search until no improvement was detected and the penalty-trader, i.e., hill climbing, took over the process. Later, Sabar et al. [41] proposed a hybrid tabu search with exponential Monte Carlo procedure to solve ETP. The work is an extension from Ayob and Kendall’s [48]. A counter-strategy was incorporated to calculate the successive nonimproving iterations to control the acceptance of worse solution. Meanwhile, Amaral and Pais [42] proposed a multiobjective tabu search approach with two new features to increase the algorithm automation. The approach, which was tested on ETP, exhibited that human interference could be avoided by combining weighting functions and compromise ratios.Moreover, Abdul-Rahman et al. [43] investigated the methods of ordering neighbourhood structures within a Variable Neighbourhood Search. The proposed approach hybridized a great deluge algorithm as a move acceptance method to vary the acceptance level. As a result, the empirical findings of a well-known examination timetabling benchmark displayed that the performance of Variable Neighbourhood Search great deluge had been reasonably well, ranking second among previously proposed approaches, with the right choice of initialisation and neighbourhood ordering methods. Next, a modified great deluge approach was proposed by Kahar and Kendall [23] to solve an ETP at Universiti Malaysia Pahang. The study concluded that the iterative process, neighbourhood, and starting solution were important factors that significantly affected the search for solution.On top of that, the population search-based algorithms were applied in solving ETPs. A hyper-heuristic methodology, known as “hyperhill-climber”, was proposed by Ersoy et al. [7]. The proposed approach employed an adaptive memetic algorithm to select the best hill climber. The hill climber determined the best ordering for the successive application of hill-climbers. Meanwhile, Pillay and Banzhaf [44] proposed a two-phased GA that was employed to induce a solution for ETP so as to cater to both hard and soft constraints. The findings showed that the proposed solutions outperformed other evolutionary approaches on some benchmark instances. Next, Innet [25] proposed a GA model in order to solve ETPs by using three genetic operators: crossover, mutation, and selection, in order to improve the effectiveness of automatic arranging examination timetable.Other than that, Turabieh and Abdullah [8] proposed a hybrid approach that considered a great deluge algorithm and an “electromagnetic-like mechanism” heuristics within timetabling approaches. An Estimation Distribution Algorithm-based hyper-heuristic was developed by Qu et al. [45] to solve ETP. The proposed approach is comparable with other hyper-heuristic approaches and was found suitable for specific problem solving situations. On top of that, Rankhambe and Kavita [46] developed harmony search hyper-heuristics, where the harmony search algorithm was based on heuristic harmony memory as low-level heuristics. The findings showed that the approach performed well on University of Nottingham benchmark datasets. Besides, Alzaqebah and Abdullah [47] hybridized bee colony optimization with late acceptance hill climbing and SA algorithms to solve the problem. As such, special selection strategies and self-adaptive neighbourhood mechanism were introduced to maintain the population diversity in backward pass, as well as to enhance the neighbourhood search. An extensive compilation of methodologies for ETP can be viewed in [49].


### 3.1.2. Course Timetabling Problem

Course timetabling refers to the process of assigning courses, rooms, students, and lecturers to a fixed time period, typically a working week, while satisfying a given set of constraints [50]. According to Obit [51], university course timetabling is considered as a weekly schedule of all university lecturers to a set of courses and at the same time to prevent the lecturers to have students in common at two different timeslots. Moreover, Obit [51] stated that, in reality, examination and course timetabling problem are about the same in some attributes but portray some variances. For instance, in examination timetabling, the room may have more than one examination scheduled at the same time, providing that the room seating capacity is not exceeded, while this is impossible for course timetabling, where the assignment normally allows one course per room, per timeslot.Typically, while constructing a feasible timetable for a course timetabling problem to satisfy all the hard constraints, the objective function of the problem has to be minimized, which usually reflects the violation of soft constraints. Some instances of the hard and soft constraints of course timetabling problem are presented in Table4. Other examples of constraints involved in course timetabling are that each course should be composed of the correct number of lecturers, no student can attend more than one lecture at the same time, and one lecturer has to be scheduled in exactly one room [52, 53].Table 4
The hard and soft constraints within the CTP adopted from Obit [51].
Constraint type Descriptions Hard constraints (i) The room capacity must be equal to or greater than the number of students attending the event in each timeslot. (ii) A student cannot attend two events simultaneously. (iii) Only one event is allowed to be assigned per timeslot in each room. (iv) The room assigned to an event must satisfy the features required by the event.  Soft constraints (i) Students should not have only one event timetabled on a day. (ii) Students should not attend more than two consecutive events on a day. (iii) Students should not attend an event in the last timeslot of a day.The real-world datasets employed in solving course timetabling problem from various institutions are depicted in Table5. There are also benchmark datasets for the CTP, commonly used as test bed such as Socha et al. [53], International Timetabling Competition 2002 and 2007 [29].Table 5
Summary of real-world course timetabling datasets from different institutions.
Reference Institution (s) Gunawan [54] University in Indonesia Oladokun & Badmus [55] University of Ibadan Thongsanit [56] Silpakorn University Borchani et al. [57] Tunisian University Méndez-Díaz et al. [58] A private university in Buenos Aires, Argentina Wahid and Hussin [59] Universiti Utara MalaysiaA number of solutions for course timetabling problems have been discussed in the academic literature (see Table6). An exact approach was proposed by Oladokun and Badmus [55] in optimizing the allocation of limited resources available for lecturing. As a test case, the study modeled and solved course timetabling problem for University of Ibadan. Furthermore, the integer linear programming (ILP) was applied in solving the problem. Next, Thongsanit [56] solved the course-classroom assignment problem for Silpakorn University within a short time and at a minimum cost. In solving the problem, the aim was to develop a mathematical model and to design the related methods. The study presented a guide to improve the solutions for classroom allocation problem with the aim of assigning courses to classrooms at a minimal cost. Meanwhile, Vermuyten et al. [60] investigated the flow of students within a course timetable problem by minimizing the travel time between consecutive lectures based on pedestrian traffic models. The problem was solved by using the decomposition approach as two-stage IP exhibited rather exceptional solutions.Table 6
Summary of studies related to CTP.
Approach Reference (s) Exact method Integer linear programming Oladokun and Badmus [55]; Thongsanit [56] Decomposition approach Vermuyten et al. [60]  Heuristic technique Integer linear programming based heuristics Méndez-Díaz et al. [58]  Metaheuristic technique Local search based Simulated annealing Ceschia et al. [61] Hyper-heuristics iterated local search Soria-Alcaraz et al. [62] Two stage metaheuristics Lewis and Thompson [63] Local search-based algorithm with adaptive mechanism Nagata [64] Variable neighborhood descent Borchani et al. [57] Tabu search with sampling and perturbation + SA with reheating Goh et al. [65] Nonlinear great deluge hyper-heuristics with reinforcement learning Obit et al. [66] Population search based Ant colony optimisation Nothegger et al. [67] Genetic algorithm Song et al. [68]  Hybrid Integer programming + greedy heuristics + modified simulated annealing Gunawan et al. [54] Genetic algorithm + local search Badoni et al. [69] Artificial bee colony algorithm + hill climbing optimizer Bolaji et al. [70] Integer programming + greedy heuristics Ghiani et al. [71] Hybrid multi-objective genetic algorithm + hill climbing + simulated annealing Akkan and Gülcü [72] Harmony search with great deluge Wahid and Hussin [59]Other than that, by using the ILP-based heuristics, a post-enrolment course timetabling problem at a private university in Buenos Aires, Argentina, was solved by Méndez-Díaz et al. [58]. The study produced good quality results and generalized other problems from the related literature.Meanwhile, Ceschia et al. [61] proposed a metaheuristic approach based on SA in solving post-enrolment course timetabling. The proposed approach was tested on benchmark dataset, which showed that the proposed approach was appropriately developed and adjusted. This is because the proposed approach worked well on all datasets and produced new best solution for most of the instances. Next, Soria-Alcaraz et al. [62] developed a constraints’ generic structure of a course timetabling problem, in which the problem was solved by using hyper-heuristics iterated local search. Furthermore, online learning showed that the proposed approach generated competitive results compared to other approaches presented in the literature and produced a number of new best-known solutions.Accordingly, Nagata [64] developed a local search-based algorithm with adaptive mechanism in varying neighbourhood sizes for a post-enrolment-based course timetabling problem. The study found that the recommended approach produced competitive results for well-known benchmark dataset of the problem and foresaw the trade-off between exploration and exploitation by adjusting the neighbourhood size. Similarly, Borchani et al. [57] investigated a university course timetabling problem in Tunisia by using Variable Neighbourhood Descent, which successfully removed an average of 52.47% of holes and isolated sessions with the introduction of 11 specific neighbourhood structures. Meanwhile, Goh et al. [65] solved a post-enrolment course timetabling problem by using a two-phase algorithm. The tabu search with sampling and perturbation was introduced to efficiently find feasible solution, while the SA with reheating eliminated the extensive tuning and scalability of runtime. The proposed algorithm produced new best solution for many instances. Obit et al. [66] investigated reinforcement learning with static and dynamic memory within nonlinear great deluge hyper-heuristics. The study showed that the static one performed better than the dynamic when solving CTP.Moreover, in the course timetabling problem domain, some researchers proposed population-based metaheuristic approaches. For instance, Nothegger et al. [67] applied Ant Colony Optimization to tackle the post-enrolment course timetabling problem, which was specified in the competition, namely, International Timetabling Competition 2007. Next, Song et al. [68] developed an energy efficiency-based course timetabling algorithm that optimized the constructed timetable based on energy consumption using GA. The study found that the proposed algorithm saved up to 4% of energy during cooling and heating seasons, when compared to the existing timetable. In addition, more energy saving up to 5.0% was achieved by mitigating hard constraints.Additionally, Gunawan et al. [54] proposed a hybrid algorithm that combined IP, a greedy heuristic, and a modified SA algorithm to solve a teacher assignment-course scheduling problem. The problem mixed both teacher assignment and course scheduling problems as mathematical programming model. Later, Badoni et al. [69] developed a hybrid approach that combined GA and local search approach by using events based on groupings of students. The hybrid approach produced better results on benchmark datasets, in comparison to other approaches found in the literature pertaining to course timetabling problem. After that, Bolaji et al. [70] employed artificial bee colony algorithm and hill climbing optimizer as a hybrid method to solve a university course timetabling problem. The study showed that a well-designed hybrid technique appeared to be a good alternative to tackle the problem, as the results displayed better performance than the other techniques. Next, a study on a course timetabling problem related to remedial education was introduced by Ghiani et al. [71] who employed both IP and greedy heuristics. The study introduced the selection of remedial courses while considering budgets and operational constraints that helped the students to achieve particular competencies in several skills at varied levels. Besides, Akkan and Gülcü [72] proposed a hybrid multiobjective genetic algorithm that was tested on benchmark dataset of course timetabling problem. The hybrid approach employed hill climbing and SA, which produced highly robust solution close to the best-known results. Wahid and Hussin [59] employed hybrid harmony search with great deluge for solving a real case of CTP.


### 3.1.3. School Timetabling Problem

The school timetabling problem (STP) is about generating school timetable that usually follows a cycle every week for all classes, in which the objective is to avoid teachers from attending two classes at the same time. In school timetabling, students are normally preassigned, while only teachers and rooms need to be assigned in the timetabling problem. As such, Cerdeira-Pena et al. [73] stated that STP is aimed at assigning period for teacher to certain subject in a specified group by considering groups of students and teachers in a fixed period scheduling. According to Pillay [74], STP is considered as NP-complete or NP-hard problem that depends on the intricacy of the problem in relation to various constraints. Moreover, studies on STP, along with its difficulty, had been investigated as early as 1976 by Even et al. [16] and more current analysis was undertaken by Carter and Tovey [75], Kingston [76], and Eikelder and Willemen [77], to name a few.In fact, the two types of constraints, which are hard and soft constraints, had been used to solve STP. With that, the fact that a teacher can only teach a lesson to one group at a time and the fact that a group cannot accept more than one lesson at a time by different teachers are examples of hard constraints. Usually, soft constraints depend on preferences by the teacher or are based on school policies, such as to minimize the number of periods for the teacher, to minimize the gaps within the timetable, and to avoid some subjects restriction at a prescribe time. Furthermore, Santos et al. [78] proposed that the basic hard constraints that need to be satisfied in school timetabling are that no teachers should be assigned to more than a class in the same timeslot, taking into account the teacher’s availability for each timeslot, and allocating the right number of timeslots for each teacher-class pair. Table 7 depicts the constraints proposed by Cerdeira-Pena et al. [73] in relation to STP.Table 7
The hard and soft constraints related to STP adopted from Cerdeira-Pena et al. [73].
Constraint type Descriptions Hard constraints (i) Overlaps: avoid the possibility of a class been taught by more than one teacher in the same period and avoid classes sharing resources (i.e., a classroom, lab, etc.), where classes which involved the same group could be assigned to the same period. (ii) Simultaneity: two classes are defined as simultaneous classes if they are taught by different teachers at the same time. (iii) Unavailability: it considers periods when a class cannot be given or when a teacher cannot teach. (iv) Consecutiveness: this constraint checks whether a distribution of hours for a pair teacher-class is followed. For example, some practical lessons should be taught in two consecutive periods of time.  Soft constraints (i) Overuse: it refers to the number of periods per day in which a teacher gives its lessons, over its specified maximum of periods per day. (ii) Underuse: when teachers have preferences on their minimum number of periods per day, it indicates the number of periods under such minimum. (iii) Holes: consider the number ofemptyperiods between two consecutive periods where a teacher is assigned a class. Breaks and free-time periods are not considered holes. (iv) Splits: consider the number of periods between two nonconsecutive assignments to the same class in the same day. (v) Groups: assuming a specified maximum of periods per day for an association teacher-class, it considers the number of exceeding periods in such day. This constraint is only considered if a maximum number of consecutive periods (related withconsecutiveness) for the pair class-teacher are not specified. (vi) Undesired: assuming that there are periods in which a teacher would prefer not to teach, this constraint indicates the number of such periods where that teacher is assigned a class. This constraint is thesoftversion of the mandatory unavailabilityconstraint (referring to teachers).The real-world datasets that had been used in solving STP are shown in Table8. Besides, the benchmark problems of STP are also available from Beligiannis et al. [79], Smith et al. [80], and International Timetabling Competition 2011 of High School Timetabling Archive XHSTT-2011 with 21 instances from 8 countries [81].Table 8
Summary of real-world school timetabling datasets from different institutions.
Reference Institution (s) Cerdeira-Pena et al. [73] Secondary school (I.E.S. Menendez Pidal) in A Coruna-Spain Santos et al. [78] Brazilian high schools Boland et al. [82] Australian high school Beligiannis et al. [79] Greek high schools Birbas et al. [83] Hellenic secondary school Ribić and Konjicija [84] Croatian secondary school Moura and Scaraficci [85] Brazilian high school Minh et al. [86] Vietnam high schoolsAs for the school timetabling field, several solutions were retrieved from the literature as described in Table9. Some approaches and new algorithms were applied and derived frequently over the years since school timetabling has further developed with SA, evolutionary algorithms, tabu search, IP, constraint programming, GRASP (Greedy Randomized Search Procedure), and so forth. Hybridizations are also some popular approaches in solving STP, which combine two or more methodologies. Comparative studies in STP were also conducted to compare the performance of several techniques. Normally, solving STP is computationally expensive and in order to reduce the running time, distributed methods have been suggested in association with the proposed approach.Table 9
Summary of studies related to STP.
Approach Reference (s) Exact method Integer Linear Programming Boland et al. [82]; Birbas et al. [83]; Ribić and Konjicija [84] Mixed Integer Programming Santos et al. [78]  Heuristic technique Hyper-heuristics Pillay [87]; Ahmed et al. [88]  Metaheuristic technique Local search based Simulated annealing Zhang et al. [89] Greedy Randomized Adaptive Search Procedure (GRASP) Moura and Scaraficci [85] Tabu search Minh et al. [86] Population search based Evolutionary algorithm Beligiannis et al. [79] Particle Swarm Optimization Tassopoulos et al. [90]  Hybrid Random Non-Ascendent Method (RNA) + genetic algorithm Cerdeira-Pena et al. [73] Simulated annealing + Tabu search Yongkai et al. [91]  Others Neural network Smith et al. [80]; Carrasco and Pato [92]For example, Boland et al. [82] proposed the exact approach by using two ILP models to solve STP. The ILP was applied in solving the problem of class blocking. Next, Birbas et al. [83] employed a hybrid approach to solve STP at the secondary Hellenic school where IP was applied in both phases. In the first phase, the shift assignment was catered by allocating teachers to shifts, while the second phase solved the whole STP, where the algorithm applied Fenchel cuts. After that, Ribić and Konjicija [84] employed IP with two-phase strategy to solve STP. The first phase focused on allocations, which later continued to solve the whole problem in the second phase. Meanwhile, Santos et al. [78] used mixed IP in solving Brazilian high schools as STP. The study proposed a cut and column generation algorithm as the solution methodology.Other than that, the hyper-heuristic based evolutionary algorithm (EA) method was employed by Pillay [87] in 2010 as the initial attempt at applying hyper-heuristics to STP. The study differentiated the performance of different low-level construction heuristics for this area. The study discovered that the use of mutation and crossover operators, which incorporated hill climbing, improves the EA-based hyper-heuristic performance. Ahmed et al. [88] in 2015 solved STP using hyper-heuristic based on the various selection of hyper-heuristics combining with different reusable components of STP. The hyper-heuristic approach combined with adaptive great deluge move acceptance method performed well on the tested ITC 2011 benchmark datasets.Similarly, Yongkai et al. [91] and Zhang et al. [89] solved a real-world STP by using SA algorithm that incorporated new neighbourhood structures in their studies. Yongkai et al. [91] proposed moves with a sequence structure, while Zhang et al. [89] performed swaps between pairs of timeslots, which had been carried out in sequence. Meanwhile, Moura and Scaraficci [85] applied path-relinking strategy with Greedy Randomized Adaptive Search Procedure (GRASP) to solve STP in three Brazilian high schools. Next, Minh et al. [86] solved STP at three Vietnamese high schools using tabu search. In the first phase, greedy search was employed to generate initial timetable, while tabu search was implemented in the second phase to improve the generated solution. The neighbourhood structures used in the study were single moves, swaps, and block moves.Other than that, Beligiannis et al. [79] employed EA technique to solve real STP in a Greek high school. Based on several comparisons made, this EA technique was found to be efficient in producing timetable more easily and quickly. On the other hand, Tassopoulos and Beligiannis [90] solved STP in a high school by using the Particle Swarm Optimization (PSO) method. This PSO method could also produce feasible and efficient timetables that outperformed four other existing techniques.Meanwhile, the hybrid algorithm was also applied in STP. Cerdeira-Pena et al. [73] recommended a new approach to solve STP, where Random Non-Ascendent Method (RNA) functioned as a local search technique and two variants of GA were hybridized to solve STP. Next, Yongkai et al. [91] proposed a two-phase approach to solve STP, where the first phase applied SA in order to get a feasible timetable. The first approach was developed by using new neighbourhoods, which swapped between timeslots in series while maintaining the timetable feasibility. Next, a tabu search was employed in the second phase to minimize the soft constraint.The study using machine learning such as neural network within education domain also appears in the literature. Example of a previous study on neural network was proposed by Smith et al. [80]. The study developed two discrete Hopfield neural network models for solving school timetabling problems. The approaches have shown competitive results when compared with other metaheuristics approaches, namely, greedy search, simulated annealing, and tabu search in terms of solution quality and computational effort.Carrasco and Pato [92] in 2004 employed the neural network-based heuristics to the class/teacher timetabling problem. Two models were introduced which are Potts mean-field annealing simulation and discrete neural network simulation. Test on a real problem showed that the discrete approach produced better performance in terms of solution quality and computation time. Comparison with multiobjective genetic algorithm also showed that the proposed neural network-based heuristics is competitive.


## 3.1.1. Examination Timetabling Problem

The examination timetabling problem (ETP) is defined as an assignment of a set of examinations to a set of timeslots while simultaneously satisfying several problem constraints. According to Carter and Laporte [15], ETP is defined as a process of assigning examinations to a limited number of timeslots with the aim of producing high quality timetable subject to constraints. In fact, the main objective of this problem is to produce timetable that optimizes certain objective functions. A set of examinations, E=e1,e2,…,en, needs to be assigned to a limited number of timeslots, T=t1,t2,…,tn, subject to certain restricted constraints. In fact, Even et al. [16] claimed that ETP is considered as an NP-hard real-world problem, which is rich and diverse, besides involving some significant levels of information from the connected problems. Meanwhile, according to McCollum [17], the complexity of the problem in recent years is related to the increasing number of student enrolments, course flexibility, and various preferences. The manual solution proposed by institution is usually time-consuming and lacks feasibility, thus requiring advanced techniques so as to satisfy both institutional and personal preferences.Hence, in considering the problem solution, the hard constraints have to be strictly obeyed under any condition to ascertain solution feasibility. On the other hand, although the soft constraints do not affect the solution feasibility, they must be satisfied as much as possible in order to produce a solution with high quality. In assessing timetable quality, both hard and soft constraints in ETP are described in Table1.Table 1
The hard and soft constraints within the ETP adopted from Qu et al. [18].
Constraint type Descriptions Hard constraints (i) Student should not sit two examinations at one time. (ii) The total number of students in the examination room should not exceed the room capacity.  Soft constraints (i) Examinations that are in conflict should be distributed within the timetable as evenly as possible. (ii) Some examinations are required to be scheduled at a particular location or on the same day. (iii) Examinations should be scheduled consecutively. (iv) Examinations with large enrolment size should be scheduled as early as possible. (v) Examinations with limited enrolment should be scheduled into a particular timeslot. (vi) Some examinations are required to be scheduled within a particular timeslot. (vii) Examinations in conflict on the same day should be located nearby. (viii) Examinations should be split over similar locations. (ix) Examinations with the same duration should be allocated the same room. (x) Resource requirements for certain examinations should be met.With that, Burke et al. [18] performed a survey that discovered the diverse real-life constraints within several academic institutions located in Britain. The constraints were imposed on the needs of the institutions, which were categorised as time- and resource-related.Moreover, a broad range of real-world datasets have been introduced in the literature with various practical constraints (see Table2). In addition, these varied approaches have been tested on the proposed dataset for verification. The most frequently tested datasets are Toronto [27], Nottingham [28], and Melbourne [19]. Meanwhile, the dataset from the Second International Timetabling Competition [29] has also been used for verification purpose. Moreover, by using the benchmark dataset, varied advanced approaches had been developed to further encourage advanced scientific researches.Table 2
Summary of real-world examination timetabling datasets from different institutions.
Reference Institution (s) Ayob et al. [5] Universiti Kebangsaan Malaysia  Carter et al. [15] Carleton University, Ottawa; Earl Haig Collegiate Institute, Toronto; Ecole des Hautes Etudes Commercials, Montreal; King Fahd University, Dharan; London School of Economics; Ryeson University, Toronto; St. Andrew's Junior High School, Toronto; Trent University, Peterborough, Ontario; Faculty of Arts and Sciences, University of Toronto; Faculty of Engineering, University of Toronto; York Mills Collegiate Institute, Toronto  Burke et al. [18] University of Nottingham  Merlot et al. [19] University of Melbourne  Ergül [10] Middle East Technical University  Wong et al. [20] Ecole de Technologie Superieure  Kendall and Hussin [21] University of Technology MARA  Tounsi [22] Prince Sultan University  Kahar and Kendall [23] Universiti Malaysia Pahang  Yong and Yi [24] Hubei University of Technology  Innet [25] University of the Thai Chamber of Commerce  Abdul-Rahman et al. [26] Universiti Utara MalaysiaReal-world timetabling problems are normally complex as they involve various constraints and require significant computational effort. In many practical situations, obtaining a good quality timetable by using the exact method is very challenging, thus leading researchers to opt heuristic approaches. Meanwhile, in academic literature, a variety of timetabling problems and solution methodologies that focus on difficulty and efficiency of the problem solving have been discussed (see Table3).Table 3
Summary of related studies in ETP.
Approach Reference (s) Exact method Integer programming Qu et al. [30] Column generation Woumans et al. [31]  Heuristic Technique Graph colouring heuristics Ayob et al. [5]; Abdul-Rahman et al. [26]; Abdul-Rahman et al. [33]; Kahar and Kendall [23]; Kahar and Kendall [37]; [34] Abdul-Rahman et al.; [35] Abdul-Rahman et al.; [36] Abdul-Rahman et al. Hyper-heuristics Burke et al. [38]; Sabar et al. [39]; Muklason et al. [40]  Metaheuristic technique Local search based Hill climbing Caramia et al. [6] Tabu search Sabar et al. [41]; Amaral and Pais [42] Variable neighbourhood search Abdul-Rahman et al. [43] Great Deluge Kahar and Kendall [23] Population search based Memetic algorithm Ersoy et al. [7] Genetic algorithm Pillay and Banzhaf [44]; Innet [25]  Hybrid Great Deluge + electromagnetic-like mechanism Turabieh and Abdullah [8] Hyper-heuristics + estimation distribution algorithm Qu et al. [45] Harmony search hyper-heuristics Rankhambe and Kavita [46] Bee colony optimization + late acceptance hill climbing + simulated annealing Alzaqebah and Abdullah [47]The exact approaches have been used to solve examination timetabling, which evokes mathematical procedures, such as objective function and related constraints. The approaches required to develop a mathematical model should be wisely developed and treated. In fact, the aim of the exact approaches is to obtain an optimal solution, but solving complex problems is computationally expensive. As such, Qu et al. [30] proposed integer programming in order to solve the intricacy of examination timetabling by dividing the problem into two subproblems, which are “easy” and “difficult”. Woumans et al. [31], on the other hand, solved the ETP by using column generation approach that considered student-centric to improve the spread of exam by dynamically allowing more versions of exams.In solving this problem, the constructive approach is one that is popular as it incrementally forms a complete solution using construction heuristics [28]. The graph colouring heuristics as a constructive approach presents the vertices as the examinations, the edges as the conflict between two examinations, and the vertices colour as varying timeslots in the timetable.Additionally, the concept of “squeaky wheel optimization” was initiated by Burke and Newall [32] to assist heuristic modifier based on basic graph colouring heuristic technique to promote difficult examinations to be scheduled first iteratively based on ordering. The study was further investigated by Abdul-Rahman et al. [26] by integrating shuffling strategies to different graph colouring heuristics. Another recent study by Abdul Rahman et al. [33] considered a linear combination of graph colouring heuristics with a heuristic modifier to calculate the difficulty score of each examination. The examinations were ordered based on new difficulty score and the examination with the highest difficulty score was scheduled first. The experiment on two benchmark datasets of ETP showed that the proposed approach generated competitive results among other examination timetable approaches.In another study, Abdul-Rahman et al. [34] considered nonlinear heuristic modifier of graph coloring heuristics to construct solutions for examination timetabling problem. A nonlinear range was proposed using nonlinear heuristic modifier to estimate a difficulty value of an examination so that an effective estimation of examination’s difficulty could be obtained. A web-based examination timetabling system was introduced in Abdul-Rahman et al. [35] by incorporating a multiobjective approach based on graph colouring heuristics. The web-based system was developed for Universiti Utara Malaysia. The study also emphasizes the graphical user interface (GUI) of the system that enables the user to participate in the input, construction, and modification of a timetable. Abdul-Rahman et al. [36] developed an adaptive decomposition and ordering strategy that automatically divides examinations into difficult and easy sets based on graph colouring heuristics for constructing an examination timetable. The examinations in the difficult set are considered to be hard to place by referring to their number of conflict examinations and hence are listed before the ones in the easy set in the construction process.Meanwhile, in solving the ETP at Universiti Malaysia Pahang (UMP), Kahar and Kendall [23] presented a solution by using constructive heuristics, which was compared with a manual solution. The study introduced predetermined room grouping, room searching, and room selection. Based on the graph colouring heuristics, an algorithm was developed to produce a greater solution for the present software. The problem was further investigated by Kahar and Kendall [37] by incorporating invigilator requirement in the timetable using graph colouring approach. Other than that, Burke et al. [38] investigated Monte Carlo hyper-heuristics as a learning mechanism, which was incorporated in search process for ETP. It was found that the choice function appeared to be the best alternative for SA with reheating move acceptance within the hyper-heuristics approach. Next, Sabar et al. [39] introduced a measurement of difficulty index to measure examination difficulty within a hybridization of hierarchical low-level graph colouring heuristics approach, whereas Muklason et al. [40] investigated the fairness in examination timetabling by introducing multiobjective solution, also using the hyper-heuristics approach.Additionally, the local search-based algorithms have successfully solved ETPs. Caramia et al. [6] proposed a hill climbing algorithm as a penalty-decreaser in improving the quality of the timetable. The iterative process by the penalty-decreaser continued to search until no improvement was detected and the penalty-trader, i.e., hill climbing, took over the process. Later, Sabar et al. [41] proposed a hybrid tabu search with exponential Monte Carlo procedure to solve ETP. The work is an extension from Ayob and Kendall’s [48]. A counter-strategy was incorporated to calculate the successive nonimproving iterations to control the acceptance of worse solution. Meanwhile, Amaral and Pais [42] proposed a multiobjective tabu search approach with two new features to increase the algorithm automation. The approach, which was tested on ETP, exhibited that human interference could be avoided by combining weighting functions and compromise ratios.Moreover, Abdul-Rahman et al. [43] investigated the methods of ordering neighbourhood structures within a Variable Neighbourhood Search. The proposed approach hybridized a great deluge algorithm as a move acceptance method to vary the acceptance level. As a result, the empirical findings of a well-known examination timetabling benchmark displayed that the performance of Variable Neighbourhood Search great deluge had been reasonably well, ranking second among previously proposed approaches, with the right choice of initialisation and neighbourhood ordering methods. Next, a modified great deluge approach was proposed by Kahar and Kendall [23] to solve an ETP at Universiti Malaysia Pahang. The study concluded that the iterative process, neighbourhood, and starting solution were important factors that significantly affected the search for solution.On top of that, the population search-based algorithms were applied in solving ETPs. A hyper-heuristic methodology, known as “hyperhill-climber”, was proposed by Ersoy et al. [7]. The proposed approach employed an adaptive memetic algorithm to select the best hill climber. The hill climber determined the best ordering for the successive application of hill-climbers. Meanwhile, Pillay and Banzhaf [44] proposed a two-phased GA that was employed to induce a solution for ETP so as to cater to both hard and soft constraints. The findings showed that the proposed solutions outperformed other evolutionary approaches on some benchmark instances. Next, Innet [25] proposed a GA model in order to solve ETPs by using three genetic operators: crossover, mutation, and selection, in order to improve the effectiveness of automatic arranging examination timetable.Other than that, Turabieh and Abdullah [8] proposed a hybrid approach that considered a great deluge algorithm and an “electromagnetic-like mechanism” heuristics within timetabling approaches. An Estimation Distribution Algorithm-based hyper-heuristic was developed by Qu et al. [45] to solve ETP. The proposed approach is comparable with other hyper-heuristic approaches and was found suitable for specific problem solving situations. On top of that, Rankhambe and Kavita [46] developed harmony search hyper-heuristics, where the harmony search algorithm was based on heuristic harmony memory as low-level heuristics. The findings showed that the approach performed well on University of Nottingham benchmark datasets. Besides, Alzaqebah and Abdullah [47] hybridized bee colony optimization with late acceptance hill climbing and SA algorithms to solve the problem. As such, special selection strategies and self-adaptive neighbourhood mechanism were introduced to maintain the population diversity in backward pass, as well as to enhance the neighbourhood search. An extensive compilation of methodologies for ETP can be viewed in [49].


## 3.1.2. Course Timetabling Problem

Course timetabling refers to the process of assigning courses, rooms, students, and lecturers to a fixed time period, typically a working week, while satisfying a given set of constraints [50]. According to Obit [51], university course timetabling is considered as a weekly schedule of all university lecturers to a set of courses and at the same time to prevent the lecturers to have students in common at two different timeslots. Moreover, Obit [51] stated that, in reality, examination and course timetabling problem are about the same in some attributes but portray some variances. For instance, in examination timetabling, the room may have more than one examination scheduled at the same time, providing that the room seating capacity is not exceeded, while this is impossible for course timetabling, where the assignment normally allows one course per room, per timeslot.Typically, while constructing a feasible timetable for a course timetabling problem to satisfy all the hard constraints, the objective function of the problem has to be minimized, which usually reflects the violation of soft constraints. Some instances of the hard and soft constraints of course timetabling problem are presented in Table4. Other examples of constraints involved in course timetabling are that each course should be composed of the correct number of lecturers, no student can attend more than one lecture at the same time, and one lecturer has to be scheduled in exactly one room [52, 53].Table 4
The hard and soft constraints within the CTP adopted from Obit [51].
Constraint type Descriptions Hard constraints (i) The room capacity must be equal to or greater than the number of students attending the event in each timeslot. (ii) A student cannot attend two events simultaneously. (iii) Only one event is allowed to be assigned per timeslot in each room. (iv) The room assigned to an event must satisfy the features required by the event.  Soft constraints (i) Students should not have only one event timetabled on a day. (ii) Students should not attend more than two consecutive events on a day. (iii) Students should not attend an event in the last timeslot of a day.The real-world datasets employed in solving course timetabling problem from various institutions are depicted in Table5. There are also benchmark datasets for the CTP, commonly used as test bed such as Socha et al. [53], International Timetabling Competition 2002 and 2007 [29].Table 5
Summary of real-world course timetabling datasets from different institutions.
Reference Institution (s) Gunawan [54] University in Indonesia Oladokun & Badmus [55] University of Ibadan Thongsanit [56] Silpakorn University Borchani et al. [57] Tunisian University Méndez-Díaz et al. [58] A private university in Buenos Aires, Argentina Wahid and Hussin [59] Universiti Utara MalaysiaA number of solutions for course timetabling problems have been discussed in the academic literature (see Table6). An exact approach was proposed by Oladokun and Badmus [55] in optimizing the allocation of limited resources available for lecturing. As a test case, the study modeled and solved course timetabling problem for University of Ibadan. Furthermore, the integer linear programming (ILP) was applied in solving the problem. Next, Thongsanit [56] solved the course-classroom assignment problem for Silpakorn University within a short time and at a minimum cost. In solving the problem, the aim was to develop a mathematical model and to design the related methods. The study presented a guide to improve the solutions for classroom allocation problem with the aim of assigning courses to classrooms at a minimal cost. Meanwhile, Vermuyten et al. [60] investigated the flow of students within a course timetable problem by minimizing the travel time between consecutive lectures based on pedestrian traffic models. The problem was solved by using the decomposition approach as two-stage IP exhibited rather exceptional solutions.Table 6
Summary of studies related to CTP.
Approach Reference (s) Exact method Integer linear programming Oladokun and Badmus [55]; Thongsanit [56] Decomposition approach Vermuyten et al. [60]  Heuristic technique Integer linear programming based heuristics Méndez-Díaz et al. [58]  Metaheuristic technique Local search based Simulated annealing Ceschia et al. [61] Hyper-heuristics iterated local search Soria-Alcaraz et al. [62] Two stage metaheuristics Lewis and Thompson [63] Local search-based algorithm with adaptive mechanism Nagata [64] Variable neighborhood descent Borchani et al. [57] Tabu search with sampling and perturbation + SA with reheating Goh et al. [65] Nonlinear great deluge hyper-heuristics with reinforcement learning Obit et al. [66] Population search based Ant colony optimisation Nothegger et al. [67] Genetic algorithm Song et al. [68]  Hybrid Integer programming + greedy heuristics + modified simulated annealing Gunawan et al. [54] Genetic algorithm + local search Badoni et al. [69] Artificial bee colony algorithm + hill climbing optimizer Bolaji et al. [70] Integer programming + greedy heuristics Ghiani et al. [71] Hybrid multi-objective genetic algorithm + hill climbing + simulated annealing Akkan and Gülcü [72] Harmony search with great deluge Wahid and Hussin [59]Other than that, by using the ILP-based heuristics, a post-enrolment course timetabling problem at a private university in Buenos Aires, Argentina, was solved by Méndez-Díaz et al. [58]. The study produced good quality results and generalized other problems from the related literature.Meanwhile, Ceschia et al. [61] proposed a metaheuristic approach based on SA in solving post-enrolment course timetabling. The proposed approach was tested on benchmark dataset, which showed that the proposed approach was appropriately developed and adjusted. This is because the proposed approach worked well on all datasets and produced new best solution for most of the instances. Next, Soria-Alcaraz et al. [62] developed a constraints’ generic structure of a course timetabling problem, in which the problem was solved by using hyper-heuristics iterated local search. Furthermore, online learning showed that the proposed approach generated competitive results compared to other approaches presented in the literature and produced a number of new best-known solutions.Accordingly, Nagata [64] developed a local search-based algorithm with adaptive mechanism in varying neighbourhood sizes for a post-enrolment-based course timetabling problem. The study found that the recommended approach produced competitive results for well-known benchmark dataset of the problem and foresaw the trade-off between exploration and exploitation by adjusting the neighbourhood size. Similarly, Borchani et al. [57] investigated a university course timetabling problem in Tunisia by using Variable Neighbourhood Descent, which successfully removed an average of 52.47% of holes and isolated sessions with the introduction of 11 specific neighbourhood structures. Meanwhile, Goh et al. [65] solved a post-enrolment course timetabling problem by using a two-phase algorithm. The tabu search with sampling and perturbation was introduced to efficiently find feasible solution, while the SA with reheating eliminated the extensive tuning and scalability of runtime. The proposed algorithm produced new best solution for many instances. Obit et al. [66] investigated reinforcement learning with static and dynamic memory within nonlinear great deluge hyper-heuristics. The study showed that the static one performed better than the dynamic when solving CTP.Moreover, in the course timetabling problem domain, some researchers proposed population-based metaheuristic approaches. For instance, Nothegger et al. [67] applied Ant Colony Optimization to tackle the post-enrolment course timetabling problem, which was specified in the competition, namely, International Timetabling Competition 2007. Next, Song et al. [68] developed an energy efficiency-based course timetabling algorithm that optimized the constructed timetable based on energy consumption using GA. The study found that the proposed algorithm saved up to 4% of energy during cooling and heating seasons, when compared to the existing timetable. In addition, more energy saving up to 5.0% was achieved by mitigating hard constraints.Additionally, Gunawan et al. [54] proposed a hybrid algorithm that combined IP, a greedy heuristic, and a modified SA algorithm to solve a teacher assignment-course scheduling problem. The problem mixed both teacher assignment and course scheduling problems as mathematical programming model. Later, Badoni et al. [69] developed a hybrid approach that combined GA and local search approach by using events based on groupings of students. The hybrid approach produced better results on benchmark datasets, in comparison to other approaches found in the literature pertaining to course timetabling problem. After that, Bolaji et al. [70] employed artificial bee colony algorithm and hill climbing optimizer as a hybrid method to solve a university course timetabling problem. The study showed that a well-designed hybrid technique appeared to be a good alternative to tackle the problem, as the results displayed better performance than the other techniques. Next, a study on a course timetabling problem related to remedial education was introduced by Ghiani et al. [71] who employed both IP and greedy heuristics. The study introduced the selection of remedial courses while considering budgets and operational constraints that helped the students to achieve particular competencies in several skills at varied levels. Besides, Akkan and Gülcü [72] proposed a hybrid multiobjective genetic algorithm that was tested on benchmark dataset of course timetabling problem. The hybrid approach employed hill climbing and SA, which produced highly robust solution close to the best-known results. Wahid and Hussin [59] employed hybrid harmony search with great deluge for solving a real case of CTP.


## 3.1.3. School Timetabling Problem

The school timetabling problem (STP) is about generating school timetable that usually follows a cycle every week for all classes, in which the objective is to avoid teachers from attending two classes at the same time. In school timetabling, students are normally preassigned, while only teachers and rooms need to be assigned in the timetabling problem. As such, Cerdeira-Pena et al. [73] stated that STP is aimed at assigning period for teacher to certain subject in a specified group by considering groups of students and teachers in a fixed period scheduling. According to Pillay [74], STP is considered as NP-complete or NP-hard problem that depends on the intricacy of the problem in relation to various constraints. Moreover, studies on STP, along with its difficulty, had been investigated as early as 1976 by Even et al. [16] and more current analysis was undertaken by Carter and Tovey [75], Kingston [76], and Eikelder and Willemen [77], to name a few.In fact, the two types of constraints, which are hard and soft constraints, had been used to solve STP. With that, the fact that a teacher can only teach a lesson to one group at a time and the fact that a group cannot accept more than one lesson at a time by different teachers are examples of hard constraints. Usually, soft constraints depend on preferences by the teacher or are based on school policies, such as to minimize the number of periods for the teacher, to minimize the gaps within the timetable, and to avoid some subjects restriction at a prescribe time. Furthermore, Santos et al. [78] proposed that the basic hard constraints that need to be satisfied in school timetabling are that no teachers should be assigned to more than a class in the same timeslot, taking into account the teacher’s availability for each timeslot, and allocating the right number of timeslots for each teacher-class pair. Table 7 depicts the constraints proposed by Cerdeira-Pena et al. [73] in relation to STP.Table 7
The hard and soft constraints related to STP adopted from Cerdeira-Pena et al. [73].
Constraint type Descriptions Hard constraints (i) Overlaps: avoid the possibility of a class been taught by more than one teacher in the same period and avoid classes sharing resources (i.e., a classroom, lab, etc.), where classes which involved the same group could be assigned to the same period. (ii) Simultaneity: two classes are defined as simultaneous classes if they are taught by different teachers at the same time. (iii) Unavailability: it considers periods when a class cannot be given or when a teacher cannot teach. (iv) Consecutiveness: this constraint checks whether a distribution of hours for a pair teacher-class is followed. For example, some practical lessons should be taught in two consecutive periods of time.  Soft constraints (i) Overuse: it refers to the number of periods per day in which a teacher gives its lessons, over its specified maximum of periods per day. (ii) Underuse: when teachers have preferences on their minimum number of periods per day, it indicates the number of periods under such minimum. (iii) Holes: consider the number ofemptyperiods between two consecutive periods where a teacher is assigned a class. Breaks and free-time periods are not considered holes. (iv) Splits: consider the number of periods between two nonconsecutive assignments to the same class in the same day. (v) Groups: assuming a specified maximum of periods per day for an association teacher-class, it considers the number of exceeding periods in such day. This constraint is only considered if a maximum number of consecutive periods (related withconsecutiveness) for the pair class-teacher are not specified. (vi) Undesired: assuming that there are periods in which a teacher would prefer not to teach, this constraint indicates the number of such periods where that teacher is assigned a class. This constraint is thesoftversion of the mandatory unavailabilityconstraint (referring to teachers).The real-world datasets that had been used in solving STP are shown in Table8. Besides, the benchmark problems of STP are also available from Beligiannis et al. [79], Smith et al. [80], and International Timetabling Competition 2011 of High School Timetabling Archive XHSTT-2011 with 21 instances from 8 countries [81].Table 8
Summary of real-world school timetabling datasets from different institutions.
Reference Institution (s) Cerdeira-Pena et al. [73] Secondary school (I.E.S. Menendez Pidal) in A Coruna-Spain Santos et al. [78] Brazilian high schools Boland et al. [82] Australian high school Beligiannis et al. [79] Greek high schools Birbas et al. [83] Hellenic secondary school Ribić and Konjicija [84] Croatian secondary school Moura and Scaraficci [85] Brazilian high school Minh et al. [86] Vietnam high schoolsAs for the school timetabling field, several solutions were retrieved from the literature as described in Table9. Some approaches and new algorithms were applied and derived frequently over the years since school timetabling has further developed with SA, evolutionary algorithms, tabu search, IP, constraint programming, GRASP (Greedy Randomized Search Procedure), and so forth. Hybridizations are also some popular approaches in solving STP, which combine two or more methodologies. Comparative studies in STP were also conducted to compare the performance of several techniques. Normally, solving STP is computationally expensive and in order to reduce the running time, distributed methods have been suggested in association with the proposed approach.Table 9
Summary of studies related to STP.
Approach Reference (s) Exact method Integer Linear Programming Boland et al. [82]; Birbas et al. [83]; Ribić and Konjicija [84] Mixed Integer Programming Santos et al. [78]  Heuristic technique Hyper-heuristics Pillay [87]; Ahmed et al. [88]  Metaheuristic technique Local search based Simulated annealing Zhang et al. [89] Greedy Randomized Adaptive Search Procedure (GRASP) Moura and Scaraficci [85] Tabu search Minh et al. [86] Population search based Evolutionary algorithm Beligiannis et al. [79] Particle Swarm Optimization Tassopoulos et al. [90]  Hybrid Random Non-Ascendent Method (RNA) + genetic algorithm Cerdeira-Pena et al. [73] Simulated annealing + Tabu search Yongkai et al. [91]  Others Neural network Smith et al. [80]; Carrasco and Pato [92]For example, Boland et al. [82] proposed the exact approach by using two ILP models to solve STP. The ILP was applied in solving the problem of class blocking. Next, Birbas et al. [83] employed a hybrid approach to solve STP at the secondary Hellenic school where IP was applied in both phases. In the first phase, the shift assignment was catered by allocating teachers to shifts, while the second phase solved the whole STP, where the algorithm applied Fenchel cuts. After that, Ribić and Konjicija [84] employed IP with two-phase strategy to solve STP. The first phase focused on allocations, which later continued to solve the whole problem in the second phase. Meanwhile, Santos et al. [78] used mixed IP in solving Brazilian high schools as STP. The study proposed a cut and column generation algorithm as the solution methodology.Other than that, the hyper-heuristic based evolutionary algorithm (EA) method was employed by Pillay [87] in 2010 as the initial attempt at applying hyper-heuristics to STP. The study differentiated the performance of different low-level construction heuristics for this area. The study discovered that the use of mutation and crossover operators, which incorporated hill climbing, improves the EA-based hyper-heuristic performance. Ahmed et al. [88] in 2015 solved STP using hyper-heuristic based on the various selection of hyper-heuristics combining with different reusable components of STP. The hyper-heuristic approach combined with adaptive great deluge move acceptance method performed well on the tested ITC 2011 benchmark datasets.Similarly, Yongkai et al. [91] and Zhang et al. [89] solved a real-world STP by using SA algorithm that incorporated new neighbourhood structures in their studies. Yongkai et al. [91] proposed moves with a sequence structure, while Zhang et al. [89] performed swaps between pairs of timeslots, which had been carried out in sequence. Meanwhile, Moura and Scaraficci [85] applied path-relinking strategy with Greedy Randomized Adaptive Search Procedure (GRASP) to solve STP in three Brazilian high schools. Next, Minh et al. [86] solved STP at three Vietnamese high schools using tabu search. In the first phase, greedy search was employed to generate initial timetable, while tabu search was implemented in the second phase to improve the generated solution. The neighbourhood structures used in the study were single moves, swaps, and block moves.Other than that, Beligiannis et al. [79] employed EA technique to solve real STP in a Greek high school. Based on several comparisons made, this EA technique was found to be efficient in producing timetable more easily and quickly. On the other hand, Tassopoulos and Beligiannis [90] solved STP in a high school by using the Particle Swarm Optimization (PSO) method. This PSO method could also produce feasible and efficient timetables that outperformed four other existing techniques.Meanwhile, the hybrid algorithm was also applied in STP. Cerdeira-Pena et al. [73] recommended a new approach to solve STP, where Random Non-Ascendent Method (RNA) functioned as a local search technique and two variants of GA were hybridized to solve STP. Next, Yongkai et al. [91] proposed a two-phase approach to solve STP, where the first phase applied SA in order to get a feasible timetable. The first approach was developed by using new neighbourhoods, which swapped between timeslots in series while maintaining the timetable feasibility. Next, a tabu search was employed in the second phase to minimize the soft constraint.The study using machine learning such as neural network within education domain also appears in the literature. Example of a previous study on neural network was proposed by Smith et al. [80]. The study developed two discrete Hopfield neural network models for solving school timetabling problems. The approaches have shown competitive results when compared with other metaheuristics approaches, namely, greedy search, simulated annealing, and tabu search in terms of solution quality and computational effort.Carrasco and Pato [92] in 2004 employed the neural network-based heuristics to the class/teacher timetabling problem. Two models were introduced which are Potts mean-field annealing simulation and discrete neural network simulation. Test on a real problem showed that the discrete approach produced better performance in terms of solution quality and computation time. Comparison with multiobjective genetic algorithm also showed that the proposed neural network-based heuristics is competitive.


## 3.2. Allocation Problem

Allocation problem has been considered as a type of assignment problem. In fact, the allocation problem has been cited widely as a fundamental combinatorial optimization problem under optimization or operation research branch. The allocation problem is a famous problem discussed in the literature with various types of applications, especially within the education domain. This problem is categorised into three subproblems, which are (Section3.2.1) student-project allocation problem (SPAP), (Section 3.2.2) new student allocation problem (NSAP), and (Section 3.2.3) space allocation problem (SAP). The next subsections discuss these problems.


### 3.2.1. Student-Project Allocation Problem

The student-project allocation problem (SPAP) is related to assigning a person to a particular project or cases based on preference or interest of student and lecturer [13]. SPAP includes a set of projects, students, and lecturers, whereby every unique lecturer is offered a project and both the lecturers and projects have some capacity constraints. Students have preference towards project, while lecturers have preference towards student(s). Hence, SPAP is considered as an application of a stable matching problem, where the members of two entity sets, students and lecturers, have their own preferences on the projects. As such, Manlove and O’Malley [95] stated that the previous formulation of SPAP considered two conditions, either not to permit lecturer preferences [93] (where stability is not applicable in this case) or to include the preferences of lecturer [94].Thus, in order to solve the problem, both hard and soft constraints need to be considered. Table10 presents the constraints within SPAP highlighted by various researchers. In most cases of SPAP, the similar constraints involved were preference lists and capacity constraints.Table 10
The hard and soft constraints related to SPAP.
Constraint type Descriptions Reference (s) Hard constraints (i) Preference lists. Teo and Ho [93]; Abraham et al. [94]; Manlove and O’Malley [95]; Abu El-Atta and Moussa [96] (ii) Capacity constraints. Anwar and Bahaj [97]; Ramli and Bakar [98]; Harper et al. [99]; Abraham et al. [94]; Abu El-Atta and Moussa [96] (iii) Every student must be allocated one and only one project. Anwar and Bahaj [97] (iv) A project can be allocated to at most one student. Anwar and Bahaj [97] (v) Total number of cases available must not be more than the total number of students. Ghazali and Abdul-Rahman [100] (vi) Maximum number of students in handling a case. Ghazali and Abdul-Rahman [100] (vii) Maximum number of cases that can be handled by certain students. Ghazali and Abdul-Rahman [100]  Soft constraints (i) Assigning a number of students to many cases. Ghazali and Abdul-Rahman [100]Furthermore, numerous real-world SPAPs have been broadly introduced in the literature with variants of measurement and more real-world constraints, as presented in Table11.Table 11
Summary of real-world SPAP from different institutions.
Reference Institution (s) Anwar and Bahaj [97] University of Southampton Ramli and Bakar [98] Universiti Utara Malaysia Ghazali and Abdul-Rahman [100] Internship students at Law Firm in Malaysia Dye [101] University of YorkThe methodologies that have solved SPAP have been discussed in the academic literature (see Table12). The exact approaches were proposed by Anwar and Bahaj [97], where the IP approach was used to solve SPAP. The paper proposed how two models of IP were used in solving the project allocation problem based on criteria and constraints. Next, Li et al. [102] attempted to maximize the number of assigned projects by using goal programming model. The student’s preference was successfully increased by giving higher weightage to the higher preference. Meanwhile, a mix-integer programming model was developed by Calvo-Serrano et al. [103] by incorporating ranking of lecturers and research areas in the allocation process. This approach increased student satisfaction and decreased computation time for a large dataset.Table 12
Summary of related studies to SPAP.
Approach Reference (s) Exact method Integer programming Anwar and Bahaj [97] Goal programming Li et al. [102] Mixed integer linear programming Calvo-Serrano et al. [103]  Metaheuristic technique Local search based Simulated annealing Ghazali and Abdul-Rahman [100] Population search based Genetic algorithm Harper et al. [99]  Hybrid 0-1 integer programming + AHP Ramli and Bakar [98]  Other techniques Constraint Logic Programming Dye [101] Linear time algorithm Abraham et al. [94] Maximum stable matching to preferences over pair Abu El-Atta and Moussa [96] Maximum stable matching to preferences over projects Manlove and O’Malley [95]; Iwama et al. [104]Other than that, the local search-based and population search-based algorithms were applied in solving SPAP as well. A study carried out by Ghazali and Abdul-Rahman [100] focused on solving chambering student-case assignment problem with SA algorithm, where this problem was categorised under SPAP. The aim was to minimize all the students’ completion time in order to solve the given cases. Next, Harper et al. [99] proposed population-based metaheuristic approaches by applying GA for the project assignment problem. They developed an algorithm and then compared it to an optimal integer programming approach.Next, a hybrid algorithm was used in solving SPAP. Ramli and Bakar [98] discussed how 0-1 IP model and Analytical Hierarchy Process (AHP) technique had been employed to assign projects to the students. The model dismissed student preference for team members, since by doing so, the total constraints and variables increased significantly.Meanwhile, Dye [101] applied a Constraint Logic Programming to improve project allocation problem in University of York. Good solution arrived for small dataset but was proven to be inefficient for large data. Abraham et al. [94] proposed linear-time algorithms to determine a stable matching for student-project. Stability is defined as a natural stability generalization to construct an optimal and stable matching for both students and lecturers. Meanwhile, Abu El-Atta and Moussa [96] presented a visual implementation to construct a SPA model with preference over pairs. A java-applet program was implemented to visualize the SPA since java is a web-oriented and object-oriented language. In addition, Manlove and O’Malley [95] proposed a SPAP with projects preferences. They studied how to allocate students to projects and fulfilled the preferences from both students and lecturers, as well as capacity requirement for both projects and lecturers. The process required a complex coding and implementation of the algorithm. The results showed that the problem of finding a maximum stable matching in SPAP was very hard that gave a polynomial-time 2-approximation algorithm. Then, in 2012, Iwama et al. [104] improved the upper bound to 1.5 and the lower bound to 21/19.


### 3.2.2. New Student Allocation Problem

The new student allocation problem (NSAP) is a clustering problem in allocating new students to their corresponding class with minimum intelligence gap by sorting method: a group of new students with similar ranking and assigned into the same class. Table13 presents the constraints involved in NSAP highlighted by different researchers. In fact, studies performed by Zukhri and Omar [105] and Hassim et al. [106] allocated new students into certain classes in order to keep the optimum students’ capacity in each class. The number of students in every class should not surpass the maximum capacity.Table 13
The hard constraints within the NSAP adopted from Zukhri and Omar [105] and Hassim et al. [106].
Constraint type Descriptions Hard constraints (i) Capacity of students in each class. (ii) A group of new students with similar ranking assigned to the same class.The real-world datasets broadly introduced to NSAP and some real-world NSAP from various institutions are presented in Table14. The studies present various measurements and practical constraints.Table 14
Summary of real-world NSAP from different institutions.
Reference Institution (s) Zukhri and Omar [105] Islamic University of Indonesia Hassim et al. [106] Politeknik Ungku Omar Rad et al. [107] 177 existing university majors in Iran Ma et al. [108] Singaporean Ministry of EducationTable15 presents the summary within NSAP highlighted by various researchers. The study by Zukhri and Omar [105] and Hassim et al. [106] shared similar aim, which was to solve NSAP so as to keep the optimum capacity of students in each class, besides helping the management in a manner and fair way in selecting new students into their classes to ensure that they can perform in their studies. However, different solution methodologies of NSAP are discussed in the academic literature. The study by Zukhri and Omar [105] explored the NSAP by using GA to allocate new students to classes subject to satisfy both students and rooms requirement.Table 15
Summary of studies related to NSAP problem.
Approach  Reference (s) Metaheuristic technique Population search-based Genetic algorithm Zukhri and Omar [105]  Hybrid  K-means algorithm + AHP Rad et al. [107]  Other techniques  Data mining Ma et al. [108] FuzzyC-means algorithm Susanto [109] Subtractive ClusteringTechnique (SCT) Yadav and Ahmed [110] Analytical Hierarchy Process Hassim et al. [106] Bayesian approach Yadav [111]Besides, by using data mining, Ma et al. [108] aimed to award Gifted Education Programme (GEP) by the Singaporean Ministry of Education (MOE) to the right students. The targeted students for remedial classes were selected in a precise manner by using the proposed approach. On the other hand, Susanto [109] proposed fuzzy C-means algorithm (FCM) to allocate students from certain subjects into different classes. Students of various subjects were clustered based on their prerequisite subject scores. In the study, students with similar achievements were pooled into the same class, while students with slightly dissimilar achievement levels were combined in different classes.Next, Yadav and Ahmed [110] explored the applicability of Subtractive Clustering Technique (SCT) to solve NSAP that allocated new students to similar groups of specified maximum capacity and analysed the impact of allocations upon students’ academic performance. Meanwhile, Hassim et al. [106] proposed AHP to solve NSAP. The paper focused on minimizing the intelligence gap in each class. Meanwhile, Yadav [111] applied the Bayesian approach in classifying new students into their classes based on their intelligence based on academic achievements.However, some researchers proposed the hybrid algorithm to solve NSAP. For example, Rad et al. [107] proposed a hybrid model to cluster and rank university majors in Iran. In fact, a total of 177 existing university majors were compared on various criteria. The university majors were clustered based on similarities and differences by using K-means algorithm and were later ranked by using AHP.


### 3.2.3. Space Allocation Problem

The space allocation problem (SAP) refers to a problem to allocate resources to space areas, for example, allocating rooms and at the same time satisfying several requirements and constraints [112]. Besides, Burke and Varley [125] described SAP as an allocation of rooms or areas of space for detailed function. Since space is limited, availability should be managed properly by assigning rooms to suitable users. With that, this subsection focuses on classroom space allocation that discusses the assignment of available classroom to a number of courses subject to room requirements and student population sizes. The aim of SAP is to ensure maximum space utilization and to satisfy all requirements and/or constraints as much as possible. In this case, all entities need to be allocated, where no wastage or overused space should occur, and any additional requirements and constraints should be satisfied. An important condition exists in this case, where the available space areas and special requirements by entities are not subject to amendment.As such, several sets of constraints had been involved in SAP, as highlighted in past studies (see Table16).Table 16
The hard and soft constraints within the SAP.
Constraint type Descriptions Reference (s) Hard constraints (i) Classroom capacity. Frimpong and Owusu [112]; Constantino [113]; Bagger et al. [114]; Navuduri [115] (ii) Room’s availability at different time of the day and room request. Gosselin and Truchon [116]  Soft constraints (i) Events from the same course occurring the same day must be allocated as close to each other as possible with respect to their geographical location. Bagger et al. [114] (ii) If an event is split into multiple rooms, these must also be as close to each other as possible in the geographical senseSome real-life datasets that have been broadly introduced to SAP are presented in Table17.Table 17
Summary of real-world SAP from different institutions.
Reference Institution (s) Burke et al. [117]; Landa-Silva [11] University of Nottingham, Nottingham Trent University and University of Wolverhampton  Beyrouthy et al. [118]; Beyrouthy et al. [119] University in Sydney Australia  Adewumi and Ali [120] Nigeria Universities  Bagger et al. [114] Technical University of Denmark (DTU)  Frimpong and Owusu [112] Premier Nurse’s Training College, Kumasi  Phillips et al. [121] University of Auckland, New Zealand  Abdullah et al. [122] Universiti Teknologi MalaysiaVarying solution approaches have been proposed in the academic literature (see Table18), where some studies proposed the exact approaches in solving SAP. For example, Gosselin and Truchon [116] proposed an allocation of classrooms in an educational institution by using the LP model to minimize penalty function. First, the model satisfied all the requested rooms as possible and then attempted to spread this departure uniformly among the requests. Meanwhile, in order to solve classroom allocation of Premier Nurse’s Training College, Kumasi, Frimpong, and Owusu [112] formulated an LP model with the aim of maximizing classroom space usage using POM-QM model for windows. Next, Phillips et al. [121] solved a classroom assignment problem of university course timetabling based on a novel formulation of IP. The proposed approach simplified the previous models and preserved tractability even when tested with large instancesTable 18
Summary of studies related to SAP.
Approach Reference (s) Exact method Linear programming Gosselin and Truchon [116]; Frimpong and Owusu [112] Integer programming Phillips et al. [121]  Metaheuristic technique Local search based Tabu search Burke et al. [123] Variable neighbourhood search Constantino [113] Population search based Genetic algorithm Adewumi and Ali [120]  Hybrid Hill climbing + SA + Tabu search + GA Burke et al. [117] Iterative improvement + SA + Tabu search + GA) Landa-Silva Dario [124] Hill climbing + SA Beyrouthy et al. [118] IP + SA Beyrouthy et al. [119] Mixed Integer Program (MIP) + C# Bagger et al. [114]  Other techniques MS EXCEL + SPSS Abdullah et al. [122] Web-based system Navuduri [115]Meanwhile, Burke et al. [123] presented multiobjective hyper-heuristic approaches to solve SAP. A tabu search hyper-heuristic technique was proposed. Next, Constantino [113] solved a classroom assignment problem in a large university by using two iterated heuristic algorithms to minimize the total distance of teaching activities between classrooms. Instead, other added requests that need to be satisfied were generating efficient space utilization, satisfying preferences of the room, and fulfilling other administrative requests. Later, Adewumi and Ali [120] presented a hierarchical-based heuristics solution in solving a hostel SAP. An interrelated heuristics was applied at different allocation process levels in order to achieve constraints and objectives. Then, GA was applied at the lowest level in order to drive the final allocation distribution.Besides, some researchers applied the hybrid technique in solving SAP. Burke et al. [117] proposed hybrid population-based metaheuristic approaches for SAP, where a series of techniques, such as hill climbing, SA, tabu search, and GA, were applied. Meanwhile, Landa-Silva Dario [124] applied metaheuristic and multiobjective approaches to solve SAP. An iterative improvement, SA, tabu search, and GA were adapted for problem application. Next, Beyrouthy et al. [118] applied hill climbing and SA to solve a teaching SAP with slipping. Later, Beyrouthy et al. [119] combined IP and SA approaches in utilizing university teaching space of University in Sydney Australia. Besides, Bagger et al. [114] proposed a Mixed Integer Program (MIP) solver within the constructive heuristic in solving a room allocation optimization problem. The heuristic and metaheuristic methods were applied to the problem for comparison and tested on five real-life data sets derived from Technical University of Denmark (DTU).Moving on, Abdullah et al. [122] employed both qualitative and quantitative techniques to measure the usage of teaching and learning space in Universiti Teknologi Malaysia (UTM). Besides, some researchers proposed a computer-assisted system in solving classroom allocation problem. Meanwhile, Navuduri [115] proposed a web-based system that helped university staff to assign classrooms for a given semester, where the system weighed in several elements, such as classroom size, course capacity, and preferred building of a department.


## 3.2.1. Student-Project Allocation Problem

The student-project allocation problem (SPAP) is related to assigning a person to a particular project or cases based on preference or interest of student and lecturer [13]. SPAP includes a set of projects, students, and lecturers, whereby every unique lecturer is offered a project and both the lecturers and projects have some capacity constraints. Students have preference towards project, while lecturers have preference towards student(s). Hence, SPAP is considered as an application of a stable matching problem, where the members of two entity sets, students and lecturers, have their own preferences on the projects. As such, Manlove and O’Malley [95] stated that the previous formulation of SPAP considered two conditions, either not to permit lecturer preferences [93] (where stability is not applicable in this case) or to include the preferences of lecturer [94].Thus, in order to solve the problem, both hard and soft constraints need to be considered. Table10 presents the constraints within SPAP highlighted by various researchers. In most cases of SPAP, the similar constraints involved were preference lists and capacity constraints.Table 10
The hard and soft constraints related to SPAP.
Constraint type Descriptions Reference (s) Hard constraints (i) Preference lists. Teo and Ho [93]; Abraham et al. [94]; Manlove and O’Malley [95]; Abu El-Atta and Moussa [96] (ii) Capacity constraints. Anwar and Bahaj [97]; Ramli and Bakar [98]; Harper et al. [99]; Abraham et al. [94]; Abu El-Atta and Moussa [96] (iii) Every student must be allocated one and only one project. Anwar and Bahaj [97] (iv) A project can be allocated to at most one student. Anwar and Bahaj [97] (v) Total number of cases available must not be more than the total number of students. Ghazali and Abdul-Rahman [100] (vi) Maximum number of students in handling a case. Ghazali and Abdul-Rahman [100] (vii) Maximum number of cases that can be handled by certain students. Ghazali and Abdul-Rahman [100]  Soft constraints (i) Assigning a number of students to many cases. Ghazali and Abdul-Rahman [100]Furthermore, numerous real-world SPAPs have been broadly introduced in the literature with variants of measurement and more real-world constraints, as presented in Table11.Table 11
Summary of real-world SPAP from different institutions.
Reference Institution (s) Anwar and Bahaj [97] University of Southampton Ramli and Bakar [98] Universiti Utara Malaysia Ghazali and Abdul-Rahman [100] Internship students at Law Firm in Malaysia Dye [101] University of YorkThe methodologies that have solved SPAP have been discussed in the academic literature (see Table12). The exact approaches were proposed by Anwar and Bahaj [97], where the IP approach was used to solve SPAP. The paper proposed how two models of IP were used in solving the project allocation problem based on criteria and constraints. Next, Li et al. [102] attempted to maximize the number of assigned projects by using goal programming model. The student’s preference was successfully increased by giving higher weightage to the higher preference. Meanwhile, a mix-integer programming model was developed by Calvo-Serrano et al. [103] by incorporating ranking of lecturers and research areas in the allocation process. This approach increased student satisfaction and decreased computation time for a large dataset.Table 12
Summary of related studies to SPAP.
Approach Reference (s) Exact method Integer programming Anwar and Bahaj [97] Goal programming Li et al. [102] Mixed integer linear programming Calvo-Serrano et al. [103]  Metaheuristic technique Local search based Simulated annealing Ghazali and Abdul-Rahman [100] Population search based Genetic algorithm Harper et al. [99]  Hybrid 0-1 integer programming + AHP Ramli and Bakar [98]  Other techniques Constraint Logic Programming Dye [101] Linear time algorithm Abraham et al. [94] Maximum stable matching to preferences over pair Abu El-Atta and Moussa [96] Maximum stable matching to preferences over projects Manlove and O’Malley [95]; Iwama et al. [104]Other than that, the local search-based and population search-based algorithms were applied in solving SPAP as well. A study carried out by Ghazali and Abdul-Rahman [100] focused on solving chambering student-case assignment problem with SA algorithm, where this problem was categorised under SPAP. The aim was to minimize all the students’ completion time in order to solve the given cases. Next, Harper et al. [99] proposed population-based metaheuristic approaches by applying GA for the project assignment problem. They developed an algorithm and then compared it to an optimal integer programming approach.Next, a hybrid algorithm was used in solving SPAP. Ramli and Bakar [98] discussed how 0-1 IP model and Analytical Hierarchy Process (AHP) technique had been employed to assign projects to the students. The model dismissed student preference for team members, since by doing so, the total constraints and variables increased significantly.Meanwhile, Dye [101] applied a Constraint Logic Programming to improve project allocation problem in University of York. Good solution arrived for small dataset but was proven to be inefficient for large data. Abraham et al. [94] proposed linear-time algorithms to determine a stable matching for student-project. Stability is defined as a natural stability generalization to construct an optimal and stable matching for both students and lecturers. Meanwhile, Abu El-Atta and Moussa [96] presented a visual implementation to construct a SPA model with preference over pairs. A java-applet program was implemented to visualize the SPA since java is a web-oriented and object-oriented language. In addition, Manlove and O’Malley [95] proposed a SPAP with projects preferences. They studied how to allocate students to projects and fulfilled the preferences from both students and lecturers, as well as capacity requirement for both projects and lecturers. The process required a complex coding and implementation of the algorithm. The results showed that the problem of finding a maximum stable matching in SPAP was very hard that gave a polynomial-time 2-approximation algorithm. Then, in 2012, Iwama et al. [104] improved the upper bound to 1.5 and the lower bound to 21/19.


## 3.2.2. New Student Allocation Problem

The new student allocation problem (NSAP) is a clustering problem in allocating new students to their corresponding class with minimum intelligence gap by sorting method: a group of new students with similar ranking and assigned into the same class. Table13 presents the constraints involved in NSAP highlighted by different researchers. In fact, studies performed by Zukhri and Omar [105] and Hassim et al. [106] allocated new students into certain classes in order to keep the optimum students’ capacity in each class. The number of students in every class should not surpass the maximum capacity.Table 13
The hard constraints within the NSAP adopted from Zukhri and Omar [105] and Hassim et al. [106].
Constraint type Descriptions Hard constraints (i) Capacity of students in each class. (ii) A group of new students with similar ranking assigned to the same class.The real-world datasets broadly introduced to NSAP and some real-world NSAP from various institutions are presented in Table14. The studies present various measurements and practical constraints.Table 14
Summary of real-world NSAP from different institutions.
Reference Institution (s) Zukhri and Omar [105] Islamic University of Indonesia Hassim et al. [106] Politeknik Ungku Omar Rad et al. [107] 177 existing university majors in Iran Ma et al. [108] Singaporean Ministry of EducationTable15 presents the summary within NSAP highlighted by various researchers. The study by Zukhri and Omar [105] and Hassim et al. [106] shared similar aim, which was to solve NSAP so as to keep the optimum capacity of students in each class, besides helping the management in a manner and fair way in selecting new students into their classes to ensure that they can perform in their studies. However, different solution methodologies of NSAP are discussed in the academic literature. The study by Zukhri and Omar [105] explored the NSAP by using GA to allocate new students to classes subject to satisfy both students and rooms requirement.Table 15
Summary of studies related to NSAP problem.
Approach  Reference (s) Metaheuristic technique Population search-based Genetic algorithm Zukhri and Omar [105]  Hybrid  K-means algorithm + AHP Rad et al. [107]  Other techniques  Data mining Ma et al. [108] FuzzyC-means algorithm Susanto [109] Subtractive ClusteringTechnique (SCT) Yadav and Ahmed [110] Analytical Hierarchy Process Hassim et al. [106] Bayesian approach Yadav [111]Besides, by using data mining, Ma et al. [108] aimed to award Gifted Education Programme (GEP) by the Singaporean Ministry of Education (MOE) to the right students. The targeted students for remedial classes were selected in a precise manner by using the proposed approach. On the other hand, Susanto [109] proposed fuzzy C-means algorithm (FCM) to allocate students from certain subjects into different classes. Students of various subjects were clustered based on their prerequisite subject scores. In the study, students with similar achievements were pooled into the same class, while students with slightly dissimilar achievement levels were combined in different classes.Next, Yadav and Ahmed [110] explored the applicability of Subtractive Clustering Technique (SCT) to solve NSAP that allocated new students to similar groups of specified maximum capacity and analysed the impact of allocations upon students’ academic performance. Meanwhile, Hassim et al. [106] proposed AHP to solve NSAP. The paper focused on minimizing the intelligence gap in each class. Meanwhile, Yadav [111] applied the Bayesian approach in classifying new students into their classes based on their intelligence based on academic achievements.However, some researchers proposed the hybrid algorithm to solve NSAP. For example, Rad et al. [107] proposed a hybrid model to cluster and rank university majors in Iran. In fact, a total of 177 existing university majors were compared on various criteria. The university majors were clustered based on similarities and differences by using K-means algorithm and were later ranked by using AHP.


## 3.2.3. Space Allocation Problem

The space allocation problem (SAP) refers to a problem to allocate resources to space areas, for example, allocating rooms and at the same time satisfying several requirements and constraints [112]. Besides, Burke and Varley [125] described SAP as an allocation of rooms or areas of space for detailed function. Since space is limited, availability should be managed properly by assigning rooms to suitable users. With that, this subsection focuses on classroom space allocation that discusses the assignment of available classroom to a number of courses subject to room requirements and student population sizes. The aim of SAP is to ensure maximum space utilization and to satisfy all requirements and/or constraints as much as possible. In this case, all entities need to be allocated, where no wastage or overused space should occur, and any additional requirements and constraints should be satisfied. An important condition exists in this case, where the available space areas and special requirements by entities are not subject to amendment.As such, several sets of constraints had been involved in SAP, as highlighted in past studies (see Table16).Table 16
The hard and soft constraints within the SAP.
Constraint type Descriptions Reference (s) Hard constraints (i) Classroom capacity. Frimpong and Owusu [112]; Constantino [113]; Bagger et al. [114]; Navuduri [115] (ii) Room’s availability at different time of the day and room request. Gosselin and Truchon [116]  Soft constraints (i) Events from the same course occurring the same day must be allocated as close to each other as possible with respect to their geographical location. Bagger et al. [114] (ii) If an event is split into multiple rooms, these must also be as close to each other as possible in the geographical senseSome real-life datasets that have been broadly introduced to SAP are presented in Table17.Table 17
Summary of real-world SAP from different institutions.
Reference Institution (s) Burke et al. [117]; Landa-Silva [11] University of Nottingham, Nottingham Trent University and University of Wolverhampton  Beyrouthy et al. [118]; Beyrouthy et al. [119] University in Sydney Australia  Adewumi and Ali [120] Nigeria Universities  Bagger et al. [114] Technical University of Denmark (DTU)  Frimpong and Owusu [112] Premier Nurse’s Training College, Kumasi  Phillips et al. [121] University of Auckland, New Zealand  Abdullah et al. [122] Universiti Teknologi MalaysiaVarying solution approaches have been proposed in the academic literature (see Table18), where some studies proposed the exact approaches in solving SAP. For example, Gosselin and Truchon [116] proposed an allocation of classrooms in an educational institution by using the LP model to minimize penalty function. First, the model satisfied all the requested rooms as possible and then attempted to spread this departure uniformly among the requests. Meanwhile, in order to solve classroom allocation of Premier Nurse’s Training College, Kumasi, Frimpong, and Owusu [112] formulated an LP model with the aim of maximizing classroom space usage using POM-QM model for windows. Next, Phillips et al. [121] solved a classroom assignment problem of university course timetabling based on a novel formulation of IP. The proposed approach simplified the previous models and preserved tractability even when tested with large instancesTable 18
Summary of studies related to SAP.
Approach Reference (s) Exact method Linear programming Gosselin and Truchon [116]; Frimpong and Owusu [112] Integer programming Phillips et al. [121]  Metaheuristic technique Local search based Tabu search Burke et al. [123] Variable neighbourhood search Constantino [113] Population search based Genetic algorithm Adewumi and Ali [120]  Hybrid Hill climbing + SA + Tabu search + GA Burke et al. [117] Iterative improvement + SA + Tabu search + GA) Landa-Silva Dario [124] Hill climbing + SA Beyrouthy et al. [118] IP + SA Beyrouthy et al. [119] Mixed Integer Program (MIP) + C# Bagger et al. [114]  Other techniques MS EXCEL + SPSS Abdullah et al. [122] Web-based system Navuduri [115]Meanwhile, Burke et al. [123] presented multiobjective hyper-heuristic approaches to solve SAP. A tabu search hyper-heuristic technique was proposed. Next, Constantino [113] solved a classroom assignment problem in a large university by using two iterated heuristic algorithms to minimize the total distance of teaching activities between classrooms. Instead, other added requests that need to be satisfied were generating efficient space utilization, satisfying preferences of the room, and fulfilling other administrative requests. Later, Adewumi and Ali [120] presented a hierarchical-based heuristics solution in solving a hostel SAP. An interrelated heuristics was applied at different allocation process levels in order to achieve constraints and objectives. Then, GA was applied at the lowest level in order to drive the final allocation distribution.Besides, some researchers applied the hybrid technique in solving SAP. Burke et al. [117] proposed hybrid population-based metaheuristic approaches for SAP, where a series of techniques, such as hill climbing, SA, tabu search, and GA, were applied. Meanwhile, Landa-Silva Dario [124] applied metaheuristic and multiobjective approaches to solve SAP. An iterative improvement, SA, tabu search, and GA were adapted for problem application. Next, Beyrouthy et al. [118] applied hill climbing and SA to solve a teaching SAP with slipping. Later, Beyrouthy et al. [119] combined IP and SA approaches in utilizing university teaching space of University in Sydney Australia. Besides, Bagger et al. [114] proposed a Mixed Integer Program (MIP) solver within the constructive heuristic in solving a room allocation optimization problem. The heuristic and metaheuristic methods were applied to the problem for comparison and tested on five real-life data sets derived from Technical University of Denmark (DTU).Moving on, Abdullah et al. [122] employed both qualitative and quantitative techniques to measure the usage of teaching and learning space in Universiti Teknologi Malaysia (UTM). Besides, some researchers proposed a computer-assisted system in solving classroom allocation problem. Meanwhile, Navuduri [115] proposed a web-based system that helped university staff to assign classrooms for a given semester, where the system weighed in several elements, such as classroom size, course capacity, and preferred building of a department.


## 4. Potential Path

Diverse methods have been proposed for assignment problem in education domain within these recent times. In fact, researchers have worked really hard to adapt several optimization procedures to solve these problems. Moreover, it is usually not easy to formulate the actual problem that suits a particular solution procedure and there will be a lot of work to be done to fully utilize the solution quality. As such, several studies are still under progress in determining effective solutions for assignment problems.The timetabling problem was classified into three subproblems, which were examination timetabling problem, course timetabling problem, and school timetabling problem. As observed, most researchers applied the heuristic techniques, which is graph colouring heuristics, to solve ETP. However, there is an idea for future work for solving a more complex problem as mentioned in Ayob et al. [5] by combining schedule for invigilators and room assignments. Current research also intended to test their approaches on well-known benchmark dataset in order to test the effectiveness of their algorithm (as proposed by Abdul-Rahman et al. [126]) which signified real examination timetabling data instances with various requirements and limitations. In terms of approaches within ETP, the latest trend shows that the hybrid approach of nature inspired algorithm has potential for further research such as harmony search algorithm and bee colony optimization. Besides, researches also tend to focus on hyper-heuristics approach as a general approach to produce good solution quality.Prior studies of course timetabling problem showed that various techniques have been implemented to address the problem. The proposed approach usually depended on the complexity of the problem, while the complexity of the problem relied on the problem size, and the difficulty of the problem was related to varied constraints and preferences. However, most of the publications in the literature on course timetabling problem focused on testing the benchmark problem, in comparison to the real-world problem. When compared with ETP, various preferences have been introduced in the problem, while the course timetabling problem mostly catered only for basic requirement of the problem. Thus, this problem has bigger opportunity to be investigated by researchers in order to understand more on the problem requirement and preferences. Hence, this bridges the gap between the benchmark problem and the real cases of the problem. In terms of techniques proposed to overcome the problem, local search technique and their hybridization have the potential to be further investigated. The variation of the approach is mostly focused on local search approach and not for any swarm-based approach, except that for Bolaji et al. [70]. Thus, there is a huge opportunity for the swarm-based approach to be investigated further within the course timetabling problem.Meanwhile, in solving STP, many researchers proposed various techniques. The problems turned narrower when the main aim was to avoid teachers from having to attend two events at one time. Therefore, the researchers tended to understand more on the real cases of the problem. As for the techniques proposed, the local search-based technique has potential to be further explored since most of the literature focused in producing good solution quality. Furthermore, the latest trend also showed that IP model is also popular in solving STP. Most of the studies proposed an algorithm in order to give an optimum solution to the problem.As for allocation problem, it had been classified into three subproblems: student-project allocation problem (SPAP), new student allocation problem (NSAP), and space allocation problem (SAP). Most researchers applied the exact method such as integer programming models to obtain an optimum solution to the problem. The main aspect in SPAP is to satisfy the constraints. As noted, most of the publications in the literature on SPAP focused on the capacity constraints and preferences of entities (students and lecturers). Furthermore, the latest trend also showed that stable matching problem, which considered both preferences of the entities towards projects, is also popular in order to solve STP. By applying stable matching problem in NSAP, it represents how real-life preferences can really occur, besides increasing the satisfaction of both entities in order to solve allocation problem.In fact, past studies concerning NSAP showed the proposal of various techniques. When compared with SPAP, it includes assigning a person to a particular project or case based on preference or interest of student and lecture, while NSAP catered to the clustering problem of new student based on ranking (intelligence gap). As observed, most researches focused on solving the real problem of NSAP by applying different techniques. For example, Ma et al. [108] proposed data mining, Susanto [109] proposed fuzzy C-means algorithm, Yadav and Ahmed [110] proposed Subtractive Clustering Technique (SCT), Hassim et al. [106] proposed AHP, and Yadav [111] proposed Bayesian approach. Then, in providing a better research for future work of their researches, they also offered several suggestions. In selecting the right students for numerous purposes, Ma et al. [108] considered students’ categorisation in developing a system within an educational institution, which was weak, good, and special needs. Meanwhile, Yadav and Ahmed [110] claimed that it is worth expanding the study by using a combinative technique of SCT and fuzzy C-means called hybrid Fuzzy Expert system in evaluating student-teacher academic performance. Other than that, Yadav [111] proposed a combination of techniques involving SCT, GA, and Artificial Neural Network techniques (i.e., hybrid Fuzzy Expert system) to evaluate the academic performances of students and teachers.Lastly, past studies in SAP showed that various approaches have been employed to solve the real problem of SAP. Most researchers tended to hybrid a number of techniques to solve SAP. Based on this review, it is found that the hybrid approaches produced better results when tested on real-world datasets compared to other single approaches in the literature. Burke et al. [117] combined hill climbing, SA, tabu search, and GA, while Landa-Silva Dario [124] proposed iterative improvement with SA, tabu search, and GA. Next, Beyrouthy et al. [118] combined hill climbing and SA, while Beyrouthy et al. [119] and Bagger et al. [114] used Mixed Integer Program (MIP). In fact, some researchers provided a few suggestions for future works. Burke et al. [117] suggested to include experiments using other SAPs in establishing more exact values for its parameters, such as the population size. Moreover, multiobjective feature displayed better future to be investigated within SAP. In addition, Landa-Silva Dario [124] suggested to test a fully automated system with a full range of data sets from diverse universities and to ponder other parts of the problem, besides completing allocations construction. Next, Beyrouthy et al. [118] aimed to improve the speed and planned for multicriteria in their future work. Meanwhile, Beyrouthy et al. [119] stated that a full series of comparisons against other real problems will be carried out in their future work. Also, extra efficient methods to produce better solutions need to be implemented.


## 5. Conclusion

The assignment problem is a combinatorial optimization problem that is flexible as it can be used as an approach to model any real-world problem. In fact, several components in assignment problem have been explored, for example, the constraints and solution methodology used within the education domain. As such, this paper presents the review of assignment problems discussed in the previous literature within educational activities. Not only that, this paper provides several solution approaches in solving assignment problem, where various approaches were introduced in solving these types of problems.Moreover, it is very important to choose the right approaches in solving the problem so as to obtain an optimal or near optimal solution depending on the complexity of the problem. Based on past literature that had been reviewed, the heuristic and metaheuristic approaches were the top trend to solve the assignment problem because these approaches produced good, but not certainly optimal solution. It was also found that numerous proposed approaches that have been discussed are significant to be used and have been adapted in some real-world situations. The assignment problem will remain an endless puzzle in the future as its flexibility in diverse applications that can be applied into real-world situations.



---

*Source: 8958393-2018-05-17.xml*