A Hybrid Immune Genetic Algorithm to Solve University Time Table Problems

Pongsarun BOONYOPAKORN; Phayung MEESAD

Authors

Pongsarun BOONYOPAKORN Department of Information Technology, Faculty of Information Technology, King Mongkut’s University of Technology North Bangkok, Bangkok 10800
Phayung MEESAD Department of Information Technology Management, Faculty of Information Technology, King Mongkut’s University of Technology North Bangkok, Bangkok 10800

Keywords:

Timetabling problems, scheduling problems, artificial immune, genetic algorithm, hybrid immune

Abstract

Timetabling problems are complex optimization tasks which can be difficult to solve, especially when trying to achieve the optimal results. Moreover, they are also known to be NP-hard (Non-deterministic Polynomial-time hard) problems. Usually, problems are defined as assigning a set of lectures to a fixed number of timeslots and rooms such that they satisfy a number of hard and soft constraints. Genetic algorithm (GA) is an approach to optimize learning based on the principles of biological evolution. In the past, GA have been applied to solve instances of timetabling which are combined with various techniques and optimization operators to optimal realistic requirements. In this paper, a new genetic hybrid algorithm which includes an artificial immune system called the Immune Genetic Algorithm (IGA) is proposed. This method mainly aims to construct a feasible timetabling which satisfies all constraints as best as possible. The main idea of this paper is to reduce the number of initial chromosomes to a local search space. In addition, the author has also compared the results with Genetic Algorithm (GA), Immune Algorithm (IA), and Practical Swarm Optimization (PSO) to illustrate that the IGA produces good quality solutions and outperforms similar methods.

Downloads

Download data is not yet available.

Metrics

Metrics Loading ...

References

MM Javidi, RH Fard and M Jampour. Research in random parameters of genetic algorithm and its application on TSP and optimization problems. Walailak J. Sci. & Tech. 2015; 12, 27-34.

A Salwani and T Hamza. Generating university course timetable using genetic algorithms and local search. In: Proceedings of the 3rd International Conference on Convergence and Hybrid Information Technology. Busan, South Korea, 2008, p. 254-60.

C Wutthipong, K Soradech and S Nidapan. Performance comparison of genetic algorithm’s crossover operators on university course timetabling problem. In: Proceedings of the 8th International Conference on Computing Technology and Information Management. Seoul, South Korea, 2012, p. 781-6.

TBH Thi, DP Quang and DP Duy. Genetic algorithm for solving the master thesis timetabling problem with multiple objectives. In: Proceedings of the Conference on Technologies and Applications of Artificial Intelligence. Tainan, Taiwan, 2012, p. 74-9.

S Alves, S Oliveira and A Neto. A novel educational timetabling solution through recursive genetic algorithms. In: Proceedings of the Latin America Congress on Computational Intelligence. Curitiba, Brazil, 2015, p. 1-6.

I Supachate. A noval approach of genetic algorithm for solving examination timetabling problems: A case study of Thai Universities. In: Proceedings of the 13th International Symposium on Communications and Information Technologies. Surat Thani, Thailand, 2013, p. 233-7.

J Sheung, A Fan and A Tang. Time tabling using genetic algorithm and simulated annealing. In: Proceedings of the IEEE Region 10 Conference on Computer, Communication, Control and Power Engineering. Beijing, China, 1993, p. 448-51.

SC Chu and HL Fang. Genetic algorithms vs. Tabu search in timetable scheduling. In: Proceedings of the 3rd International Conference Knowledge-Based Intelligent Information Engineering Systems. Adelaide, Australia, 1999, p. 492-5.

S Vinayak, R Kaushik and B Sivaselvan. Time table scheduling using genetic algorithms employing guided mutation. In: Proceedings of the Computational Intelligence and Computing Research. Coimbatore, India, 2010, p. 1-4.

B Nguyen, T Nguyen and T Tran. A new hybrid GA-Bees algorithm for a real-world university timetabling problem. In: Proceedings of the Intelligent Computation and Bio-Medical Instrumentation. Hubei, China, 2011, p. 321-6.

S Meysam, S Mohammad and S Hedieh. A fuzzy genetic algorithm with local search for university course timetabling. In: Proceedings of the Data Mining and Intelligent Information Technology Applications. Macao, China, 2011, p. 250-4.

PV Om, G Rohan and SB Vikram. Optimal time-table generation by hybridized bacterial foraging and genetic algorithm. In: Proceedings of the Communication Systems and Network Technologies. Rajkot, India, 2012, p. 919-23.

LN de Castro and J Timmis. Artificial immune systems: A novel paradigm to pattern recognition. In: JM Corchado, L Alonso and C Fyfe (eds.). Artificial Neural Networks in Pattern Recognition. University of Paisley, UK, 2002, p. 67-84.

S Juan, DS Yi and X Min. Reach on application of IGA (Immune Genetic Algorithm) to the solution of course-timetabling problem. In: Proceedings of the Computer Science & Education. 2009, p. 1105-9.

AR Hafizah, I Zaidah and MH Naimah. Bipartite graph edge coloring approach to course timetabling. In: Proceedings of the Information Retrieval & Knowledge Management. Selangor, Malaysia, 2010, p. 229-34.

J Zhou. Revisiting negative selection algorithms. J. Evol. Comput. 2007; 15, 223-51.