A Modified Migrating Bird Optimization For University Course Timetabling Problem
DOI:
https://doi.org/10.11113/jt.v72.2949Keywords:
Migrating bird optimization algorithm, iterated local search, neighbourhood sharing mechanism, post enrolment-based course timetablingAbstract
University course timetabling problem is a dilemma which educational institutions are facing due to various demands to be achieved in limited resources. Migrating bird optimization (MBO) algorithm is a new meta-heuristic algorithm which is inspired by flying formation of migrating birds. It has been applied successfully in tackling quadratic assignment problem and credit cards fraud detection problem. However, it was reported that MBO will get stuck in local optima easily. Therefore, a modified migrating bird optimization algorithm is proposed to solve post enrolment-based course timetabling. An improved neighbourhood sharing mechanism is used with the aim of escaping from local optima. Besides that, iterated local search is selected to be hybridized with the migrating bird optimization in order to further enhance its exploitation ability. The proposed method was tested using Socha’s benchmark datasets. The experimental results show that the proposed method outperformed the basic MBO and it is capable of producing comparable results as compared with existing methods that have been presented in literature. Indeed, the proposed method is capable of addressing university course timetabling problem and promising results were obtained.
References
Colorni, A., M. Dorigo, and V. Maniezzo. 1998. Metaheuristics for High School Timetabling. Computational Optimization and Applications. 9(3): 275–298.
Beligiannis, G.N., C.N. Moschopoulos, G.P. Kaperonis, and S.D. Likothanassis. 2008. Applying evolutionary computation to the school timetabling problem: The Greek case. Computers & Operations Research. 35(4): 1265–1280.
Burke, E.K., D.G. Elliman, and R.F. Weare. 1994. A Genetic Algorithm based University Timetabling System. Proceedings of the 2nd East-West International Conference on Computer Technologies in Education. 19th-23rd Sept. Crimea, Ukraine.35–40.
Burke, E.K., J.P. Newall, and R.F. Weare. 1996. A memetic algorithm for university exam timetabling. Practice and Theory of Automated Timetabling. E. Burke and P. Ross, Springer Berlin Heidelberg. 1153: 241–250.
Burke, E.K., G. Kendall, and E. Soubeiga. 2003. A Tabu-Search Hyperheuristic for Timetabling and Rostering. Journal of Heuristics 9(6): 451–470.
Özcan, E. 2005. Memetic Algorithms for Nurse Rostering. Computer and Information Sciences - ISCIS 2005. Yolum, et al., Springer Berlin Heidelberg. 3733: 482–492.
Burke, E.K., T. Curtois, G. Post, R. Qu, and B. Veltman. 2008. A hybrid heuristic ordering and variable neighbourhood search for the nurse rostering problem. European Journal of Operational Research 188(2): 330–341.
Caprara, A., M. Fischetti, P.L. Guida, M. Monaci, G. Sacco, and P. Toth. 2001. Solution of real-world train timetabling problems. System Sciences, 2001. Proceedings of the 34th Annual Hawaii International Conference on. 3-6 Jan. 10
Caprara, A., M. Fischetti, and P. Toth. 2002. Modeling and Solving the Train Timetabling Problem. Operations Research 50(5): 851–861.
Liu, Z.-g. and J.-s. Shen. 2007. Regional Bus Operation Bi-level Programming Model Integrating Timetabling and Vehicle Scheduling. Systems Engineering - Theory & Practice 27(11): 135–141.
Schaerf, A. 1999. Scheduling Sport Tournaments using Constraint Logic Programming. Constraints . 4(1): 43–65.
Rasmussen, R.V. and M.A. Trick. 2008. Round robin scheduling – a survey. European Journal of Operational Research. 188(3): 617–636.
Rust, R.T. and N.V. Eechambadi. 1989. Scheduling Network Television Programs: A Heuristic Audience Flow Approach to Maximizing Audience Share. Journal of Advertising. 18(2): 11–18.
Wuang, M.S., C.L. Yang, R.H. Huang, and S.P. Chuang. 2010. Scheduling of television commercials. Industrial Engineering and Engineering Management (IEEM). 2010 IEEE International Conference on. 7-10 Dec. 2010.803–807.
Carter, M., E. Burke , M. Carter and G. Laporte. 1998. Recent developments in practical course timetabling. Practice and Theory of Automated Timetabling II. Springer Berlin Heidelberg. 1408: 3–19.
de Werra, D. 1985. An introduction to timetabling. European Journal of Operational Research 19(2): 151–162.
Merlot, L.G., N. Boland, B. Hughes, E. Burke. P. Causmaecker, Springer Berlin Heidelberg and P. Stuckey. 2003. A Hybrid Algorithm for the Examination Timetabling Problem. Practice and Theory of Automated Timetabling IV. 2740: 207–231.
Ahandani, M.A. and M.T. Vakil-Baghmisheh. 2011. Examination timetabling using a hill climbing with combined neighbourhood structure. Computer and Knowledge Engineering (ICCKE). 2011 1st International eConference on. 13-14 Oct. 2011. 45–48.
Kostuch, P. 2003. Timetabling competition-sa-based heuristic.
Alzaqebah, M. Wang, X. Zhu, D.-Z. Du, Springer Berlin Heidelberg.and S. Abdullah. 2011. Hybrid Artificial Bee Colony Search Algorithm Based on Disruptive Selection for Examination Timetabling Problems. Combinatorial Optimization and Applications. 6831: 31–45.
Burke, E., Y. Bykov, J. Newall, and S. Petrovic. 2003. A time-predefined approach to course timetabling. The Yugoslav Journal of Operations Research ISSN: 0354-0243 EISSN: 2334-6043 13(2).
Obit, J. V. Sgurev, M. Hadjiski, J. Kacprzyk, Springer Berlin Heidelberg.and D. Landa-Silva. 2010. Computational Study of Non-linear Great Deluge for University Course Timetabling. Intelligent Systems: From Theory to Practice. 299: 309–328.
Jat, S. and S. Yang. 2011. A hybrid genetic algorithm and tabu search approach for post enrolment course timetabling. Journal of Scheduling 14(6): 617–637.
Li, L. and S.-h. Liu. 2011. Study of course scheduling based on particle swarm optimization. Cross Strait Quad-Regional Radio Science and Wireless Technology Conference (CSQRWC), 2011. 26-30 July 2011.1692–1695.
Chen, R.-M. and H.-F. Shih. 2013. Solving University Course Timetabling Problems Using Constriction Particle Swarm Optimization with Local Search. Algorithms. 6(2): 227–244.
Al-Betar, M. and A. Khader. 2012. A harmony search algorithm for university course timetabling. Annals of Operations Research. 194(1): 3–31.
Al-Betar, M.A., A.T. Khader, and M. Zaman. 2012. University Course Timetabling Using a Hybrid Harmony Search Metaheuristic Algorithm. Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions. 42(5): 664–681.
Socha, K., J. Knowles, M. Dorigo, G. Caro, Springer Berlin Heidelberg. and M. Sampels. 2002. A MAX-MIN Ant System for the University Course Timetabling Problem. Ant Algorithms. 2463: 1–13.
Duman, E., M. Uysal, and A.F. Alkaya. 2012. Migrating Birds Optimization: A new metaheuristic approach and its performance on quadratic assignment problem. Information Sciences. 217: 65–77.
Portugal, S.J., T.Y. Hubel, J. Fritz, S. Heese, D. Trobe, B. Voelkl, S. Hailes, A.M. Wilson, and J.R. Usherwood. 2014. Upwash exploitation and downwash avoidance by flap phasing in ibis formation flight. Nature. 505(7483): 399–402.
Maeng, J.-S., J.-H. Park, S.-M. Jang, and S.-Y. Han. 2013. A modeling approach to energy savings of flying Canada geese using computational fluid dynamics. Journal of Theoretical Biology. 320(0): 76–85.
Gao, K.Z., P.N. Suganthan, and T.J. Chua. 2013. An enhanced migrating birds optimization algorithm for no-wait flow shop scheduling problem. Computational Intelligence in Scheduling (SCIS), 2013 IEEE Symposium. 16-19 April 2013. 9–13.
Duman, E. and I. Elikucuk. Applying Migrating Birds Optimization to Credit Card Fraud Detection. Trends and Applications in Knowledge Discovery and Data Mining.2013. J. Li, et al., Springer Berlin Heidelberg. 7867: 416–427.
Burke, E.K., A.J. Eckersley, B. McCollum, S. Petrovic, and R. Qu. 2010. Hybrid variable neighbourhood approaches to university exam timetabling. European Journal of Operational Research. 206(1): 46–53.
Mladenović, N., D. Urošević, S.d. Hanafi, and A. Ilić. 2012. A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem. European Journal of Operational Research. 220(1): 270–285.
Shaker, K., S. Abdullah, A. Alqudsi, and H. Jalab. 2013. Hybridizing Meta-heuristics Approaches for Solving University Course Timetabling Problems. Rough Sets and Knowledge Technology. P. Lingras, et al., Springer Berlin Heidelberg. 8171: 374–384.
Bolaji, A.A., A. Khader, M. Al-Betar, M. Awadallah. Y. Tan, Y. Shi, and H. Mo, A Modified Artificial Bee Colony Algorithm for Post-enrolment Course Timetabling. Advances in Swarm Intelligence.2013. Springer Berlin Heidelberg 7928: 377–386.
Karami, A.H. and M. Hasanzadeh. 2012. University course timetabling using a new hybrid genetic algorithm. Computer and Knowledge Engineering (ICCKE), 2012 2nd International eConference on. 18-19 Oct. 2012. 144–149.
Abuhamdah, A., M. Ayob, G. Kendall, and N. Sabar. 2014. Population based Local Search for university course timetabling problems. Applied Intelligence. 40(1): 44–53.
Jaradat, G., M. Ayob, and Z. Ahmad. 2012. On the performance of Scatter Search for post-enrolment course timetabling problems. Journal of Combinatorial Optimization. 1–23.
Jaradat, G.M. and M. Ayob. 2013. Effect of Elite Pool and Euclidean Distance in Big Bang-Big Crunch Metaheuristic for Post-Enrolment Course Timetabling Problems. International Journal of Soft Computing 8(2): 96–107.
Abdullah, S., H. Turabieh, B. McCollum, and P. McMullan. 2012. A hybrid metaheuristic approach to the university course timetabling problem. Journal of Heuristics 18(1): 1–23.
Sabar, N.R., M. Ayob, G. Kendall, and R. Qu. 2012. A honey-bee mating optimization algorithm for educational timetabling problems. European Journal of Operational Research. 216(3): 533–543.
Downloads
Published
Issue
Section
License
Copyright of articles that appear in Jurnal Teknologi belongs exclusively to Penerbit Universiti Teknologi Malaysia (Penerbit UTM Press). This copyright covers the rights to reproduce the article, including reprints, electronic reproductions, or any other reproductions of similar nature.
