NEW EXAMINATION TIMETABLING ALGORITHM USING THE SUPERSTAR ASSIGNMENT TECHNIQUE
DOI:
https://doi.org/10.20319/mijst.2018.33.253270Keywords:
Examination Timetabling Principle, Examination Timetabling Algorithm, Registration Problem, Superstar Assignment TechniqueAbstract
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
How to Cite
Issue
Section
License
Copyright of Published Articles
Author(s) retain the article copyright and publishing rights without any restrictions.
All published work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
