Generic placeholder image

The Chinese Journal of Artificial Intelligence

Author(s): Jiawei Li* and Tad Gonsalves

DOI: 10.2174/2666782701666220610145137

Cite As
A Variant Genetic Algorithm for a Specific Examination Timetabling Problem in a Japanese University

Article ID: e100622205848 Pages: 12

  • * (Excluding Mailing and Handling)

Abstract

Background: Examination Timetabling Problem that tries to find an optimal examination schedule for schools, colleges, and universities, is a well-known NP-hard problem. This paper presents a Genetic Algorithm variant approach to solve a specific examination timetabling problem common in Japanese colleges and universities.

Methods: The proposed algorithm uses a direct chromosome representation Genetic Algorithm and implements constraint-based initialization and constraint-based crossover operations to satisfy the hard and soft constraints. An island model with varying crossover and mutation probabilities and an improvement approach called pre-training are applied to the algorithm to further improve the result quality.

Results: The proposed model is tested on synthetic as well as real datasets obtained from Sophia University, Japan and shows acceptable results. The algorithm was fine-tuned with different penalty point combinations and improvement combinations.

Conclusion: The comparison results support the idea that the initial population pre-training and the island model are effective approaches to improve the result quality of the proposed model. Although the current island model used only four islands, incorporating a greater number of islands, and some other diversity maintenance approaches such as memetic structures are expected to further improve the diversity and the result quality of the proposed algorithm on large scale problems.

Keywords: Examination timetabling problem, genetic algorithm, direct chromosome representation, Island model, parallel genetic algorithm, evolutionary algorithms, meta-heuristic algorithms.

Graphical Abstract

[1]
Qu, R.; Burke, E.; McCollum, B.; Merlot, L.; Lee, S. A survey of search methodologies and automated system development for examina-tion timetabling. J. Sched., 2008, 12(1), 55-89.
[http://dx.doi.org/10.1007/s10951-008-0077-5]
[2]
Carter, M.; Laporte, G. Recent developments in practical examination time-tabling. In: International conference on the practice and theory of automated timetabling; Springer: Berlin, 1995; 1153, pp. 1-21.
[3]
Thompson, J.; Dowsland, K. Variants of simulated annealing for the examination timetabling problem. Ann. Oper. Res., 1996, 63(1), 105-128.
[http://dx.doi.org/10.1007/BF02601641]
[4]
Thompson, J.; Dowsland, K. A robust simulated annealing based examination timetabling system. Comput. Oper. Res., 1998, 25(7-8), 637-648.
[http://dx.doi.org/10.1016/S0305-0548(97)00101-9]
[5]
Di Gaspero, L.; Schaerf, A. Tabu search techniques for examination timetabling.International Conference on the Practice and Theory of Automated Timetabling; Springer: Berlin, 2020, pp. 104-117.
[6]
Abdullah, S.; Ahmadi, S.; Burke, E.; Dror, M.; McCollum, B. A tabu-based large neighbourhood search methodology for the capacitated examination timetabling problem. J. Oper. Res. Soc., 2007, 58(11), 1494-1502.
[http://dx.doi.org/10.1057/palgrave.jors.2602258]
[7]
Naji Azimi, Z. Hybrid heuristics for examination timetabling problem. Appl. Math. Comput., 2005, 163(2), 705-733.
[http://dx.doi.org/10.1016/j.amc.2003.10.061]
[8]
van Laarhoven, P.; Aarts, E. Simulated annealing. Simulated annealing: Theory and applications; Springer: Dordrecht, 1987, pp. 7-15.
[http://dx.doi.org/10.1007/978-94-015-7744-1_2]
[9]
Tuson, A.; Glover, F.; Laguna, M. Tabu search. J. Oper. Res. Soc., 1999, 50(1), 106.
[http://dx.doi.org/10.2307/3010402]
[10]
Galletly, J.E. An overview of genetic algorithms. Kybernetes, 1992, 21, 26-30.
[http://dx.doi.org/10.1108/eb005943]
[11]
Dorigo, M.; Gambardella, L.M. Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Trans. Evol. Comput., 1997, 1(1), 53-66.
[http://dx.doi.org/10.1109/4235.585892]
[12]
Eley, M. Ant algorithms for the exam timetabling problemInternational Conference on the Practice and Theory of Automated Timetabling; Springer: Berlin, 2006, 3867, pp. 364-382.
[13]
Mandal, A.K.; Kahar, M.N.M. Solving examination timetabling problem using partial exam assignment with great deluge algorithm. Inter-national Conference on Computer, Communications, and Control Technology, 2015, (I4CT), pp. 530-534.
[http://dx.doi.org/10.1109/I4CT.2015.7219635]
[14]
Song, Y.; Wan, F.; Chen, X. An improved genetic algorithm for numerical function optimization. Appl. Intell., 2019, 49(5), 1880-1902.
[http://dx.doi.org/10.1007/s10489-018-1370-4]
[15]
Rozaimee, A.; Shafee, A.; Hadi, N.; Mohamed, M. A framework for university’s final exam timetable allocation using genetic algorithm. World Appl. Sci. J., 2017, 35(7), 1210-1215.
[16]
Shatnawi, A.; Fraiwan, M.; Al-Qahtani, H.S. Exam scheduling: A case study. 2017 Ninth International Conference on Advanced Compu-tational Intelligence (ICACI), 2017, pp. 137-142.
[http://dx.doi.org/10.1109/ICACI.2017.7974498]
[17]
Dener, M.; Calp, M.H. olving the exam scheduling problems in central exams with genetic algorithms. arXiv preprint 2019, 1902-01360.
[18]
Ezike, J.O.J.; Oyeleye, C.A.; Olabiyisi, S.O.; Omidiora, E.O. Development of a hybrid tabu search and genetic algorithms for the exami-nation timetabling problem. J. Sci. Technol. Res., 2020, 2(3), 127.
[http://dx.doi.org/10.37933/nipes/2.3.2020.14]
[19]
Ngo, S.; Jaafar, J.; Aziz, I.; Nguyen, G.; Bui, A. Genetic algorithm for solving multi-objective optimization in examination timetabling problem. Int. J. Emerging Technol. Learning, 2021, 16(11), 4.
[http://dx.doi.org/10.3991/ijet.v16i11.21017]
[20]
Kurdi, M. An effective new island model genetic algorithm for job shop scheduling problem. Comput. Oper. Res., 2016, 67, 132-142.
[http://dx.doi.org/10.1016/j.cor.2015.10.005]
[21]
Palomo-Romero, J.M.; Salas-Morera, L.; García-Hernández, L. An island model genetic algorithm for unequal area facility layout prob-lems. Expert Syst. Appl., 2017, 68, 151-162.
[http://dx.doi.org/10.1016/j.eswa.2016.10.004]
[22]
García-Hernández, L.; Salas-Morera, L.; Carmona-Muñoz, C.; Garcia-Hernandez, J.A.; Salcedo-Sanz, S. A novel island model based on coral reefs optimization algorithm for solving the unequal area facility layout problem. Eng. Appl. Artif. Intell., 2020, 89, 103445.
[http://dx.doi.org/10.1016/j.engappai.2019.103445]
[23]
Gozali, A.; Kurniawan, B.; Weng, W.; Fujimura, S. Solving university course timetabling problem using localized island model genetic algorithm with dual dynamic migration policy. IEEJ Trans. Electr. Electron. Eng., 2019, 15(3), 389-400.
[http://dx.doi.org/10.1002/tee.23067]
[24]
Rezaeipanah, A.; Matoori, S.S.; Ahmadi, G. A hybrid algorithm for the university course timetabling problem using the improved parallel genetic algorithm and local search. Appl. Intell., 2021, 51(1), 467-492.
[http://dx.doi.org/10.1007/s10489-020-01833-x]
[25]
Leite, N.; Fernandes, C.M.; Melicio, F.; Rosa, A.C. A cellular memetic algorithm for the examination timetabling problem. Comput. Oper. Res., 2018, 94, 118-138.
[http://dx.doi.org/10.1016/j.cor.2018.02.009]
[26]
Miller, B.L.; Goldberg, D.E. Genetic algorithms, tournament selection, and the effects of noise. Complex Syst., 1995, 9(3), 193-212.
[27]
Yadav, S.L.; Sohal, A.A. Comparative study of different selection techniques in genetic algorithm. Int. J. Eng. Sci. Mathematics, 2017, 6(3), 174-180.
[28]
Du, H.; Wang, Z.; Zhan, W.; Guo, J. Elitism and distance strategy for selection of evolutionary algorithms. IEEE Access, 2018, 6, 44531-44541.
[http://dx.doi.org/10.1109/ACCESS.2018.2861760]
[29]
Reed, P.M.; Minsker, B.S.; Goldberg, D.E. The practitioner’s role in competent search and optimization using genetic algorithms. In: Bridging the Gap; Meeting the World's Water and Environmental Resources Challenges, 2001; pp. 1-9.
[30]
Ahn, C.W.; Ramakrishna, R.S. Elitism-based compact genetic algorithms. IEEE Trans. Evol. Comput., 2003, 7(4), 367-385.
[http://dx.doi.org/10.1109/TEVC.2003.814633]
[31]
Schoenauer, M.; Xanthakis, S. Constrained GA optimization. In: Proc. 5th International Conference on Genetic Algorithms; Morgan Kaufmann, 1993; pp. 573-580.
[32]
Meng, Q.; Wu, J.; Ellis, J.; Kennedy, P.J. Dynamic island model based on spectral clustering in genetic algorithm 2017 International Joint Conference on Neural Networks (IJCNN), 2017, pp. 1724-1731.
[http://dx.doi.org/10.1109/IJCNN.2017.7966059]
[33]
Li, C.C.; Lin, C.H.; Liu, J.C. Parallel genetic algorithms on the graphics processing units using island model and simulated annealing. Adv. Mech. Eng., 2017, 9(7), 1-14.
[http://dx.doi.org/10.1177/1687814017707413]
[34]
Cantu-Paz, E. Efficient and accurate parallel genetic algorithms; Springer Science & Business Media: Newyork, 2000.
[35]
Whitley, D.; Rana, S.; Heckendorn, R.B. The island model genetic algorithm: On separability, population size and convergence. CIT J. Comput. Inf. Technol., 1999, 7(1), 33-47.
[36]
Gozali, A.A.; Fujimura, S. DM-LIMGA: Dual migration localized island model genetic algorithm—a better diversity preserver island model. Evol. Intell., 2019, 12(4), 527-539.
[http://dx.doi.org/10.1007/s12065-019-00253-2]
[37]
Sun, X.; Chou, P.; Wu, C.C.; Chen, L.R. Quality-oriented study on mapping island model genetic algorithm onto CUDA GPU. Symmetry (Basel), 2019, 11(3), 318.
[http://dx.doi.org/10.3390/sym11030318]
[38]
Gong, G.; Deng, Q.; Chiong, R.; Gong, X.; Huang, H. An effective memetic algorithm for multi-objective job-shop scheduling. Knowl. Base. Syst., 2019, 182, 104840.
[http://dx.doi.org/10.1016/j.knosys.2019.07.011]
[39]
Hornby, G.S. ALPS: The age-layered population structure for reducing the problem of premature convergence. Proceedings of the 8th annual conference on Genetic and evolutionary computation, 2006, pp. 815-822.
[http://dx.doi.org/10.1145/1143997.1144142]
[40]
Hutter, M.; Legg, S. Fitness uniform optimization. IEEE Trans. Evol. Comput., 2006, 10(5), 568-589.
[http://dx.doi.org/10.1109/TEVC.2005.863127]
[41]
Souad. “A survey of particle swarm optimization techniques for solving university examination timetabling problem. Artif. Intell. Rev., 2015, 44(4), 537-546.
[http://dx.doi.org/10.1007/s10462-015-9437-7]
[42]
Muklason, A.; Bwananesia, P.C.; S. H., Y.T.; Angresti, N.D.; Supoyo, V.A. Automated examination timetabling optimization using greedy-late acceptance-hyperheuristic algorithm 2018 International Conference on Electrical Engineering and Computer Science (ICECOS), 2018, pp. 201-206.
[http://dx.doi.org/10.1109/ICECOS.2018.8605194]