Solving University Course Timetabling Problem Using Parallel Genetic Algorithm

Amin Rezaeipanah¹ , Zahra Abshirini² , Milad Boshkani Zade³

Section:Research Paper, Product Type: Journal-Paper
Vol.7 , Issue.5 , pp.5-13, Oct-2019

CrossRef-DOI:   https://doi.org/10.26438/ijsrcse/v7i5.513

Online published on Oct 31, 2019

Copyright © Amin Rezaeipanah, Zahra Abshirini, Milad Boshkani Zade . 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.
 

View this paper at   Google Scholar | DPI Digital Library

XML View     PDF Download

How to Cite this Paper

465 Views    364 Downloads    112 Downloads

Abstract :
Scheduling is one of the problems which so many researches have been conducted on it over the years. The university course timetabling problem (UCTP) which is an NP-Hard problem is a type of scheduling problem. The allocation of whole of events in timeslots and rooms performs by the university course timetabling process considering the list of hard and soft constraints presented in one semester, so that no conflict is created in such allocations. In general, it means assigning predefined courses to certain rooms and timeslots under specific constraints. In this paper we establish a hybrid algorithm based on Parallel Genetic Algorithm and Local Search to solve course timetabling problem (PGALS). This combines a direct representation of the timetable with heuristic crossover operators to ensure that the most fundamental constraints are never violated. We see how the algorithm is guaranteed to always produce a feasible solution by hard coding constraints which must not be broken. The proposed algorithm has been applied and evaluated against the latest methodologies in the literature with respect to standard benchmark problems. We demonstrate that the proposed algorithm produces some of the best-known results when tested on BenPaechter competition datasets

Key-Words / Index Term :
Parallel Genetic Algorithm; Local Search; Timetabling Problem; Hybrid Algorithm; BenPaechter Dataset

References :
[1] J. A. Soria-Alcaraz, G. Ochoa, J. Swan, M. Carpio, H. Puga, and E. K. Burke, “Effective learning hyper-heuristics for the course timetabling problem,” European Journal of Operational Research, Vol. 238, Issue. 1, pp. 77-86, 2014.
[2] E. K. Burke, J. H. Drake, B. McCollum, and E. Özcan, “Comments on: An overview of curriculum-based course timetabling,” Top, Vol. 23, Issue. 2, pp. 355-358, 2015.
[3] M. Ghalehgolabi and A. Rezaeipanah, "Intrusion Detection System Using Genetic Algorithm and Data Mining Techniques Based on the Reduction Features", International Journal of Computer Applications Technology and Research, Vol. 6, Issue. 11, pp. 461-466, 2016.
[4] J. Makkar, H. Monga, and S. Baglha, “Reduction of Inter-Symbol Interference using Artificial Neural Network System in Multicarrier OFDM System,” International Journal of Scientific Research in Computer Sciences and Engineering. Vol. 2, Issue. 5, pp. 553-558, 2017.
[5] R. Karimpour, M. Khayyambashi and N. Movahhedinia, "Load Balancing in Grid Computing Using Ant Colony Algorithm and Max-min Technique", Malaysian Journal of Computer Science, Vol. 29, Issue. 3, pp. 196-206, 2016.
[6] A. Alkan, and E. Ozcan, “Memetic algorithms for timetabling,” In Evolutionary Computation, IEEE, Vol. 3, pp. 1796-1802, 2003.
[7] C. H. Aladag, G. Hocaoglu and M. Basaran, "The effect of neighborhood structures on tabu search algorithm in solving course timetabling problem", Expert Systems with Applications, Vol. 36, Issue. 10, pp. 12349-12356, 2009.
[8] M. Nandhini, and Kanmani, “A survey of simulated annealing methodology for university course timetabling,” International Journal of Recent Trends in Engineering, Vol. 1, Issue. 2, 255-262, 2009.
[9] S. Abdullah, H. Turabieh, B. McCollum and P. McMullan, "A hybrid metaheuristic approach to the university course timetabling problem", Journal of Heuristics, Vol. 18, Issue. 1, pp. 1-23, 2012.
[10] R. Chen and H. Shih, "Solving University Course Timetabling Problems Using Constriction Particle Swarm Optimization with Local Search", Algorithms, Vol. 6, Issue. 2, pp. 227-244, 2013.
[11] M. Al-Betar, A. Khader and M. Zaman, "University Course Timetabling Using a Hybrid Harmony Search Metaheuristic Algorithm", IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), Vol. 42, Issue. 5, pp. 664-681, 2012.
[12] R. Bai, E. Burke, G. Kendall, J. Li and B. McCollum, "A Hybrid Evolutionary Approach to the Nurse Rostering Problem", IEEE Transactions on Evolutionary Computation, Vol. 14, Issue. 4, pp. 580-590, 2010.
[13] S. Ait Haddadene, N. Labadie and C. Prodhon, "A GRASP Ă— ILS for the vehicle routing problem with time windows, synchronization and precedence constraints", Expert Systems with Applications, Vol. 66, pp. 274-294, 2016.
[14] N. Pillay, "A survey of school timetabling research", Annals of Operations Research, Vol. 218, Issue. 1, pp. 261-293, 2014.
[15] A. V. Moura and R. Scaraficci, "A GRASP strategy for a more constrained School Timetabling Problem", International Journal of Operational Research, Vol. 7, Issue. 2, pp. 152-160, 2010.
[16] Bolaji, A. Khader, M. Al-Betar and M. Awadallah, "University course timetabling using hybridized artificial bee colony with hill climbing optimizer", Journal of Computational Science, Vol. 5, Issue. 5, pp. 809-818, 2014.
[17] S. Daskalaki, T. Birbas and E. Housos, "An integer programming formulation for a case study in university timetabling", European Journal of Operational Research, Vol. 153, Issue. 1, pp. 117-135, 2004.
[18] G. da Fonseca, H. Santos, T. Toffolo, S. Brito and M. Souza, "GOAL solver: a hybrid local search based solver for high school timetabling", Annals of Operations Research, Vol. 239, Issue. 1, pp. 77-97, 2014.
[19] L. Ahmed, E. Ă–zcan and A. Kheiri, "Solving high school timetabling problems worldwide using selection hyper-heuristics", Expert Systems with Applications, Vol. 42, Issue. 13, pp. 5463-5471, 2015.
[20] S. Al-Yakoob and H. Sherali, "Mathematical models and algorithms for a high school timetabling problem", Computers & Operations Research, Vol. 61, pp. 56-68, 2015.
[21] R. Lewis, and J. Thompson, “Analysing the effects of solution space connectivity with an effective metaheuristic for the course timetabling problem,” European Journal of Operational Research, Vol. 240, Issue. 3, pp. 637-648, 2015.
[22] E, K. Burke, M. Gendreau, M. Hyde, G. Kendall, G. Ochoa, E. O¨ zcan, and R. Qu, “Hyper-heuristics: A survey of the state of the art,” Journal of the Operational Research Society, Vol. 64, Issue. 12, pp. 1695-1724, 2013.
[23] Datta, K. Deb, C. M. Fonseca, “Multi-objective evolutionary algorithm for university class timetabling problem,” In Evolutionary scheduling, Springer, Berlin, Heidelberg, pp. 197-236, 2017.
[24] S. Abdullah, H. Turabieh, B. McCollum, and P. McMullan, “A multi-objective post enrolment course timetabling problems: a new case study,” In IEEE congress on evolutionary computation, IEEE, pp. 1-7, 2010.
[25] T. Thepphakorn, P. Pongcharoen, and S. Vitayasak, “A New Multiple Objective Cuckoo Search for University Course Timetabling Problem,” In International Workshop on Multi-disciplinary Trends in Artificial Intelligence, Springer, Cham, pp. 196-207, 2016.
[26] 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, Issue. 1, pp. 177-192, 2007.
[27] M. Rogalska, W. Bo?ejko, and Z. Hejducki, “Time/cost optimization using hybrid evolutionary algorithm in construction project scheduling,” Automation in Construction, Vol. 18, Issue. 1, pp. 24-31, 2008.
[28] S. Kifah, and S. Abdullah, “An adaptive non-linear great deluge algorithm for the patient-admission problem,” Information Sciences, Vol. 295, pp. 573-585, 2015.
[29] Y. Lei, M. Gong, L. Jiao, and Y. Zuo, “A memetic algorithm based on hyper-heuristics for examination timetabling problems,” International Journal of Intelligent Computing and Cybernetics, Vol. 8, Issue. 2, pp. 139-151, 2015.
[30] H. Babaei, J. Karimpour, and A. Hadidi, “A survey of approaches for university course timetabling problem,” Computers & Industrial Engineering, Vol. 86, 43-59, 2015.
[31] J. A. Soria-Alcaraz, E. Özcan, J. Swan, G. Kendall, and M. Carpio, “Iterated local search using an add and delete hyper-heuristic for university course timetabling,” Applied Soft Computing, Vol. 40, 581-593, 2016.
[32] G. N. Beligiannis, C. N. Moschopoulos, G. P. Kaperonis, and S. D. Likothanassis, “Applying evolutionary computation to the school timetabling problem: The Greek case,” Computers & Operations Research, Vol. 35, Issue. 4, pp. 1265-1280, 2008.
[33] Nothegger, A. Mayer, A. Chwatal, and G. R. Raidl, “Solving the post enrolment course timetabling problem by ant colony optimization,” Annals of Operations Research, Vol. 194, Issue. 1, pp. 325-339, 2012.
[34] F. Cavdur, and M. Kose, “A fuzzy logic and binary-goal programming-based approach for solving the exam timetabling problem to create a balanced-exam schedule,” International Journal of Fuzzy Systems, Vol. 18, Issue. 1, pp. 119-129, 2016.
[35] S. Yang, and S. N. Jat, “Genetic algorithms with guided and local search strategies for university course timetabling,” IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), Vol. 41, Issue. 1, pp. 93-106, 2011.
[36] H. Ishibuchi, T. Yoshida, and T. Murata, “Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling,” IEEE transactions on evolutionary computation, Vol. 7, Issue. 2, pp. 204-223, 2003.
[37] X. Feng, Y. Lee, and I. Moon, “An integer program and a hybrid genetic algorithm for the university timetabling problem,” Optimization Methods and Software, Vol. 32, Issue. 3, pp. 625-649, 2017.
[38] N. Mladenovi?, M. Draži?,V. Kova?evic-Vuj?i?, and M. ?angalovi?, “General variable neighborhood search for the continuous optimization,” European Journal of Operational Research, Vol. 191, Issue. 3, pp. 753-770, 2008.
[39] E. K. Burke, G. Kendall, and E. Soubeiga, “A Tabu-Search Hyperheuristic for Timetabling and Rostering,” Springer Journal of Heuristics, pp. 451-470, 2003.