A hybrid algorithm for the university course timetabling problem using the improved parallel genetic algorithm and local search

Abstract

Scheduling is one of the problems that has attracted the attention of many researchers over the years. The University Course Timetabling Problem (UCTP) is a highly constrained real-world combinatorial optimization task. Designing course timetables for academic institutions has always been challenging, because it is a non-deterministic polynomial-time hardness (NP-hard) problem. This problem attempts to assign specific timeslots and rooms to the events considering a number of hard and soft constraints. All hard constraints must be satisfied to achieve a feasible solution, whereas satisfying all soft constraints is not necessary. Although the quality of the solution is directly related to the number of soft constraints that are satisfied. One of the recent innovative methodologies for solving UCTP is the hybrid algorithm, which attempts to automate the timetabling design process so that it would be able to work with different instances of problem domains. In this paper, we present a hybrid method based on the Improved Parallel Genetic Algorithm and Local Search (IPGALS) to solve the course timetabling problem. The Local Search (LS) approach is used to strengthen the Genetic Algorithm (GA). The IPGALS has applied a representation of the timetable, which ensure the hard constraints would never be violated. Hard constraints are measured by Distance to Feasibility (DF) criterion. In fact, applying the DF criterion leads to achieving feasible solutions and promotes the performance of our algorithm. Due to the wide range of problem constraints, the proposed algorithm is performed in parallel to improve the GA searching process. The IPGALS algorithm is tested over BenPaechter and ITC-2007 standard benchmarks and compared with the state-of-the-art techniques in this literature. The experimental results confirm the effectiveness and the superiority of the proposed algorithm compared to other prominent methods for solving UCTP.

1 Introduction

The scheduling and timetabling of the courses in universities is a multi-stage process which requires proper coordination and communication among several groups. The planning groups of universities often consist of students, instructors, department head and education officer [1]. Basically, there are various constraints in a University Course Timetabling Problem (UCTP) [2,3,4,5]. Some of these constraints must necessarily be satisfied, which are called hard constraints. On the contrary, another category of constraints known as soft constraints helps to improve the timetabling quality [6]. Therefore, satisfying soft constraints leads to approach the optimal solution. The UCTP attempts to conduct a conflict-free assignment of all classes and laboratory sessions to instructors, rooms, and timeslots considering the hard and soft constraints [7]. Each institution pursues unique sets of hard and soft constraints based on its resources and facilities.

Generally, three categories of education timetabling are considered such as school timetabling [8, 9], course timetabling [10, 11], and examination timetabling [12, 13]. All above-mentioned categories resemble in some aspects, but they mainly vary in their unique constraints that require to be satisfied. In this paper, course timetabling is investigated in which courses/events are assigned to certain timeslots and rooms such that a set of requirements and constraints are satisfied. This problem bears a high resemblance to the graph coloring problem in which an identical color could not be assigned to two neighbor nodes (i.e. connected by an edge) [14]. Formerly, the university timetables were manually formed. Needless to mention that forming a course timetable manually is a highly time-consuming and complicated task. Nonetheless, it is mostly unable to form a conflict-free timetable even after several reforming iterations. The UCTP is a hybrid optimization problem and has been shown to be NP-hard [10,11,12]. The complexity of UCTP is due to the diversity of requirements of different institutions. Additionally, various approaches have been proposed to address the problem due to its importance [15, 16]. Most of these approaches use optimization methods to create an automatic timetable that is able to produce an optimal or best near-optimal schedule. However, there are still opportunities to generate more solid results.

The BenPaechter and ITC-2007 instances have been widely used as UCTP benchmarks for algorithmic comparison [16]. In this literature, numerous approaches have been presented on these instances to form course timetables so far. Scheduling tasks including UCTP are recently conducted applying various exact and meta-heuristic algorithms [17, 18]. Integer Linear Programming (ILP) settles in the category of exact algorithms which applies mathematical models to solve an objective function. ILP is capable of solving scheduling problems including the UCTP [17]. In addition, a large number of researches have discussed various meta-heuristic techniques for the UCTP. Some of the meta-heuristic approaches are Hybrid Evolutionary Algorithm [19], Hybrid GA with LS [20], Hybrid Evolutionary Approach with Nonlinear Great Deluge [21] and Hybrid Electromagnetism-like Mechanism with Great Deluge [22]. The evolutionary and heuristic algorithms suffer from two primary drawbacks such as early convergence to and getting stuck in the local optimum. Hence, hybrid algorithms are presented to cope with these drawbacks [10]. In fact, hybrid algorithms are a kind of approximate optimization algorithms that utilize mechanisms for escaping the local optimum and preventing early convergence as well [23].

In this paper, a hybrid approach based on the Improved Parallel Genetic Algorithm (GA) and Local Search (LS) is developed for solving UCTP, which we briefly called IPGALS. Due to the simultaneous investigation of several solutions and random survey of case space, which is suitable for the scheduling problem, the basis of the proposed hybrid algorithm in this study is the GA. We propose a two-stage method to deal with the UCTP. In the first stage, feasible solutions are generated. In the second stage, the algorithm attempts to improve the generated solutions progressively. The IPGALS used a representation of the timetable, which ensure the hard constraints would never be violated. In fact, hard constraints are measured by Distance to Feasibility (DF) criterion. GA tries to find feasible solutions based on the DF criterion. Then, we improve the feasible solutions in terms of soft constraints violation by using intelligent and elitist operators. Here, the LS approach is used to strengthen the GA. In addition, due to the wide range of problem constraints, the proposed algorithm is performed in parallel to improve the GA searching process.

The rest of the paper is organized as follows. The details of the UCTP are presented in Section 2. Section 3 is dedicated to literature review. The structure of proposed IPGALS algorithm is elaborated in Section 4 and the experimental results and discussion are presented in Section 5. Finally, Section 6 concludes and suggests possible future works.

2 The university course timetabling problem

The University Course Timetabling Problem (UCTP) is a classic and famous problem in the field of optimization problems. This problem is an abstraction of a real-world timetabling problem. The purpose of UCTP is to schedule a number of events (courses) in proper timeslots and rooms. This problem consists of a set of events to be scheduled in a number of timeslots, a set of rooms in which events can take place, a set of the attended students in each event, and a set of features satisfied by rooms and required by events [10]. Therefore, The UCTP is an abstraction of a real-world timetabling problem. The problem consists of a set of N_e events $E=\left\{{e}_1,{e}_2,\dots, {e}_{N_e}\right\}$ scheduled in a set of 45 timeslots T = {t₁, t₂, …, t₄₅} (5 days in a week, 9 timeslots per day), and a set of N_r rooms $R=\left\{{r}_1,{r}_2,\dots, {r}_{N_r}\right\}$, in which events can take place (rooms capacity is determined according to the input instances). Additionally, there is a set of N_s students $S=\left\{{s}_1,{s}_2,\dots, {s}_{N_s}\right\}$, which attend in each event, and a set of N_f features $F=\left\{{f}_1,{f}_2,\dots, {f}_{N_f}\right\}$, which is intended for each room and is required to satisfy each event (e.g. computer, video projector, etc.). Meanwhile, each room has a capacity, and each student attends a number of events.

In addition, there are some hard and soft constraints in the UCTP. A feasible timetable ensures that the timeslot and room are assigned to all events while all hard constraints are satisfied. In addition, the UCTP attempts to maximize the number of satisfied soft constraints because violating each soft constraint leads to a penalty.

2.1 Constraints

Constraints in UCTP are classified into two hard and soft constraints. All hard constraints must be satisfied, so that the generated solution would be feasible. Soft constraints are related to the objective function. The objective function attempts to maximize the number of satisfied soft constraints. Unlike hard constraints, soft constraints are not necessarily required to be satisfied. However, the more the number of satisfied soft constraints increases, the more the quality of solutions of objective function promotes. In the following, a list of extracted hard and soft constraints from the literature is presented [24]. We use these constraints to solve the UCTP.

2.1.1 Hard constraints

• HC₁: No student can have more than one enrolled course in a timeslot.

• HC₂: The room must be capable of satisfying the required features of the course.

• HC₃: The number of enrolled students in the course must be less than or equal to the capacity of the room.

• HC₄: No more than one course is allowed to be held during a timeslot in each room.

2.1.2 Soft constraints

• SC₁: A student should not have a single course during a day.

• SC₂: A student should not have more than two consecutive courses.

• SC₃: A student should not have a course which is scheduled in the last timeslot of the day.

The UCTP aims to form feasible timetables with the lowest penalty. Obviously, no hard constraint is violated in a feasible timetable, and the violation of soft constraint impose penalties.

2.2 Benchmarks

A set of benchmark instances from two different sources such as BenPaechter [25] and ITC-2007 Track 2 [26] is used for performance evaluation and comparison work. Although these instances have ignored multiple real-world problem constraints, they have empowered us to compare our approach with the state-of-the-art techniques. The instances in the BenPaechter benchmark include scheduling 100–400 events into a timetable with 45 timeslots (5 days and 9 h per day) as well as satisfying the room features and the room capacity constraints. These instances are divided into three categories: small, medium and large. We deal with 12 instances including five small, five medium and two large ones. We utilize ‘S1’ to ‘S5’ notations to show small instance 1 to 5 respectively, ‘M1’ to ‘M5’ to distinguish medium instance 1 to 5, and ‘L1’ and ‘L2’ notations to identify large instance 1 and 2. More details on the BenPaechter benchmark are given in Table 1. The instances with the identical characteristics (e.g. number of events, number of students, etc.), possess various internal parameters. Therefore, the time complexity of solving them is different, and they need different timetabling. The ITC-2007 benchmark is composed by real-world instances and was created by the University of Udine (Italy). This ITC-2007 benchmark contains 24 instances with 100–600 events. Similarly, we need to schedule the events into 45 timeslots. More details on the ITC-2007 benchmark are given in Table 2. In the experimental studies on this dataset, ‘C01’ to ‘C24’ notations are utilized to represent the instance COMP01 COMP24, respectively.

Table 1 Details of the BenPaechter benchmark instances

Table 2 Details of the ITC-2007 Track 2 benchmark instances

Tables 1 and 2 consist of nine columns in which the first column is a list of the instances and the other columns represent the specifications of scheduling resources. Specifications include the number of events, the number of rooms, the number of features and the number of students. In addition, rest of columns represent the maximum students per event, maximum events per student, mean features per room and mean features per event, respectively. The reported statistics are rounded numbers in the table.

All instances have at least one feasible solution (no hard constraint violations), although it is not known which is the optimal value for the soft constraints. Also, each instance comes in a single file, containing a file header and four sections: room’s capacity, student/event, room/feature, and event/feature. The header contains number of events, number of rooms, number of features and number of students. The capacity for each room represents the maximum number of seats. The student/event means that the student does attend the event or not. The room/feature means that the room does satisfy the feature or not, and finally, event/feature means the event does require the feature or not.

3 Literature review

In the past few years, researchers have focused on hyper-heuristic, hybridization and meta-heuristic approaches such as Harmony Search (HS) [27], Ant Colony Optimization (ACO) [28], Particle Swarm Optimization (PSO) [29], Genetic Algorithm (GA) [30], Great Deluge (GD) [31], Simulated Annealing (SA) [32], Hill Climbing (HC) [33], Local Search (LS) [2] and Tabu Search (TS) [34]. Susan and Bhutani [35], have compared the performance of SA and GA for forming the university timetables after mining the students’ preferences in selecting courses from the online repository of the university. Abuhamdah et al. [2] proposed a population-based LS algorithm for UCTP, which is a subcategory of LS (i.e. a mechanism to exploit the search space). This method implements two operators. One of them operates on a single solution to determine the force by comparing the current generating solution and the most recent generated solution. Another one operates on all generated solutions to determine the force in all directions.

In evolutionary-based optimization methods, GA is very popular and various GA-based strategies have been examined for UCTP. Goh et al. [36] utilized a hybrid local search algorithm which hybridizes TS and SAR (SA with Reheating) to solve the UCTP. Chen et al. [23] developed a TS algorithm with controlled randomization for solving the UCTP. Here, a random acceptation strategy with threshold mechanism is proposed to cater for subsequent algorithm design. Muklason et al. [37] proposed a method called Tabu-Variable Neighborhood Search to mitigate the drawbacks of meta-heuristic optimization methods (i.e. requiring the parameters tuning for every instance). Their method has selected heuristics at each decision point instead of directly solving the problem. Goh et al. [32] applied a highly tuned SA on the instances and reported superior results. Mazlan et al. [28] have recently utilized ACO on these instances. Their method has yielded more solid results such that it is still considered as the current state-of-the-art method. Hossain et al. [29] investigated a novel PSO-based method for solving highly constrained UCTP in which the basic PSO operations are transformed to solve combinatorial optimization task of UCTP and introduced couple of novel operations to PSO to solve UCTP efficiently. In this method, swap sequence-based velocity calculation and its application is implemented to transform each particles in order to improve them.

Matias et al. [38] investigates the GA with guided strategies and a self-adaptive mechanism to solve the UCTP. These data structures have used to guide or direct the searching process to an available resource and enhance the solutions produced by the genetic operators. In addition, a self-adaptive mechanism has integrated with choosing a neighborhood structure. Gozali and Fujimura [39] have applied the localized island model GA with dual dynamic migration policy (DM-LIMGA) for solving the UCTP. Thepphakorn and Pongcharoen [3] applied Particle Swarm Optimisation based Timetabling (PSOT) to solve the real-world datasets of the UCTP. The PSO, the standard PSO (SPSO), and the Maurice Clerc PSO (MCPSO) were embedded in the PSOT program for optimising the desirable objective function. The MCPSO outperformed the other variants of PSO for most datasets. Pintér and Dávid [5] proposed a two-stage heuristic method for solving UCTP. Here, an initial solution is created using a recursive search algorithm, then its quality is improved using local search heuristic. In addition, they use tabu list of forbidden transformations at the end of each iteration.

The hybrid approaches (the combination of evolutionary mechanisms with TS) have provided highly efficient solutions for the UCTP [40]. Yusoff and Roslan [33] proposed a hybrid GA-HC with the elitist for UCTP considering a bunch of constraints and a repair mechanism for all infeasible solutions. Akkan and Gülcü [6] proposed a hybrid bi-criteria GA algorithm for scheduling in UCTP. Gülcü and Akkan [41] exposed the problem of a robust UCTP to single and multiple disruptions. In their study, two versions of a hybrid Multi-Objective-GA (MOGA) have been developed, i.e. MOGA-Single Disruption (MOGA-SD) for problems with single disruptions and MOGA-Sample Average Approximation (MOGA-SAA) for problems with multiple disruptions. In fact, these two differ in the robustness level of the generated solution resulted in the MOGA. These algorithms aimed to identify an appropriate Pareto Archive which has been determined by the quality and robustness of the solution (imposed penalties due to soft constraints violations). A novel GA for UCTP has been presented by Susan and Bhutani [42]. They have hybridized the global search strategies of GA with the LS heuristics of SA, and implemented a greedy randomized LS mutation in GA.

Niknamian [37] has provided a survey on hybrid and meta-heuristic based approaches for UCTP. Kostuch [7] won the International Timetabling Competition 2002 (ITC-2002) using a meta-heuristic algorithm. Rezaeipanah et al. [10] proposed a parallel hybrid approach for generating initial timetables, and applied GA to improve the quality of the generated timetables. Some other hybrid approaches have been developed such as the multi-population hybrid GA in [11], the hybrid fuzzy evolutionary approach in [15] and the fuzzy-GA with LS in [16]. Hambali et al. [1] proposed a combination of GA and SA to form a heuristic approach for solving UCTP in the Federal University Wukari. Bashab et al. [4] proposed a meta-heuristic algorithm for UCTP which has combined grey-wolf optimizer and cat swarm optimization. Habashi et al. [43] suggested an adaptive diversifying meta-heuristic based approach for UCTP. In their study, a competitive iterated-LS approach has been proposed which has been strengthened by an add-delete meta-heuristic. The meta-heuristic has utilized an adaptive heuristic mechanism for generating solutions by using a variable-length list of add and delete operations.

4 IPGALS algorithm for UCTP

It is very difficult to find a general and effective solution for UCTP due to the diversity of the problem, variation of constraints, and different needs in universities and institutions planning. Despite presenting various approaches, many researchers use hybrid methods for solving the UCTP [6, 11, 15]. In addition, extensive researches have shown that GAs is an effective method for solving the UCTP [44,45,46,47]. The GA is a population-based algorithm which explores the entire search space without concentrating on the individuals bearing the best fitness function within a population. The GA may not always be able to find the optimal solution due to the possibility of premature convergence and getting stuck into local optima. Therefore, LS applies changes in the generated solutions. In fact, it performs local changes in a valid solution to achieve another valid solution in the search space until certain conditions are satisfied. The process iterated until achieving an optimal solution or in a time-bound. The hybrid of GA and LS (GALS) improves the performance by properly adjusting the global search [20, 33]. Therefore, GA is a well-suited tool for solving the UCTP which has increasingly attracted the attention of researchers.

The key superiority of GA is the searching for the solution with a population of solutions. However, GA requires an improvement due to random searches within all the problem space. This has been inferred after analyzing the solutions yielded from applying the classic GA on different instances (i.e. instances with a large number of events). Therefore, we have proposed a hybrid parallel method to solving the UCTP using the GA and LS and called it IPGALS. The IPGALS is an improved GA algorithm with a parallel architecture, where it is combined with LS for better convergence. Here, GA has been developed with some reforms such as initial population creation, offspring production, parallel structure and some intelligent operators. Meanwhile, the proposed structure for timetables does not violate any hard constraints in UCTP. Hard constraints are measured by Distance to Feasibility (DF) criterion in IPGALS. This leads to achieving feasible solutions and promoting the performance of our algorithm.

Parallel Genetic Algorithm (PGA) is such an algorithm that uses multiple GAs to solve a single task [10]. In the paper, we use ‘island model’ for PGA, because populations are isolated from each other. In the PGA, each algorithm performs over its population. Accordingly, the individuals of populations may differ from one conducting algorithm to another. Therefore, PGA may take a little more time than a non-parallel one. For that reason, PGA solutions are expected to produce more solid results than non-parallel GA. In addition, if the population of an algorithm does not progress after a number of generations, chromosomes are exchanged between algorithms. Higher genetic diversity, finding the global optima with higher probability, accelerating convergence, search in high-dimensional spaces, and so on, are the advantages of this work. The architecture of IPGALS algorithm is depicted in Fig. 1.

Fig. 1

The architecture of the IPGALS algorithm

In the following, each component of the proposed IPGALS algorithm is described in details.

4.1 Genetic algorithm

Researchers have applied numerous techniques to find the most suitable and fastest way of solving UCTP. In proposed IPGALS algorithm, timetables are formed through combination of an improved PGA and LS. Several studies have shown that GA is an effective and executable method for solving UCTP [44,45,46,47]. In computer science, GA is a search heuristic that is inspired by Charles Darwin’s theory of natural evolution [33]. This algorithm inspired by the natural selection of chromosomes in which the fittest chromosomes candidates are combined to produce subsequent offspring. The GA and developed models of it have been successfully applied to solve a number of scheduling problems such as UCTP [10, 15]. We have applied the IPGALS to take the advantages of both GA and LS. Here are the details of the improved GA.

4.1.1 Chromosome representation

Each chromosome in the GA population is represented by a chromosome representation. The representation scheme reflects the structure of the GA problem and either does determine the applied genetic operators. The proposed chromosome representation includes a two-dimensional vector of gene sequences. The proposed chromosome length in UCTP is related to the number of events. In addition, each event in chromosome structure includes two genes characterized by timeslot (event time) and room number (event location). Here, chromosome representation is subtly designed to make the use of genetic operators very simple. Structure of the proposed chromosome is shown in Fig. 2, where t_i ∈ T and r_i ∈ R represent the j-th timeslot and k-th room number assigned to i-th event, respectively.

Fig. 2

The structure of proposed chromosome representation

4.1.2 Initial population

Population initialization is the first step in the GA Process. Population is a subset of chromosomes in the current generation. Generally, chromosomes in GA are generated randomly or by heuristic methods from the search space. The initial population for the GA is usually generated randomly. Applying a random method for generating the initial population often leads to producing the infeasible solutions due to the lack of satisfying the problem constraints. In fact, the infeasible solutions are achieved due to the absence of any preconditions to generate the population. In the following, we will describe a three-step approach to generate an initial population. This approach generates the initial population based on a random-heuristic method.

• Step 1: Generate all states to set an event (gene) of the chromosome. All states are determined by the timeslots and the room’s number. For example, all states of a timetable with 5 timeslots and 3 rooms are 15 (3 × 5). To better understand this issue, see Fig. 3. Each state represents a gene from the chromosome that could be assigned to an event.

• Step 2: Shuffling technique assists to promote evolution, the genetic diversity and population variety [10]. Therefore, all the states generated in the first step are shuffled for producing each new chromosome. This is done in order to select chromosomes from the entire search space and prevent generating of duplicated chromosomes. Preventing the production of duplicate chromosomes is accomplished by considering the value of an event according to the set of possible states for that event. Meanwhile, all states are shuffled to generate each new chromosome. In addition, this technique adds a random property to the production of the initial population. Figure 4 shows the effect of using the shuffling technique of the given example in Fig. 3.

• Step 3: Here, each event of the chromosome is assigned a state (among the states of the second step). The proposed heuristic method provides the best state for each event. Hence, it is necessary to select a subset of all states assigned to an event. Finally, a state among the subsets of the selected states is assigned to the event. The subsets of states for each event is selected so that all hard constraints are not violated in the chromosome. Accordingly, all the states for each event are investigated. The first state with no violated hard constraint is assigned to the event. Then, the selected state is eliminated from the set of all states, since it should not be selected for other events. That way, a subset of states is determined for other events. However, it may not be acceptable state for some events, especially in the final events of the chromosome. Therefore, some events may violate hard constraint by selecting any remaining state. In this paper, these events are denoted by the ‘-1’ symbols, and we call them conflicting events. Figure 5 shows an example of a chromosome with six events according to Fig. 4.

Fig. 3

All states of a timetable with 5 timeslots and 3 rooms

Fig. 4

Shuffling technique on the example given in Fig. 3

Fig. 5

Selecting states for a chromosome with six events according to Fig. 4

In this example, 10th and 14th states are assigned to first and second events. Since selecting any remaining state for the third event violates the hard constraint, this event is set to ‘-1’ symbol. Also, the fourth and fifth events are set to 6th and 15th states. The eighth state with content {2, 1} (2 for timeslot and 1 for room number), violates the hard constraint in the sixth event. Therefore, it is impossible to assign this state to the sixth event. Here, the sixth event has been set to third state (with content {1, 3}).

4.1.3 Fitness function

The input data for each instance of the problem include number of events, number of students, number of features, room’s capacity, attended students in each event, features required for each event and features satisfied by rooms. Based on the data of each instance as well as the constraints defined in Section 2.1, the fitness function for each chromosome is calculated. A fitness function is a particular type of objective function and shows how close a given design solution is to achieving the set aims. Here, each chromosome contains a set of events and each event that causes the constraints violation penalizes the fitness function. At first, the constraints violation in the solution X is calculated based on the fitness function defined in the Eq. (1) [44, 45].

$$ {F}_{obj}(X)=\sum \limits_{i=1}^{N_{sc}}{w}_i^{sc}\times {P}_i^{sc}+\sum \limits_{j=1}^{N_{hc}}{w}_j^{hc}\times {P}_j^{hc} $$

(1)

Where, ${w}_i^{sc}$ and ${w}_j^{hc}$ represent the weight of each soft and hard constraint, respectively. ${P}_i^{sc}$ and ${P}_j^{hc}$ number of soft and hard constraints violation, respectively. Also, N_sc and N_hc is the number of soft and hard constraints, respectively. The constraints weight is determined according to their importance in the timetable. However, F_obj(X) represents the fitness function for the solution X.

In the IPGALS algorithm, the value of hard constraints is always equal to zero, i.e. the hard constraints violation is impossible. Because we use the ‘-1’ symbol for conflicting events. Therefore, in Eq. (1) it is always $\sum \limits_{j=1}^{N_{hc}}{w}_j^{hc}\times {P}_j^{hc}=0$. However, IPGALS does not allow any of the hard constraint to be violated in the optimization process. In this paper, instead of hard constraints violation, DF criterion is defined for conflicting events. Therefore, if there are events with a ‘-1’ symbol in the solution, their penalty is calculated by DF for the fitness function. DF for a solution expresses the distance to feasibility. Consequently, the value of fitness function in each solution considering soft constraints violation and DF criterion is calculated by Eq. (2).

$$ {F}_{obj}(X)=\sum \limits_{i=1}^{N_{sc}}{w}_i^{sc}\times {P}_i^{sc}+\sum \limits_{j=1}^{N_{df}}{w}^{df}\times {P}_j^{df} $$

(2)

Where, w^df is the weight of DF criterion, ${P}_j^{df}$ shows the DF for j-th conflicting event, and N_df is the number of conflicting events (events with ‘-1’ symbol in the chromosome). The following is considered to calculate the fitness function of a solution:

• DF criterion (P^df): This criterion is calculated for a conflicting event based on the number of attended students. In fact, DF for a solution is the overall of the number of students in conflicting events. As an example, if the solution contains three conflicting events, and the number of students in each case is 7, 14 and 3. Hence, the DF for this solution is equal to 24 (7 + 14 + 3).

• Number of violated soft constraints (P^sc): The number of violated soft constraints is equal to the overall of the three soft constraints defined in Section 2.1.2.

4.1.4 Selection operator

Selection operator is the stage of GA, which chromosomes with good fitness function are preferred and allows them to pass on their genes to the successive generations. So, this operator is for selecting combining a pair of parents to produce offspring in the next generation. Parent selection plays an important role in GA converging duration such a way that proper parents direct chromosomes to fitter solutions. In IPGALS, the roulette wheel technique is used to select parents [48]. This technique is a common method for selecting an item proportional to its probability. In addition, shared memory chromosomes are used to aid convergence. Here the first parent is selected from the population of the current GA. Also, the second parent with a 50% probability is the best chromosome from the shared memory, and with a 50% probability is selected from the chromosomes of shared memory.

4.1.5 Crossover operator

The performance of GA mainly depends on the type of genetic operators involve in crossover and mutation. Crossover is a genetic operator used to vary the genome of chromosomes from one generation to the next. The IPGALS algorithm consists of three crossover operators: Uniform, One-Point and Heuristic Operators. According to the two selected parents, one chromosome is generated as an offspring in each crossover operator. Crossover operator is usually applied in a GA with the highest C_R probability. Otherwise, offspring is generated by repeating the parents in case the crossover is not conducted on a chromosome pair. However, based on the three crossover operators, three offspring are generated. The details of the proposed crossover operators are discussed below.

Uniform crossover operator

Generally, the uniform crossover is more effective for many problems, especially for numerical optimization problems [45, 46]. At first, the chromosome of offspring is randomly generated with ‘0’ and ‘-1’ genes in the proposed uniform crossover operator. Then, the equivalent genes are duplicated from the first parent for each gene with the content of ‘0’. Afterwards, the genes are duplicated from the second parent instead of genes with the symbol ‘-1’, provided they do not violate the hard constraints. Finally, some genes may not be assigned any value with the content of ‘-1’. Hence, these genes are considered as conflicting events. An example of a uniform crossover operator is shown in Fig. 6.

Fig. 6

An example of uniform crossover operator

In this example, events 2, 4, and 5 of the offspring chromosome with ‘0’ content and other events (1, 3 and 6) with ‘-1’ are initially set. Then, events 2, 4, and 5 are duplicated by the equivalent genes of the first parent. That is, {14, 1}, {2, 3} and {3, 1}. Similarly, the events 1, 3 and 6 are set by the second parent, where the hard constraints have been violated for the third event with {14, 1} content. Therefore, the third event is a conflicting event.

One-point crossover operator

In one-point crossover, a random crossover point is selected and the genes of its two parents are swapped to get new offspring. At first, the offspring chromosome with the content of ‘-1’ is generated by default. Then a random number is generated and the parents are cut from the same point. Afterwards, the genes swap is done between two parent chromosomes. The first part of the first parent is placed directly on the offspring chromosome. The genes of the second part of the second parent are used to complete offspring chromosome, provided they do not violate the hard constraints. If an event violates a hard constraint, it is set by the ‘-1’ symbol. An example of a one-point crossover operator is shown in Fig. 7.

Fig. 7

An example of one-point crossover operator

In this example, crossover point is randomly selected with the value of 3. In this case, events 1 and 2 of the first parent and other events (3, 4, 5 and 6) of the second parent are used to generate the offspring chromosome. Here, the third event of the second parent violates the hard constraints. Therefore, this event is a conflicting event in the offspring chromosome and it is denoted by the ‘-1’ symbol.

Heuristic crossover operator

The heuristic crossover operator also fills the offspring chromosome genes with the content of ‘-1’ by default to avoid hard constraints violation at first. Then, the shared genes between the parents are placed directly on the offspring chromosome. Afterwards, other genes of the offspring chromosome are set according to the remaining events of parents, provided they do not violate the hard constraints. An example of the heuristic crossover operator is illustrated in Fig. 8.

Fig. 8

An example of heuristic crossover operator

In this example, events 1, 3, and 6 are share to both parents. Therefore, these events are duplicated in the offspring chromosome with {7, 3}, {5, 2} and {4, 2}, respectively. Then, according to the remaining events of parents (namely, {14, 1}, {2, 3}, {3, 1}, {6, 1}, {13, 3} and {8, 4}), other genes of the offspring chromosome are set. Here, none of the remaining events has been able to complete the fifth event without the violating hard constraints. Hence, the fifth event is a conflicting event and setting by the ‘-1’ symbol.

4.1.6 Mutation operator

The mutation operator aims to produce a little modification to a chromosome to produce the next offspring stochastically. This operator alters one or more gene values in the offspring chromosomes from its initial state. One of the main advantages of this operator is the ability to access the entire search space. Mutation operator is used to maintain and introduce diversity in the genetic population and is usually applied in a GA with the lowest M_R probability. It has been observed that mutation is essential to the convergence of the GA while crossover is not [48]. The IPGALS algorithm consists of three mutation operators: Local, Global and Swap Operators. These operators apply on three offspring produced by crossover operators. Therefore, the IPGALS algorithm produces nine offspring. The details of the proposed mutation operators are discussed below.

Local mutation operator

In this operator, two events are randomly selected from the contradictory events of the offspring chromosome. Where, contradictory events include a list of events that violate soft constraints. The selected events are replaced, provided does not violate the hard constraints and improve the fitness function. The probability of changing the timeslot and room is as follows: with a 50% probability both timeslot and room, with a 25% probability only the timeslots and with 25% probability only the room. In this operator, if the offspring chromosome had conflict events, one of the events is randomly selected from them. Therefore, according to internal events investigate of the offspring chromosome, the efficiency of this mutation operator is local.

Global mutation operator

This operator first compiles a list of all possible states that can be added to the chromosome. According to Fig. 3, each state consists of the timeslot and the room number. The possible states are the result of sharing all the states and states of the offspring chromosome. Then, an event is randomly selected from the list of possible states and a random event from the offspring chromosome. The event related to the offspring chromosome is selected from the conflicting events. The selected state is replaced, provided does not violate the hard constraints and improve the fitness function. The probability of changing timeslot and room is similar to the local mutation operator. In general, there is a probability of selecting any conflicting event from the offspring chromosome in this operator. But, if the offspring chromosome contains conflicting events, the focus of selection is only on those events. Therefore, the efficiency of this mutation operator is global according to investigate of unseen events in the chromosome.

Swap mutation operator

This operator randomly selects two events among all events within the chromosome. Then, the events are swapped in case fitness function produce better results.

4.1.7 Improvement operator

According to the structure of the proposed chromosome, some events might not be scheduled in a timetable. These are conflicting events which are represented by the ‘-1’ symbols. The purpose of the improvement operator is to find the timeslot and the room for conflicting events so that the timetable becomes a feasible solution. In fact, this operator has been designed to improve the timetable by reducing the DF criterion in which we tend to minimize DF in the offspring population. This operator may drastically increase the number of soft constraints violation, but it reduces the DF criterion without violating hard constraints. Meanwhile, this operator applies to all nine offspring produced by mutation operator. Improvement operator performs in following steps for each conflicting event.

• Creating all possible states for events in E_S parameter

• Eliminate the states in the offspring chromosome from E_S

• The remaining states in E_S are examined in order to be replaced by conflicting event. The first state that does not violate any hard constraints for the offspring chromosome is replaced with the conflicting event.

4.1.8 Elitism operator

The interesting point of GA is the possibility of generating highly suitable chromosomes in median generations (yielding solid results at fitness function). These chromosomes might be destroyed in the result of the crossover and mutation operators and not generated anymore. Elitism technique identifies such cases and uses them in subsequent generations. Therefore, this technique can help IPGALS to find optimal solutions for UCTP. The elitism operator of this paper selects the best chromosome from the shared memory in each generation and transfers it directly to the next-generation population (for all PGAs).

4.1.9 New population for next generation

In the IPGALS, nine offspring chromosomes are produced at each generation by operators. Three offspring are produced by crossover operators (C₁, C₂ and C₃) which three offspring ({C_{1, 1}, C_{1, 2} and C_{1, 3}}, {C_{2, 1}, C_{2, 2} and C_{2, 3}} and {C_{3, 1}, C_{3, 2} and C_{3, 3}}) are produced by each offspring through mutation operators. Thus, GA created a new population sequence by designed operators. Therefore, only nine new offspring are produced at each generation and the population is updated based on them. For the next population, the best chromosomes (based on the fitness function) from the old population and the offspring population are selected for the next-generation population. Then, the new generation of candidate solutions is used in the next generation of the algorithm. Following the above steps, the genetics cycle is transferred to the next generation. The reason for producing only nine offspring chromosomes is to reduce the inter-dependency of the population size and the algorithm running time in each generation. Accordingly, the population size can be increased due to genetic diversity without affecting the running time of the algorithm. This generation process is repeated until a termination condition has been reached. In particular, the termination condition in IPGALS is to reach the maximum number of the generation G_max.

4.2 Local search

Local Search (LS) is the basis of many heuristic methods for combinatorial optimization problems. This algorithm performs local changes in a valid solution to achieve another valid solution in the search space until certain conditions are satisfied. In general, LS is introduced to find a solution in order to maximize a fitness function among a number of ongoing solutions. In UCTP, there might be the genes of a chromosome that are less repeated or never been used. For this reason, it is necessary to increase the probability of choosing unselected states for each event. In the IPGALS algorithm, LS applies to the population of the offspring in each generation. The LS randomly swaps some of the unused genes in the chromosome. Unused genes include states that have not been used as events in the solution. LS changes only the amount of one gene in each iteration and changes are applied if the quality (fitness function) of timetabling increases. The maximum number of iterations to complete the LS process is LS_iter.

4.3 Shared memory

Shared memory contains the best chromosomes produced in all PGAs (based on the fitness function). The shared memory members are updated after calculating fitness function in each generation. Each running GA, stores Q chromosomes with the best fitness function in the shared memory. Therefore, the size of the shared memory is Q × Z, where Z represents the number of running PGAs.

4.4 Structure of the PGA

As a matter of fact, the parallel implementation has been introduced for finding the solution in the NP-hard problems with the emergence of multi-core systems. Parallel computing techniques can be used to improve the efficiency of GA by exploiting the concurrency of calculations performed in GAs. One of the important features of the GA is the capability of running in parallel and searching for complicated spaces. In general, the possibility of getting stuck in a local optimum trap is much low using PGAs. PGA uses multiple genetic algorithms to solve a single task. In PGA, different populations are generated and processed in parallel instead of using a population and evolving it. In UCTP, developing a high-performance GA which always solves the problem is almost impossible due to the diversity of constraints. In IPGALS, a GA with multi-population has been proposed to solve this problem. In addition, in IPGALS, the parallelization of GA is done applying the shared memory programming and island model. In a parallel implementation of an island model each processor executes a GA. The processors perform the evolutionary process by periodically exchanging a portion of their populations.

The chromosome structure is identical in all populations, so that each population has its own unique operators. Meanwhile, each population is processed in parallel and independently. In addition, the initial population and fitness function are calculated in parallel, since this was the most time-consuming part of the algorithm. Although the selection, crossover and mutation operators can be performed in parallel, these are not computationally intensive tasks. Here, the process of exchanging chromosomes between populations of PGAs is performed after number of generations using elitist methods. Number of generations for the exchanging the chromosomes is determined based on th₁ threshold. According to this threshold, each th₁ generation of chromosomes is exchanged. In the exchange process, L item of the worst chromosomes are eliminated from the current population and the best chromosomes of the shared memory replace L items. The worst and best chromosomes are determined by fitness function. The number of exchanging chromosomes should be selected based on population size. Therefore, choosing a very high or very low value for L may have negative influences on the evolution of population, genetic diversity, and disrupting the final convergence.

4.5 Pseudo-code for the proposed IPGALS algorithm

The sequence of pseudo-code presented in Fig. 9 shows the proposed algorithm.

Fig. 9

Pseudo-code of the proposed IPGALS algorithm

5 Results and discussion

In this section, we conduct an experimental study to evaluate the performance of the proposed algorithm. All experiments are carried out on an Intel Core i5 CPU at 2.2GHz and 8GB of memory and Windows 10 64-bit operating system. Furthermore, MATLAB R2016a is used for implementation. In order to achieve more reliable results, all experiments have been reported an average of 10 independent executions. The proposed algorithm is evaluated on the BenPaechter [25] and ITC-2007 Track 2 [26] benchmark instances. Best-known solutions is available at the website of the Timetabling Research Group at the University of Udine (http://satt.diegm.uniud.it), which researchers can upload their best solutions and results.

In this paper, all considered constraints for the comparing algorithms have been identified according to Section 2.1. Due to the same constraints and instances, all comparisons between algorithms have been performed in fair conditions. This section divided into five subsections. The first subsection discusses the parameters setting. The second subsection reports the soft constraints violation for all instances. The third subsection shows the convergence of IPGALS algorithm in reducing constraints. The fourth subsection investigates the effectiveness of each operator in producing the final solutions. The fifth subsection proves the superiority of IPGALS algorithm versus IGA and IGALS methods. The sixth subsection compares the IPGALS algorithm with the state-of-the-art techniques. The discussion on the time complexity of the IPGALS algorithm is presented in last subsection.

5.1 Parameters setting

The efficiency and effectiveness of hybrid and meta-heuristic algorithms highly depend on the appropriate adjustment of the parameters. The IPGALS algorithm has several parameters, which are presented in Table 3. Parameters are set into three categories according to the complexity (number of events) of the instances such as the events fewer than 200 (N_e ≤ 200), between 200 and 400 (200 < N_e ≤ 400) and more than 400 (N_e > 400). Some of the initial parameter values are derived from the studies of [47, 49], including control parameters for the weight adjustment mechanism, i.e. N_pop, C_R, M_R and G_max. Other parameters (i.e. Z, LS_iter, th₁, L and Q) are determined using Taguchi method to achieve the best solution [50]. This method ensures the identification of effective parameters and levels with fewer experiments by providing balance among the orthogonal index, parameters, and levels. The aim of Taguchi method is to maximize the S/N ratio (signal-to-noise) which in the paper is calculated by Eq. (3).

$$ S/{N}_{ij}=-10{\log}_{10}\left(\frac{1}{m}\sum \limits_{i=1}^m{F}_{obj}{\left(i,j\right)}^2\right),\kern4em \forall j\in level $$

(3)

Where, F_obj(i, j) is the objective function value using the parameter i on j-th level and m is the number of times j-th level of the parameter i is repeated over the runs of all trials.

Table 3 Parameter setting for IPGALS algorithm

The results obtained through various parameters of 4 levels are estimated based on standard table of orthogonal arrays L₁₆ [50]. Because of the similarity in reasoning procedure, the parameters setting process is only shown for instances with 100 event numbers. Table 4 presents the value of different parameters at each level in Taguchi method.

Table 4 Level values considered for parameters

In this Table, rows denote the level of parameters in each experimental scheme and columns indicate a specific level of a parameter that is changeable in each scheme. The S/N ratio obtained from the experiment (illustrated in Fig. 10) indicates the order of importance of the variables. Rank shows the level according to which variables should be used in order to receive the best solution. The level with the highest S/N value is the most suitable level. According to the S/N ratio, it is inferred that Z, LS_iter, th₁, L and Q, which are 3, 2000, 10, 2, and 3, respectively, is an appropriate solution based on Taguchi method.

Fig. 10

The S/N ratio obtained in the Taguchi method

In IPGALS, the weight for the DF criterion is set to be 1.0 ( w^df = 1). This weight prevents the selection of chromosomes with conflicting events. In general at UCTP, the weight of soft constraints (w^sc) is very effective for determining the optimal solutions in UCTP. Therefore, the weight of soft constraints is evaluated by different states to find the most appropriate values for them. In each state, we assign different weights in the range [0–1] to the soft constraints ${w}_1^{sc}$,${w}_2^{sc}$ and ${w}_3^{sc}$. The performance of the IPGALS is investigated through setting the weights on the BenPaechter and ITC-2007 benchmarks. The results of this comparison have been shown in Table 5.

Table 5 The Performance results of the IPGALS with different weights

The bold row of the table indicates the relative optimum values. Here, average of the constraints violation is presented for all instances. The results show that the best values of weights are when ${w}_1^{sc}$, ${w}_2^{sc}$ and ${w}_3^{sc}$ are 0.25, 0.75 and 0.50, respectively. Meanwhile, selecting chromosomes based on this weights leads to increase efficiency and genetic diversity.

5.2 The IPGALS algorithm results

We applied the IPGALS algorithm on the instances of BenPaechter and ITC-2007 benchmarks and the results are shown in Tables 6 and 7, respectively. The results are depicted based on the best and mean cases of soft constraints violation. For each experiment, the average of 10 runs of IPGALS algorithm is reported in the results. IPGALS does not cause the hard constraints of the input instance. Therefore, the presented results are only related to soft constraints and DF criterion. In these tables, the number of violations for each constraint is individually calculated and has been reported for each instance. DF in Tables 6 and 7 represents the distance to feasibility criterion. In fact, DF indicates how far a solution is from a feasible solution. The last column of these tables represents the sum of all soft constraints plus DF criterion. So, the column is entitled ‘Total’ equals SC₁ + SC₂ + SC₃ + DF, where SC_i is the i-th soft constraint in the fitness function.

Table 6 The performance of IPGALS algorithm on BenPaechter benchmark

Table 7 The performance of IPGALS algorithm ITC-2007 benchmark

The results of Table 6 show that the IPGALS generates solutions without constraints for all small instances in the BenPaechter benchmark. Medium instances have little soft constraints. However, IPGALS is able to present a feasible timetable for all medium instances (the DF criterion for all medium instances equals zero). In large instances, the number of constraints violation is greater than in small instances. For example, the total number of violated constraints in the Medium1 instance is 84, while this value is 516 for Large1 instance (best case). In addition, the performance of the IPGALS is satisfactory based on DF criterion, since feasible solutions are presented for all the 12 instances of the BenPaechter benchmark (best case). DF criterion results are 193 and 386 on average for Large1 and Large2 instances, respectively. These results indicate that the IPGALS does not always provide the feasible timetable for large instances. Moreover, the results of SC₁, SC₂ and SC₃ constraints show that reducing SC₂ is more difficult for IPGALS. This constraint is equivalent to the number of times a student has taken more than two consecutive classes.

Results of Table 7 for the ITC-2007 benchmark show that the IPGALS algorithm for some instances always presents the timetable without any violated constraint, i.e. C05-C09, C13-C18 and C21. The results of other instances are also satisfactory, since feasible solutions are presented for all 24 instances of the ITC-2007 benchmark (best case). However, the average DF results for C01, C10, C22 and C23 instances show that the IPGALS has not always been able to always provide a feasible timetable. In addition, the results show the relatively high difference between the average and the best value, which represents the scattering in the solution space. It is believed that there is a close relationship among the soft constraints. Note that satisfy soft constraint 1, increases the violation on soft constraint 2 and 3, because more events will be scheduled in a day to avoid having a single event on a day. For example, in Table 7, satisfaction of soft constraints 2 and 3 is weaker in most instances.

5.3 Observing the convergence of IPGALS

GA results are usually converged when there is no significant improvement in the values of the fitness function of the population from one generation to the next. It causes evolution halting because all chromosomes in the population become identical. IPGALS convergence analysis for reducing the constraints is covered in this subsection.

In order to solve constrained optimization problems through GA, the algorithm must generate feasible solutions and select a near-optimal solution among all the feasible solutions. IPGALS algorithm benefits from being able to escape local optima utilizing intelligent operators. In IPGALS, accelerating the convergence is performed using improvement operator and LS. These operators reproduce valid chromosomes in each generation. Moreover, IPGALS accelerates convergence by embedding the process of reasoning with reducing the distance to feasibility. Because IPGALS does not waste its time on the infeasible solutions.

In Figs. 11 and 12 the convergence of IPGALS for the BenPaechter and ITC-2007 benchmarks is shown based on the number of violated constraints. Meanwhile, the results have been reported on average for all small, medium and large instances in the BenPaechter benchmark. For example, convergence in small instances is calculated based on the average S1-S5 instances. Similarly, the results have been reported on average for instances with a number of events of less than 200, between 200 and 400, and more than 400 in the ITC-2007 benchmark.

Fig. 11

The convergence of proposed algorithm on the BenPaechter instances

Fig. 12

The convergence of proposed algorithm on the ITC-2007 instances

DF criterion in small instances converges to zero rapidly which means a feasible solution has been produced. For these instances, due to the tiny size of the search space and the random-heuristic method for initial population, the hard constraints are not violated. This means that there is no gene with the ‘-1’ symbol in the solution. Therefore, operators focus on reducing soft constraints based on the mutation operator structure. In fact, mutation operators for solutions without DF constraints only apply to conflicting events. Obviously, all three soft constraints SC₁, SC₂ and SC₃ are rapidly reduced and the best result is achieved after the 60th generation. However, DF values are not zero in the medium and large instances, due to the extent of the problem dimensions in these instances. Therefore, IPGALS focuses on reducing DF constraints according to the designed operators and IPGALS algorithm strategy against DF criterion. For this reason, other soft constraints are sometimes increased by DF decrement. That is clearly indicated in the Fig. 11 for medium and large instances. For example, DF value is about 100 in the first generation of the medium instances and after 17 generations converges to an optimum value of zero. However, SC₂ is about 150 in the first generation and its value reaches more than 160 after 17 generations. In general, SC₂ constraint value is higher than any other constraints. The number of SC₂ constraint is much higher than SC₁ and SC₃ constraints due to the high number of students and events for each student.

In all experiments, only the value of DF criterion equals zero for IPGALS except for the small instances of BenPaechter. It demonstrates that reducing DF constraints is more important than the soft constraints for IPGALS. Because, IPGALS algorithm allocates higher priority to reducing DF, through allocating higher weight and the behavior of some operators. Figure 12 confirms that IPGALS for the instances on the ITC-2007 benchmark performs similar to the BenPaechter benchmark.

5.4 Observing the effectiveness of operators

IPGALS algorithm defines different operators for reproducing and improving the solutions. These operators consist of uniform crossover, one-point crossover, heuristic crossover, local mutation, global mutation, swap mutation, improvement, elitism and local search. Each of these operators has different responsibilities in creating a new population. In Figs. 13 and 14 the effectiveness of each operator in producing the final solutions is shown for BenPaechter and ITC-2007 instances. The effectiveness of an operator in producing final solutions is measured based on performing IPGALS with deactivating that operator. Therefore, greater importance for an operator is achieved when the efficiency of IPGALS is reduced without its use.

Fig. 13

The effectiveness of the proposed algorithm operators on BenPaechter instances

Fig. 14

The effectiveness of the proposed algorithm operators on ITC-2007 instances

Here, the number of violated constraints with deactivating each operator is reported based on 10 runs of an instance on the best case. In Figs. 13 and 14, the term ‘S1’ means the first instance of small data, ‘S2’ means the second instance of small data, and so on. Likewise, the term ‘M1’ denotes the first instance of the medium data and ‘L1’ denotes the first instance of large data and so on. Similarly, the term ‘C01’ means COMP01 instance, ‘C02’ means COMP02 instance, and so on. The effectiveness of improvement, local search, and heuristic crossover operators is clearly demonstrated in various instances. The importance of these operators (especially improvement operator) is in reducing the DF criterion and creating feasible solutions. The improvement operator is more efficient than all operators except M4 instance of BenPaechter and C06 and C09 instances of ITC-2007.

5.5 Comparing IPGALS with IGA and IGALS

In this paper, we proposed a hybrid method for solving UCTP using IPGALS. IPGALS is a hybrid of GA and LS that use a parallel architecture. Here, we compare the results of IPGALS with the results of IGA and IGALS methods. IGA is an improved GA, and IGALS is a combined algorithm of IGA and LS. The IGA and IGALS methods details are similar to the proposed IPGALS algorithm. The performance of IPGALS versus IGA and IGALS is shown by the total average of violated soft constraints (for all instances) in Table 8. The results are reported an average of 10 runs for each instance of BenPaechter and ITC-2007 benchmarks.

Table 8 Comparing average of soft constraints violation between IGA, IGALS and IPGALS algorithms

As evident in Table 8, each algorithm recorded the average of violated soft constraints for all instances of a benchmark. The averages produced by IGALS and IPGALS methods are comparable for these benchmarks. Meanwhile, IPGALS clearly outperforms IGA on the both benchmarks. Overall, IPGALS seems to be the most effective algorithm.

Here, we compare the performance of IGA, IGALS and IPGALS methods in minimizing the number of violated soft constraints. For BenPaechter instances, the comparison between IPGALS and IGALS is shown in Table 9. In order to compare, the best values of soft constraints violation are depicted for 10 runs. Moreover, a paired t-test has been used to verify the effectiveness of the proposed algorithm. The paired t-test has been performed between IPGALS and each of the IGA and IGALS methods. A value of p < 0.05 is considered to determine statistical significance. The t-test values constitute of the soft constraints violation achieved with methods as one distribution. The p values reveal that there is no significant difference between the means of IGALS and IPGALS for all the instances except M4 where IGALS is better than IPGALS. In addition, IPGALS performance is clearly better than IGA for all instances.

Table 9 Comparison between IGA, IGALS and IPGALS methods on BenPaechter instances

Results of comparison between IGA, IGALS and IPGALS methods for ITC-2007 instances have been shown in Table 10. The t-tests show that IGALS only performed better than IPGALS for instances C03, C04 and C11. However, IPGALS is clearly more effective for instances C02 and C19. The difference between both methods for the rest of the instances is negligible on average. In addition, IPGALS has performed significantly better compared to IGA for instances C02, C06, C10, C19, C22, C23 and C24. IGA has performed better than IPGALS for instance C03 on the best case. The difference between both methods for the rest of the instances is negligible on average. Totally, IPGALS outperforms IGALS on 4 instances. Also, IPGALS is significantly outperforming IGA on 12 instances. The t-tests to indicate significant statistical differences between the means of the three methods for the rest of the instances.

Table 10 Comparison between IGA, IGALS and IPGALS methods on ITC-2007 instances

5.6 Comparing IPGALS with other methods

The existence of different methods for solving UCTP has opened a vast opportunity for researchers in this field. Therefore, choosing the best method or following its sequence could provide relatively better successes for future approaches. In this respect, the BenPaechter and ITC-2007 instances have been widely used as UCTP benchmarks for algorithmic comparison. Here, the performance of the proposed IPGALS algorithm is compared with other methods in solving UCTP. The average numbers of constraints violation of 10 independent executions for BenPaechter instances are shown in Table 11. In addition, comparison results for ITC-2007 instances are reported in Table 12. Meanwhile, A_i (i = 1, 2, …, 38) denote the compared methods which A₃₈ denotes the proposed IPGALS algorithm. Appendix is dedicated to present a list of compared methods.

Table 11 Comparison of IPGALS performance with other methods on the BenPaechter instances, all solutions are possible, and i.e. the hard constraints are 0

Table 12 Comparison of IPGALS performance with other methods on the ITC-2007 instances, all solutions are possible, and i.e. the hard constraints are 0

In Table 11, the number of violated soft constraints is presented on the mean and best cases for all small (S1–S5), medium (M1–M5) and large (L1 and L2) instances. The terms B and M refer to the best and mean cases, respectively. The reported results confirm the superiority of the IPGALS algorithm in comparison with other methods in most of the instances. According to Table 11, A₂, A₈, A₁₁, A₁₈ and A₂₁ suffer from inefficiency for small instances. Hereby, the performance of algorithms is degraded over medium instances. Here, the order of superiority of methods is A₃₈, A₂₃, A₁₂, A₄ and A₁₇. In general, A₃, A₁₂, A₂₃ and A₃₈ methods have appropriate efficiency over large instances. The methods A₁, A₃, A₅, A₁₂, A₁₅, A₁₆, A₁₇, A₁₉, A₂₂, A₂₃ and A₃₈ methods in small instances present best performances, because they do not violate any soft constraints. However, the worst performance belongs to both A₁₁ and A₂₁ methods.

We have obtained the performance of the above methods on medium instances, where the A₃₈ method (IPGALS algorithm) presents the best efficiency and A₁₂ and A₂₃ methods have an acceptable performance. However, the worst performance belongs to A₂ and A₁₈ methods. Finally, we have obtained the performance of the abovementioned methods on large instances in which the A₂₃ method presents the best performance and A₃ and A₃₈ methods have an acceptable performance. However, the worst performance belongs to both A₁₁ and A₁₃ methods.

Similarly, the number of violated soft constraints has been presented for ITC-2007 instances in Table 12. In general, A₂₄, A₃₀ and A₃₈ methods have appropriate efficiency over C05-C08 and C13-C18 instances because they do not violate any soft constraints. In addition, the performance for these methods is degraded over other instances. Here, the order of superiority of methods is A₃₈, A₂₅ and A₃₀. Hereto, the method A₃₂ yields the best performance while A₃₈, A₂₇ and A₃₆ methods show appropriate performances. Meanwhile, we realized that the A₂₃, A₃₂ and A₃₈ methods outperformed other methods in all instances.

Table 13 presents a summary of the results to evaluate the performance of the IPGALS algorithm in comparison with other methods. The number of violated soft constraints in the best case is presented for the average of all instances in each method. Here, results for both BenPaechter and ITC-2007 benchmarks are reported based on the difference in the number of violated soft constraints. In addition, comparisons have also been conducted in terms of the number of instances, which the IPGALS algorithm performance is superior to other methods. Negative values refer to the no-superiority of the IPGALS algorithm over any of the compared methods. It is worth-mentioning the methods whose results are not reported in this comparison have not been used to calculate results in some instances.

Table 13 Summary of the results to evaluate the performance of the IPGALS algorithm compared to other methods

The results of this comparison show that in all instances except A₂₃ (for BenPaechter benchmark) and A₃₂, A₃₇ (for ITC-2007 benchmark), the IPGALS algorithm performs better than the other methods. This superiority is clearly evident in both the average of violated soft constraints and the number of instances with lower number of violated soft constraints. The best IPGALS results are obtained compared to A₂ in the BenPaechter, where 187 is less violated constraints and is superior in all 10 instances. In addition, IPGALS reports the best results compared to the A₃₁ at ITC-2007, where the number of violated constraints is 551 less, and it performs better in 23 out of the 24 instances.

5.7 Time complexity for IPGALS

Studenovský [51] showed that the time complexity of UCTP was initially O(n⁴). In general, UCTP parameters include: set of events, $E=\left\{{e}_1,{e}_2,\dots, {e}_{N_e}\right\}$, set of timeslots, T = {t₁, t₂, …, t₄₅}, set of rooms, $R=\left\{{r}_1,{r}_2,\dots, {r}_{N_r}\right\}$, set of students, $S=\left\{{s}_1,{s}_2,\dots, {s}_{N_s}\right\}$ and set of features $F=\left\{{f}_1,{f}_2,\dots, {f}_{N_f}\right\}$. It is clear that these conditions can be verified in a time O(n⁴). However, the proposed IPGALS algorithm for solving UCTP bears less time complexity. The time complexity of IPGALS highly depends on GA. In some cases, GAs are not chaotic, they are stochastic. IPGALS complexity depends on the genetic operators, their implementation (which may have a very significant effect on overall complexity), the representation of the chromosomes, the population size, and obviously on the fitness function. According to the applied operators, the time complexity for the roulette wheel selection is O(N_pop), the uniform crossover is O(N_e), the one-point crossover is O(N_e), the heuristic crossover is O(N_e²), the local mutation is O(N_e), the global mutation is O(N_e), the swap mutation is O(1), the improvement is O(N_e²), the elitism is O(1), the local search is O(LS_iter), and finally the fitness function is O(N_e²N_s). Hence, the time complexity of IPGALS algorithm for UCTP is O(G_maxN_pop(N_e²N_s + LS_iter)). Where, G_max is the number of generations, N_pop is the population size and LS_iter is the number of LS iterations.

However, most GAs are inherently chaotic [50]. So, calculating the time complexity could not be useful and even might be misleading. A better way to measure the time complexity is to actually measuring the run-time and averaging. The performed studies related to the run-time of the compared hybrid methods for UCTP reveal that the algorithms A₁₅, A₂₄ and A₃₈ have less average run-time compared to other methods. The run-time of A₁₅ and A₃₈ algorithms is 825 s and 780 s respectively in the BenPaechter benchmark and the run-time of A₂₄ and A₃₈ algorithms is 482 s and 546 s in the ITC-2007 benchmark (average for all instances). Since many algorithms have not been investigated the run-time factor in their studies, this comparison has been conducted only among some of the algorithms.

6 Conclusion and future work

In this study, a new method has been presented for solving UCTP based on a hybrid approach. We have presented an enhanced variant of GA and called it IPGALS. This algorithm is an improved PGA combined with LS. In IPGALS, the hard and soft constraints have been applied for determining the feasible solutions. In addition, the DF criterion has been applied to identify the distance to the feasibility of solutions. DF criterion reduces the number of violated hard constraints and improves the quality of solutions. GA is an efficient solution for the UCTP due to its multi-directional search characteristic. Since GA focuses more on the extraction, it might be failed by getting stuck in the local optimum. In this paper, LS and the elitism operator are implemented after applying crossover and mutation operators in GA to enhance its performance and prevent getting stuck in the local optimum trap. The use of parallel structure also significantly accelerates GA convergence and diversifies the genetic populations. Experimental results reveal that the proposed IPGALS algorithm provides higher-quality solutions compared to other similar methods.

Unfortunately, our IPGALS has not always been able to form a feasible timetable for the some large instances. Therefore, the major shortcoming of IPGALS is that it is unable to assure the offering a feasible timetable in large instances. However, the proposed hybrid algorithm has yielded acceptable results in creating the feasible timetable for UCTP. Further analyzing the contribution of individual components (local search and guided search) for enhancing the performance of IPGALS is considered as a future direction. Additionally, improvement of genetic operators and new neighborhood techniques based on different constraints can be investigated. It is demonstrated that the performance of GA for UCTP would be improved by applying advanced genetic and heuristic operators. The correct relationship between these techniques and their proper arrangement in a GA might lead to higher performance.

Appendix

Full names of applied algorithms (A_i) in Tables 11, 12 and 13. A₁: (RIICN: Randomize Iterative Improvement with Composite Nears [52]), A₂: (GBHH: Graph Based Hyper Heuristic [53]), A₃: (HEA: Hybrid Evolutionary Algorithm [54]), A₄: (NLGD: Non-Linear Great Deluge [55]), A₅: (MA: Memetic Algorithm [56]), A₆: (VNS: Variable Neighborhood Search [52]), A₇: (THH: Taboo based Hyper Heuristics [44]), A₈: (LS: Local Search [57]), A₉: (EA: Evolutionary Algorithm [58]), A₁₀: (ACO: Ant Colony Optimization [59]), A₁₁: (FA: Fuzzy Approach [60]), A₁₂: (EGSGA: Extended Guided Search with Genetic Algorithm [20]), A₁₃: (GA w LS: Genetic Algorithm with Local Search [61]), A₁₄: (GA: Genetic Algorithm [25]), A₁₅: (HGA: Hybrid Genetic Algorithm [62]), A₁₆: (RIIA: Randomised Iterative Improvement Algorithm [44]), A₁₇: (HEA: Hybrid Evolutionary Approach [63]), A₁₈: (GHH: Graph-based Hyper Heuristic [53]), A₁₉: (VNS: Variable Neighborhood Search [64]), A₂₀: (TSH: Tabu-Search Hyperheuristic [65]), A₂₁: (FMH: Fuzzy Multiple Heuristic [66]), A₂₂: (GSGA: Guided Search Genetic Algorithm [48]), A₂₃: (HA: Hybrid Algorithm [67]), A₂₄: (HGATS: Hybrid Genetic Algorithm and Tabu Search [68]), A₂₅: (MMH: Mixed Meta-Heuristic [69]), A₂₆: (HA: Hybrid Algorithm [24]), A₂₇: (ACO w ILS: Ant Colony Optimization with Iterative Local Search [59]), A₂₈: (LS: Local Search [26]), A₂₉: (HHADL: Hyper-Heuristic with Add Delete Lists [43]), A₃₀: (GAGLS: Genetic Algorithms with Guided and Local Search [20]), A₃₁: (TDMH: Time-Dependent Meta-Heuristic [70]), A₃₂: (SA: Simulated Annealing [71]), A₃₃: (HH: Hyper-Heuristics [72]), A₃₄: (TS-ILS: Tabu Search And Iterated Local Search [73]), A₃₆: (CB-CTT: Curriculum-Based Course TimeTabling [74]), A₃₇: (RPNS: Random Partial Neighborhood Search [75]), A₃₈: (SAIRL: Simulated Annealing with Improved Reheating and Learning [32]), A₃₉: (IPGALS: Improved Parallel Genetic Algorithm and Local Search (Proposed Algorithm)).