University Examination Timetabling Using a Hybrid Black Hole Algorithm

Cheng Weng Fong - Tunku Abdul Rahman University College, Johor Branch Campus, Malaysia
Pui Huang Leong - Tunku Abdul Rahman University College, Johor Branch Campus, Malaysia
Hishammuddin Asmuni - Universiti Teknologi Malaysia, 81300, Skudai, Johor Malaysia
Yee Yong Pang - Universiti Teknologi Malaysia, 81300, Skudai, Johor Malaysia
Hiew Moi Sim - Universiti Teknologi Malaysia, 81300, Skudai, Johor Malaysia
Radziah Mohamad - Universiti Teknologi Malaysia, 81300, Skudai, Johor Malaysia
Jun Kit Chaw - Institute of IR4.0, Universiti Kebangsaan Malaysia, Bangi, Malaysia


Citation Format:



DOI: http://dx.doi.org/10.30630/joiv.6.2-2.1092

Abstract


University timetabling construction is a complicated task that is encountered by universities in the world. In this study, a hybrid approach has been developed to produce timetable solution for the university examination timetabling problem. Black Hole Algorithm (BHA), a population-based approach that mimics the black hole phenomenon has been introduced in the literature recently and successfully applied in addressing various optimization problems. Although its effectiveness has been proven, there still exists inefficiency regarding the exploitation ability where BHA is poor in fine tuning search region in reaching for good quality of solution. Hence, a hybrid framework for university examination timetabling problem that is based on BHA and Hill Climbing local search is proposed (hybrid BHA). The aim of this hybridization is to improve the exploitation ability of BHA in fine tuning the promising search regions and convergence speed of the search process. A real-world university examination benchmark dataset has been used to evaluate the performance of hybrid BHA. The computational results demonstrate that hybrid BHA capable of generating competitive results and recording best results for three instances, compared to the reference approaches and current best-known recorded in the literature. Other than that, findings from the Friedman tests show that the hybrid BHA ranked second and third in comparison with hybrid and meta-heuristic approaches (total of 27 approaches) reported in the literature, respectively.

Keywords


black hole algorithm; university examination timetabling; meta-heuristic; optimization

Full Text:

PDF

References


A. K. Mandal, M. N. M. Kahar, and G. Kendall, “Addressing Examination Timetabling Problem Using a Partial Exams Approach in Constructive and Improvement”. Computation, vol. 8, pp. 46, 2020.

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

M. W. Carter and G. Laporte. “Recent developments in practical examination timetabling”. 1996. p.1-21.

B. A. Aldeeb, M. A. Al-Betar, A. O. Abdelmajeed, M. J. Younes, M. AlKenani, W. Alomoush, K. A. Alissa, and M. A. Alqahtani, “A comprehensive review of uncapacitated university examination timetabling problem”. International Journal of Applied Engineering Research, vol. 14, pp. 4524-4547, 2019.

A. Schaerf, “A Survey of Automated Timetabling”. Artificial Intelligence Review, vol. 13, pp. 87-127, 1999.

N. R. Sabar, M. Ayob, G. Kendall, and R. Qu. “Roulette Wheel Graph Colouring for Solving Examination Timetabling Problems”. 2009. p.463-470.

R. Qu, E. K. Burke, and B. McCollum, “Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems”. European Journal of Operational Research, vol. 198, pp. 392-404, 2009.

C. Blum and A. Roli, “Metaheuristics in combinatorial optimization: Overview and conceptual comparison”. ACM Comput. Surv., vol. 35, pp. 268–308, 2003.

S. Abdullah, S. Ahmadi, E. K. Burke, M. Dror, and B. McCollum, “A tabu-based large neighbourhood search methodology for the capacitated examination timetabling problem”. Journal of the Operational Research Society, vol. 58, pp. 1494-1502, 2007.

S. Abdullah and H. Turabieh, “On the use of multi neighbourhood structures within a Tabu-based memetic approach to university timetabling problems”. Information Sciences, vol. 191, pp. 146-168, 2012.

R. Bellio, S. Ceschia, L. Di Gaspero, and A. Schaerf, “Two-stage multi-neighborhood simulated annealing for uncapacitated examination timetabling”. Computers & Operations Research, vol. 132, pp. 105300, 2021.

E. K. Burke and Y. Bykov. “A late acceptance strategy in hill-climbing for exam timetabling problems”. in PATAT 2008 Conference, Montreal, Canada. 2008. p.1-7.

H. Turabieh and S. Abdullah. “A Hybrid Fish Swarm Optimisation Algorithm for Solving Examination Timetabling Problems”. in Learning and Intelligent Optimization. 2011. p.539-551.

H. Turabieh and S. Abdullah, “An integrated hybrid approach to the examination timetabling problem”. Omega, vol. 39, pp. 598-607, 2011.

F. Ghaisani and S. Suyanto. “Discrete Firefly Algorithm for an Examination Timetabling”. in 2019 International Seminar on Research of Information Technology and Intelligent Systems (ISRITI). 2019. p.1-4.

N. R. Sabar, M. Ayob, G. Kendall, and R. Qu, “A honey-bee mating optimization algorithm for educational timetabling problems”. European Journal of Operational Research, vol. 216, pp. 533-543, 2012.

K. Alomari, O. Almarashdi, A. Marashdh, and B. Zaqaibeh, “A new optimization on harmony search algorithm for exam timetabling system”. Journal of Information & Knowledge Management, vol. 19, pp. 2040009, 2020.

K. Anwar, A. T. Khader, M. A. Al-Betar, and M. A. Awadallah. “Harmony search-based hyper-heuristic for examination timetabling”. in 2013 IEEE 9th international colloquium on signal processing and its applications. 2013. p.176-181.

C. W. Fong, H. Asmuni, and B. McCollum, “A Hybrid Swarm-Based Approach to University Timetabling”. IEEE Transactions on Evolutionary Computation, vol. 19, pp. 870-884, 2015.

C. W. Fong, H. Asmuni, B. McCollum, P. McMullan, and S. Omatu, “A new hybrid imperialist swarm-based optimization algorithm for university timetabling problems”. Information Sciences, vol. 283, pp. 1-21, 2014.

M. Alzaqebah and S. Abdullah, “Comparison on the selection strategies in the artificial bee colony algorithm for examination timetabling problems”. International Journal of Soft Computing and Engineering, vol. 1, pp. 2011.

E. K. Burke, A. J. Eckersley, B. McCollum, S. Petrovic, and R. Qu, “Hybrid variable neighbourhood approaches to university exam timetabling”. European Journal of Operational Research, vol. 206, pp. 46-53, 2010.

M. H. Abed and A. Y. Tang, “Hybridizing genetic algorithm and record-to-record travel algorithm for solving uncapacitated examination timetabling problem”. Electronic Journal of Computer Science and Information Technology, vol. 4, pp. 2013.

M. Alzaqebah and S. Abdullah, “Hybrid bee colony optimization for examination timetabling problems”. Computers & Operations Research, vol. 54, pp. 142-154, 2015.

B. A. Aldeeb, M. Azmi Al-Betar, N. Md Norwawi, K. A. Alissa, M. K. Alsmadi, A. A. Hazaymeh, and M. Alzaqebah, “Hybrid intelligent water Drops algorithm for examination timetabling problem”. Journal of King Saud University - Computer and Information Sciences, vol. pp. 2021.

N. Leite, C. M. Fernandes, F. Melício, and A. C. Rosa, “A cellular memetic algorithm for the examination timetabling problem”. Computers & Operations Research, vol. 94, pp. 118-138, 2018.

A. F. Jahwar, A. M. Abdulazeez, D. Q. Zeebaree, D. A. Zebari, and F. Y. H. Ahmed. “An Integrated Gapso Approach for Solving Problem of an Examination Timetabiking System”. in 2021 IEEE Symposium on Industrial Electronics & Applications (ISIEA). 2021. p.1-6.

P. Alefragis, C. Gogos, C. Valouxis, and E. Housos. “A multiple metaheuristic variable neighborhood search framework for the Uncapacitated Examination Timetabling Problem”. in Proceedings of the 13th International Conference on the Practice and Theory of Automated Timetabling-PATAT. 2021. p.159-171.

A. Hatamlou, “Black hole: A new heuristic optimization approach for data clustering”. Information Sciences, vol. 222, pp. 175-184, 2013.

M. W. Carter, G. Laporte, and S. Y. Lee, “Examination Timetabling: Algorithmic Strategies and Applications”. The Journal of the Operational Research Society, vol. 47, pp. 373-383, 1996.

R. Qu and E. Burke, “Hybrid Variable Neighborhood Hyper Heuristics for Exam Timetabling Problems”. vol. pp. 2005.

R. Qu and E. K. Burke, “Hybridizations within a graph-based hyper-heuristic framework for university timetabling problems”. Journal of the Operational Research Society, vol. 60, pp. 1273-1285, 2009.

M. A. Al-Betar, A. T. Khader, and I. A. Doush, “Memetic techniques for examination timetabling”. Annals of Operations Research, vol. 218, pp. 23-50, 2014.

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, pp. 867645, 2014.

E. K. Burke, R. Qu, and A. Soghier, “Adaptive selection of heuristics for improving exam timetables”. Annals of Operations Research, vol. 218, pp. 129-145, 2014.

A. L. a. Bolaji, A. T. Khader, M. A. Al-Betar, and M. A. Awadallah, “A Hybrid Nature-Inspired Artificial Bee Colony Algorithm for Uncapacitated Examination Timetabling Problems”. Journal of Intelligent Systems, vol. 24, pp. 37-54, 2015.

H. A. Abbass. “A monogenous MBO approach to satisfiability”. in Proceeding of the international conference on computational intelligence for modelling, control and automation, CIMCA. 2001.

H. Asmuni, E. K. Burke, J. M. Garibaldi, B. McCollum, and A. J. Parkes, “An investigation of fuzzy multiple heuristic orderings in the construction of university examination timetables”. Computers & Operations Research, vol. 36, pp. 981-1001, 2009.

J. S. Appleby, D. V. Blake, and E. A. Newman, “Techniques for Producing School Timetables on a Computer and their Application to other Scheduling Problems”. The Computer Journal, vol. 3, pp. 237-245, 1961.

J. M. Thompson and K. A. Dowsland, “Variants of simulated annealing for the examination timetabling problem”. Annals of Operations Research, vol. 63, pp. 105-128, 1996.

Y. Yang and S. Petrovic. “A Novel Similarity Measure for Heuristic Selection in Examination Timetabling”. in Practice and Theory of Automated Timetabling V. 2005. p.247-269.

S. L. Tilahun, “Prey-predator algorithm for discrete problems: a case for examination timetabling problem”. Turkish Journal of Electrical Engineering and Computer Sciences, vol. 27, pp. 950-960, 2019.

E. K. Burke and Y. Bykov, “An Adaptive Flex-Deluge Approach to University Exam Timetabling”. INFORMS J. on Computing, vol. 28, pp. 781–794, 2016.

S. Casey and J. Thompson. “GRASPing the Examination Scheduling Problem”. in Practice and Theory of Automated Timetabling IV. 2003. p.232-244.

E. K. Burke and J. P. Newall. “Enhancing Timetable Solutions with Local Search Methods”. in Practice and Theory of Automated Timetabling IV. 2003. p.195-206.

E. Burke, Y. Bykov, J. Newall, and S. Petrovic, “A time-predefined local search approach to exam timetabling problems”. IIE Transactions, vol. 36, pp. 509-528, 2004.

M. Eley. “Ant Algorithms for the Exam Timetabling Problem”. in Practice and Theory of Automated Timetabling VI. 2007. p.364-382.

N. Pillay and W. Banzhaf, “An informed genetic algorithm for the examination timetabling problem”. Applied Soft Computing, vol. 10, pp. 457-467, 2010.

M. A. Al-Betar, A. T. Khader, and J. J. Thomas. “A combination of metaheuristic components based on harmony search for the uncapacitated examination timetabling”. in the 8th Int. Conf. Practice and Theory of Automated Timetabling (PATAT 2010). 2010. p.57-80.

M. A. Al-Betar, “A β-hill climbing optimizer for examination timetabling problem”. Journal of Ambient Intelligence and Humanized Computing, vol. 12, pp. 653-666, 2021

C. W. Fong, H. Asmuni, P. H. Leong, Y. H. Sam, Y. Y. Pang and H. M. Sim. “Zombie Survival Optimization in Solving University Examination Timetabling Problem”. in 2022 IEEE International Conference on Automatic Control and Intelligent Systems (I2CACIS). 2022. p. 169-173.

F. C. Weng, and H. Asmuni. “An automated approach based on bee swarm in tackling university examination timetabling problem” Int J Electr Comput Sci, vol. 13, pp. 8-23, 2013

L. W. Shen, H. Asmuni and F. C. Weng. “A modified migrating bird optimization for university course timetabling problem” Jurnal Teknologi, vol. 72, pp. 89-96, 2015




Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

__________________________________________________________________________
JOIV : International Journal on Informatics Visualization
ISSN 2549-9610  (print) | 2549-9904 (online)
Organized by Department of Information Technology - Politeknik Negeri Padang, and Institute of Visual Informatics - UKM and Soft Computing and Data Mining Centre - UTHM
W : http://joiv.org
E : joiv@pnp.ac.id, hidra@pnp.ac.id, rahmat@pnp.ac.id

View JOIV Stats

Creative Commons License is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.