Printer Friendly

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

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 assign n 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: Section 2 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 potentialpathofsolutionapproacharepresentedinSection4.

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

[n.summation over (i=1)] [n.summation over (j=1)] [c.sub.ij][x.sub.ij] (1)

subject to

[n.summation over (j=1)] [x.sub.ij] = 1, j = 1,..., n (2)

[n.summation over (i=1)] [x.sub.ij] = 1, j = 1,..., n (3)

[x.sub.ij] = 0 or 1, i = 1,..., n, j = 1,..., n (4)

where [c.sub.ij] is the cost or effectiveness of assigning ith resource to jth demand, [x.sub.ij] 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 matrix [[c.sub.ij]],where [c.sub.ij] 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:

[mathematical expression not reproducible] (5)

Moreover, 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 Marti 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 = [e.sub.1], [e.sub.2],..., [e.sub.n], needs to be assigned to a limited number of timeslots, T = [t.sub.1], [t.sub.2],..., [t.sub.n], 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 Table 1.

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 Table 2). 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.

Real-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 Table 3).

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 hyperheuristics 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 Table 4. 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].

The real-world datasets employed in solving course timetabling problem from various institutions are depicted in Table 5. 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].

A number of solutions for course timetabling problems have been discussed in the academic literature (see Table 6). 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.

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 Mendez-Diaz 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 newbest-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 tacke 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 Gulcu [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 CerdeiraPena et al. [73] in relation to STP.

The real-world datasets that had been used in solving STP are shown in Table 8. 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].

As for the school timetabling field, several solutions were retrieved from the literature as described in Table 9. 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.

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, Ribic 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 hyperheuristic performance. Ahmed et al. [88] in 2015 solved STP using hyper-heuristic based on the various selection of hyperheuristics 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 (Section 3.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 studentproject 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. Table 10 presents the constraints within SPAP highlighted by various researchers. In most cases of SPAP, the similar constraints involved were preference lists and capacity constraints.

Furthermore, numerous real-world SPAPs have been broadly introduced in the literature with variants of measurement and more real-world constraints, as presented in Table 11.

The methodologies that have solved SPAP have been discussed in the academic literature (see Table 12). 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 weight-age 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.

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. Table 13 presents the constraints involved in NSAP highlighted by different researchers. In fact, studies performed by Zukhri and Omar[105] and Hassi metal. [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.

The real-world datasets broadly introduced to NSAP and some real-world NSAP from various institutions are presented in Table 14. The studies present various measurements and practical constraints.

Table 15 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.

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 Thmeans 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 Table 16).

Some real-life datasets that have been broadly introduced to SAP are presented in Table 17.

Varying solution approaches have been proposed in the academic literature (see Table 18), 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 instances

Meanwhile, Burke et al. [123] presented multiobjective hyper-heuristic approaches to solve SAP. A tabu search hyperheuristic 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 Cmeans algorithm, Yadav and Ahmed [110] proposed Subtractive Clustering Technique (SCT),Hassimetal. [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.

Conflicts of Interest

The authors declare that there are no conflicts of interest regarding the publication of this paper.


The work reported in this paper was supported by the Ministry of Higher Education of Malaysia under the Exploratory Research Grant Scheme, S/O code 12826, and Universiti Utara Malaysia (UUM) under the University Grant S/O code 13415.

The authors are grateful and would like to thank UUM for the financial support received during the research period that had enabled to produce this piece of work.


[1] H. Basirzadeh, "Ones assignment method for solving assignment problems," Applied Mathematical Sciences, vol. 6, no. 4548, pp. 2345-2355, 2012.

[2] S. Singh, "A Comparative Analysis of Assignment Problem," IOSR Journal Of Engineering, vol. 2, no. 8, pp. 1-15, 2012.

[3] E. Ilela, "Assignment Problems," in Handbook of Applied Optimization, Part II-Applications, vol. 6, pp. 667-678, 2002.

[4] R. Qu, E. K. Burke, B. McCollum, L. T. G. Merlot, and S. Y. Lee, "A survey of search methodologies and automated system development for examination timetabling," Journal of Scheduling, vol. 12, no. 1, pp. 55-89, 2009.

[5] M. Ayob, S. Abdullah, and A. M. A. Malik, "A practical examination timetabling problem at the Universiti Kebangsaan Malaysia," International Journal of Computer Science and Network Security, vol. 7, no. 9, pp. 198-204, 2007.

[6] M. Caramia, P. Dell'Olmo, and G. F. Italiano, "Novel local-search-based approaches to university examination timetabling," INFORMS Journal on Computing, vol. 20, no. 1, pp. 86-99, 2008.

[7] E. Ersoy, E. Ozcan, and A. S. Uyar, "Memetic algorithms and hyperhill-climbers," in Proceedings of the 3rd Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA07), pp. 159-166, 2007

[8] H. Turabieh and S. Abdullah, "An integrated hybrid approach to the examination timetabling problem," Omega, vol. 39, no. 6, pp. 598-607, 2011.

[9] R. E. Burkard, "Selected topics on assignment problems," Discrete Applied Mathematics: The Journal of Combinatorial Algorithms, Informatics and Computational Sciences, vol. 123, no. 1-3, pp. 257-302, 2002.

[10] A. Ergul, "GA-Based examination scheduling experience at middle east technical university," Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Preface, vol. 1153, pp. 212-226, 1996.

[11] R. Marti, G. Reinelt, and A. Duarte, "A benchmark library and a comparison of heuristic methods for the linear ordering problem," Computational Optimization and Applications, vol. 51, no. 3, pp. 1297-1317, 2012.

[12] Z. Lu and J.-K. Hao, "Solving the course timetabling problem with a hybrid heuristic algorithm," Lecture Notes in Computer Science (including sub series Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Preface, vol. 5253, pp. 262-273, 2008.

[13] A. Wren, "Scheduling, timetabling and rostering - A special relationship?" Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Preface, vol. 1153, pp. 46-75,1996.

[14] E. Burke, D. de Werra, and J. Kingston, Handbook of graph theory, Chapter Applications to timetabling, Chapman and Hall/CRC, 2004.

[15] M. W Carter and G. Laporte, "Recent developments in practical examination timetabling," Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Preface, vol. 1153, pp. 3-21, 1996.

[16] S. Even, A. Itai, and A. Shamir, "On the complexity of timetable and multicommodity flow problems," SIAM Journal on Computing, vol. 5, no. 4, pp. 691-703,1976.

[17] B. McCollum, "A perspective on bridging the gap between theory and practice in university timetabling," in Practice and Theory of Automated Timetabling VI, vol. 3867, pp. 3-23, Springer, Berlin, Germany, 2007.

[18] E. Burke, D. Elliman, P. Ford, and R. Weare, "Examination timetabling in British universities: A survey," Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Preface, vol. 1153, pp. 76-90, 1996.

[19] L. T Merlot, N. Boland, B. D. Hughes, and P. J. Stuckey, "A Hybrid Algorithm for the Examination Timetabling Problem," in Practice and Theory of Automated Timetabling IV, vol. 2740 of Lecture Notes in Computer Science, pp. 207-231, Springer, Berlin, Germany, 2003.

[20] T Wong, P. Cote, and P. Gely, "Final exam timetabling: a practical approach," in Proceedings of the IEEE CCECE2002. Canadian Conference on Electrical and Computer Engineering. Conference Proceedings, vol. 2, pp. 726-731, 2002.

[21] G. Kendall and N. M. Hussin, "A tabu search hyper-heuristic approach to the examination timetabling problem at the MARA university of technology," in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Preface, vol. 3616 of LNCS, pp. 270-293, 2005.

[22] M. Tounsi, "A heuristic-based technique for university resource allocation problems," in Proceedings of the 2006 IEEE GCC Conference, GCC 2006, Bahrain, March 2006.

[23] M. N. M. Kahar and G. Kendall, "The examination timetabling problem at Universiti Malaysia Pahang: comparison of a constructive heuristic with an existing software solution," European Journal of Operational Research, vol. 207, no. 2, pp. 557-565, 2010.

[24] O. Yong and C. Yi, "Research on automated timetabling algorithm for make-up examination and final clear examination," in Proceedings of the 5th International Conference on Computer Science and Education, ICCSE 2010, pp. 570-573, chn, August 2010.

[25] S. Innet, "A noval approach of genetic algorithm for solving examination timetabling problems: A case study of Thai Universities," in Proceedings of the 13th International Symposium on Communications and Information Technologies: Communication and Information Technology for New Life Style Beyond the Cloud, ISCIT 2013, pp. 233-237, tha, September 2013.

[26] S. Abdul-Rahman, N. S. Sobri, M. F. Omar, A. M. Benjamin, and R. Ramli, "Graph coloring heuristics for solving examination timetabling problem at Universiti Utara Malaysia," in Proceedings of the 3rd International Conference on Quantitative Sciences and Its Applications: Fostering Innovation, Streamlining Development, ICOQSIA 2014, pp. 491-496, mys, August 2014.

[27] M. W. Carter, G. Laporte, and S. Y. Lee, "Examination timetabling: Algorithmic strategies and applications," Journal of the Operational Research Society, vol. 47, no. 3, pp. 373-383,1996.

[28] E. K. Burke, J. R. Newall, and R. E. Weare, "A memetic algorithm for university exam timetabling," Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Preface, vol. 1153, pp. 241-250, 1996.

[29] B. McCollum, A. Schaerf, B. Paechter et al., "Setting the research agenda in automated timetabling: The second international timetabling competition," INFORMS Journal on Computing, vol. 22, no. 1, pp. 120-130, 2010.

[30] R. Qu, F. He, and E. K. Burke, "Hybridizing Integer Programming Models with an Adaptive Decomposition Approach for Exam Timetabling Problems," in Proceedings of the 4th Multidisciplinary International Scheduling: Theory and Applications, pp. 435-446, 2009.

[31] G. Woumans, L. De Boeck, J. Belien, and S. Creemers, "A column generation approach for solving the examination-timetabling problem," European Journal of Operational Research, vol. 253, no. 1, pp. 178-194, 2016.

[32] E. K. Burke and J. P. Newall, "Solving examination timetabling problems through adaption of heuristic orderings," Annals of Operations Research, vol. 129, pp. 107-134, 2004.

[33] S. Abdul Rahman, A. Bargiela, E. K. Burke, E. Ozcan, B. McCollum, and P. McMullan, "Adaptive linear combination of heuristic orderings in constructing examination timetables," European Journal of Operational Research, vol. 232, no. 2, pp. 287-297, 2014.

[34] S. Abdul-Rahman, S. S. S. Abdullah, and A. M. Benjamin, "A nonlinear heuristic modifier for constructing examination timetable," Journal ofTheoretical and Applied Information Technology, vol. 95, no. 20, pp. 5642-5653, 2017

[35] S. Abdul-Rahman, A. M. Benjamin, M. F. Omar, R. Ramli, K.-R. Ku-Mahamud, and W. K. Abduljabbar, "Designing and implementation a web-based architecture for an examination timetabling system," Journal of Engineering and Applied Sciences, vol. 12, no. 23, pp. 7299-7305, 2017

[36] S. Abdul-Rahman, E. K. Burke, A. Bargiela, B. McCollum, and E. Ozcan, "A constructive approach to examination timetabling based on adaptive decomposition and ordering," Annals of Operations Research, vol. 218, no. 1, pp. 3-21, 2014.

[37] M. N. M. Kahar and G. Kendall, "A great deluge algorithm for a real-world examination timetabling problem," Journal of the Operational Research Society, vol. 66, no. 1, pp. 116-133, 2015.

[38] E. K. Burke, G. Kendall, M. Misir, and E. Ozcan, "Monte Carlo hyper-heuristics for examination timetabling," Annals of Operations Research, vol. 196, pp. 73-90, 2012.

[39] N. R. Sabar, M. Ayob, R. Qu, and G. Kendall, "A graph coloring constructive hyper-heuristic for examination timetabling problems," Applied Intelligence, vol. 37, no. 1, pp. 1-11, 2012.

[40] A. Muklason, A. J. Parkes, E. Ozcan, B. McCollum, and P. McMullan, "Fairness in examination timetabling: Student preferences and extended formulations," Applied Soft Computing, vol. 55, pp. 302-318, 2017.

[41] N. R. Sabar, M. Ayob, and G. Kendall, "Tabu exponential montecarlo with counter heuristic for examination timetabling," in Proceedings of the 2009 IEEE Symposium on Computational Intelligence in Scheduling, CI-Sched 2009, pp. 90-94, USA, April 2009.

[42] P. Amaral and T C. Pais, "Compromise ratio with weighting functions in a tabu search multi-criteria approach to examination timetabling," Computers & Operations Research, vol. 72, pp. 160-174, 2016.

[43] S. Abdul-Rahman, A. Bargiela, E. K. Burke, and B. Mccollum, "Investigation of Multistage Approaches to Examination Timetabling," in Proceedings of the 6th Multidisciplinary International Conference on Scheduling?: Theory and Applications (MISTA), pp. 528-542, 2013.

[44] N. Pillay and W. Banzhaf, "An informed genetic algorithm for the examination timetabling problem," Applied Soft Computing, vol. 10, no. 2, pp. 457-467, 2010.

[45] R. Qu, N. Pham, R. Bai, and G. Kendall, "Hybridising heuristics within an estimation distribution algorithm for examination timetabling," Applied Intelligence, vol. 42, no. 4, pp. 679-693, 2015.

[46] J. Rankhambe and S. Kavita, "Optimization of Examination Timetable Using Harmony Search Hyper-Heuristics (HSHH," International Journal of Computer Science and Information Technologies, vol. 5, no. 5, pp. 6719-6723, 2014.

[47] M. Alzaqebah and S. Abdullah, "Hybrid bee colony optimization for examination timetabling problems," Computers & Operations Research, vol. 54, pp. 142-154, 2015.

[48] M. Ayob and G. Kendall, "A Monte Carlo Hyper-Heuristic To Optimise Component Placement Sequencing For Multi Head Placement Machine," in Proceedings of the in International Conference on Intelligent Technologies, pp. 132-141, 2003.

[49] S. Abdul-Rahman, Search methodologies for examination timetabling [Ph.D. thesis], University of Nottingham, 2010.

[50] P. Cote, T Wong, and R. Sabourin, "A Hybrid Multi-objective Evolutionary Algorithm for the Uncapacitated Exam Proximity Problem," in Practice and Theory of Automated Timetabling V, vol. 3616 of Lecture Notes in Computer Science, pp. 294-312, Springer, Berlin, Germany, 2005.

[51] J. H. Obit, Developing Novel Meta-Heuristic, Hyper-Heuristic and Cooperative Search for Course Timetabling Problems, University of Nottingham, 2010.

[52] A. Schaerf, "A survey of automated timetabling," Artificial Intelligence Review, vol. 13, no. 2, pp. 87-127,1999.

[53] K. Socha, J. Knowles, and M. Sampels, "A MAX-MIN ant system for the university course timetabling problem," in Proceedings of ANTS, pp. 1-13, 2002.

[54] A. Gunawan, K. M. Ng, and K. L. Poh, "Solving the Teacher Assignment-Course Scheduling Problem by a Hybrid Algorithm," vol. 1, pp. 136-141, 2007.

[55] V. O. Oladokun and S. O. Badmus, "An Integer Linear Programming Model of a University Course Timetabling," The Pacific Journal of Science and Technology, vol. 9, no. 2, pp. 426-431, 2008.

[56] K. Thongsanit, "Solving the Course-Classroom Assignment Problem for a University," Silpakorn University Science and Technology Journal, vol. 8, no. 1, pp. 46-52, 2014.

[57] R. Borchani, A. Elloumi, and M. Masmoudi, "Variable neighborhood descent search based algorithms for course timetabling problem: application to a Tunisian university," in Electronic Notes in Discrete Mathematics, vol. 58, pp. 119-126, Elsevier Sci. B. V., Amsterdam, Netherlands, 2017.

[58] I. Mendez-Diaz, P. Zabala, and J.. Miranda-Bront, "An ILP based heuristic for a generalization of the post-enrollment course timetabling problem," Computers & Operations Research, vol. 76, pp. 195-207, 2016.

[59] J. Wahid and N. M. Hussin, "Hybrid harmony search with great deluge for UUM CAS curriculum based course timetabling," Journal of Telecommunication, Electronic and Computer Engineering, vol. 9, no. 1-2, pp. 33-38, 2017

[60] H. Vermuyten, S. Lemmens, I. Marques, and J. Belien, "Developing compact course timetables with optimized student flows," European Journal of Operational Research, vol. 251, no. 2, pp. 651-661, 2016.

[61] S. Ceschia, L. Di Gaspero, and A. Schaerf, "Design, engineering, and experimental analysis of a simulated annealing approach to the post-enrolment course timetabling problem," Computers & Operations Research, vol. 39, no. 7, pp. 1615-1624, 2012.

[62] J. A. Soria-Alcaraz, G. Ochoa, J. Swan, M. Carpio, H. Puga, and E. K. Burke, "Effective learning hyper-heuristics for the course timetabling problem," European Journal of Operational Research, vol. 238, no. 1, pp. 77-86, 2014.

[63] R. Lewis and J. Thompson, "Analysing the effects of solution space connectivity with an effective metaheuristic for the course timetabling problem," European Journal of Operational Research, vol. 240, no. 3, pp. 637-648, 2015.

[64] Y. Nagata, "Random partial neighborhood search for the post-enrollment course timetabling problem," Computers & Operations Research, vol. 90, pp. 84-96, 2018.

[65] S. L. Goh, G. Kendall, and N. R. Sabar, "Improved local search approaches to solve the post enrolment course timetabling problem," European Journal of Operational Research, vol. 261, no. 1, pp. 17-29, 2017.

[66] J. H. Obit, D. Landa-Silva, M. Sevaux, and D. Ouelhadj, "Nonlinear great deluge with reinforcement learning for university course timetabling," in Metaheuristics: intelligent decision making, vol. 50 of Operations research/computer science interfaces series, p. 19, Springer, New York, NY, USA, 2011.

[67] C. Nothegger, A. Mayer, A. Chwatal, and G. R. Raidl, "Solving the post enrolment course timetabling problem by ant colony optimization," Annals of Operations Research, vol. 194, pp. 325-339, 2012.

[68] K. Song, S. Kim, M. Park, and H.-S. Lee, "Energy efficiency-based course timetabling for university buildings," Energy, vol. 139, pp. 394-405, 2017

[69] R. P. Badoni, D. K. Gupta, and P. Mishra, "A new hybrid algorithm for university course timetabling problem using events based on groupings of students," Computers & Industrial Engineering, vol. 78, pp. 12-25, 2014.

[70] A. L. Bolaji, A. T. Khader, M. A. Al-Betar, and M. A. Awadallah, "University course timetabling using hybridized artificial bee colony with hill climbing optimizer," Journal of Computational Science, vol. 5, no. 5, pp. 809-818, 2014.

[71] G. Ghiani, E. Manni, and A. Romano, "Training offer selection and course timetabling for remedial education," Computers & Industrial Engineering, vol. 111, pp. 282-288, 2017.

[72] C. Akkan and A. Gulcu, "A bi-criteria hybrid genetic algorithm with robustness objective for the course timetabling problem," Computers & Operations Research, vol. 90, pp. 22-32, 2018.

[73] A. Cerdeira-Pena, L. Carpente, A. Farina, and D. Seco, "New approaches for the school timetabling problem," in Proceedings of the 7th Mexican International Conference on Artificial Intelligence, MICAI2008, pp. 261-267, mex, October 2008.

[74] N. Pillay, "A survey of school timetabling research," Annals of Operations Research, vol. 218, pp. 261-293, 2014.

[75] M. W. Carter and C. A. Tovey, "When Is the Classroom Assignment Problem Hard?" Operations Research, vol. 40, no. 1supplement-1, pp. S28-S39,1992.

[76] T. B. Cooper and J. H. Kingston, "Solution of real instances of the timetabling problem," The Computer Journal, vol. 36, no. 7, pp. 645-653, 1993.

[77] H. M. M. Ten Eikelder and R. J. Willemen, "Some complexity aspects of secondary school timetabling problems," Complexity, vol. 2079, pp. 18-27, 2001.

[78] H. G. Santos, E. Uchoa, L.. Ochi, and N. Maculan, "Strong bounds with cut and column generation for class-teacher timetabling," Annals of Operations Research, vol. 194, pp. 399-412, 2012.

[79] G. N. Beligiannis, C. N. Moschopoulos, G. P. Kaperonis, and S. D. Likothanassis, "Applying evolutionary computation to the school timetabling problem: The Greek case," Computers & Operations Research, vol. 35, no. 4, pp. 1265-1280, 2008.

[80] K. A. Smith, D. Abramson, and D. Duke, "Hopfield neural networks for timetabling: Formulations, methods, and comparative results," Computers & Industrial Engineering, vol. 44, no. 2, pp. 283-305, 2003.

[81] G. Post, J. H. Kingston, S. Ahmadi et al., "XHSTT: an XML archive for high school timetabling problems in different countries," Annals of Operations Research, vol. 218, pp. 295-301, 2014.

[82] N. Boland, B. D. Hughes, L. T G. Merlot, and P. J. Stuckey, "New integer linear programming approaches for course timetabling," Computers & Operations Research, vol. 35, no. 7, pp. 2209-2233, 2008.

[83] T Birbas, S. Daskalaki, and E. Housos, "School timetabling for quality student and teacher schedules," Journal of Scheduling, vol. 12, no. 2, pp. 177-197, 2009.

[84] S. Ribic and S. Konjicija, "A two phase integer linear programming approach to solving the school timetable problem," in Proceedings of the 32nd International Conference on Information Technology Interfaces, ITI 2010, pp. 651-656, hrv, June 2010.

[85] A. V. Moura and R. A. Scaraficci, "A GRASP strategy for a more constrained School Timetabling Problem," International Journal of Operational Research, vol. 7, no. 2, pp. 152-170, 2010.

[86] K. N. T T Minh, N. D. T Thanh, K. T Trang, and N. T T Hue, "Using tabu search for solving a high school timetabling problem," Studies in Computational Intelligence, vol. 283, pp. 305-313, 2010.

[87] N. Pillay, "A study into the use of hyper-heuristics to solve the school timetabling problem," in Proceedings of the the 2010 Annual Research Conference of the South African Institute of Computer Scientists and Information Technologists, pp. 258-264, Bela Bela, South Africa, October 2010.

[88] L. N. Ahmed, E. Ozcan, and A. Kheiri, "Solving high school timetabling problems worldwide using selection hyper-heuristics," Expert Systems with Applications, vol. 42, no. 13, pp. 54635471, 2015.

[89] D. Zhang, Y. Liu, R. M'Hallah, and S. C. H. Leung, "A simulated annealing with a new neighborhood structure based algorithm for high school timetabling problems," European Journal of Operational Research, vol. 203, no. 3, pp. 550-558, 2010.

[90] I. X. Tassopoulos and G. N. Beligiannis, "Solving effectively the school timetabling problem usingparticle swarm optimization," Expert Systems with Applications, vol. 39, no. 5, pp. 6029-6040, 2012.

[91] L. Yongkai, Z. Defu, and S. C. H. Leung, "A simulated annealing algorithm with a new neighborhood structure for the timetabling problem," in Proceedings of the 1st ACM/SIGEVO Summit on Genetic and Evolutionary Computation - GEC '09, pp. 381-386, June 2009.

[92] M. P. Carrasco and M. V. Pato, "A comparison of discrete and continuous neural network approaches to solve the class/ teacher timetabling problem," European Journal of Operational Research, vol. 153, no. 1, pp. 65-79, 2004.

[93] C. Y. Teo and D. J. Ho, "A systematic approach to the implementation of final year project in an electrical engineering undergraduate course," IEEE Transactions on Education, vol. 41, no. 1, pp. 25-30, 1998.

[94] D. J. Abraham, R. W. Irving, and D. F. Man love, "Two algorithms for the Student-Project Allocation problem," Journal of Discrete Algorithms, vol. 5, no. 1, pp. 73-90, 2007

[95] D. F. Manlove and G. O'Malley, "Student-project allocation with preferences over projects," Journal of Discrete Algorithms, vol. 6, no. 4, pp. 553-560, 2008.

[96] A. H. Abu El-Atta and M. I. Moussa, "Student project allocation with preference lists over (student, project) pairs," in Proceedings of the International Conference on Computer and Electrical Engineering, ICCEE 2009, pp. 375-379, UAE, December 2009.

[97] A. A. Anwar and A. S. Bahaj, "Student project allocation using integer programming," IEEE Transactions on Education, vol. 46, no. 3, pp. 359-367, 2003.

[98] R. Ramli and E. M. N. E. A. Bakar, "The Assignment of Projects to Students Using 0-1 Integer Programming," in Operational Research and Its Applications: Research Trends (APORS 2003), vol. 2, New Delhi, 2003.

[99] P. R. Harper, V De Senna, I. T. Vieira, and A. K. Shahani, "A genetic algorithm for the project assignment problem," Computers & Operations Research, vol. 32, no. 5, pp. 1255-1265,2005.

[100] S. Ghazali and S. Abdul-Rahman, "Simulated annealing algorithm for solving chambering student-case assignment problem," in Proceedings of the AIP Conference Proceedings, vol. 1691, pp. 1-5, 2015.

[101] J. Dye, A constraint logic programming approach to the stable marriage problem and its application to student-project allocation, University of York, York, UK, 2001.

[102] P. Li, C. K. C. Sydney, H. Guangyue, and Z. H. Joshua, "Multicriteria Student Project Allocation: A Case Study of Goal Programming Formulation with DSS Implementation," in Proceedings of the 8th International Symposium on Operations Research and Its Applications (ISORA'09), pp. 75-82, Zhangjiajie, China, 2016.

[103] R. Calvo-Serrano, G. Guillen-Gosalbez, S. Kohn, and A. Masters, "Mathematical programming approach for optimally allocating students' projects to academics in large cohorts," Education for Chemical Engineers, vol. 20, pp. 11-21, 2017

[104] K. Iwama, S. Miyazaki, and H. Yanagisawa, "Improved approximation bounds for the student-project allocation problem with preferences over projects," Journal of Discrete Algorithms, vol. 13, pp. 59-66, 2012.

[105] Z. Zukhri and K. Omar, "Solving New Student Allocation Problem with Genetic Algorithms: A Hard Problem for Partition Based Approach," International Journal of Soft Computing Applications, vol. 3, no. 3, pp. 6-15, 2008.

[106] W. H. W. Hassim, A. S. Shibghatullah, and F. Shahbodin, "Solving New Student Allocation Problem (NSAP) With Analytical Hierarchy Process (AHP)," in Proceedings of the International Symposium on Research in Innovation and Sustainability 2014 (ISoRIS '14), pp. 1659-1662, Malacca, Malaysia, October 2014.

[107] A. Rad, B. Naderi, and M. Soltani, "Clustering and ranking university majors using data mining and AHP algorithms: A case study in Iran," Expert Systems with Applications, vol. 38, no. 1, pp. 755-763, 2011.

[108] Y. Ma, B. Liu, C. K. Wong, P. S. Yu, and S. M. Lee, "Targeting the right students using data mining," in Proceeding of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 457-464, 2000.

[109] S. Susanto, I. Suharto, and P. Sukapto, "Using the fuzzy clustering algorithm for the allocation of students," World Transactions on Engineering and Technology Education (UICEE), vol. 1, no. 2, pp. 245-248, 2002.

[110] R. S. Yadav and P. Ahmed, "Modeling Academic Performance Evaluation using Fuzzy C-Means Clustering Techniques," International Journal of Computer Science And Technology, vol. 4, no. 1, 2013.

[111] R. S. Yadav, "Implementation of Data Mining Techniques to Classify New Students into Their Classes?: A Bayesian Approach," International Journal of Computer Applications, vol. 85, no. 11, pp. 16-19, 2014.

[112] F. O. Frimpong and A. Owusu, "Allocation of Classroom Space Using Linear Programming (A Case Study: Premier Nurses Training College, Kumasi)," Journal of Economics and Sustainable Development, vol. 6, no. 2, pp. 12-20, 2015.

[113] A. A. Constantino, W. M. Filho, and D. Landa-Silva, "Iterated heuristic algorithms for the classroom assignment problem," in Proceedings of the 8th International Conference on the Practice and Theory of Automated Timetabling, PATAT 2010, pp. 152-166, August 2010.

[114] N. F. Bagger, J. Larsen, and T. J. R. Stidsen, "Room Allocation Optimisation at the Technical University of Denmark Room Allocation Optimisation at the Technical University of Denmark," in Proceedings of the 10th International Conference of the Practice and Theory of Automated Timetabling, pp. 454-458, 2014.

[115] S. Navuduri, Design and Implementation of a Classroom Allocation System Prototype, A&M University-Corpus Christi, 2016.

[116] K. Gosselin and M. Truchon, "Allocation of classrooms by linear programming," Journal ofthe Operational Research Society, vol. 37, no. 6, pp. 561-569,1986.

[117] E. Burke, P Cowling, and J. Landa Silva, "Hybrid population-based metaheuristic approaches for the space allocation problem," in Proceedings ofthe Congress on Evolutionary Computation, Vols 1 and 2, pp. 232-239, Seoul, South Korea.

[118] C. Beyrouthy, E. K. Burke, D. Landa-Silva, B. McCollum, P McMullan, and A. J. Parkes, "The teaching space allocation problem with splitting," Practice and Theory of Automated Timetabling Vi, vol. 3867, pp. 228-247, 2007.

[119] C. Beyrouthy, E. K. Burke, D. Landa-Silva, B. McCollum, P McMullan, and A. J. Parkes, "Towards improving the utilization of university teaching space," Journal of the Operational Research Society, vol. 60, no. 1, pp. 130-143, 2009.

[120] Adewumi. and M. M. Ali, "A Hierarchical Heuristic Strategy for Hostel Space Allocation Problem," 2010.

[121] A. E. Phillips, H. Waterer, M. Ehrgott, and D. M. Ryan, "Integer programming methods for large-scale practical classroom assignment problems," Computers & Operations Research, vol. 53, pp. 42-53, 2015.

[122] S. Abdullah, H. M. Ali, I. Sipan et al., "Classroom Management: Measuring Space Usage," Procedia-Social and Behavioral Sciences, vol. 65, pp. 931-936, 2012.

[123] E. K. Burke, J. D. L. Silva, and E. Soubeiga, "Multi-Objective Hyper-Heuristic approaches for space allocation and timetabling," in Metaheuristics: Progress as Real Problem Solvers, pp. 129-158, 2005.

[124] J. Landa-Silva Dario, "Metaheuristic and Multiobjective Approaches for Space Allocation," 2003.

[125] E. K. Burke and D. B. Varley, "Space Allocation?: An Analysis of Higher Education Requirements," in Proceedings ofthe International Conference on the Practice and Theory of Automated Timetabling (PATAT), pp. 20-33,1997

[126] S. Abdul-Rahman, A. Bargiela, E. K. Burke, E. Ozcan, and B. McCollum, "Construction of examination timetables based on ordering heuristics," in Proceedings of the 24th International Symposium on Computer and Information Sciences (ISCIS 2009), pp. 727-732, 2009.

Syakinah Faudzi, (1) Syariza Abdul-Rahman, (2) and Rosshairy Abd Rahman (1)

(1) Decision Science Department, School of Quantitative Sciences, College of Arts and Sciences, Universiti Utara Malaysia, Malaysia

(2) Institute of Strategic Industrial Decision Modeling (ISIDM), School of Quantitative Sciences, College of Arts and Sciences, Universiti Utara Malaysia, Malaysia

Correspondence should be addressed to Syariza Abdul-Rahman;

Received 11 November 2017; Accepted 18 March 2018; Published 17 May 2018

Academic Editor: Yi-Kuei Lin
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

                            (iv) Examinations with large enrolment
                            size should be scheduled as early as

                            (v) Examinations with limited enrolment
                            should be scheduled into a particular

                            (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.

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

Ergul [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 Malaysia

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        Ayob et al. [5];
                       heuristics             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          Hill climbing          Caramia et al. [6]

Local search based     Tabu search            Sabar et al. [41];
                                              Amaral and Pais [42]

                       Variable               Abdul-Rahman et al.
                       neighbourhood search   [43]

                       Great Deluge           Kahar and Kendall [23]

Population search      Memetic algorithm      Ersoy et al. [7]

                       Genetic algorithm      Pillay and Banzhaf
                                              [44]; Innet [25]

                       Great Deluge +         Turabieh and
                       electromagnetic-       Abdullah [8]
                       like mechanism

Hybrid                 Hyper-heuristics +     Qu et al. [45]

                       Harmony search         Rankhambe and Kavita
                       hyper-heuristics       [46]

                       Bee colony             Alzaqebah and
                       optimization + late    Abdullah [47]
                       acceptance hill
                       climbing + simulated

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

                            (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

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.

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
Mendez-Diaz et al. [58]     A private university in Buenos Aires,
Wahid and Hussin [59]       Universiti Utara Malaysia

Table 6: Summary of studies related to CTP.

                       Approach               Reference (s)

Exact method           Integer linear         Oladokun and Badmus
                       programming            [55]; Thongsanit

                       Decomposition          Vermuyten et al. [60]

Heuristic technique    Integer linear         Mendez-Diaz et al.
                       programming based      [58]

Metaheuristic          Simulated annealing    Ceschia et al. [61]

                       Hyper-heuristics       Soria-Alcaraz et al.
                       iterated local         [62]

                       Two stage              Lewis and Thompson
                       metaheuristics         [63]

Local search based     Local search-based     Nagata [64]
                       algorithm with
                       adaptive mechanism

                       Variable               Borchani et al. [57]
                       neighborhood descent

                       Tabu search with       Goh et al. [65]
                       sampling and
                       perturbation + SA
                       with reheating

                       Nonlinear great        Obit et al. [66]
                       deluge hyper-
                       heuristics with

Population search      Ant colony             Nothegger et al. [67]
based                  optimisation

                       Genetic algorithm      Song et al. [68]

Hybrid                 Integer programming    Gunawan et al. [54]
                       + greedy heuristics
                       + modified simulated

                       Genetic algorithm +    Badoni et al. [69]
                       local search

                       Artificial bee         Bolaji et al. [70]
                       colony algorithm +
                       hill climbing

                       Integer programming    Ghiani et al. [71]
                       + greedy heuristics

                       Hybrid multi-          Akkan and Guldi [72]
                       objective genetic
                       algorithm + hill
                       climbing + simulated

                       Harmony search with    Wahid and Hussin [59]
                       great deluge

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

                            (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 of empty
                            periods 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

                            (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
                            with consecutiveness) 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 the soft version of the
                            mandatory unavailability constraint
                            (referring to teachers).

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

Ribic and Konjicija [84]    Croatian secondary school

Moura and Scaraficci [85]   Brazilian high school

Minh et al. [86]            Vietnam high schools

Table 9: Summary of studies related to STP.

                       Approach               Reference (s)

Exact method           Integer Linear         Boland et al. [82];
                       Programming            Birbas et al. [83];
                                              Ribic and Konjicija

                       Mixed Integer          Santos et al. [78]

Heuristic technique    Hyper-heuristics       Pillay [87]; Ahmed
                                              et al. [88]

Metaheuristic          Simulated annealing    Zhang et al. [89]

Local search based     Greedy Randomized      Moura and Scaraficci
                       Adaptive Search        [85]
                       Procedure (GRASP)

                       Tabu search            Minh et al. [86]

Population search      Evolutionary           Beligiannis et al.
based                  algorithm              [79]

                       Particle Swarm         Tassopoulos et al.
                       Optimization           [90]

Hybrid                 Random Non-            Cerdeira-Pena et al.
                       Ascendent Method       [73]
                       (RNA) + genetic

                       Simulated annealing    Yongkai et al. [91]
                       + Tabu search

Others                 Neural network         Smith et al. [80];
                                              Carrasco and Pato

Table 10: The hard and soft constraints related to SPAP

Constraint type        Descriptions           Reference (s)

Hard constraints       (i) Preference         Teo and Ho [93];
                       lists.                 Abraham et al. [94];
                                              Manlove and O'Malley
                                              [95]; Abu El-Atta
                                              and Moussa [96]
                                              Anwar and Bahaj
                                              [97]; Ramli and
                                              Bakar [98]; Harper
                                              et al. [99]; Abraham
                                              et al. [94]; Abu El-
                                              Atta and Moussa [96]

                       (ii) Capacity

                       (iii) Every student    Anwar and Bahaj [97]
                       must be allocated
                       one and only one

                       (iv) A project can     Anwar and Bahaj [97]
                       be allocated to at
                       most one student.

                       (v) Total number of    Ghazali and Abdul-
                       cases available must   Rahman [100]
                       not be more than the
                       total number of

                       (vi) Maximum number    Ghazali and Abdul-
                       of students in         Rahman [100]
                       handling a case.

                       (vii) Maximum number   Ghazali and Abdul-
                       of cases that can be   Rahman [100]
                       handled by certain

Soft constraints       (i) Assigning a        Ghazali and Abdul-
                       number of students     Rahman [100]
                       to many cases.

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    Internship students at Law Firm in
[100]                        Malaysia

Dye [101]                   University of York

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   Calvo-Serrano et al.
Metaheuristic          programming            [103]

Local search based     Simulated annealing    Ghazali and Abdul-
                                              Rahman [100]

Population search      Genetic algorithm      Harper et al. [99]

Hybrid                 0-1 integer            Ramli and Bakar [98]
                       programming + AHP

                       Constraint Logic       Dye [101]

Other techniques       Linear time            Abraham et al. [94]

                       Maximum stable         Abu El-Atta and
                       matching to            Moussa [96]
                       preferences over

                       Maximum stable         Manlove and O'Malley
                       matching to            [95]; Iwama et al.
                       preferences over       [104]

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.

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 Education

Table 15: Summary of studies related to NSAP problem.


Metaheuristic          Population search-     Genetic algorithm
technique              based

Hybrid                                        R-means algorithm +

Other techniques                              Data mining

                                              Fuzzy C-means

                                              Clustering Technique

                                              Analytical Hierarchy

                                              Bayesian approach

Approach               Reference (s)

Metaheuristic          Zukhri and Omar [105]

Hybrid                 Rad et al. [107]

Other techniques       Ma et al. [108]
                       Susanto [109]
                       Yadav and Ahmed [110]
                       Hassim et al. [106]
                       Yadav [111]

Table 16: The hard and soft constraints within the SAP.

Constraint type        Descriptions           Reference (s)

Hard constraints       (i) Classroom          Frimpong and Owusu
                       capacity.              [112]; Constantino
                                              [113]; Bagger et al.
                                              [114]; Navuduri

                       (ii) Room's            Gosselin and Truchon
                       availability at        [116]
                       different time of
                       the day and room

Soft constraints       (i) Events from the    Bagger et al. [114]
                       same course
                       occurring the same
                       day must be
                       allocated as close
                       to each other as
                       possible with
                       respect to their

                       (ii) If an event is
                       split into multiple
                       rooms, these must
                       also be as close to
                       each other as
                       possible in the
                       geographical sense

Table 17: Summary of real-world SAP from different institutions.

Reference                   Institution (s)

Burke et al. [117];         University ofNottingham, Nottingham Trent
Landa-Silva [11]            University and University of Wolverhampton

Beyrouthy et al. [118];     University in Sydney Australia
Beyrouthy et al. [119]

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 Malaysia

Table 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]


Local search based     Tabu search            Burke et al. [123]

                       Variable               Constantino [113]
                       neighbourhood search

Population search      Genetic algorithm      Adewumi and Ali [120]

                       Hill climbing + SA +   Burke et al. [117]
                       Tabu search + GA

                       Iterative              Landa-Silva Dario
                       improvement + SA +     [124]
                       Tabu search + GA)

Hybrid                 Hill climbing + SA     Beyrouthy et al. [118]

                       IP + SA                Beyrouthy et al. [119]

                       Mixed Integer          Bagger et al. [114]
                       Program (MIP) + C#

Other techniques       MS EXCEL + SPSS        Abdullah et al. [122]

                       Web-based system       Navuduri [115]
COPYRIGHT 2018 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2018 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Faudzi, Syakinah; Abdul-Rahman, Syariza; Rahman, Rosshairy Abd
Publication:Advances in Operations Research
Article Type:Report
Geographic Code:7IRAN
Date:Jan 1, 2018
Previous Article:Multiobjective Optimization for Multimode Transportation Problems.
Next Article:Multicriteria Evaluation of Urban Regeneration Processes: An Application of PROMETHEE Method in Northern Italy.

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters