NEW EXAMINATION TIMETABLING ALGORITHM USING THE SUPERSTAR ASSIGNMENT TECHNIQUE

Authors

  • Pornpun Prachapipat Faculty of Science, Ramkhamhaeng University, Bangkok, Thailand
  • Arkom Leelertpanchai Faculty of Science, Ramkhamhaeng University, Bangkok, Thailand
  • Chouvalit Khancome Faculty of Science, Ramkhamhaeng University, Bangkok, Thailand

DOI:

https://doi.org/10.20319/mijst.2018.33.253270

Keywords:

Examination Timetabling Principle, Examination Timetabling Algorithm, Registration Problem, Superstar Assignment Technique

Abstract

In this paper, a new examination timetabling algorithm, SAT, is introduced. In order to solve the current problems that SAT algorithm can meet the requirement under the limited of all related resources and factors. It combined with rules, constraints, exceptions and priorities. This algorithm works in three steps: pre-processing, creating superstars and getting rid of superstars. SAT mechanisms sort all related parameters and factors, then determine stars and superstars of each related parameter. Each iteration of algorithm is trying to assign all superstars of all parameters as targets for processing. As well as, the process mechanism is run for putting the output into a suitable timeslot. To prove the algorithm implementation, a dataset from semester 1/2016 of Registration Centre, Ramkhamhaeng University has been selected as test subject. This dataset consists of 20/2 days/periods, 85,000 registered students, 1,325 subjects, 813,253 seats, and 11/76/22,582 buildings/rooms/seats per day. The proposed model could be solved the current problems and shown details of subject such as the colour of answer sheet, room and so on. It could be done within less than two hours, meanwhile the current system took at least one month. For the future work, the large scale of algorithm is to be improved and developed into more dynamic version for a larger volume of data and handling more complicated constraints.

References

Al-Betar, M. A., Khader, A. T., & Nadi, F. ( 2010 ). Selection mechanisms in memory consideration for examination timetabling with harmony search. July 2010 GECCO’10: Proceeding of the 12th annual conference on Genetic and evolutionary computation, 12, 1203-1210. https://doi.org/10.1145/1830483.1830702

Ansari, A., & Bojewar, S. ( 2014, Nov ). Genetic Algorithm to Generate the Automatic Time-Table – An Over View. International Journal on Recent and Innovation Trends in Computing and Communication ( IJRITCC ), 2 (11) , 3480-3483.

Anwar, K., Khader, A. T., Al-Betar, M. A., & Awadallah, M. A. ( 2013 ). Harmony Search-based Hyper-heuristic for examination timetabling, Signal Processing and its Applications (CSPA). 2013 IEEE 9th International Colloquium on, 9, 176–181. https://doi.org/10.1109/CSPA.2013.6530037

Cheong, C. Y., Tan, K. C., & Veeravalli, B. ( 2007 ). Solving the Exam Timetabling Problem via a Multi-Objective Evolutionary Algorithm – A More General Approach. Proceeding of the 2007 IEEE Symposium on Computational, Intelligence in Scheduling (CI-Sched 2007), 07, 165-172. https://doi.org/10.1109/SCIS.2007.367685

Dorigo, M., Maniezzo, V., & Colorni, A. ( 1996 ). Ant system:optimization by a colony of Cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics,Part B: Cybernetics, 26, 29–41. https://doi.org/10.1109/3477.484436

Fernandes, C., Caldeira, J. P., Melicio, F.&Rosa, A. ( 1999 ). High school weekly timetabling by evolutionary algorithms. February 1999 SAC '99: Proceedings of the 1999 ACM symposium on Applied computing, 344-350. https://doi.org/10.1145/298151.298379

Fong, C. W. ( 2015 ). Hishammuddin Asmuni, Barry McCollum, A Hybrid Swarm-Based Approach to University Timetabling. IEEE Transactions on Evolutionary Computation, 19, 870–884. https://doi.org/10.1109/TEVC.2015.2411741

Glover, F. (1986 ). Future Paths for Integer Programming and Links to Artificial Inlligence. Oxford: Elsevier Ltd.

Goldberg, DE. ( 1989 ). Genetic Algorithms in Search, Optimization and Machine Learning. 1st ed. New York: Addison-Wesley Longman Publishing Co.,Inc.

Gupta, A., Narang, B., & Bansal, R. ( 2013 ). Use of Active Rules and Genetic Algorithm to Generate the Automatic Time-Table. International Journal of Advances in Engineering Sciences, 3 ( 3 ) , 40-43.

Innet, S. ( 2013 ). A Noval Approach of Genetic Algorithm for Solving Examination Timetabling Problems a case study of Thai Universities. 2013 13th International Symposium on Communications and Information Technologies (ISCIT), 13, 233-237. https://doi.org/10.1109/ISCIT.2013.6645855

Kahar, M.N.M., & Kendall, G. ( 2010 ). The examination timetabling problem at Universiti Malaysia Pahang: Comparison of a constructive heuristic with an existing software solution. European Journal of Operational Research, 207 , 557–565. https://doi.org/10.1016/j.ejor.2010.04.011

Kirkpatrick, S., Gelatt, C., & Vecchi, M,. (1983, May 13 ). Optimization by Simulated Annealing. Science, 220 (4598) , 671–680. https://doi.org/10.1126/science.220.4598.671

Li, Xiaoping., Lv, Xiaoxing., Mei Wenbo., & Xu, Hu. ( 2010 ). Algorithm for solving Timetable questions based on Ga. The 3rd International Conference on Information Sciences and Interaction Sciences, 3, 18–21. https://doi.org/10.1109/ICICIS.2010.5534702

Liu, Y., Zhang, D., & Leung, S. C.H. ( 2009 ). A simulated annealing algorithm with a new neighborhood structure for the timetabling problem. June 2009 GEC '09:Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation, 9, 381-386. https://doi.org/10.1145/1543834.1543885

Malik, A. M. A., Ayob, M., & Hamdan, A. R. ( 2010 ). Stratified Random Sampling Techinique for Integrated Two-stage Multi-neighbourhood Tabu Search for Examination Timetabling Problem. 2010 10th International Conference on Intelligent Systems Design and Applications, 1326-1331 . https://doi.org/10.1109/ISDA.2010.5687093

Mandal, A. K., & Kahar, M. N. ( 2015 ). Combination of graph heuristic with hill climbing Search for solving capacitated examination timetabling problem. the 4th International Conference on Software Engineering and Computer Systems (ICSECS) 2015, 4, 118-123. https://doi.org/10.1109/ICSECS.2015.7333095

Mumford, C. L. ( 2007 ). An Order Based Evolutionary Approach to Dual Objective Examination Timetabling– A More General Approach, Proceedings of the 2007 IEEE Symposium on Computational, Intelligence in Scheduling (CI-Sched 2007), 07, 176-186. https://doi.org/10.1109/SCIS.2007.367687

Pillay, N. ( 2010 ). An empirical study into the structure of heuristic combinations in an evolutionary algorithm hyper-heuristic for the examination timetabling problem. October 2010 SAICSIT '10: Proceedings of the 2010 Annual Research Conference of the South African Institute of Computer Scientists and Information Technologists, 10, 251-257. https://doi.org/10.1145/1899503.1899531

Raghavjee, R., & Pillay, N. (2008). An application of genetic algorithms to the school timetabling problem. SAICSIT '08: Proceedings of the 2008 annual research conference of the South African Institute of Computer Scientists and Information Technologists on IT research in developing countries: riding the wave of technology, 8, 193-199. https://doi.org/10.1145/1456659.1456682

Raghavjee, R., & Pillay, N. (2010). An informed genetic algorithm for the high school timetabling problem. October 2010 SAICSIT '10: Proceedings of the 2010 Annual Research Conference of the South African Institute of Computer Scientists and Informationn Technologists, 10, 408-412. https://doi.org/10.1145/1899503.1899555

Raghavjee, R., & Pillay, N. (2011). The effect of construction heuristics on the performance of a genetic algorithm for the school timetabling problem. SAICSIT '11: Proceedings of the South African Institute of Computer Scientists and Information Technologists Conference on Knowledge, Innovation and Leadership in a Diverse, Multidisciplinary Environment, 11, 187-194 . https://doi.org/10.1145/2072221.2072243

Tito, Amranes. ( 2017, July 8 ). RU Background. Institute of International Studies (IIS-RU ) Ramkhamhaeng University. Retrieved from http://www.ru.ac.th/index.php/ru-background

Sabar, N. R., Ayob, M., & Kendall, G. ( 2009 ). Tabu exponential Monte-Carlo with counter heuristic for examination timetabling. 2009 IEEE Symposium on Computational Intelligence in Scheduling, 90-94. https://doi.org/10.1109/SCIS.2009.4927020

Santos, H. G., Ochi, L. S., & Souza, M. J.F. ( 2005 ). A Tabu search heuristic with efficient diversification strategies for the class/teacher timetabling problem. December 2005 Journal of Experimental Algorithmics, 10, 1-16. https://doi.org/10.1145/1064546.1180621

Downloads

Published

2018-02-01

How to Cite

Prachapipat, P., Leelertpanchai, A., & Khancome, C. (2018). NEW EXAMINATION TIMETABLING ALGORITHM USING THE SUPERSTAR ASSIGNMENT TECHNIQUE. MATTER: International Journal of Science and Technology, 3(3), 253–270. https://doi.org/10.20319/mijst.2018.33.253270