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

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 MetaHeuristics 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.

Keywords
Course Timetabling; Classification; MetaHeuristics; Optimization; Hard Constraints; Soft Constraints.

References
[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 StateoftheArt," Appl. Evol. Comput. pp. 334345, 2003.
[3] A. Schaerf, "Survey of automated timetabling," Artif. Intell. Rev., vol. 13, no. 2, pp. 87127, 1999.
[4] H. Babaei, J. Karimpour, and A. Hadidi, "A survey of approaches for university course timetabling problem," Comput. Ind. Eng., vol. 86, pp. 4359, 2015.
[5] G. Molnar and M. Cupi, "University Course Timetabling Using AGO: A Case Study on Laboratory Exercises," KnowledgeBased Intell. Inf. Eng. Syst. Pt I, vol. 6276, no. 36, pp. 100110, 2010.
[6] R. Lewis, "A survey of metaheuristicbased techniques for University Timetabling problems," OR Spectr., vol. 30, no. 1, pp. 167190, 2008.
[7] R. Burke, E. K., McCollum, B., Meisels, A., Petrovic, S., & Qu, "A GraphBased HyperHeuristic for Educational Timetablong problem," Eur. J. Oper. Res., vol. 176, no. 1, pp. 177192, 2007.
[8] S. G. M, W. P, and Buttcher, "A standard framework for timetabling problems," Pract. Theory Autom. Timetabling Iv, vol. 2740, pp. 2438, 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. 105130, 2010.
[10] T. Nottingham and N. E. User, "Structured cases in casebased reasoningreusing and adapting cases for timetabling problems," KnowledgeBased Syst., vol. 13, no. 2, pp. 159165, 2000.
[11] S. Abdullah, K. Shaker, B. Mccollum, and P. Mcmullan, "Dual sequence simulated annealing with roundrobin approach for university course timetabling," Eur. Conf. Evol. Comput. Comb. Optim. pp. 110, 2010.
[12] S. Yassin, R. M., Nazri, M. Z. A., & Abdullah, "Hybrid approach: Tabubased nonlinear great deluge for the course timetabling problem," Res. J. Appl. Sci., vol. 8, no. 2, pp. 131138, 2013.
[13] E. Burke and J. Newall, "Enhancing Timetable Solutions with Local Search Methods," Pract. Theory Autom. Timetabling IV, vol. 2740, pp. 195206, 2003.
[14] R. Lewis and B. Paechter, "Application of the Grouping Genetic Algorithm to University Course Timetabling," Evol. Comput. Comb. Optima. pp. 144153, 2005.
[15] S. Kazarlis, "Solving University Timetabling Problems Using Advanced Genetic Algorithms," vol. 2, no. 7, pp. 812, 2005.
[16] M. Tawfeek, A. Elsisi, A. Keshk, and F. Torkey, "Cloud Task Scheduling Based on Ant Colony Optimization," Int. Arab J. Inf. Technol., vol. 12, no. 2, pp. 129136, 2015.
[17] J. Su, "Using Ant Colony Optimization to Solve Train Timetabling Problem of Mass Rapid Transit," pp. 25, 1991.
[18] D. Merkle, M. Middendorf, and H. Schmeck, "Ant Colony Optimization for ResourceConstrained Project Scheduling," vol. 6, no. 4, pp. 333346, 2002.
[19] H. Rudov, "University Course Timetabling with Soft Constraints," 2016.
[20] T. Nottingham, "Casebased heuristic selection for timetabling problems," J. Sched., vol. 9, no. 2, pp. 115132, 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. 7383, 2011.
[22] I. M￩ndezD?az, P. Zabala, and J. J. MirandaBront, "An ILP based heuristic for a generalization of the postenrollment course timetabling problem," Comput. Oper. Res., vol. 76, pp. 195207, 2016.
[23] D. Banks, P. Van Beek, and A. Meisels, "A Heuristic Incremental Modeling Approach to Course Timetabling," Adv. Artif. Intell. pp. 1629, 1998.
[24] N. Pillay, "HyperHeuristics for Educational Timetabling," Proc. ninth Int. Conf. Pract. Theory Autom. Timetabling (PATAT 2012), no. August, pp. 2931, 2012.
[25] E. K. Burke, J. D. L. Silva, and E. Soubeiga, "Multiobjective hyperheuristic approaches for space allocation and timetabling," Metaheuristics Prog. as Real Probl. Solvers, pp. 129158, 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. 400409, 2006.
[27] I. H. Osman and J. P. Kelly, "MetaHeuristics: An Overview," in MetaHeuristics, 1996, pp. 121.
[28] O. Rossidoria et al., "A Comparison of the Performance of Different Metaheuristics on the Timetabling Problem," Patat 2002, pp. 329351, 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. 108117, 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. 685695, 2016.
[31] K. Nurmi and J. Kyng?s, "A Framework for School Timetabling Problem," Proc. 3rd Multidiscip. Int. Sched. Conf. theory Appl. Paris, pp. 386393, 2007.
[32] T. Thepphakorn, P. Pongcharoen, and C. Hicks, "An ant colony based timetabling tool," Intern. J. Prod. Econ., vol. 149, pp. 131144, 2014.
[33] S. Abdullah, H. Turabieh, B. Mccollum, and E. K. Burke, "An Investigation of a Genetic Algorithm and Sequential Local Search Approach for Curriculumbased Course Timetabling Problems," Proc. Multildisciplinary Int. Conf. Sched. Theory Appl. (MISTA 2009), Dublin, Irel. pp. 737731, 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 postenrolment course timetabling problem," Comput. Oper. Res., vol. 39, no. 7, pp. 16151624, 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. 253263, 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. 110, 2016.
[38] R. Qu and E. K. Burke, "Hybridizations within a graphbased hyperheuristic framework for university timetabling problems," J. Oper. Res. Soc., vol. 60, no. 9, pp. 12731285, 2008.
[39] K. Shaker and S. Abdullah, "Incorporating Great Deluge Approach with Kempe Chain Neighbourhood Structure for CurriculumBased Course Timetabling Problems," Data Min. Optim. 2009. DMO'09. Second Conf., no. October, pp. 149153, 2009.
[40] S. Abdullah, K. Shaker, B. Mccollum, and P. Mcmullan, "Incorporating Great Deluge with Kempe Chain Neighbourhood Structure for the EnrolmentBased Course Timetabling Problem," RSKT, pp. 7077, 2010.
[41] L. Di Gaspero and A. Schaerf, "MultiNeighbourhood Local Search with Application to Course Timetabling," Int. Conf. Pract. Theory Autom. Timetabling, pp. 262275, 2002.
[42] J. Hao and F. Glover, "Neighborhood Analysis?: a Case Study on CurriculumBased Course Timetabling," J. Heuristics, vol. 17, no. 2, pp. 97118, 2011.
[43] E. K. Burke and S. Petrovic, "Recent research directions in automated timetabling," Eur. J. Oper. Res., vol. 140, no. 2, pp. 266280, 2002.
[44] S. Abdennadher and M. Marte, "u UNIVERSITY COURSE TIMETABLING USING CONSTRAINT HANDLING," pp. 311325, 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. 497514, 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. 92112, 1997.
[47] M. Chiarandini, M. Birattari, K. Socha, and O. RossiDoria, "An effective hybrid algorithm for university course timetabling," J. Sched., vol. 9, no. 5, pp. 403432, 2006.
[48] K. Murray, "Modeling and Solution of a Complex University Course Timetabling Problem," 2016.
[49] T. M￼ller, H. Rudov?, and R. Bart?k, "Minimal Perturbation Problem in Course Timetabling," Int. Conf. Pract. Theory Autom. Timetabling, vol. 3616, pp. 126146, 2005.
[50] N. R. Sabar, M. Ayob, G. Kendall, and R. Qu, "A honeybee mating optimization algorithm for educational timetabling problems," Eur. J. Oper. Res., vol. 216, no. 3, pp. 533543, 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. 120126.
[52] S. Abdullah, E. K. Burke, and B. Mccollum, "A Hybrid Evolutionary Approach to the University Course Timetabling Problem," Evol. Comput. pp. 17641768, 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. 123, 2012.
[54] O. Rossidoria, 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. 124127, 2002.
[55] K. Socha, J. Knowles, and M. Sampels, "A MAX  MIN Ant System for the University Course Timetabling Problem," Ant algorithms, pp. 113, 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. 427433, 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. 617637, 2010.
[58] E. K. Burke, G. Kendall, and E. Soubeiga, "A TabuSearch Hyperheuristic for Timetabling and Rostering," J. Heuristics, vol. 9, no. 6, pp. 451470, 2003.
[59] E. Burke, Y. Bykov, J. Newall, and S. Petrovi, "A timepredefined approach to course timetabling," Yugosl. J. Oper. Res., vol. 13, no. 2, pp. 139151, 2003.
[60] G. M. Jaradat and M. Ayob, "An elitistant system for solving the postenrolment course timetabling problem," Database Theory Appl. BioScience BioTechnology, pp. 167176, 2010.
[61] P. Mcmullan, "An Extended Implementation of the Great Deluge Algorithm for Course Timetabling," Comput. Sci., pp. 538545, 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. 413427, 2005.
[63] G. M. Jaradat, "Big BangBig Crunch Optimization Algorithm to Solve the Course Timetabling Problem," Intell. Syst. Des. Appl. (ISDA), 2010 10th Int. Conf., pp. 14481452, 2010.
[64] S. Abdullah, H. Turabeih, and B. Mccollum, "Electromagnetismlike Mechanism with Force Decay Rate Great Deluge for the Course Timetabling Problem," 2009, no. 1986, pp. 497504.
[65] D. Landasilva and J. H. Obit, "Evolutionary Nonlinear Great Deluge for University Course Timetabling," HAIS, pp. 269276, 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. 192200, 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. 93106, 2011.
[68] D. Landasilva and J. H. Obit, "Great Deluge with Nonlinear Decay Rate for Solving Course Timetabling Problems," Intell. Syst. 2008. IS'08. Fourth Int. IEEE Conf., vol. 1, pp. 811, 2008.
[69] E. K. Burke, B. L. MacCarthy, S. Petrovic, and R. Qu, "Knowledge discovery in a hyperheuristic for course timetabling using casebased reasoning," Int. Conf. Pract. Theory Autom. Timetabling, vol. 2740, pp. 276287, 2002.
[70] D. Strnad and N. Guid, "Metaheuristics for university course timetabling," Evol. Shed. pp. 237272, 2007.
[71] J. H. Obit, D. Landasilva, D. Ouelhadj, and M. Sevaux, "NonLinear Great Deluge with Learning Mechanism for Solving the Course Timetabling Problem," 8th Metaheuristics Int. Conf. (MIC 2009), pp. 110, 2009.
[72] J. Studenovsk?, "Polynomial reduction of timespace scheduling to time scheduling," Discret. Appl. Math., vol. 157, no. 7, pp. 13641378, 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. 19, 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. 325339, 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. 22092233, 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 threephase approach," Int. Conf. Pract. Theory Autom. Timetabling, pp. 109125, 2004.
[78] W. Erben and J. Keppler, "A Genetic Algorithm Solving a Weekly CourseTimetabling Problem," Int. Conf. Pract. Theory Autom. Timetabling, pp. 198211, 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. 334352, 2008.
[80] T. Thepphakorn and P. Pongcharoen, "Heuristic ordering for ant colony based timetabling tool," J. Appl. Oper. Res., vol. 5, no. 3, pp. 113123, 2013.
[81] T. M￼ller and R. Bart?k, "Interactive Timetabling: Concepts, Techniques, and Practical Results," PATAT 2002 Proc. 4th Int. Conf. Pract. Theory Autom. Timetabling, no. 201, pp. 5872, 2002.
[82] H. Kanoh and Y. Sakamoto, "KnowledgeBased Genetic Algorithm for University Course Timetabling Problems," Int. J. Knowledgebased Intell. Eng. Syst., vol. 12, no. 4, pp. 283294, 2008.
[83] E. K. Burke, B. L. MacCarthy, S. Petrovic, and R. Qu, "Multipleretrieval casebased reasoning for course timetabling problems," J. Oper. Res. Soc., vol. 57, no. 2, pp. 148162, 2006.
[84] A. R. Mushi, "Tabu search heuristic for university course timetabling problem," African J. Sci. Technol., vol. 7, no. 1, pp. 3440, 2006.
[85] E. K. Kalender, M., Kheiri, A., ?zcan, E., & Burke, "A Greedy GradientSimulated Annealing Hyperheuristic for a Curriculumbased Course Timetabling Problem," Comput. Intell. 12th UK Work. pp. 18, 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. 1217, 2012.
[87] L. Zhipeng, "Adaptive tabu search for course timetabling," Eur. J. Oper. Res., vol. 200, no. 1, pp. 235244, 2010.
[88] R. As?n and A. Robert, "Curriculumbased course timetabling with SAT and MaxSAT," Ann. Oper. Res., vol. 218, no. 1, pp. 7191, 2014.
[89] M. Doulaty, M. R. F. Derakhshi, and M. Abdi, "Timetabling: A StateoftheArt Evolutionary Approach," Int. J. Mach. Learn. Comput. vol. 3, no. 3, pp. 255258, 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. KnowledgeBased Intell. Inf. Eng. Syst., vol. 6276, no. 1, pp. 100110, 2010.
[91] E. K. Burke, J. Mare?, A. J. Parkes, and H. Rudov, "A Branchandcut Procedure for the Udine Course Timetabling Problem," pp. 122, 2010.

View 
Download  Article ID: 12824 
