A study on optimization methods for solving course timetabling problem in university

  • Authors

    • Munirah Mazlan
    • Mokhairi Makhtar
    • Ahmad Firdaus Khair Ahmad Khairi
    • Mohamed Afendee Mohamed
    • Mohd Nordin Abdul Rahman
    2018-04-06
    https://doi.org/10.14419/ijet.v7i2.14.12824
  • Course Timetabling, Classification, Meta-Heuristics, Optimization, Hard Constraints, Soft Constraints.

  • Abstract

    Course timetabling is one of the most important processes faced by any educational institution. However, the course timetabling process is time consuming and tiresome as it needs to be done for each regular semester. This paper aims to study on the Optimization methods to solve the course timetabling problem. The study is obtained and discussed by categorizing between the classification of Hard Constraint and Soft Constraint and the classification of Optimization Methods. From the study, it shows that Meta-Heuristics are the mostly method used in solving the course timetabling problem. It is concluded that this method is suitable for future used compared to other techniques studied. An analysis and observation will be carried out for the research future.

     

     

  • References

    1. [1] S. Hosny, M., & Fatima, "A Survey of Genetic Algorithms for the University Timetabling Problem Manar Hosny and Shameem Fatima," Int. Proc. Comput. Sci. Inf. Technol., vol. 13, 2011.
      [2] K. Socha, M. Sampels, and M. Manfrin, "Ant Algorithms for the University Course Timetabling Problem with Regard to the State-of-the-Art," Appl. Evol. Comput. pp. 334-345, 2003.
      [3] A. Schaerf, "Survey of automated timetabling," Artif. Intell. Rev., vol. 13, no. 2, pp. 87-127, 1999.
      [4] H. Babaei, J. Karimpour, and A. Hadidi, "A survey of approaches for university course timetabling problem," Comput. Ind. Eng., vol. 86, pp. 43-59, 2015.
      [5] G. Molnar and M. Cupi, "University Course Timetabling Using AGO: A Case Study on Laboratory Exercises," Knowledge-Based Intell. Inf. Eng. Syst. Pt I, vol. 6276, no. 36, pp. 100-110, 2010.
      [6] R. Lewis, "A survey of metaheuristic-based techniques for University Timetabling problems," OR Spectr., vol. 30, no. 1, pp. 167-190, 2008.
      [7] R. Burke, E. K., McCollum, B., Meisels, A., Petrovic, S., & Qu, "A Graph-Based Hyper-Heuristic for Educational Timetablong problem," Eur. J. Oper. Res., vol. 176, no. 1, pp. 177-192, 2007.
      [8] S. G. M, W. P, and Buttcher, "A standard framework for timetabling problems," Pract. Theory Autom. Timetabling Iv, vol. 2740, pp. 24-38, 2003.
      [9] E. K. Burke, J. Mare?, A. J. Parkes, and H. Rudov, "A supernodal formulation of vertex colouring with applications in course timetabling," Ann. Oper. Res., vol. 179, no. 1, pp. 105-130, 2010.
      [10] T. Nottingham and N. E. User, "Structured cases in case-based reasoning-re-using and adapting cases for time-tabling problems," Knowledge-Based Syst., vol. 13, no. 2, pp. 159-165, 2000.
      [11] S. Abdullah, K. Shaker, B. Mccollum, and P. Mcmullan, "Dual sequence simulated annealing with round-robin approach for university course timetabling," Eur. Conf. Evol. Comput. Comb. Optim. pp. 1-10, 2010.
      [12] S. Yassin, R. M., Nazri, M. Z. A., & Abdullah, "Hybrid approach: Tabu-based non-linear great deluge for the course timetabling problem," Res. J. Appl. Sci., vol. 8, no. 2, pp. 131-138, 2013.
      [13] E. Burke and J. Newall, "Enhancing Timetable Solutions with Local Search Methods," Pract. Theory Autom. Timetabling IV, vol. 2740, pp. 195-206, 2003.
      [14] R. Lewis and B. Paechter, "Application of the Grouping Genetic Algorithm to University Course Timetabling," Evol. Comput. Comb. Optima. pp. 144-153, 2005.
      [15] S. Kazarlis, "Solving University Timetabling Problems Using Advanced Genetic Algorithms," vol. 2, no. 7, pp. 8-12, 2005.
      [16] M. Tawfeek, A. El-sisi, A. Keshk, and F. Torkey, "Cloud Task Scheduling Based on Ant Colony Optimization," Int. Arab J. Inf. Technol., vol. 12, no. 2, pp. 129-136, 2015.
      [17] J. Su, "Using Ant Colony Optimization to Solve Train Timetabling Problem of Mass Rapid Transit," pp. 2-5, 1991.
      [18] D. Merkle, M. Middendorf, and H. Schmeck, "Ant Colony Optimization for Resource-Constrained Project Scheduling," vol. 6, no. 4, pp. 333-346, 2002.
      [19] H. Rudov, "University Course Timetabling with Soft Constraints," 2016.
      [20] T. Nottingham, "Case-based heuristic selection for timetabling problems," J. Sched., vol. 9, no. 2, pp. 115-132, 2006.
      [21] A R. Mushi, "Two Phase Heuristic Algorithm for the University Course Timetabling Problem?: the Case of University of Dar Es Salaam," Tanzania J. Sci., vol. 37, no. 2008, pp. 73-83, 2011.
      [22] I. Mï¿©ndez-D?az, P. Zabala, and J. J. Miranda-Bront, "An ILP based heuristic for a generalization of the post-enrollment course timetabling problem," Comput. Oper. Res., vol. 76, pp. 195-207, 2016.
      [23] D. Banks, P. Van Beek, and A. Meisels, "A Heuristic Incremental Modeling Approach to Course Timetabling," Adv. Artif. Intell. pp. 16-29, 1998.
      [24] N. Pillay, "Hyper-Heuristics for Educational Timetabling," Proc. ninth Int. Conf. Pract. Theory Autom. Timetabling (PATAT 2012), no. August, pp. 29-31, 2012.
      [25] E. K. Burke, J. D. L. Silva, and E. Soubeiga, "Multi-objective hyper-heuristic approaches for space allocation and timetabling," Metaheuristics Prog. as Real Probl. Solvers, pp. 129-158, 2005.
      [26] L. Ingolotti, A. Lova, F. Barber, P. Tormos, M. A. Salido, and M. Abril, "New Heuristics to Solve the" CSOP" Railway Timetabling Problem," Int. Conf. Ind. Eng. Other Appl. Appl. Intell. Syst., pp. 400-409, 2006.
      [27] I. H. Osman and J. P. Kelly, "Meta-Heuristics: An Overview," in Meta-Heuristics, 1996, pp. 1-21.
      [28] O. Rossi-doria et al., "A Comparison of the Performance of Different Metaheuristics on the Timetabling Problem," Patat 2002, pp. 329-351, 2003.
      [29] G. H. G. Fonseca, H. G. Santos, and E. G. Carrano, "Integrating matheuristics and metaheuristics for timetabling," Comput. Oper. Res., vol. 74, pp. 108-117, 2016.
      [30] ?. P. Dorneles, O. C. B. de Ara?job, and L. S. Buriola, "A column generation approach to high school timetabling modeled as a multicommodity flow problem," Eur. J. Oper. Res., vol. 256, pp. 685-695, 2016.
      [31] K. Nurmi and J. Kyng?s, "A Framework for School Timetabling Problem," Proc. 3rd Multidiscip. Int. Sched. Conf. theory Appl. Paris, pp. 386-393, 2007.
      [32] T. Thepphakorn, P. Pongcharoen, and C. Hicks, "An ant colony based timetabling tool," Intern. J. Prod. Econ., vol. 149, pp. 131-144, 2014.
      [33] S. Abdullah, H. Turabieh, B. Mccollum, and E. K. Burke, "An Investigation of a Genetic Algorithm and Sequential Local Search Approach for Curriculum-based Course Timetabling Problems," Proc. Multildisciplinary Int. Conf. Sched. Theory Appl. (MISTA 2009), Dublin, Irel. pp. 737-731, 2009.
      [34] L. G. Bharade, A. B. Khandekar, and P. R. P. Bijwe, "Automatic Time Table Generator Using Genetic Algorithm," Imp. J. Interdiscip. Res., vol. 2, no. 5, 2016.
      [35] S. Ceschia, L. Di Gaspero, and A. Schaerf, "Design, engineering, and experimental analysis of a simulated annealing approach to the post-enrolment course timetabling problem," Comput. Oper. Res., vol. 39, no. 7, pp. 1615-1624, 2012.
      [36] C. A. D. Mahiba, A. A., & Durai, "Genetic algorithm with search bank strategies for university course timetabling problem," Procedia Eng., vol. 38, pp. 253-263, 2012.
      [37] K. Patrick and Z. Godswill, "Greedy Ants Colony Optimization Strategy for Solving the Curriculum Based University Course Timetabling Problem," Br. J. Math. Comput. Sci., vol. 14, no. 2, pp. 1-10, 2016.
      [38] R. Qu and E. K. Burke, "Hybridizations within a graph-based hyper-heuristic framework for university timetabling problems," J. Oper. Res. Soc., vol. 60, no. 9, pp. 1273-1285, 2008.
      [39] K. Shaker and S. Abdullah, "Incorporating Great Deluge Approach with Kempe Chain Neighbourhood Structure for Curriculum-Based Course Timetabling Problems," Data Min. Optim. 2009. DMO'09. Second Conf., no. October, pp. 149-153, 2009.
      [40] S. Abdullah, K. Shaker, B. Mccollum, and P. Mcmullan, "Incorporating Great Deluge with Kempe Chain Neighbourhood Structure for the Enrolment-Based Course Timetabling Problem," RSKT, pp. 70-77, 2010.
      [41] L. Di Gaspero and A. Schaerf, "Multi-Neighbourhood Local Search with Application to Course Timetabling," Int. Conf. Pract. Theory Autom. Timetabling, pp. 262-275, 2002.
      [42] J. Hao and F. Glover, "Neighborhood Analysis?: a Case Study on Curriculum-Based Course Timetabling," J. Heuristics, vol. 17, no. 2, pp. 97-118, 2011.
      [43] E. K. Burke and S. Petrovic, "Recent research directions in automated timetabling," Eur. J. Oper. Res., vol. 140, no. 2, pp. 266-280, 2002.
      [44] S. Abdennadher and M. Marte, "u UNIVERSITY COURSE TIMETABLING USING CONSTRAINT HANDLING," pp. 311-325, 2000.
      [45] P. Avella and I. V. Ev, "A computational study of a cutting plane algorithm for university course timetabling," J. Sched., vol. 8, no. 6, pp. 497-514, 2005.
      [46] M. A. S. Elmohamed, G. C. Fox, P. Coddington, and P. Coddington, "A Comparison of Annealing Techniques for Academic Course Scheduling," Int. Conf. Pract. Theory Autom. Timetabling. Springer, Berlin, Heidelberg. pp. 92-112, 1997.
      [47] M. Chiarandini, M. Birattari, K. Socha, and O. Rossi-Doria, "An effective hybrid algorithm for university course timetabling," J. Sched., vol. 9, no. 5, pp. 403-432, 2006.
      [48] K. Murray, "Modeling and Solution of a Complex University Course Timetabling Problem," 2016.
      [49] T. Mller, H. Rudov?, and R. Bart?k, "Minimal Perturbation Problem in Course Timetabling," Int. Conf. Pract. Theory Autom. Timetabling, vol. 3616, pp. 126-146, 2005.
      [50] N. R. Sabar, M. Ayob, G. Kendall, and R. Qu, "A honey-bee mating optimization algorithm for educational timetabling problems," Eur. J. Oper. Res., vol. 216, no. 3, pp. 533-543, 2012.
      [51] M. Ayob and G. Jaradat, "Hybrid Ant Colony Systems for course timetabling problems," in 2009 2nd Conference on Data Mining and Optimization, DMO 2009, 2009, pp. 120-126.
      [52] S. Abdullah, E. K. Burke, and B. Mccollum, "A Hybrid Evolutionary Approach to the University Course Timetabling Problem," Evol. Comput. pp. 1764-1768, 2007.
      [53] S. Abdullah, H. Turabieh, B. Mccollum, and P. Mcmullan, "A hybrid metaheuristic approach to the university course timetabling problem," J. Heuristics, vol. 18, no. 1, pp. 1-23, 2012.
      [54] O. Rossi-doria, C. Blum, J. Knowles, M. Sampels, K. Socha, and B. Paechter, "A local search for the timetabling problem," Proc. 4th Int. Conf. Pract. Theory Autom. Timetabling, PATAT, pp. 124-127, 2002.
      [55] K. Socha, J. Knowles, and M. Sampels, "A MAX - MIN Ant System for the University Course Timetabling Problem," Ant algorithms, pp. 1-13, 2002.
      [56] S. N. Jat, "A Memetic Algorithm for the University Course Timetabling Problem," Tools with Artif. Intell. 2008. ICTAI'08. 20th IEEE Int. Conf., vol. 1, pp. 427-433, 2008.
      [57] S. Naseem and J. Shengxiang, "A Hybrid Genetic Algorithm and Tabu Search Approach for Post Enrolment Course Timetabling," J. Sched., vol. 14, no. 6, pp. 617-637, 2010.
      [58] E. K. Burke, G. Kendall, and E. Soubeiga, "A Tabu-Search Hyperheuristic for Timetabling and Rostering," J. Heuristics, vol. 9, no. 6, pp. 451-470, 2003.
      [59] E. Burke, Y. Bykov, J. Newall, and S. Petrovi, "A time-predefined approach to course timetabling," Yugosl. J. Oper. Res., vol. 13, no. 2, pp. 139-151, 2003.
      [60] G. M. Jaradat and M. Ayob, "An elitist-ant system for solving the post-enrolment course timetabling problem," Database Theory Appl. Bio-Science Bio-Technology, pp. 167-176, 2010.
      [61] P. Mcmullan, "An Extended Implementation of the Great Deluge Algorithm for Course Timetabling," Comput. Sci., pp. 538-545, 2007.
      [62] A. Scheduling, J. Campus, W. Road, and U. Kingdom, "An investigation of variable neighbourhood search for university course timetabling," 2nd Multidiscip. Int. Conf. Sched. Theory Appl., pp. 413-427, 2005.
      [63] G. M. Jaradat, "Big Bang-Big Crunch Optimization Algorithm to Solve the Course Timetabling Problem," Intell. Syst. Des. Appl. (ISDA), 2010 10th Int. Conf., pp. 1448-1452, 2010.
      [64] S. Abdullah, H. Turabeih, and B. Mccollum, "Electromagnetism-like Mechanism with Force Decay Rate Great Deluge for the Course Timetabling Problem," 2009, no. 1986, pp. 497-504.
      [65] D. Landa-silva and J. H. Obit, "Evolutionary Non-linear Great Deluge for University Course Timetabling," HAIS, pp. 269-276, 2009.
      [66] A. Abuhamdah, "Experimental Result of Late Acceptance Randomized Descent Algorithm for Solving Course Timetabling Problems," Int. J. Comput. Sci. Netw. Secur. vol. 10, no. 1, pp. 192-200, 2010.
      [67] S. Yang and S. N. Jat, "Genetic Algorithms with Guided and Local Search Strategies for University Course Timetabling," IEEE Trans. Syst. Man, Cybern. Part C (Applications Rev., vol. 41, no. 1, pp. 93-106, 2011.
      [68] D. Landa-silva and J. H. Obit, "Great Deluge with Non-linear Decay Rate for Solving Course Timetabling Problems," Intell. Syst. 2008. IS'08. Fourth Int. IEEE Conf., vol. 1, pp. 8-11, 2008.
      [69] E. K. Burke, B. L. MacCarthy, S. Petrovic, and R. Qu, "Knowledge discovery in a hyper-heuristic for course timetabling using case-based reasoning," Int. Conf. Pract. Theory Autom. Timetabling, vol. 2740, pp. 276-287, 2002.
      [70] D. Strnad and N. Guid, "Metaheuristics for university course timetabling," Evol. Shed. pp. 237-272, 2007.
      [71] J. H. Obit, D. Landa-silva, D. Ouelhadj, and M. Sevaux, "Non-Linear Great Deluge with Learning Mechanism for Solving the Course Timetabling Problem," 8th Metaheuristics Int. Conf. (MIC 2009), pp. 1-10, 2009.
      [72] J. Studenovsk?, "Polynomial reduction of time-space scheduling to time scheduling," Discret. Appl. Math., vol. 157, no. 7, pp. 1364-1378, 2009.
      [73] R. Lewis, "Post Enrolment based Course Timetabling?: A Description of the Problem Model used for Track Two of the Second International Timetabling Competition," pp. 1-9, 2007.
      [74] C. Nothegger, A. Mayer, A. Chwatal, and G. R. Raidl, "Solving the post enrolment course timetabling problem by ant colony optimization," Ann. Oper. Res., vol. 194, no. 1, pp. 325-339, 2012.
      [75] N. Boland, B. D. Hughes, L. T. G. Merlot, and P. J. Stuckey, "New Integer Linear Programming Approaches for Course Timetabling," Comput. Oper. Res., vol. 35, no. 7, pp. 2209-2233, 2006.
      [76] P. Kostuch and K. Socha, "Hardness Prediction for the University Course Timetabling Problem."
      [77] P. Kostuch, "The university course timetabling problem with a three-phase approach," Int. Conf. Pract. Theory Autom. Timetabling, pp. 109-125, 2004.
      [78] W. Erben and J. Keppler, "A Genetic Algorithm Solving a Weekly Course-Timetabling Problem," Int. Conf. Pract. Theory Autom. Timetabling, pp. 198-211, 1995.
      [79] A. Dammak, J. A. Ferland, and H. Kamoun, "Course timetabling at a Tunisian university: A case study.," J. Syst. Sci. Syst. Eng., vol. 17, no. 3, pp. 334-352, 2008.
      [80] T. Thepphakorn and P. Pongcharoen, "Heuristic ordering for ant colony based timetabling tool," J. Appl. Oper. Res., vol. 5, no. 3, pp. 113-123, 2013.
      [81] T. Mller and R. Bart?k, "Interactive Timetabling: Concepts, Techniques, and Practical Results," PATAT 2002 Proc. 4th Int. Conf. Pract. Theory Autom. Timetabling, no. 201, pp. 58-72, 2002.
      [82] H. Kanoh and Y. Sakamoto, "Knowledge-Based Genetic Algorithm for University Course Timetabling Problems," Int. J. Knowledge-based Intell. Eng. Syst., vol. 12, no. 4, pp. 283-294, 2008.
      [83] E. K. Burke, B. L. MacCarthy, S. Petrovic, and R. Qu, "Multiple-retrieval case-based reasoning for course timetabling problems," J. Oper. Res. Soc., vol. 57, no. 2, pp. 148-162, 2006.
      [84] A. R. Mushi, "Tabu search heuristic for university course timetabling problem," African J. Sci. Technol., vol. 7, no. 1, pp. 34-40, 2006.
      [85] E. K. Kalender, M., Kheiri, A., ?zcan, E., & Burke, "A Greedy Gradient-Simulated Annealing Hyper-heuristic for a Curriculum-based Course Timetabling Problem," Comput. Intell. 12th UK Work. pp. 1-8, 2012.
      [86] K. Nguyen, P. Nguyen, and N. Tran, "A hybrid algorithm of Harmony Search and Bees Algorithm for a University Course Timetabling Problem," Int. J. Comput. Sci., vol. 9, no. 1, pp. 12-17, 2012.
      [87] L. Zhipeng, "Adaptive tabu search for course timetabling," Eur. J. Oper. Res., vol. 200, no. 1, pp. 235-244, 2010.
      [88] R. As?n and A. Robert, "Curriculum-based course timetabling with SAT and MaxSAT," Ann. Oper. Res., vol. 218, no. 1, pp. 71-91, 2014.
      [89] M. Doulaty, M. R. F. Derakhshi, and M. Abdi, "Timetabling: A State-of-the-Art Evolutionary Approach," Int. J. Mach. Learn. Comput. vol. 3, no. 3, pp. 255-258, 2013.
      [90] V. Dino Matija?, G. Molnar, M. ?upi?, D. Jakobovi?, and B. Dalbelo Ba?i?, "University course timetabling using ACO: A case study on laboratory exercises," Int. Conf. Knowledge-Based Intell. Inf. Eng. Syst., vol. 6276, no. 1, pp. 100-110, 2010.
      [91] E. K. Burke, J. Mare?, A. J. Parkes, and H. Rudov, "A Branch-and-cut Procedure for the Udine Course Timetabling Problem," pp. 1-22, 2010.

  • Downloads

  • How to Cite

    Mazlan, M., Makhtar, M., Firdaus Khair Ahmad Khairi, A., Afendee Mohamed, M., & Nordin Abdul Rahman, M. (2018). A study on optimization methods for solving course timetabling problem in university. International Journal of Engineering & Technology, 7(2.14), 196-200. https://doi.org/10.14419/ijet.v7i2.14.12824

    Received date: 2018-05-14

    Accepted date: 2018-05-14

    Published date: 2018-04-06