Solving examination timetabling problem in UniSZA using ant colony optimization

 
 
 
  • Abstract
  • Keywords
  • References
  • PDF
  • Abstract


    At all educational institutions, timetabling is a conventional problem that has always caused numerous difficulties and demands that need to be satisfied. For the examination timetabling problem, those matters can be defined as complexity in scheduling exam events or non-deterministic polynomial hard problems (NP-hard problems). In this study, the latest approach using an ant colony optimisation (ACO) which is the ant system (AS) is presented to find an effective solution for dealing with university exam timetabling problems. This application is believed to be an impressive solution that can be used to eliminate various types of problems for the purpose of optimising the scheduling management system and minimising the number of conflicts. The key of this feature is to simplify and find shorter paths based on index pheromone updating (occurrence matrix). With appropriate algorithm and using efficient techniques, the schedule and assignation allocation can be improved. The approach is applied according to the data set instance that has been gathered. Therefore, performance evaluation and result are used to formulate the proposed approach. This is to determine whether it is reliable and efficient in managing feasible final exam timetables for further use.

     

     


  • Keywords


    Ant colony optimization; Ant system; Examination timetabling; Scheduling.

  • References


      [1] Carter MW, Laporte G & Lee SY (1996), Examination timetabling: Algorithmic strategies and applications. Journal of the Operational Research Society 47, 373–383.

      [2] Cooper TB & Kingston JH (1995), The complexity of timetable construction problems. Proceedings of the International Conference on the Practice and Theory of Automated Timetabling, pp. 281–295.

      [3] Casey S, Thompson J. GRASPing the examination scheduling problem. Proceedings of the International Conference on the Practice and Theory of Automated Timetabling, pp. 232–244.

      [4] Di Gaspero L & Schaerf A (2000), Tabu search techniques for examination timetabling. Proceedings of the International Conference on the Practice and Theory of Automated Timetabling, pp. 104–117.

      [5] Turabieh H & Abdullah S (2011), An integrated hybrid approach to the examination timetabling problem. Omega 39, 598–607.

      [6] Thanh ND (2007), Solving timetabling problem using genetic and heuristic algorithms. Proceedings of the IEEE 8th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, pp. 472–477.

      [7] Matijaš VD, Molnar G, Čupić M, Jakobović D & Bašić BD (2010), University course timetabling using ACO: A case study on laboratory exercises. Proceedings of the International Conference on Knowledge-Based and Intelligent Information and Engineering Systems, pp. 100–110.

      [8] Katiyar S, Ibraheem AQ & Ansari AQ (2015), Ant colony optimization: A tutorial review. MR International Journal of Engineering and Technology 7, 35–41.

      [9] Abounacer R, Boukachour J, Dkhissi B & Alaoui AE (2010), A hybrid Ant Colony Algorithm for the exam timetabling problem. Revue Africaine de la Recherche en Informatique et Mathématiques Appliquées 12, 15–42.

      [10] Eley M (2006), Ant algorithms for the exam timetabling problem. Proceedings of the International Conference on the Practice and Theory of Automated Timetabling, pp. 364–382.

      [11] Djannaty F & Mirzaei AR (2008), Enhancing max-min ant system for examination timetabling problem. International Journal of Soft Computing 3, 230–238.

      [12] Thepphakorn T & Pongcharoen P (2013), Heuristic ordering for ant colony based timetabling tool. Journal of Applied Operational Research 5, 113–123.

      [13] Doulaty M, Derakhshi MF & Abdi M (2013), Timetabling: A state-of-the-art evolutionary approach. International Journal of Machine Learning and Computing 3, 255–258.


 

View

Download

Article ID: 11369
 
DOI: 10.14419/ijet.v7i2.15.11369




Copyright © 2012-2015 Science Publishing Corporation Inc. All rights reserved.