Printer Friendly

A NNIA Scheme for Timetabling Problems.

1. Introduction

The examination timetabling problem has long been a challenging area for researchers in the fields of operational research and artificial intelligence, especially at the time that the Toronto benchmark dataset was stated by Carter and Laporte (1996) [1]. The problem has been more difficult because universities are recruiting more students into a larger variety of courses with a growing number of combined degree courses [2] (Merlot et al. 2002). In the past 40 years there are many methods that have been applied to this problem. The represented techniques include constraint-based techniques [3], population-based techniques including genetic algorithms [4], graph coloring techniques [5, 6], ant colony optimization [7], scatter search [8], local search methods including tabu search [9] and simulated annealing [10, 11], variable neighborhood search [12], and hybrid and hyperheuristic approaches [5]. Generally, this problem is modeled as a single-objective optimization problem; only the number of clashes is considered by researchers.

To minimize the number of clashes in an exam timetable, Burke and Newall (2005) [13] stated that the clashes can be eliminated if a large number of periods were allocated. Burke et al. (1998) [14] also stated that longer timetables are needed to decrease the number of clashes. It is obvious that the ETTP is definitely a two-objective optimization problem: the number of clashes and the number of periods. Within the reasonable scope of the number of periods, the number of clashes must be minimized as much as possible. Hence, it is needed to minimize multiple conflicting cost functions, which can be best solved through the method of multiobjective optimization [15] that imported several features from the research on the graph coloring problem and used a variable-length chromosome representation that this paper also adopts.

Evolutionary multiobjective optimization (EMO), whose main goal is to handle multiobjective optimization problems (MOPs), has become a hot topic in the field of evolutionary computation. By simultaneously optimizing more than one objective, Multiobjective Optimization Evolutionary Algorithms (MOEAs) can acquire a set of solutions considering the influence of all the objective functions. Each of those solutions cannot be said better than the other and corresponds to the tradeoffs between those different objectives. Multiobjective examination timetabling problem as a MOP has two contradictory objectives. The optimization of one objective tends to minimize the number of clashes; the other objective tends to decrease the number of time periods. Many MOEAs have been proposed in recent years. Malim et al. (2006) [16] studied three different Artificial Immune systems and indicated that the algorithms can be appropriate for both course and exam timetabling problems. However, after published they were found to represent a mistake in the code, and it is invalid [17].

Many of the existing methods for exam timetabling problems are applicable to single-objective exam timetabling problems. By calculation, these single-objective optimization algorithms only can obtain one result, and the computational efficiency is poor. In this paper, we proposed a novel MOEA-based approach for multiobjective examination timetabling problem. By calculation, multiple results can be obtained by our proposed algorithms. In order to simultaneously optimize the two objectives, we adopt the framework of multiobjective immune algorithm NNIA [18] with some modifications. The NNIA simulates the phenomenon of the multifarious antibodies symbiosis and a small number of antibody's activation in the immune response according to a method of selecting the nondominated neighborhood individuals. It chooses the small number of relatively isolated individuals as active antibodies and clones according to the crowding-distance value and then applies on the operators of recombination and mutation to strengthen the searching of the sparse area of the pareto front. The reasons we adopt the frame of the NNIA are that NNIA is proposed by ourselves and the clone strategy can make the pareto front uniform and get the satisfied solutions. The main contributions are that we adopt elitism group strategy to keep the diversity of the group and the two vertical local search operators to get the optimized solutions. Experiments show that the proposed algorithm is able to find a set of tradeoff solutions between the two objectives.

The paper is organized as follows. Section 2 describes the background information with problem formulation and related works. Section 3 gives a description of the proposed algorithm in detail. Section 4 presents the experimental study. Finally, conclusions are given in Section 5.

2. Background

2.1. Mathematical Model. As previously mentioned, the format of examination timetabling problems described in this paper was first formulated by Carter and Laporte [1] in 1996. In this problem, a set of exams E = {[e.sub.1], [e.sub.2], ..., [e.sub.[absolute value of E]}] need to be scheduled into a set of periods P = {1, 2, ..., [absolute value of P]} with each period having a seating capacity s. There are three periods per weekday and a Saturday morning period. No exam is held on Sundays. It is assumed that the exam period starts on a Monday. The problem can be formally specified by first defining the following:

[mathematical expression not reproducible] (1)

min [absolute value of P] (2)

[mathematical expression not reproducible] (3)

[[absolute value of P].summation over (p=1)] [a.sub.ip] [less than or equal to] 1, [for all]i [member of] {1, ..., [absolute value of E]]}, (4)

where [a.sub.ip] is one if exam [e.sub.i] is allocated to period p; otherwise, [a.sub.ip] equals zero. [c.sub.ij] is the number of students registered for exams [e.sub.i] and [e.sub.j].

Equations (1) and (2) are the two objectives of minimizing the number of clashes and timetable length, respectively. Equation (3) is the constraint that no student is to be scheduled to take two exams at any one time, while (4) states that every exam can only be scheduled once in any timetable.

To evaluate the quality of one feasible timetable, a function evaluating the average cost for per student based on soft constraints has been proposed. It can be presented as follows:

fitness = ([[summation.sup.4.sub.s=0]] [[omega].sub.s] x [N.sub.s]/S), (5)

where [[omega].sub.s] = [2.sup.s] (s = 0, 1, 2, 3, 4) is the weight that represents the importance of scheduling exams with common students either 4, 3, 2, 1, or 0 timeslots away in one timetable and Ns is the number of students involved in the violation of the soft constraint. S is the total number of students in the problem. For this reason that (5) emphasizes the most important indicators, that is, whether the exams in the timetable are allocated throughout the timetable equally, we use this function as one of the objectives in our algorithm. The two objectives of our algorithm optimized are described as follows:

min [f.sub.1] = [absolute value of P]

min [f.sub.2] = ([[summation.sup.4.sub.s=0]] [[omega].sub.s] x [N.sub.s]/S). (6)

2.2. Related Works. The ETTP is a semiannual or annual problem for colleges and is studied by many operational researches widely due to its complexity and utility. There have been proposed a large range of approaches to solve the problem, discussed in the existing literature. These approaches can be classified into the following broad categories [19]: graph-based sequential techniques, local search-based techniques, population-based techniques, and hyperheuristics.

The graph coloring heuristics are one of the earliest algorithms. Welsh and Powell [20] in 1967 proposed abridge that is built between graph coloring and timetabling and made a great contribution to the field of the timetabling. The five ordering strategies which extended from graph coloring heuristics on examination timetabling problems and a series of examination timetabling problems were introduced by Carter, Laporte, and Lee in 1996, called University of Toronto Benchmark Data. By developing two variants of selection strategies, Burke et al. [21] studied the influence of bringing a random element into the employment of graph heuristics in 1998. These simple strategies showed improved pure graph heuristics on the sides of both the quality and diversity of the solutions when tested on three of the Toronto datasets. Asmuni et al. [22] in 2005 employed fuzzy logic to order the exams to be scheduled on account of graph coloring heuristics on the Toronto datasets and indicated that it is an appropriate evaluation for arranging the exams. Corr et al. [23] investigated a neural network, the objective of which is to arrange the most difficult exams at an early stage of solution construction. The work has showed the feasibility of using neural network as a generally adaptive applicable technique on timetabling problems.

The local search-based techniques represent a large portion of the work which has appeared in the last decade [1]. Mainly because various constraints can be handled relatively easily, they have been applied on a variety of timetabling problems. Di Gaspero and Schaerf (2001) [24] carried out a valuable investigation on a family of tabu search based techniques whose neighborhoods concerned those which contributed to the violations of hard and soft constraints. Burke et al. [5] investigated variants of Variable Neighbourhood Search and obtained the best results in the literature across some of the problems in the Toronto datasets. Caramia et al. [25, 26] developed a fine-tuned local search method where a greedy scheduler assigned examinations into the least timeslots and a penalty decrease improved the timetable without increasing the number of timeslots.

The genetic algorithm is one of the most typical representatives of the population-based techniques. It is noticed that the algorithm has a good performance in the literatures. Particularly, the hybridizations of genetic algorithms with local search methods, memetic algorithms, have an excellent performance in this area. In 1994, Corne et al. [27] introduced genetic algorithms to solve general educational timetabling problems. The function of this work is that certain problem structures in some particularly generated graph coloring problems cannot be handled by obtaining direct representation in the genetic algorithms. Ross et al. [28] in 1996 indicated that by testing on specially generated graph coloring problems of different homogeneity and connectivity the transition regions were existent in solvable timetabling problems. The study can make researchers understand how different algorithms perform on complex timetabling problems. Terashima-Marin et al. [29] in 1999 indicated a clique-based crossover on the timetabling problems which was turned into graph problems. Erben [30] (2001) indicated a grouping genetic algorithm with appropriate encoding, crossover and mutation operators, and fitness functions studied. This method requires less computational time than some of the methods in the literature. Burke and Landa Silva [31] discussed some issues concerning the design of memetic algorithms for scheduling and timetabling problems. Burke et al. [21] developed a memetic algorithm to reassign single exams and sets of exams and employed light and heavy mutation operators. However, neither of these mutations on their own improved the solution quality. Malim et al. [16] developed three variants of Artificial Immune systems and indicated that the algorithms can be suitable for course and exam timetabling problems. However, there was a problem in the results; after publication they were showed to represent an error in the code and invalidness.

More and more researchers pay attention to the hyperheuristics approach. In 2003 Ahmadi et al. [32] investigated a variable neighborhood search, aiming to find good combinations of heuristics for different examination timetabling problem. Kendall and Hussin [33] in 2005 developed a tabu search hyperheuristic; they adopted moving strategies and constructive graph heuristics to be the low level heuristics. In 2007 Burke et al. [5] researched obtaining tabu search to find sequences of graph heuristics to construct solutions for timetabling problems and considered the effects of various numbers of low level graph heuristics on the examination timetabling problems. By conducting an empirical study on both benchmark functions and exam timetabling problems, Bilgin et al. [34] (2007) studied 7 heuristic selection methods and 5 acceptance criteria within a hyperheuristic. The memetic algorithm hyperheuristic with a single hill climber at a time showed that it performed better on approaches tested. For the interested readers, more details can be referred from [5].

In summary, during the recent years, there are an increasing number of excellent algorithms; almost all of these algorithms were tested on either benchmark datasets or in real applications, which had made quite good achievements. In this paper, we also proposed a multiobjective optimization algorithm, called Nondominated Neighbor Immune Algorithm (NNIA) in [18]. NNIA adopts an immune inspired operator, a nondominated neighbor-based selection technique, two heuristic search operators, and elitism. It indicates that NNIA is an effective method for solving MOPs by a number of experiments. Due to its good performance, we will adopt the framework of NNIA with some modifications, which will be described in the following section. The contribution of this paper is that we solve this task by using multiobjective optimization technique.

3. The Proposed Algorithm

3.1. Algorithmic Flow of MOEA Based on NNIA. The algorithmic flow of our algorithm is presented in Figure 1. At the start of the algorithm, a conflict matrix C was created according to Burke and Newall [13], which has dimensions [absolute value of E] by [absolute value of E] with the definition from Section 2.1 being its (i, j)th element. This matrix can check and eliminate the conflicts in the timetables efficiently.

Because of the large-scale individual of the population, it is inadvisable to search in the normal population. Elitism strategy and crowded selection optimization mechanism are put forward. In our algorithm we adopt elitism strategy two times to reduce the computation burden and extend the range of nondominated solutions in elitism group. In the normal population, the children population after crossover and mutation is mixed with parent population. Then the nondomined solutions of this new population are put into the elitism group. The purpose of the strategy is to offer more nondominated solutions to the elitism group.

3.2. Hyper-Heuristic Initialization. As a common step, initialization is to produce an initial population. In our algorithm, there are a large number of feasible solutions that need to be optimized, but the process of generating the feasible solutions is hard for most of the examination timetabling problems. The difficulty level that feasible solutions generated for different examination timetabling problems is different. It is hard to make some unfeasible solutions be the feasible ones with some conventional ways in the subsequent operation. The result of the algorithm is influenced by the number of feasible solutions in the initial population for some issues. The initialization in our algorithm produces a set of solutions randomly and updates the random solutions to be the feasible ones with the simple genetic algorithm. The details are shown in the following.

The hyperheuristic initialization is that the exams are selected for insertion with the help of some heuristic information when used in the graph coloring problem [21,35]. The heuristics we use in this paper are as follows:

(1) Largest degree (LD): exams with the largest number of conflicts with other exams are inserted first.

(2) Largest weighted degree (LWD): it is the same as LD but weighted by the number of students involved.

(3) Saturation degree (SD): exams with the fewest valid timeslots, in terms of satisfying the hard constraints, remaining in the timetable are inserted first.

There are two terminated conditions, maximum iteration number and the maximum number of feasible solutions, which can make the whole algorithm achieve the stable result for most examination timetabling problems. But our algorithm has obvious superiority for the problems that the feasible solutions are hardly generated, because of this strategy of the initialization. The advantage of the hyperheuristic initialization is that we can get the timetables with the lengths being close to the demands of the users. The result can be seen in the next section.

3.3. Local Search Operators. Some researchers indicated that adopting local search within evolutionary algorithms is an much effective approach for finding high quality exam timetables which can also contribute to the intensification of the optimization results [36, 37]. A description of the two-direction local search operators this paper adopted is given below.

The first kind is to minimize the timetable length as far as possible without concerning the conflict number, aiming at the operator in the local search to minimize the time periods among the nondominated elitism group.

The selected individual is P, the search depth is SD, the maximum mutation probability is [P.sub.max], the original mutation probability is [P.sub.ori], the probability increasing step length is r, the exam timetable is T, the maximum iteration number is Itermax, and the number of examinations is [E.sub.num].

Step 1. Set the original mutation probability [P.sub.ori].

Step 2. Set search depth variable sign V = 0.

Step 3. Randomly select [[P.sub.ori] x [E.sub.num]] exams in E, which is denoted as [E.sub.m]. Delete all the selected exams in E.

Step 4. Rearrange the exams in [E.sub.m] according to the maximum number of conflicts and the timeslots in T according to the heuristics. Then insert the exams in [E.sub.m] into the timetable T; if you can not insert them into the inherent timeslots, extend the timeslots until all exams are arranged; the newly produced timeslots are [].

Step 5. If the number of [] is less than the number of T, replace T with [], and stop; otherwise, V = V + 1, and go to Step 3.

Step 6. If V = depth, then [P.sub.ori] = [P.sub.ori] + r and go to Step 2.

Step 7. If [P.sub.ori] = [P.sub.max], compare the timeslots of [] and T; then put the smaller one into the elitist group and stop; otherwise, go to Step 6 and go on.

The second kind aims at minimizing the number of conflicts without concerning the number of timeslots. The details are described below.

The selected probability is P, the search depth is SD, the maximum selected probability is [P.sub.max], the original mutation probability is [P.sub.ori], the probability increasing step length is r, the exam timetable is T, the maximum iteration number is Itermax, and the number of examinations is [E.sub.num].

Step 1. Set the original examination selected probability [P.sub.ori] = P.

Step 2. Set search depth variable sign V = 0.

Step 3. Randomly select [[P.sub.ori] x [E.sub.num]] exams in E and the newly set [E.sub.temp].

Step 4. Rearrange exams in [E.sub.temp] according to the number of conflicts, delete all the exams in [E.sub.temp], and sort all the timeslots in the changed timetable T.

Step 5. Insert the exams in [E.sub.temp] into the timetable T at the premise of not affecting the number of timeslots; the newly produced individual is [].

Step 6. Compare the number of conflicts in [] with which, in T according to the formulation, if the former is smaller, replace original individuals with [] and then stop. Otherwise, V = V + 1; go to Step 3.

Step 7. If V = SD, judge the number of conflicts in [] and T; if the former is smaller, replace T with []; put the smaller one into the elitist group; otherwise, P = P + r; go to Step 2.

Step 8. If P = [P.sub.max], judge the number of conflicts in [] and T; if the former is smaller, replace T with []; then put the smaller one into the elitist group; otherwise, T remain unchanged.

3.4. Diversity-Keeping Operators

3.4.1. Elitism Group Strategy. Although the local search can intensify the optimization results, the discrete optimization is different from the continuous optimization that a small disturbance in decision domain may probably let individuals transform irregularly and even result in deterioration. As such, in order to avoid this phenomenon we put forward a novel local search exploitation with an extra elitism group to save nondominated solutions in every generation. However, normal population is just offering a space of updating the nondominated solutions. In our algorithm we also introduce a corresponding elitism strategy and a crowded selection optimization mechanism; the details will be introduced in the next part.

The local search operators are applied after the strategy of extension and optimization of the elitism group. The operators avoid an objective in an individual deterioration and then minimize the other objective and get the new elitist solutions mixed with original elitist solutions to conduct a nondominated sorting. The frontier may extend to the two different directions as far as possible according to the operators. The local search is searching vertically between two objectives in order which is shown as Figure 2. It indicates that one objective is optimized prior and then the other is shown as rout A or rout B of the individual i in the figure.

3.4.2. Extension Optimization Strategy. Due to the normal selection and mutation operators making a little contribution to the nondominated elitism group, we present a strategy to extend and optimize the elitism group based on the congestion degree which is shown in Figure 3. Compute the difference of timetable length between every individual and its right side one. If the D-value is 1, then extend a time period of this individual and randomly select some exams into the time period. We can get a uniform frontier by this means. As is shown in Figure 3, the crowding degree of individual i is the length of the line segment AB. Assume that the crowding degree of individual i is 2; according to our theory, expend the individual i and get i' and then put it into the original elitism group. Finally, we take local search operators to the generations after extending the time periods.

4. Experimental Analysis

Our algorithm is programmed in Matlab and simulations are performed on the 2.8 GHz Core Personal Computer. We use 9 uncapacitated benchmark examinations timetabling datasets proposed by Carter and Laporte [1] to evaluate the effectiveness of our algorithm. The details of the proposed benchmarks are shown in Table 1. As no dataset is designed to evaluate the multiobjective timetabling algorithms, we just use the datasets used in the single objective to evaluate the feasibility and reasonableness of our algorithm. The parameter settings are presented in Table 2. The population size is 100 and the maximum iteration is 100. The other parameters' choosing reason will be described in the following parts.

In the following sections, we will study our algorithm in two sides. One is to make analysis on the contribution of diversity-keeping local search operators searching in two different directions orderly which is shown with four comparative experiments. The other one is to discuss the contribution of elitism group strategy applied on our algorithm two times with four experiments presented.

4.1. Contribution of Diversity-Keeping Strategy. This section presents the performance of the diversity-keeping operators. To assess the effectiveness of the strategies, a comparison was conducted as in Figure 4. with E is saying that the algorithm runs with the strategies while without E is indicating that the algorithm runs without the strategies. The boxplots were drawn according to the statistic number of solutions. The eight data in this experiment were running ten times independently. From Figure 4, it can be observed obviously that the operator of with E does better than without E does in every dataset. The results well proved the efficiency of diversity-keeping operator.

4.2. Contribution of Local Search Operators. In this section, we use the hypervolume as an indicator to estimate the effectiveness of the algorithm; in our comparable experiments the indicator rp is the maximum value of the dataset to be compared in all dimensions.

To prove the efficiency of the proposed two local search operators, this section shows the performance of the algorithms with and without local search operators. As is shown in Figure 5, none is the setting that does not use local search at all, and with F is the setting with the local search aiming at minimizing the conflict number, while the setting with S is the local search to minimize the timeslots and double incorporates two local search operators. Ten independent runs of the four settings are conducted to obtain statistical results. From Figure 5, the contribution of local search operators is obvious, since the operators which use two local search are able to generate solutions with significantly lower number of clashes. For the hypervolume value of the nondominated solutions of datasets Ute92, Sta83, Lse91, Kfu93, Hec92, and Ear83, the application of the two local search settings shows better results than other three settings.

From the statistic boxplots we can see that our algorithm is robust to the indicator of the students conflict numbers. The outliers are few and the differences between the highest and the lowest values are small, which also demonstrate the robustness of our algorithm.

4.3. Performance of Multiobjective Algorithm Based on NNIA. This section presents the multiobjective optimization performance of the algorithm based on NNIA. On top of showing the advantages of our algorithm, the role of the two objectives will be validated as follows. The experiment was conducted running ten times independently.

The boxplots in Figure 6 show the number of pareto optimal solutions of the eight datasets. The number of pareto optimal solutions for the dataset ute92 is nearly four. The number of pareto optimal solutions for other datasets is almost distributed from seven to ten.

Experiments were conducted to further show the results. From Figure 7, we can see the details of both the number of periods and its corresponding clashes. All of the datasets tested perform good, the pareto optimal solutions are distributed uniformly, and the clashes are relatively small. The experiments support our algorithm powerfully and the multiobjective exam timetabling problem is solved well.

5. Conclusions

In this paper, the exam timetabling problem has been regarded as a multiobjective optimization problem which involves the minimizing of the number of clashes and number of periods in a timetable. A multiobjective evolutionary algorithm, based on NNIA, featured with elitism group strategy, congestion degree based on extension optimization strategy, and two local search operators, has been presented.

The proposed MOEA is different from most existing single-objective-based methods in the fact that it optimizes two objectives concurrently and get a set of solutions reasonable instead of producing single-length timetables. It has been proved that such an approach is more universal and would be able to function effectively. The results also show that the algorithm can generate relatively short clash-free timetables and various solutions which are convenient for deciders to choose on their own preference.

The work we do in this paper focuses on the temporal aspect of the ETTP, which has solved the problem well in a sense. However, it still has some shortcomings, how to balance the diversity and approximation, which can be subjected for future study.

Conflicts of Interest

The authors declare that they have no conflicts of interest.


[1] M. W. Carter and G. Laporte, "Recent developments in practical examination timetabling," in Proceedings of the 1st International Conference on Practice and Theory of Automated Timetabling, E. K. Burke and P. Ross, Eds., vol. 1153 of Springer Lecture Notes in Computer Science, pp. 3-21, 1996.

[2] L. T. G. Merlot, N. Boland, B. D. Hughes, and P. J. Stuckey, "A hybrid algorithm for the examination timetabling problem," in Proceedings of the 4th International conference on the Practice and Theory of Automated Timetabling (PATAT '02), K. Burke and P. De Causmaecker, Eds., vol. 2740 of Lecture Notes in Computer Science, pp. 207-231, Springer, Berlin, Germany, 2002.

[3] T. Muller, "ITC2007 solver description: a hybrid approach," Annals of Operations Research, vol. 172, no. 1, pp. 429-446, 2009.

[4] P. Ross, E. Hart, and E. Corne, "Some observations about GA based exam timetabling," in Proceedings of the 2nd International Conference on Practice and Theory of Automated Timetabling, E. K. Burke and M. W. Carter, Eds., vol. 1408 of Lecture Notes in Computer Science, pp. 115-129, Springer, 1998.

[5] E. K. Burke, B. McCollum, A. Meisels, S. Petrovic, and R. Qu, "A graph-based hyper-heuristic for educational timetabling problems," European Journal of Operational Research, vol. 176, no. 1, pp. 177-192, 2007

[6] N. R. Sabar, M. Ayob, G. Kendall, and R. Qu, "Roulette wheel graph colouring for solving examination timetabling problems," in Proceedings of the 3rd International Conference on Combinatorial Optimization and Applications, vol. 5573 of Lecture Notes in Comput. Sci., pp. 463-470, Springer, 2009.

[7] M. Eley, "Ant algorithms for the exam timetabling problem," in Proceedings of the International Conference on the Practice and Theory of Automated Timetabling (PATAT '07), E. K. Burke and H. Rudova, Eds., vol. 3867 of Lecture Notes in Computer Science (2007), pp. 364-382, Springer.

[8] N. Mansour, V Isahakian, and I. Ghalayini, "Scatter search technique for exam timetabling," Applied Intelligence, vol. 34, no. 2, pp. 299-310, 2011.

[9] G. De Smet, "ITC2007--Examination Track," in Proceedings of the Practice and Theory of Automated Timetabling (PATAT '08), Montreal, Canada, 2008.

[10] E. Burke, Y. Bykov, J. Newall, and S. Petrovic, "A time-predefined local search approach to exam timetabling problems," IIE Transactions, vol. 36, no. 6, pp. 509-528, 2004.

[11] J. M. Thompson and K. A. Dowsland, "A robust simulated annealing based examination timetabling system," Computers and Operations Research, vol. 25, pp. 637-648, 1998.

[12] R. Qu and E. K. Burke, "Hybrid variable neighbourhood hypeheuristics for exam timetabling problems," in Proceedings of the MIC2005: The Sixth Meta-Heuristics International Conference, Vienna, Austria, 2005.

[13] E. K. Burke and J. P. Newall, "Solving examination timetabling-problems through adaptation of heuristic orderings," Annals of Op-erational Research, vol. 129, pp. 107-134, 2005.

[14] E. K. Burke, D. G. Elliman, P. H. Ford, and R. F. Weare, "Specialisedrecombinative operators for the timetabling problem," in Evolutionary Computing: AISB Workshop, pp. 75-85, Springer, Sheffield, UK, 1998.

[15] C. Y. Cheong, K. C. Tan, and B. Veeravalli, "A multi-objective evolutionary algorithm for examination timetabling," Journal of Scheduling, vol. 12, no. 2, pp. 121-146, 2009.

[16] M. R. Malim, A. T. Khader, and A. Mustafa, "Artificial immune-algorithms for university timetabling," in Proceedings of The 6th International Conference on Prac-Tice and Theory of Automated Timetabling, E. K. Burke and H. Rudova, Eds., pp. 234-245, Brno, Czech Republic, August 2006.

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

[18] M. Gong, L. Jiao, H. Du, and L. Bo, "Multiobjective immune algorithm with nondominated neighbor-based selection," Evolutionary Computation, vol. 16, no. 2, pp. 225-255, 2008.

[19] E. K. Burke, J. Kingston, and D. de Werra, "Applications to timetabling," in Handbook of Graph Theory, J. Gross and J. Yellen, Eds., pp. 445-474, Chapman Hall, London, UK, 2004.

[20] D. J. A. Welsh and M. B. Powell, "An upper bound for the chromatic number of a graph and its application to timetabling problems," The Computer Journal, vol. 10, no. 1, pp. 85-86, 1967

[21] E. K. Burke, J. P. Newall, and R. F. Weare, "A memetic-algorithm for university exam timetabling," in Proceedings of the 1st International Conference on the Practice and Theory of Automated Timetabling (PATAT '95), E. K. Burke and P. Ross, Eds., vol. 1153 of Lecture Notes in Computer Science, pp. 241-250, Springer, Edinburgh, Scotland, 1996.

[22] H. Asmuni, E. K. Burke, J. Garibaldi, and B. McCollum, "Fuzzy multipleordering criteria for examination timetabling," in Proceedings of the 5th International Conference on Practice and Theory of Automated Timetabling, E. K. Burke and M. Trick, Eds., vol. 3616 of Springer Lecture Notes in Computer Science, pp. 334-353, 2005.

[23] P. H. Corr, B. McCollum, M. A. J. McGreevy, and P. McMullan, "A newneural network based construction heuristic for the examination time tabling problem," in Proceedings of the International Conference on Parallel Problem Solving From Nature (PPSN), pp. 392-401, Springer, Reykjavik, Iceland, September 2006.

[24] L. Di Gaspero and A. Schaerf, "Tabu search techniques for examination timetabling," in Proceedings of the 3rd International Conference on Practice and Theory of Automated Timetabling III, E. K. Burke and W. Erben, Eds., vol. 2079 of Lecture Notes in Computer Science, pp. 104-117, Springer, Berlin, Germany, 2001.

[25] M. Caramia, P. DellOlmo, and G. F. Italiano, "New algorithms for examination timetabling," in Proceedings of the 4th International Workshop, on Algorithm Engineering (WAE 2000), S. Naher and D. Wagner, Eds., vol. 1982 of Lecture Notes in Computer Science, pp. 230-241, Springer, Berlin, Germany, 2000.

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

[27] D. Corne, P. Ross, and H. Fang, "Evolutionary timetabling: Practice, prospects and work in progress," in Proceedings of the UK Planning and Scheduling SIG Workshop, P Prosser, Ed., 1994.

[28] P. Ross, D. Corne, and H. Terashima-Marin, "The phase transition niche for evolutionary algorithms in timetabling," in Proceedings of the 1st International Conference on Practice and Theory of Automated Timetabling, E. K. Burke and P. Ross, Eds., vol. 1153 of Lecture Notes in Computer Science, pp. 309-324, 1996.

[29] H. Terashima-Marin, P. Ross, and M. Valenzuela-Rendon, "Clique-based crossover for solving the timetabling problem with GAs," in Proceedings of the Congress on Evolutionary Computation, CEC1999, pp. 1200-1206, Washington, DC, USA, July 1999.

[30] W. Erben, "A grouping genetic algorithm for graph colouring and examtimetabling," in Proceedings of the 3rd International Conference on Practice and Theory of Automated Timetabling, E. K. Burke and W. Erben, Eds., vol. 2079 of Lecture Notes in Computer Science, pp. 132-156, Springer, Berlin, Germany, 2001.

[31] E. K. Burke and J. D. Landa Silva, "He design of memetic algorithms forscheduling and timetabling problems," in Proceedings of the Recent Advances in Memetic Algorithms and Related Search Technologies. Studies in Fuzziness and Soft Computing 166, W. E. Hart, N. Krasnogor, and J. E. Smith, Eds., pp. 289-312, Springer, Berlin, Germany, 2004.

[32] S. Ahmadi, R. Barone, P. Cheng, P Cowling, and B. McCollum, "Erturbation based variable neighbourhood search in heuristic space for examination time tabling problem," in Proceedings of the Multidisciplinary International Scheduling: Theory and Applications (MISTA '03), pp. 155-171, Nottingham, UK, August 2003.

[33] G. Kendall and N. M. Hussin, "A tabu search hyper-heuristic approach to the examination timetabling problem at the MARA university of technology," in Proceedings of the 5th International Conference on Practice and Theory of Automated Timetabling, E. K. Burke and M. Trick, Eds., vol. 3616 of Lecture Notes in Computer Science, pp. 199-218, 2005.

[34] B. Bilgin, E. Ozcan, and E. E. Korkmaz, "An experimental study on hyper-heuristics and exam timetabling," in Proceedings of the 6th International Conference on Practice and Theory of Automated Timetabling, E. K. Burke and H. Rudova, Eds., vol. 3867 of Lecture Notes in Computer Science, pp. 394-412, Springer, 2007.

[35] E. K. Burke, D. G. Elliman, P. H. Ford, and R. F. Weare, "Examination timetabling in British universitiesa survey," in Proceedings of The 1st International Conference on the Practice and Theory of Automated Timetabling (PATAT '96), E. K. Burke and P Ross, Eds., vol. 1153 of Lecture Notes in Computer Science, pp. 76-90, Springer, Edinburgh, Scotland, 1996.

[36] Y. Lei, M. Gong, L. Jiao, W. Li, Y. Zuo, and Q. Cai, "A double evolutionary pool memetic algorithm for examination timetabling problems," Mathematical Problems in Engineering, vol. 2014, Article ID 867645,13 pages, 2014.

[37] Y. Lei, M. Gong, J. Zhang, W. Li, and L. Jiao, "Resource allocation model and double-sphere crowding distance for evolutionary multi-objective optimization," European Journal of Operational Research, vol. 234, no. 1, pp. 197-208, 2014.

Yu Lei and Jiao Shi

School of Electronics and Information, Northwestern Polytechnical University, Xi'an, Shaanxi 710072, China

Correspondence should be addressed to Yu Lei;

Received 29 December 2016; Revised 6 March 2017; Accepted 16 March 2017; Published 30 May 2017

Academic Editor: Linqiang Pan

Copyright [C] 2017 Yu Lei and Jiao Shi. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Caption: Figure 1: The flow of algorithm.

Caption: Figure 2: Elitism group local search.

Caption: Figure 3: The computation of congestion degree.

Caption: Figure 4: Performance comparison for MOEA with and without diversity-keeping strategy.

Caption: Figure 5: Performance comparison for MOEA with different local search settings.

Caption: Figure 6: Number of pareto optimal solutions for the datasets.

Caption: Figure 7: Pareto optimal solutions for the datasets.
Table 1: Characteristics of datasets.

Dataset   Timeslots   Exams   Students   Conflict density

Car 91       35        682     16925           0.13
Car 92       32        543     18419           0.14
Ear 83       24        190      1125           0.27
Hec 92       18        81       2823           0.42
Kfu 93       20        461      5349           0.6
Lse 91       18        381      2726           0.6
Rye 92       23        486     11483           0.08
Sta 83       13        139      611            0.14
Tre 92       23        261      4360           0.18
Ute 92       10        184      2750           0.08
York 83     3521       181      941            0.29

Table 2: Parameter setting for simulation study.

Parameter                                              Value

Population size                                         100
E: the number of exams scheduled by each heuristic       2
[P.sub.c]: the crossover probability                    0.8
[P.sub.m]: the mutation probability                     0.2
SD: the search depth of the local search                10
Itermax: the maximum iteration number                   500
COPYRIGHT 2017 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2017 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Lei, Yu; Shi, Jiao
Publication:Journal of Optimization
Article Type:Report
Date:Jan 1, 2017
Previous Article:A Genetic Algorithm Based Approach for Solving the Minimum Dominating Set of Queens Problem.
Next Article:Maximum Lateness Scheduling on Two-Person Cooperative Games with Variable Processing Times and Common Due Date.

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