A Simulated Annealing Genetic Algorithm for Solving Timetable Problems
The post-enrolment course timetabling (PE-CTT) is one of the most studied timetabling problems, for which many instances and results are available. In this paper, we design a metaheuristic approach based on Simulated Annealing to solve the PE-CTT. We cons
- PDF / 164,960 Bytes
- 10 Pages / 439.37 x 666.142 pts Page_size
- 48 Downloads / 212 Views
Abstract The post-enrolment course timetabling (PE-CTT) is one of the most studied timetabling problems, for which many instances and results are available. In this paper, we design a metaheuristic approach based on Simulated Annealing to solve the PE-CTT. We consider all the different variants of the problems that have been proposed in the literature and perform a comprehensive experimental analysis on all the public instances available. The outcome is that the solver, properly engineered and tuned, performs very well in all cases. Thus we provide the new best known results for many instances and state-of the-art values for the others. An algorithm SAGA for solving timetable problem was presented by analyzing all kinds of restricting conditions and special requirements in timetable arrangement of colleges and universities. Moreover, the crossover and mutation operators in the simulated annealing genetic algorithm were improved with adaptive strategy in order to enhance its searching ability and efficiency of the algorithm. The numerical experiments showed that the algorithm was efficient and feasible. Keywords Course timetabling Metaheuristics
·
Genetic algorithms
·
Simulated annealing
·
1 Introduction The timetabling of events [1] (such as lectures, tutorials, and seminars) at universities in order to meet the demands of its users is often a difficult problem to solve effectively. As well as wanting a timetable that can actually be used by the institution, users will also want a timetable that is “nice” to use and which doesn’t overburden the people who will have to base their days’ activities around it. Timetabling is also Y. Dun (B) · Q. Wang · Y. Shao School of Mathematics and Computer Technology, Northwest University for Nationalities, Lanzhou 730030, China e-mail: [email protected]
B.-Y. Cao and H. Nasseri (eds.), Fuzzy Information & Engineering and Operations Research & Management, Advances in Intelligent Systems and Computing 211, DOI: 10.1007/978-3-642-38667-1_36, © Springer-Verlag Berlin Heidelberg 2014
365
366
Y. Dun et al.
a very idiosyncratic problem that can vary between different countries, different universities, and even different departments. From a computer- science perspective, it is therefore a problem that is quite difficult to study in a general way. Educational timetabling is a sub-field of timetabling that considers the scheduling of meetings between teachers and students. In the middle of 1970s, the authors demonstrated that the timetable problem is a NP complete problem [1] with other researchers. In the 1990s’, Colorni et al. [2] using genetic algorithms (GAs) to solve the timetable problems. Sigeru [3] using GAs to solve the problem of university timetable arrangements by the way of adds control constraints. Zhang Chunmei [4] introduced the Adaptive genetic algorithms for solving the university timetable problem, they divided the university courses into Several categories such as compulsory, elective, minor and Solving respectively, and have achieved good results. Ye Ning et
Data Loading...
