Swarm Intelligence For Educational Timetabling: A Survey Of The State Of The Art
Volume 3 - Issue 9, September 2019 Edition
[Download Full Paper]
Author(s)
Omer ElhagMusa, Adil Ail Abdelaziz
Keywords
educational timetabling; swarm intelligence; scheduling; systematic literature review.
Abstract
Educational timetabling problems regardless of their classification are complex combinatorial problems that face many educational institutions. These problems require the satisfaction of a set of constraints to attain an efficient solution in the matter of resources and time consumption. Swarm intelligence techniques have been successfully applied to solve educational timetabling problems. In this review, the swarm intelligence solutions for solving educational timetabling problems will be investigated and critically discussed. The paper reports the implementation and results of a systematic literature review (SLR) used to collect and highlight the scientific literature on swarm intelligence for educational timetabling. The review links related areas and discusses hot topics on the efficiency of using swarm intelligence, and the gap between academia results and industry implementation in educational timetabling. The paper will be concluded by pointing out and comparing the results obtained in literature. Current promising directions for future research are also presented.
References
[1]. Abdullah, S. (2006). Heuristic approaches for university timetabling problems, University of Nottingham Nottingham.
[2]. Abramson, D. and H. Dang (1993). School timetables: A case study in simulated annealing. Applied simulated annealing, Springer: 103-124.
[3]. Adrianto, D. (2014). "Comparison Using Particle Swarm Optimization and Genetic Algorithm for Timetable Scheduling." Journal of Computer Science 10(2): 341.
[4]. Agahian, S., H. Pehlivan and R. Dehkharghani (2014). Adaptation and Use of Artificial Bee Colony Algorithm to Solve Curriculum-based Course Time-Tabling Problem. Intelligent Systems, Modelling and Simulation (ISMS), 2014 5th International Conference on, IEEE.
[5]. Ahandani, M. A., M. T. V. Baghmisheh, M. A. B. Zadeh and S. Ghaemi (2012). "Hybrid particle swarm optimization transplanted into a hyper-heuristic structure for solving examination timetabling problem." Swarm and Evolutionary Computation 7: 21-34.
[6]. Alzaqebah, M. and S. Abdullah (2011). "Hybrid artificial bee colony search algorithm based on disruptive selection for examination timetabling problems." Combinatorial Optimization and Applications: 31-45.
[7]. Alzaqebah, M. and S. Abdullah (2015). "Hybrid bee colony optimization for examination timetabling problems." Computers & Operations Research 54: 142-154.
[8]. Ayob, M. and G. Jaradat (2009). Hybrid ant colony systems for course timetabling problems. Data Mining and Optimization, 2009. DMO'09. 2nd Conference on, IEEE.
[9]. Aziz, M. A. A., M. N. Taib and N. M. Hussin (2010). Assignments acceptance strategy in a modified PSO algorithm to elevate local optima in solving class scheduling problems. Signal Processing and Its Applications (CSPA), 2010 6th International Colloquium on, IEEE.
[10]. Aziz, M. A. A., M. N. Taib and N. M. Hussin (2010). The effects of Event Selection Based on Soft Constraint Violation (ESSCV) in a modified PSO algorithm to solve class scheduling problems. Computer Applications and Industrial Electronics (ICCAIE), 2010 International Conference on, IEEE.
[11]. Aziz, M. A. A., M. N. Taib and N. M. Hussin (2010). The Effects of Room Slot Address (RSA) Selection Technique in a Modified PSO Algorithm to Solve Class Scheduling Problems. Computational Intelligence, Modelling and Simulation (CIMSiM), 2010 Second International Conference on, IEEE.
[12]. Babaei, H., J. Karimpour and A. Hadidi (2015). "A survey of approaches for university course timetabling problem." Computers & Industrial Engineering 86: 43-59.
[13]. 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.
[14]. Blum, C. (2005). "Ant colony optimization: Introduction and recent trends." Physics of Life reviews 2(4): 353-373.
[15]. Blum, C., S. Correia, M. Dorigo, B. Paechter, O. Rossi-Doria and M. Snoek (2002). "A GA evolving instructions for a timetable builder."
[16]. Blum, C. and X. Li (2008). Swarm intelligence in optimization. Swarm Intelligence, Springer: 43-85.
[17]. Bolaji, A. (2012). "Tackling university course timetabling problem using artificial bee colony algorithm." Chapter Twelve.
[18]. Bolaji, A. L. a., A. Khader, M. Al-Betar, M. Awadallah and J. Thomas (2012). The effect of neighborhood structures on examination timetabling with artificial bee colony. Proceedings of the 9th International Conference on the Practice and Theory of Automated Timetabling,(PATAT 2012).
[19]. Bolaji, A. L. a., A. T. Khader, M. A. Al-betar and M. Awadallah (2011). Artificial bee colony algorithm for curriculum-based course timetabling problem. 5th international conference on information technology (ICIT 2011).
[20]. Bolaji, A. L. a., A. T. Khader, M. A. Al-Betar and M. A. Awadallah (2011). An improved artificial bee colony for course timetabling. Bio-Inspired Computing: Theories and Applications (BIC-TA), 2011 Sixth International Conference on, IEEE.
[21]. Bolaji, A. L. a., A. T. Khader, M. A. Al-Betar and M. A. Awadallah (2013). A Modified Artificial Bee Colony Algorithm for Post-enrolment Course Timetabling. International Conference in Swarm Intelligence, Springer.
[22]. Bolaji, A. L. a., A. T. Khader, M. A. Al-Betar and M. A. Awadallah (2014). "University course timetabling using hybridized artificial bee colony with hill climbing optimizer." Journal of Computational Science 5(5): 809-818.
[23]. Bolaji, A. L. a., A. T. Khader, M. A. Al-Betar and M. A. Awadallah (2015). "A hybrid nature-inspired artificial bee colony algorithm for uncapacitated examination timetabling problems." Journal of Intelligent Systems 24(1): 37-54.
[24]. Brännlund, U., P. O. Lindberg, A. Nou and J.-E. Nilsson (1998). "Railway timetabling using Lagrangian relaxation." Transportation science 32(4): 358-369.
[25]. Burke, E., D. Elliman, P. Ford and R. Weare (1995). Examination timetabling in British universities: A survey. International Conference on the Practice and Theory of Automated Timetabling, Springer.
[26]. Burke, E. K., P. De Causmaecker, G. V. Berghe and H. Van Landeghem (2004). "The state of the art of nurse rostering." Journal of scheduling 7(6): 441-499.
[27]. Burke, E. K. and S. Petrovic (2002). "Recent research directions in automated timetabling." European Journal of Operational Research 140(2): 266-280.
[28]. Carter, M. W. and G. Laporte (1995). Recent developments in practical examination timetabling. International Conference on the Practice and Theory of Automated Timetabling, Springer.
[29]. Carter, M. W. and G. Laporte (1997). Recent developments in practical course timetabling. International Conference on the Practice and Theory of Automated Timetabling, Springer.
[30]. Chu, S.-C., Y.-T. Chen and J.-H. Ho (2006). Timetable scheduling using particle swarm optimization. Innovative Computing, Information and Control, 2006. ICICIC'06. First International Conference on, IEEE.
[31]. Corne, D., P. Ross and H. Fang (1995). "Evolving timetables." The practical handbook of genetic algorithms 1: 219-276.
[32]. Corne, D. W., A. Reynolds and E. Bonabeau (2012). Swarm intelligence. Handbook of Natural Computing, Springer: 1599-1622.
[33]. Di Gaspero, L., B. McCollum and A. Schaerf (2007). The second international timetabling competition (ITC-2007): Curriculum-based course timetabling (track 3), Citeseer.
[34]. Dorigo, M., M. Birattari and T. Stutzle (2006). "Ant colony optimization." IEEE computational intelligence magazine 1(4): 28-39.
[35]. Dorigo, M. and K. Socha (2006). An introduction to ant colony optimization: 26.21-26.14.
[36]. Dorigo, M. and T. Stutzle (2003). "The ant colony optimization metaheuristic: Algorithms, applications, and advances." International series in operations research and management science: 251-286.
[37]. Ejaz, N. and M. Y. Javed (2007). A hybrid approach for course scheduling inspired by die-hard co-operative ant behavior. Automation and Logistics, 2007 IEEE International Conference on, IEEE.
[38]. Eley, M. (2006). Ant algorithms for the exam timetabling problem. International Conference on the Practice and Theory of Automated Timetabling, Springer.
[39]. Fernandes, P., C. S. Pereira and A. Barbosa (2016). "A decision support approach to automatic timetabling in higher education institutions." Journal of Scheduling 19(3): 335-348.
[40]. Fister Jr, I., X.-S. Yang, I. Fister, J. Brest and D. Fister (2013). "A brief review of nature-inspired algorithms for optimization." arXiv preprint arXiv:1307.4186.
[41]. Fong, C. W., H. Asmuni and B. McCollum (2015). "A hybrid swarm-based approach to university timetabling." IEEE Transactions on Evolutionary Computation 19(6): 870-884.
[42]. Fong, C. W., H. Asmuni, B. McCollum, P. McMullan and S. Omatu (2014). "A new hybrid imperialist swarm-based optimization algorithm for university timetabling problems." Information Sciences 283: 1-21.
[43]. Gambardella, L. M., É. D. Taillard and M. Dorigo (1999). "Ant colonies for the quadratic assignment problem." Journal of the operational research society 50(2): 167-176.
[44]. Ghasemi, E., P. Moradi and M. Fathi (2015). Integrating ABC with genetic grouping for university course timetabling problem. Computer and Knowledge Engineering (ICCKE), 2015 5th International Conference on, IEEE.
[45]. Glover, F. (1992). "New ejection chain and alternating path methods for traveling salesman problems." Computer science and operations research 449: 491-507.
[46]. Ilyas, R. and Z. Iqbal (2015). Study of hybrid approaches used for university course timetable problem (UCTP). Industrial Electronics and Applications (ICIEA), 2015 IEEE 10th Conference on, IEEE.
[47]. Jaradat, G. M. and M. Ayob (2010). "An elitist-ant system for solving the post-enrolment course timetabling problem." Database Theory and Application, Bio-Science and Bio-Technology: 167-176.
[48]. Junaedi, D. and N. U. Maulidevi (2011). Solving curriculum-based course timetabling problem with artificial bee colony algorithm. Informatics and Computational Intelligence (ICI), 2011 First International Conference on, IEEE.
[49]. Karaboga, D. and B. Basturk (2007). "A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm." Journal of global optimization 39(3): 459-471.
[50]. Karaboga, D., B. Gorkemli, C. Ozturk and N. Karaboga (2014). "A comprehensive survey: artificial bee colony (ABC) algorithm and applications." Artificial Intelligence Review 42(1): 21-57.
[51]. Katsaragakis, I. V., I. X. Tassopoulos and G. N. Beligiannis (2015). "A comparative study of modern heuristics on the school timetabling problem." Algorithms 8(3): 723-742.
[52]. Kenekayoro, P. and G. Zipamone (2016). "Greedy Ants Colony Optimization Strategy for Solving the Curriculum Based University Course Timetabling Problem." arXiv preprint arXiv:1602.04933.
[53]. Kennedy, J. (2011). Particle swarm optimization. Encyclopedia of machine learning, Springer: 760-766.
[54]. Kennedy, J. and R. Eberhart (1942). Particle swarm optimization 1995 IEEE International Conference on Neural Networks Proceedings, Vols.
[55]. Khang, N. T. T. M., N. B. Phuc and T. T. H. Nuong (2011). The bees algorithm for a practical university timetabling problem in vietnam. Computer Science and Automation Engineering (CSAE), 2011 IEEE International Conference on, IEEE.
[56]. Koshino, M. and T. Otani (2013). Constraint propagation+ Ant Colony Optimization for automated school timetabling. Computational Intelligence & Applications (IWCIA), 2013 IEEE Sixth International Workshop on, IEEE.
[57]. Kristiansen, S. and T. R. Stidsen (2013). A comprehensive study of educational timetabling-a survey, Department of Management Engineering, Technical University of Denmark.
[58]. Lewis, R. (2008). "A survey of metaheuristic-based techniques for university timetabling problems." OR spectrum 30(1): 167-190.
[59]. Lewis, R., B. Paechter and B. McCollum (2007). "Post enrolment based course timetabling: A description of the problem model used for track two of the second international timetabling competition."
[60]. Lutuksin, T. and P. Pongcharoen (2010). Best-worst ant colony system parameter investigation by using experimental design and analysis for course timetabling problem. Computer and Network Technology (ICCNT), 2010 Second International Conference on, IEEE.
[61]. Marie-Sainte, S. L. (2015). "A survey of Particle Swarm Optimization techniques for solving university Examination Timetabling Problem." Artificial Intelligence Review 44(4): 537-546.
[62]. McCollum, B. and N. Ireland (2006). "University timetabling: Bridging the gap between research and practice." E Burke, HR, ed.: PATAT: 15-35.
[63]. McCollum, B., A. Schaerf, B. Paechter, P. McMullan, R. Lewis, A. J. Parkes, L. D. Gaspero, R. Qu and E. K. Burke (2010). "Setting the research agenda in automated timetabling: The second international timetabling competition." INFORMS Journal on Computing 22(1): 120-130.
[64]. MirHassani, S. and F. Habibi (2013). "Solution approaches to the course timetabling problem." Artificial Intelligence Review: 1-17.
[65]. Nothegger, C., A. Mayer, A. Chwatal and G. R. Raidl (2012). "Solving the post enrolment course timetabling problem by ant colony optimization." Annals of Operations Research 194(1): 325-339.
[66]. Oswald, C. (2013). Novel hybrid PSO algorithms with search optimization strategies for a University Course Timetabling Problem. Advanced Computing (ICoAC), 2013 Fifth International Conference on, IEEE.
[67]. Ow, P. S. and T. E. Morton (1988). "Filtered beam search in scheduling." The International Journal Of Production Research 26(1): 35-62.
[68]. Paechter, B. (2014). “Mine’s better than yoursâ€â€“comparing timetables and timetabling algorithms. Proceedings of the 10th International Conference on the Practice and Theory of Automated Timetabling.
[69]. Pandey, J. and A. Sharma (2016). Survey on University timetabling problem. Computing for Sustainable Global Development (INDIACom), 2016 3rd International Conference on, IEEE.
[70]. Pillay, N. (2012). Hyper-heuristics for educational timetabling. Proceedings of the ninth international conference on the practice and theory of automated timetabling (PATAT 2012).
[71]. Pillay, N. (2014). "A survey of school timetabling research." Annals of Operations Research 218(1): 261-293.
[72]. Pillay, N. (2016). "A review of hyper-heuristics for educational timetabling." Annals of Operations Research 239(1): 3-38.
[73]. Sabar, N. R., M. Ayob and G. Kendall (2009). Solving examination timetabling problems using honey-bee mating optimization (ETP-HBMO). Proceedings of the 4th multidisciplinary international scheduling conference: theory and applications (MISTA 2009), Dublin, Ireland.
[74]. 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.
[75]. Schaerf, A. (1999). "A survey of automated timetabling." Artificial intelligence review 13(2): 87-127.
[76]. Shiau, D.-F. (2011). "A hybrid particle swarm optimization for a university course scheduling problem with flexible preferences." Expert Systems with Applications 38(1): 235-248.
[77]. Smith, K. A., D. Abramson and D. Duke (2003). "Hopfield neural networks for timetabling: formulations, methods, and comparative results." Computers & industrial engineering 44(2): 283-305.
[78]. Socha, K., J. Knowles and M. Sampels (2002). "A max-min ant system for the university course timetabling problem." Ant algorithms 2463: 1-13.
[79]. Socha, K., M. Sampels and M. Manfrin (2003). "Ant algorithms for the university course timetabling problem with regard to the state-of-the-art." Applications of evolutionary computing: 334-345.
[80]. Sörensen, K. (2015). "Metaheuristics—the metaphor exposed." International Transactions in Operational Research 22(1): 3-18.
[81]. Swan, J., S. Adriaensen, M. Bishr, E. K. Burke, J. A. Clark, P. De Causmaecker, J. Durillo, K. Hammond, E. Hart and C. G. Johnson (2015). A research agenda for metaheuristic standardization. Proceedings of the XI Metaheuristics International Conference.
[82]. Tang, W. and Q. Wu (2009). "Biologically inspired optimization: a review." Transactions of the Institute of Measurement and Control 31(6): 495-515.
[83]. Tassopoulos, I. X. and G. N. Beligiannis (2012). "A hybrid particle swarm optimization based algorithm for high school timetabling problems." applied soft computing 12(11): 3472-3489.
[84]. Tassopoulos, I. X. and G. N. Beligiannis (2012). "Solving effectively the school timetabling problem using particle swarm optimization." Expert Systems with Applications 39(5): 6029-6040.
[85]. Thepphakorn, T., P. Pongcharoen and C. Hicks (2014). "An ant colony based timetabling tool." International Journal of Production Economics 149: 131-144.
[86]. Vrielink, R. A. O., D. Schepers, E. A. Jansen and E. W. Hans (2016). Practices in Timetabling in Higher Education Institutions. PATAT 2016: Proceedings of the 11th International Conference of the Practice and Theory of Automated Timetabling.
[87]. Weng, F. C. and H. Bin Asmuni (2013). "An automated approach based on bee swarm in tackling university examination timetabling problem." Int J Electr Comput Sci 13(02): 8-23.
[88]. Weyland, D. (2012). "A rigorous analysis of the harmony search algorithm: how the research community can be." Modeling, Analysis, and Applications in Metaheuristic Computing: Advancements and Trends: Advancements and Trends 72.
[89]. Yang, X.-S. (2010). Nature-inspired metaheuristic algorithms, Luniver press.
[90]. Yang, X.-S. and X. He (2013). "Firefly algorithm: recent advances and applications." International Journal of Swarm Intelligence 1(1): 36-50.
[91]. Yang, X. S. (2010). "Firefly algorithm." Engineering optimization: 221-230.
[92]. Zou, K., Y. Qian, X. Liu and P. Zhang (2010). Based on discrete particle swarm algorithm and simulated annealing algorithm to solve course timetabling problem. Computer, Mechatronics, Control and Electronic Engineering (CMCE), 2010 International Conference on, IEEE.