A study on university course and exam timetabling problems and methods: an optimization survey

  • Authors

    • Ahmad Firdaus Khair
    • Mokhairi Makhtar
    • Munirah Mazlan
    • Mohamad Afendee Mohamed
    • Mohd Nordin Abdul Rahman
    2018-04-06
    https://doi.org/10.14419/ijet.v7i2.14.12823
  • Examination Timetabling, Scheduling, Ant Colony Optimization, Ant System, Optimization.

  • Abstract

    The objective of this paper was to retrieve the overview approaches that have been proposed and classification constraints related to previ-ous papers of timetabling problems. Optimisation and scheduling are essential problems in every type of timetabling that can be considered as a non-deterministic polynomial. The objective of this paper to investigate the course and exam timetabling problem by presented classifi-cation table of set of constraints and describes the most reliable method that has been used to solve university timetabling problem. The re-sult of study concerned the two most successfully method that widely used for optimising course and exam timetable. The contribution of this study also help to provide knowledge and idea for further surveys.

     

  • References

    1. [1] E. A. Abdelhalim and G. A. El Khayat, "A Utilization-based Genetic Algorithm for Solving the University Timetabling Problem (UGA)," Alexandria Eng. J., vol. 55, no. 2, pp. 1395-1409, 2016.
      [2] S. Abdennadher and M. Marte, "University course timetabling using constraint handling rules," Appl. Artif. Intel. vol. 14, no. 4, pp. 311-325, 2000.
      [3] S. Abdul Rahman, A. Bargiela, E. K. Burke, E. ?zcan, B. McCollum, and P. McMullan, "Adaptive linear combination of heuristic orderings in constructing examination timetables," Eur. J. Oper. Res., vol. 232, no. 2, pp. 287-297, 2014.
      [4] S. Abdullah, "Heuristic Approaches for University Timetabling Problems," no. June, p. 226, 2006.
      [5] S. Abdullah, E. K. Burke, and B. Mccollum, "An investigation of variable neighbourhood search for university course timetabling," Proc. 2nd Multi-disciplinary Interna- tional Conf. Sched. Theory Appl., pp. 413-427, 2005.
      [6] S. Abdullah and H. Turabieh, "Generating University Course Timetable Using Genetic Algorithms and Local Search," in 2008 Third International Conference on Convergence and Hybrid Information Technology, 2008, vol. 1, pp. 254-260.
      [7] R. Abounacer et al., "A hybrid Ant Colony Algorithm for the exam timetabling problem to cite this version: A hybrid Ant Colony Algorithm for the exam timetabling problem," vol. 12, pp. 15-42, 2016.
      [8] A. O. Adewumi, B. A. Sawyerr, and M. Montaz Ali, "A heuristic solution to the university timetabling problem," Eng. Comput., vol. 26, no. 8, pp. 972-984, Nov. 2009.
      [9] A. Akbulut and G. Y?lmaz, "University Exam Scheduling System Using Graph Coloring Algorithm and RFID Technology," Int. J. Innov. Manag. Technol., vol. 4, no. 1, pp. 66-72, 2013.
      [10] S. M. Al-yakoob and H. D. Sherali, "Computers & Operations Research Mathematical models and algorithms for a high school timetabling problem," Comput. Oper. Res., vol. 61, pp. 56-68, 2015.
      [11] R. Alvarez-Vald￩s, E. Crespo, and J. M. Tamarit, "A tabu search algorithm to schedule university examinations," Qestii?, vol. 21, no. 2, pp. 201-215, 1997.
      [12] M. Alzaqebah and S. Abdullah, "Artificial bee colony search algorithm for examination timetabling problems," vol. 6, no. 17, pp. 4264-4272, 2011.
      [13] P. Amaral and T. Cardal, "Computers & Operations Research Compromise ratio with weighting functions in a Tabu Search multi-criteria approach to examination timetabling $," Comput. Oper. Res., vol. 72, pp. 160-174, 2016.
      [14] T. Arbaoui, J.-P. Boufflet, and A. Moukrim, "A matheuristic for exam timetabling," IFAC-PapersOnLine, vol. 49, no. 12, pp. 1289-1294, 2016.
      [15] 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," Comput. Oper. Res., vol. 36, no. 4, pp. 981-1001, 2009.
      [16] E. Aycan and T. Ayav, "Solving the Course Scheduling Problem Using Simulated Annealing," no. March, pp. 6-7, 2009.
      [17] M. Ayob, S. Abdullah, and A. Malik, "A practical examination timetabling problem at the Universiti Kebangsaan Malaysia," Int. J. Comput. ï¾…, vol. 7, no. 9, pp. 198-204, 2007.
      [18] M. Ayob et al., "Intelligent Examination Timetabling Software," Procedia - Soc. Behav. Sci., vol. 18, pp. 600-608, 2011.
      [19] Z. N. Azimi, "Comparison of metaheuristic algorithms for Examination Timetabling Problem," J. Appl. Math. Comput., vol. 16, no. 1-2, pp. 337-354, Mar. 2004.
      [20] M. Bader-El-Den, R. Poli, and S. Fatima, "Evolving timetabling heuristics using a grammar-based genetic programming hyper-heuristic framework," Memetic Comput., vol. 1, no. 3, pp. 205-219, Nov. 2009.
      [21] H. Belhaouari and F. Peschanski, "A Constraint Logic Programming Approach to Automated Testing," 24th Int. Conf. Log. Program, vol. 5366, pp. 754-758, 2008.
      [22] A. L. aro Bolaji, A. T. Khader, M. A. Al-Betar, and M. A. Awadallah, "University course timetabling using hybridized artificial bee colony with hill climbing optimizer," J. Comput. Sci., vol. 5, no. 5, pp. 809-818, 2014.
      [23] P. Taylor et al., "A time-predefined local search approach to exam timetabling problems A time-predefined local search approach to exam timetabling problems," no. October 2014, pp. 37-41.
      [24] E. Burke, Y. Bykov, and S. Petrovic, "A Multicriteria Approach to Examination Timetabling," Springer Berlin Heidelberg, 2001, pp. 118-131.
      [25] E. Burke, D. Elliman, P. Ford, and R. Weare, "Examination timetabling in British universities: A survey," 1996, vol. 1153, pp. 76-90.
      [26] E. K. Burke, G. Kendall, M. Misir, and E. ?zcan, "Monte Carlo hyper-heuristics for examination timetabling," Ann. Oper. Res., vol. 196, no. 1, pp. 73-90, 2012.
      [27] 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, Dec. 2003.
      [28] E. K. Burke and J. P. Newall, "Solving Examination Timetabling Problems through Adaptation of Heuristic Orderings."
      [29] E. K. Burke, S. Petrovic, and R. Qu, "Case-based heuristic selection for timetabling problems," J. Sched., vol. 9, no. 2, pp. 115-132, Apr. 2006.
      [30] E. K. Burke, R. Qu, and A. Soghier, "Adaptive selection of heuristics for improving exam timetables," Ann. Oper. Res., vol. 218, no. 1, pp. 129-145, 2014.
      [31] M. Caramia, P. Dell'Olmo, and G. F. Italiano, "New Algorithms for Examination Timetabling," Springer, Berlin, Heidelberg, 2001, pp. 230-241.
      [32] M. W. Carter, "OR Practice-A Survey of Practical Applications of Examination Timetabling Algorithms," Oper. Res., vol. 34, no. 2, pp. 193-202, Apr. 1986.
      [33] R.-M. Chen and H.-F. Shih, "Solving University Course Timetabling Problems Using Constriction Particle Swarm Optimization with Local Search," Algorithms, vol. 6, no. 2, pp. 227-244, 2013.
      [34] M. Chiarandini, M. Birattari, K. Socha, and O. Rossi-doria, "An effective hybrid algorithm for university course timetabling," pp. 403-432, 2006.
      [35] P. H. Corr, B. Mccollum, M. A. J. Mcgreevy, and P. Mcmullan, "A New Neural Network Based Construction Heuristic for the Examination Timetabling Problem," Parallel Probl. Solving from Nature-PPSN IX, pp. 392-401, 2006.
      [36] M. ?upi?, M. Golub, and D. Jakobovi?, "Exam timetabling using genetic algorithm," in Proceedings of the International Conference on Information Technology Interfaces, ITI, 2009, pp. 357-362.
      [37] P. David, "A constraint-based approach for examination timetabling using local repair techniques," in Practice and Theory of Automated Timetabling II, 1998, pp. 169-186.
      [38] P. De Causmaecker, P. Demeester, and G. Vanden Berghe, "A decomposed metaheuristic approach for a real-world university timetabling problem," Eur. J. Oper. Res., vol. 195, no. 1, pp. 307-318, 2009.
      [39] P. Demeester, B. Bilgin, P. De Causmaecker, and G. Vanden Berghe, "A hyperheuristic approach to examination timetabling problems: benchmarks and a new problem from practice," J. Sched., vol. 15, no. 1, pp. 83-103, Feb. 2012.
      [40] L. Di Gaspero and A. Schaerf, "Tabu search techniques for EXAMINATION TIMETABLING," 2001, vol. 2079 LNCS, pp. 104-117.
      [41] 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," Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 6276 LNAI, no. PART 1, pp. 100-110, 2010.
      [42] O. R. Doria and B. Paechter, "A memetic algorithm for University Course Timetabling," pp. 1-8, 2003.
      [43] 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.
      [44] O. El Mahdi, R. N. Ainon, and R. Zainuddin, "Using a Genetic Algorithm optimizer tool to generate good quality timetables," 2003, vol. 3, pp. 1300-1303.
      [45] M. Eley, "Ant Algorithms for the Exam Timetabling Problem," in Practice and Theory of Automated Timetabling VI, Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 364-382.
      [46] A.R.Mirzaei and F.Djannaty, "Enhancing Max-Min Ant System for Examination Timetabling Problems," Int. J. Soft Comput., pp. 230-238, 2008.
      [47] W. Erben, "A Grouping Genetic Algorithm for graph colouring and exam timetabling," 2001, vol. 2079 LNCS, pp. 132-156.
      [48] W. Erben and J. Keppler, "A Genetic Algorithm Solving a Weekly Course- Timetabling Problem," 1995.
      [49] W. Erben and P. Y. Song, "A Hybrid Grouping Genetic Algorithm for Examination Timetabling 2 The Hybrid Grouping Genetic Algorithm," no. 1, 2004.
      [50] 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, Oct. 2016.
      [51] F. Zhaohui and A. Lim, "Heuristics for the Exam Scheduling Problem," pp. 172-175, 2000.
      [52] D. Hadjidj and H. Drias, "A hybrid grasp and scatter search for the exam timetabling problem," 2010, pp. 297-302.
      [53] A. Hertz, "Tabu search for large scale timetabling problems," Eur. J. Oper. Res., vol. 54, no. 1, pp. 39-47, Sep. 1991.
      [54] W. K. Ho, A. Lim, and W. C. Oon, "Maximizing paper spread in examination timetabling using a vehicle routing method," 2001, pp. 359-366.
      [55] M. Hosny and M. Al-Olayan, "A mutation-based genetic algorithm for room and proctor assignment in examination scheduling," in 2014 Science and Information Conference, 2014, pp. 260-268.
      [56] B. Hussin, A. S. H. Basari, A. S. Shibghatullah, S. A. Asmai, and N. S. Othman, "Exam timetabling using graph colouring approach," in 2011 IEEE Conference on Open Systems, 2011, pp. 133-138.
      [57] S. Innet, "A Noval Approach of Genetic Algorithm for Solving Examination Timetabling Problems," pp. 233-237, 2013.
      [58] S. K. Jha, "Exam Timetabling Problem using Genetic Algorithm," Int. J. Res. Eng. Technol., vol. 3, no. 4, pp. 649-654, 2014.
      [59] M. N. M. Kahar and G. Kendall, "The examination timetabling problem at Universiti Malaysia Pahang: Comparison of a constructive heuristic with an existing software solution," Eur. J. Oper. Res., vol. 207, no. 2, pp. 557-565, 2010.
      [60] C. B. Kalayci, "Model Focusing on Student Success for the Case of the College of Engineering at Pamukkale University, Turkey," vol. 25, no. 1, pp. 137-153, 2012.
      [61] M. Karova, "Solving timetabling problems using genetic algorithms," in 27th International Spring Seminar on Electronics Technology: Meeting the Challenges of Electronics Technology Progress, 2004., 2004, vol. 1, no. 7, pp. 96-98.
      [62] S. K. Ibraheem and A. Q. Ansari, "Ant colony optimization?: A tutorial," MR Int. J. Eng. Technol., vol. 7, no. 2, pp. 35-41, 2015.
      [63] Z. L? In addition, J. K. Hao, "Solving the course timetabling problem with a hybrid heuristic algorithm," Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 5253 LNAI, pp. 262-273, 2008.
      [64] R. Lewis and B. Paechter, "Application of the Grouping Genetic Algorithm to University Course Timetabling," 2002.
      [65] A. Lim, J. Ang, W. Ho, and W. Oon, "UTTSExam?: A Campus-Wide University Exam-Timetabling System," Natl. Conf. Artif. Intell., pp. 838-844, 2002.
      [66] Z. L and J. K. Hao, "Adaptive Tabu Search for course timetabling," vol. 200, no. 1, pp. 235-244, Jan. 2010.
      [67] N. Mansour, V. Isahakian, and I. Ghalayini, "Scatter search technique for exam timetabling," Appl. Intell., vol. 34, no. 2, pp. 299-310, Apr. 2011.
      [68] B. McCollum, P. McMullan, A. J. Parkes, E. K. Burke, and S. Abdullah, "An extended great deluge approach to the examination timetabling problem," Proc. 4th Multidiscip. Int. Conf. Sched. Theory Appl., no. August, pp. 424-434, 2009.
      [69] 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.
      [70] V. Beldi, "Timetabling through Constrained Heuristic Search and Genetic Algorithms," vol. 26, no. March 1995, 1996.
      [71] T. Mller, "Real-life Examination Timetabling."
      [72] Z. N. Azimi, "Hybrid heuristics for Examination Timetabling problem," vol. 163, pp. 705-733, 2005.
      [73] 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.
      [74] R. Burke, Edmund and MacCloumn, Barry and Meisels, Amnon and Petrovic, Sanja and Qu, "A Graph-Based Hyper-Heuristic for Educational Timetabling Problems," vol. 176, pp. 177-192, 2007.
      [75] O. S. O, F. T. M, O. E. O, and O. A. C, "Hybrid MetaHeuristic Feature Extraction Technique for Solving Timetabling Problem," Int. J. Sci. Eng. Res., vol. 3, no. 8, pp. 1-6, 2012.
      [76] E. Ozcan and A. Alkan, "Timetabling using a steady state genetic algorithm," fourth Int. Conf. Pract. Theory Autom. Timetabling, 2002.
      [77] E. ?zcan and A. Alkan, "A Memetic Algorithm for Solving a Timetabling Problem?: An Incremental Strategy," Computer (Long. Beach. Calif). pp. 394-401, 2007.
      [78] S. Petrovic and Y. Bykov, "A Multiobjective Optimisation Technique for Exam Timetabling Based on Trajectories."
      [79] N. Pillay, "Evolving hyper-heuristics for the uncapacitated examination timetabling problem," J. Oper. Res. Soc., vol. 63, no. 1, pp. 47-58, Jan. 2012.
      [80] N. Pillay, A review of hyper-heuristics for educational timetabling. 2014.
      [81] N. Pillay and W. Banzhaf, "An informed genetic algorithm for the examination timetabling problem," Appl. Soft Comput., vol. 10, no. 2, pp. 457-467, Mar. 2010.
      [82] R. Qu, E. K. Burke, and B. Mccollum, "Adaptive Automated Construction of Hybrid Heuristics for Exam Timetabling and Graph Colouring Problems 1 Introduction 2 Benchmark Exam Timetabling and Graph Colouring Problems," pp. 1-19.
      [83] L. P. Reis and E. Oliveira, "A language for specifying complete timetabling problems," Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 2079 LNCS, pp. 322-341, 2001.
      [84] P. Ross, E. Hart, D. Corne, F. Hill, and E. Eh, "Some observations about GA-based exam timetabling 1 Introduction 2 The representation," vol. 2, no. August 1997, pp. 1-16, 1998.
      [85] P. Ross, E. Prossnapieracuk, J. G. Marin-blizquez, and E. Hart, "Hyper-heuristics applied to Class and Exam Timetabling problems," 2003.
      [86] N. R. Sabar, M. Ayob, R. Qu, and G. Kendall, "A graph coloring constructive hyper-heuristic for examination timetabling problems," Appl. Intell., vol. 37, no. 1, pp. 1-11, Jul. 2012.
      [87] B. Sigl, M. Golub, and V. Mornar, "Solving timetable scheduling problem using genetic algorithms," Proc. 25th int. conf. ï¾…, pp. 519-524, 2003.
      [88] E. S. Sin, "REINFORCEMENT LEARNING WITH EGD BASED HYPER HEURISTIC SYSTEM FOR EXAM," in IEEE CCIS, 2011, pp. 462-466.
      [89] A. Soghier and R. Qu, "Adaptive selection of heuristics for assigning time slots and rooms in exam timetables," Appl. Intell., vol. 39, no. 2, pp. 438-450, Sep. 2013.
      [90] J. A. Soria-Alcaraz, G. Ochoa, J. Swan, M. Carpio, H. Puga, and E. K. Burke, "Effective learning hyper-heuristics for the course timetabling problem," Eur. J. Oper. Res., vol. 238, no. 1, pp. 77-86, 2014.
      [91] R. Burke, Edmund and Dror, Moshe and Petrovic, Sanja and Qu, "Hybrid Graph Heuristics within a Hyper-heuristic Approach to Exam Timetabling Problems," vol. 9, pp. 79-91, 2005.
      [92] N. D. Thanh, "Solving Timetabling Problem Using Genetic and Heuristic Algorithms," in Eighth ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing (SNPD 2007), 2007, vol. 3, pp. 472-477.
      [93] T. Thepphakorn and P. Pongcharoen, "Heuristic ordering for ant colony based timetabling tool," 2012, vol. 4, pp. 87-96.
      [94] J. M. Thompson and K. A. Dowsland, "A robust simulated annealing based examination timetabling system," Comput. & Oper. Res., vol. 25, no. 7-8, pp. 637-648, 1998.
      [95] H. T. ? and S. Abdullah, "An integrated hybrid approach to the examination timetabling problem," Omega, vol. 39, no. 6, pp. 598-607, 2011.
      [96] B. M. Abdullah, Salwani, Edmund K.Burke, "A hybrid Evoluationary Appraoch to the University Course Timetabling Problem," IEEE Congr., pp. 1764-1768, 2007.
      [97] R. Willemen, School timetable construction; algorithms and complexity. 2002.
      [98] G. Woumans, L. De Boeck, J. Beliï¿«n, and S. Creemers, "A column generation approach for solving the examination-timetabling problem," Eur. J. Oper. Res., vol. 253, no. 1, p. 17, 2016.
      [99] 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 Appl. Rev., vol. 41, no. 1, pp. 93-106, 2011.
      [100] J. Yellen, R. College, and E. K. Burke, "Linear Combinations of Heuristics for Examination Timetabling," vol. 194, pp. 89-109, 2012.

  • Downloads

  • How to Cite

    Firdaus Khair, A., Makhtar, M., Mazlan, M., Afendee Mohamed, M., & Nordin Abdul Rahman, M. (2018). A study on university course and exam timetabling problems and methods: an optimization survey. International Journal of Engineering & Technology, 7(2.14), 191-195. https://doi.org/10.14419/ijet.v7i2.14.12823

    Received date: 2018-05-14

    Accepted date: 2018-05-14

    Published date: 2018-04-06