1 Introduction

Timetabling is one of the most important administrative activities that is required in all academic institutions. There has been a collection of perceptive contributions to the scientific literature both in terms of theoretical problems and practical aspects. Timetabling problems are involved in different areas such that educational timetabling (Burke et al. 2004), nurse scheduling (Burke et al. 2004), sports timetabling (Easton et al. 2004), transportation timetabling Leake (1996) and other specific assignment tasks like paper-reviewer assignment problem (Kolasa and Krol 2011). Researchers in both Operational Research and Artificial Intelligence have notably considered timetabling problems since 1960s; and in these recent years they have attained an improved level of research activity. Qu et al. (2009) provided a definition of general timetabling as follows: “A timetabling problem is composed of 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 times and resources to the meetings so as to satisfy the constraints as far as possible.”

Educational timetabling is one of the most studied timetabling problems. This task is important and time-consuming which arises periodically in all academic institutions. A wide variety of educational timetabling incorporates school timetabling, university course and examination timetabling, faculty timetabling and classroom assignment. Course and examination timetabling are comparatively close problems (Simonis 1995) but with important differences (Mehta 1982).

This survey focuses on examination timetabling. A number of surveys and papers have been published since 1986 (Carter and Laporte 1996; Carter 1986; Qu et al. 2009) to solve this type of problem using different artificial intelligence techniques. This study concentrates on the research that has appeared in the last decade and concerns the Particle Swarm Optimization techniques.

The paper is organized as follows: Sect. 2 defines the examination timetabling problem including a number of well-known hard and soft constraints, in addition to the definition of the conflict matrix and the fitness functions. Section 3 illustrates some related surveys. Section 4 discusses the concept of PSO. Section 5 itemizes numerous PSO methods published in the last ten years. And finally Sect. 6 exposes some conclusions and future research directions and opens issues in examination timetabling research.

2 Examination Timetabling Problem

The definition of Examination Timetabling Problems (ETP) can be presented as an assignment of a set of examinations into a limited number of ordered timeslots (time periods) and rooms of certain capacity subject to a set of constraints.

2.1 Problem constraints

The ETP can be composed of a large number of constraints and some of which contradict another. These constraints are usually categorized into two types: hard constraints and soft constraints. It is crucial that some constraints must be satisfied. Such constraints are called hard constraints. These constraints must be enforced in the solution (obtained timetable) to make it feasible. Several ETP articles found that the constraints diverge broadly from institution to institution. The main hard constraints come across in ETP are:

  1. 1.

    One student cannot have two examinations in the same time. This constraint is known as conflicting constraint.

  2. 2.

    The number of students taking an examination should not exceed the capacity of the rooms.

  3. 3.

    Each course that requires an examination must be scheduled.

  4. 4.

    Each examination should be assigned to one room in its timeslot.

Soft constraints are those that are considered desirable. However, these constraints are usually either difficult or not fully attainable. It is typically impossible to find feasible solutions that satisfy all the soft constraints. Soft constraints also differ from one institution to another in terms of both the types and their importance (Burke et al. 1996). The most common soft constraints covered in the examination timetabling (Burke et al. 1996) are:

  1. 1.

    Plan spare time between two consecutive examinations scheduled in the same day.

  2. 2.

    The examinations in conflict should not be consecutively scheduled. This constraint is commonly considered in Toronto benchmark (Toronto website: http://www.asap.cs.nott.ac.uk/resources/data.shtml).

  3. 3.

    Plan all the important examinations as first as possible. This soft constraint may conflict with the previous one.

  4. 4.

    Students who have consecutive examinations on the similar day would be assigned to the same room.

  5. 5.

    Scheduling more than a fixed number of consecutive examinations for student is supposed to be avoided. This fixed number changes from institution to another.

2.2 Conflict matrix

Before addressing the fitness function, it is vital to introduce the conflict matrix. The conflict matrix is utilized in order to stand for the clashes between a couple of examinations. The rows and columns of the matrix represent examinations. The most common definitions of this matrix proposed in the literature are:

  • Each element of the matrix shows the number of students common for a pair of examinations.

  • Each element of the matrix is equal to 1 if both examinations are conflicting, 0 otherwise.

The density of the conflict matrix is calculated as the quotient between the number of examinations in conflict and the total number of examinations.

2.3 Fitness function

The quality of timetables is calculated by inspecting the number of satisfied constraints in the generated solutions. Due to the large multiplicity of problems presented and investigated, several objective functions have been proposed. Here, we list the mostly used in ETP.

  • The fitness function applied in Aftab and Li (2010) uses the penalty cost for particular constraint violation while taking into account both hard and soft constraints.

  • The fitness function used in Di Gaspero and Schaerf (2001) represents a penalty function that computes average value of violation in terms of each student. This function also takes into account both hard and soft constraints.

  • The fitness function used in Burke and Newall (2004), Carter and Laporte (1996) represents only one soft constraint that consists in spreading examinations as uniformly as possible throughout the timetable, subject to the unique conflicting constraint: no students should sit two examinations simultaneously.

3 Previous surveys of educational timetabling problems

Before starting to overview the different papers that deal with ETP using Particle Swarm Optimization, we outline a number of surveys that have appeared in the literature this last decade. Most of these surveys handle educational timetabling and so focus on examination timetabling.

Burke and Petrovic (2002) introduced overviews of study performed on university course and examination timetabling based on hybrid evolutionary algorithms, meta-heuristics, multi-criteria approaches, case-based reasoning techniques and adaptive approaches. They also presented sequential, clustering and constraint based techniques to solve this type of problem. They underlined some future directions on knowledge based systems and approaches in order to increase the quality of timetabling systems.

Burke et al. (2004) addressed graph-coloring methods applied to timetabling based on teacher, course, examination and sports. The authors specified the character of graph coloring approaches in timetabling problems for 40 years and their successful integration in different recent hybrid heuristic techniques.

McCollum (2007) dealt with several articles in course and examination timetabling in order to set a research schema to link between timetabling research and practice. McCollum recognized the development of timetables in institutions, and introduced different real world examination and course timetabling.

Schaerf and Di Gaspero (2007) drew some exceptionally motivating and significant concerns in timetabling research. They studied measurability and reproducibility in university course and examination timetabling. The authors addressed some practice cases that can involve to the improvement of both aspects.

Lewis (2008) achieved a summary of metaheuristic-based techniques for solving University Timetabling problem. The author highlighted various methods that have been proposed to handle the problem and distinguished between constraints of varying importance. The author also classified these methods into three general classes and gave some informative comments on each of these algorithms.

Qu et al. (2009) presented a significant discussion on examination timetabling methods appeared in the 10 years until 2009. The authors aimed to stress the new developments and essential research success that have been performed in that decade, in addition to a variety of significant research issues and challenges that have been generated by this study. The authors introduced diverse versions of problem datasets that have the same name and which generated a considerable confusion. They clarified the situation by renaming the commonly studied datasets to avoid future confusion.

Hosney and Shaameem (2011) illustrated some Genetic Algorithms (GA) techniques that have been newly performed with successful results to diverse variants of university timetabling problems. The authors presented some techniques focusing on the chromosome representation and the crossover and mutation operators.

4 Particle Swarm Optimization

Particle Swarm Optimization (PSO) is well-known optimization method invented in 1995 Kennedy and Eberhart (2005). It is an evolutionary computation method inspired by flocks of birds and shoals of fish.

PSO is considered such a multi-agent parallel search technique. Particles are intangible individual, which move through the multi-dimensional search space. Each particle has a position, a velocity and a best position reached so far. PSO uses a population called “swarm” where each particle represents a candidate solution.

The swarm is randomly initialized to search for optima using a specific fitness function (objective function). The search is performed through updating the velocity and the position of each particle over the generations. In fact, particles move through the N-dimensional problem search space by following the best particle of the swarm. At each iteration, the position of each particle is evaluated. Each particle can know its best position found so far, called Pbest, as well as the best position of the best particle in the swarm called Gbest. These steps, which consititute the PSO algorithm, are well shown in Fig. 1. The velocity and the position of each particle are updated according to Eqs. 1 and 2 respectively.

Let Eq. 1 be the following:

$$\begin{aligned} V_{ij} = w*V_{ij} + C1*rand( )*(Pbest_{ij} - X_{ij}) + C2*rand( )*(Gbest_{j} - X_{ij}) \end{aligned}$$
(1)

Where w is the inertia weight defined by the user. It is used to balance the search ability of PSO algorithm over global and local exploration and exploitation. C1 is the cognitive parameter and C2 is the social parameter, they are considered as the acceleration weight. rand( ) is a random number uniformly distributed in the interval [0, 1]. This equation contains the previous velocity of the particle, the collaborative effect parameters, the distance between the particle‘s current position \((X_{ij})\) and its own best historical position \((Pbest_{ij})\), and also the distance between the particle‘s current position and the position of global best particle \((Gbest_{j})\). Note that, \(X_{ij}\) is jth component of the spatial coordinate \(X_{i}\) of the ith particle. For more details about the parameters setting, the reader can refer to Berro et al. (2010).

Equation 2 calculates the new position of a particle i according to the current position \(X_{ij}\) and the current velocity \(V_{ij}\).

$$\begin{aligned} X_{ij} = X_{ij} + V_{ij} \end{aligned}$$
(2)
Fig. 1
figure 1

PSO algorithm

Full size image

PSO algorithm is very speed, simple and straightforward to implement. In addition, it has a very few parameters to adjust Kennedy and Eberhart (2005) and necessitates a little memory for computation. PSO can rapidly achieve fit particles (not constantly the best fit), but who are commonly good enough to be considered as solutions to problems. PSO generally performed well in a large number of hard combinatorial optimization problems, especially in continuous optimization (Sandeep Rana et al. 2011; Berro et al. 2010). In these recent years, PSO has confirmed more encouraging results in undertaking discrete optimization problems (Jordehi and Jasni 2015). The researchers are motivating to adopt suitable continuous PSO approaches to be applicable to discrete problems like scheduling and ETP. Furthermore, PSO does not depend greatly on the information associated with the fundamental problem, and it can be straightforwardly hybridized to produce a new version.

In the next section, we briefly describe some PSO techniques that have been used to solve ETP. This survey deals with selected papers that were published this last decade. We organize the papers chronologically (most recent last). For each paper, we describe the PSO technique used and give an idea about the experimental results of the approach.

5 Particle Swarm Optimization techniques

Fealko (2005) in his thesis explored the pertinence and the efficiency of PSO method applied to university Examination Timetabling Problem. This research work methodically investigated the impact of problem and algorithm factors in solving this specific timetabling problem and established the algorithm’s performance profile under the specified test environment. The author also provided insight about the performance of PSO compared with other algorithms used to handle the problem taking into account the same datasets. In addition, the author proposed a better way to produce examination timetabling datasets that are more representative of real world examination timetabling datasets. Finally, he suggested PSO-NoConflicts optimization approach to achieve searches while still fulfilling constraints.

Chu et al. (2006) addressed PSO in discrete domain to solve timetabling problem. The problem is to construct examination timetable using low-dimensional database. There were three days for the allocation of examinations which each day contained four timeslots. The authors considered the problem in terms of maximum number of examinations per student. They treated three cases: a student takes 11 examinations, 13 examinations and 15 examinations. The authors considered not only the conflicting hard constraint but also three soft constraints. To solve this problem, they proposed the self-mutation PSO method that consisted in including mutation operator to update position of the particles. The proposed method has not been compared with any existing methods. Experimental results showed that the proposed discrete PSO was an efficient method for solving this Examination Timetabling Problem.

Aftab et al. (2011) proposed PSO to manage the overall hyper-heuristic solving method. Hyper-heuristic consists of combining and/or generating different simple heuristics or part of them, in order to efficiently solve hard combinatorial problems. It is composed of a high-level method and a set of low-level heuristics. The high level method chooses a specific low-level heuristic to be applied at a specific time based on the current problem state. The problem addressed the real world examination scheduling dataset on Faculty of Information and Communication Tecnology (ICT) in BUITEMS, Quetta. It consists in assigning examinations to timeslots in addition to the assignment of invigilators and rooms to examinations while respecting the requirements of the departments. The authors defined four hard constraints and four soft constraints and used the fitness function proposed by Aftab and Li (2010). To solve this problem, the standard PSO is used. The initialization of each particle is done randomly. The PSO is utilized as top level heuristic to handle the performance quality of the complete mechanism. Each particle is partial solution and sequence of low-level heuristics. For the low level heuristic, they applied different simple heuristics. To experiment their results, the authors considered the real world dataset of Faculty of ICT. This dataset is composed of 16 rooms, 23 invigilators and 305 examinations where 15 examinations should be scheduled per day (there are five working days). They concluded that their approach was a highly effective method and found promising results.

Montero et al. (2011) presented a PSO algorithm to solve University timetabling Problem. The problem tackled is a university (the Chilean Technical University Federico Santa Maria UTFSM) course timetable and a dynamic examination timetable. The problem can be divided into two phases and summarized as follows. First, each department of the university communicates its course requirements for the semester and gives the timeslots required. Then, the problem consists in assigning a classroom to each course taking into consideration the associated facility and capacity constraints. The second phase consists in solving the dynamic problem. It is based on satisfying new requirements, as examinations, by just modifying the solution found in the first phase. In fact, each lecturer according to his course requirements independently programs examination. When a classroom is not available, some re-assignments are required in order to update the original course timetable. For the static problem (first phase), the authors have proposed a PSO-based algorithm applied in a discrete domain. The position for each particle uses a binary representation, where it is equal to 1 if a fixed classroom is being assigned to a fixed timeslot. Velocity uses a real-valued representation and varies between 0 and maximum velocity (this value is predefined). The authors also defined the initial feasible solution procedure whereas the velocity is randomly initialized with values between 0 and 1. The algorithm handled all the constraints required by the problem. For the dynamic problem (second phase), the authors proposed an incremental hill-climbing local search approach that is operated on the solution obtained by PSO algorithm. The authors used a real problem data obtained from the UTFSM. They considered around 950 lectures, 49 classrooms and 48 timeslots in a week. They compared the results with both, the manual one used at the UTFSM and a forward checking based algorithm. The obtained results showed that their method managed to obtain high quality solution within minutes while a traditional forward checking necessitates hours to find equivalent one.

Morteza Alinia et al. (2012) proposed Hybrid PSO for solving examination timetabling problem. The authors used a version of discrete PSO (DPSO) proposed by Pan et al. (2008) and employed mutation and crossover genetic operators to update position of particles. They proposed three versions to update positions of particles, which led to three versions of DPSO. After updating particles position, three strategies of local search methods are applied to hybridize DPSO in order to improve the quality of current position of the particles. These strategies are: graph coloring, evolutionary operators and Hill Climbing local search method. For the computational results, the authors used the datasets introduced by Carter and Laporte (1996) to show the efficiency of the proposed algorithms. They also compared the performance of these proposed algorithms with four previous studies proposed in the literature. The results proved that their proposed algorithms were very competitive with other state of the art techniques.

6 Conclusion and future research directions

ETP is one sort of scheduling problems that has taken the attention of the researchers since 1986. ETP is an important useful practice in several schools and universities. It is distinguished by its difficulty to find feasible solution due to the huge number of hard and soft constraints it can have. Since the last few decades, the scientific community has proposed many heuristic and meta-heuristic methods for solving this problem. Particle Swarm Optimization method (PSO) is one of the common meta-heuristic which is considered as an intelligent optimization technique and which is appropriate for solving this category of hard constrained problem. The use of PSO to solve ETP requires first representing a particle in the swarm, which is in general defined as a whole timetable where examinations are assigned to timeslots and/or rooms. The fitness function for each particle in the swarm is typically focused on the number of constraints violations in the timetable. It can also be a sum of penalizing violations of the soft constraints while preventing all infeasible solutions to get rid of hard constraints violations. In order to optimize the resulting timetable and avoid converging to local optimal points, certain solution approaches hybridize PSO with local search methods. Some PSO techniques used local search methods to get initial feasible solution. As well some genetic operators such as crossover and/or mutation are also used to update position of the particles. Experimental results of most PSO techniques showed the efficiency of PSO and a high quality of generated solutions which is usually as good as state of the art techniques from the literature.

This research work leads us to conclude that PSO is a new stochastic global optimization method for solving university Examination Timetabling Problem. Contrary to other optimization techniques (such as Genetic Algorithms), few articles have been found in the literature to solve this type of problem. According to Morteza Alinia et al. (2012), their article is the first that applied PSO to examination timetabling for real world Carter benchmark. So, the application of PSO on ETP is even now considered limited and deserves more attention.

However, discrete PSO may have some inconveniences. It can stuck in local extreme and it can eventually fail to guarantee the global optimum solution in some problems (Xianfeng and ShengLi 2014).

In order to solve ETP, three alternatives are suggested to improve discrete PSO. The first one is to well adjust PSO parameters since the research on PSO algorithm mainly focuses on how to adjust its parameters. For example, the inertia parameter is used to control the velocity of the particle and it will affect the global and local search of particle. So, a good adjustment can lead to the global search (Xianfeng and ShengLi 2014). The second alternative is to hybridize discrete PSO with other intelligent optimization algorithm since hybrid PSO has outperformed the standard PSO in many problems (see the methods described above). The third alternative is to propose a discrete hybrid free parameter PSO that allows not only to avoid the parameter setting step but also to achieve faster convergence without trapping in local optimum solution. Such algorithm has been proposed in continuous optimization called Tribes (Clerc 2006). Therefore, it is crucial to develop this intelligent method in discrete case and investigate further research in ETP problem.