{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:27:50Z","timestamp":1760243270472,"version":"build-2065373602"},"reference-count":63,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2014,7,3]],"date-time":"2014-07-03T00:00:00Z","timestamp":1404345600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The examination timetabling problem belongs to the class of combinatorial optimization problems and is of great importance for every University. In this paper, a hybrid evolutionary algorithm running on a GPU is employed to solve the examination timetabling problem. The hybrid evolutionary algorithm proposed has a genetic algorithm component and a greedy steepest descent component. The GPU computational capabilities allow the use of very large population sizes, leading to a more thorough exploration of the problem solution space. The GPU implementation, depending on the size of the problem, is up to twenty six times faster than the identical single-threaded CPU implementation of the algorithm. The algorithm is evaluated with the well known Toronto datasets and compares well with the best results found in the bibliography. Moreover, the selection of the encoding of the chromosomes and the tournament selection size as the population grows are examined and optimized. The compressed sparse row format is used for the conflict matrix and was proven essential to the process, since most of the datasets have a small conflict density, which translates into an extremely sparse matrix.<\/jats:p>","DOI":"10.3390\/a7030295","type":"journal-article","created":{"date-parts":[[2014,7,3]],"date-time":"2014-07-03T11:13:17Z","timestamp":1404385997000},"page":"295-327","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Solving the Examination Timetabling Problem in GPUs"],"prefix":"10.3390","volume":"7","author":[{"given":"Vasileios","family":"Kolonias","sequence":"first","affiliation":[{"name":"Computer Systems Laboratory, Department of Electrical and Computer Engineering,University of Patras, GR-26504 Patras, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"George","family":"Goulas","sequence":"additional","affiliation":[{"name":"Computer Systems Laboratory, Department of Electrical and Computer Engineering,University of Patras, GR-26504 Patras, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1113-8462","authenticated-orcid":false,"given":"Christos","family":"Gogos","sequence":"additional","affiliation":[{"name":"Technological Educational Institute of Epirus, GR-48100 Preveza, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Panayiotis","family":"Alefragis","sequence":"additional","affiliation":[{"name":"Technological Educational Institute of Western Greece, GR-30020 Antirio, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Efthymios","family":"Housos","sequence":"additional","affiliation":[{"name":"Computer Systems Laboratory, Department of Electrical and Computer Engineering,University of Patras, GR-26504 Patras, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2014,7,3]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Boyd, S., and Vandenberghe, L. (2004). Convex Optimization, Cambridge University Press.","DOI":"10.1017\/CBO9780511804441"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1109\/4235.585893","article-title":"No free lunch theorems for optimization","volume":"1","author":"Wolpert","year":"1997","journal-title":"IEEE Trans. Evol. Comput."},{"key":"ref_3","unstructured":"Dantzig, G.B. (1998). Linear Programming and Extensions, Princeton University Press."},{"key":"ref_4","first-page":"12","article-title":"A proposal for the dartmouth summer research project on artificial intelligence, august 31, 1955","volume":"27","author":"McCarthy","year":"2006","journal-title":"AI Mag."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Glover, F., and Kochenberger, G.A. (2003). Handbook of Metaheuristics, Kluwer Academic Publishers.","DOI":"10.1007\/b101874"},{"key":"ref_6","unstructured":"Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co. Inc.. [1st ed.]."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/BF01556771","article-title":"Numerical testing of evolution theories","volume":"16","author":"Barricelli","year":"1962","journal-title":"Acta Biotheor."},{"key":"ref_8","unstructured":"Holland, J.H. (1975). Adaptation in Natural and Artificial Systems: An Introductory Analysis With Applications to Biology, Control, and Artificial Intelligence, University of Michigan Press."},{"key":"ref_9","unstructured":"Darwin, C.R. (2001). The Origin of Species, New York: P.F. Collier & Son."},{"key":"ref_10","unstructured":"McCollum, B., McMullan, P., Burke, E.K., Parkes, A.J., and Qu, R. (2007). The Second International Timetabling Competition: Examination Timetabling Track, Queen\u2019s University. Technical Report, Technical Report QUB\/IEEE\/Tech\/ITC2007\/-Exam\/v4.0\/17."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/s10479-010-0712-3","article-title":"An improved multi-staged algorithmic process for the solution of the examination timetabling problem","volume":"194","author":"Gogos","year":"2012","journal-title":"Ann. Oper. Res."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1057\/jors.1996.37","article-title":"Examination Timetabling: Algorithmic Strategies and Applications","volume":"47","author":"Carter","year":"1996","journal-title":"J. Oper. Res. Soc."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/3-540-61794-9_63","article-title":"A memetic algorithm for university exam timetabling","volume":"Volume 1153","author":"Burke","year":"1996","journal-title":"Practice and Theory of Automated Timetabling"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/978-3-540-45157-0_14","article-title":"A Hybrid Algorithm for the Examination Timetabling Problem","volume":"Volume 2740","author":"Burke","year":"2003","journal-title":"Practice and Theory of Automated Timetabling IV"},{"key":"ref_15","first-page":"202","article-title":"The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software","volume":"30","author":"Sutter","year":"2005","journal-title":"Dr. Dobb\u2019s J."},{"key":"ref_16","unstructured":"Pospichal, P., Jaros, J., and Schwarz, J. (2010, January 7\u20139). Parallel genetic algorithm on the CUDA architecture. Proceedings of the 2010 international conference on Applications of Evolutionary Computation\u2014Volume Part I, ( EvoApplicatons 2010), Istanbul, Turkey."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Arora, R., Tulshyan, R., and Deb, K. (2010, January 18\u201323). Parallelization of binary and real-coded genetic algorithms on GPU using CUDA. Proceedings of the IEEE Congress on Evolutionary Computation (CEC), Barcelona, Spain.","DOI":"10.1109\/CEC.2010.5586260"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/s10951-008-0077-5","article-title":"A survey of search methodologies and automated system development for examination timetabling","volume":"12","author":"Qu","year":"2009","journal-title":"J. Sched."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1023\/A:1006576209967","article-title":"A Survey of Automated Timetabling","volume":"13","author":"Schaerf","year":"1999","journal-title":"Artif. Intell. Rev."},{"key":"ref_20","unstructured":"Petrovic, S., and Burke, E. (2004). Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Chapman Hall\/CRC Press. Chapter 45."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1093\/comjnl\/10.1.85","article-title":"An upper bound for the chromatic number of a graph and its application to timetabling problems","volume":"10","author":"Welsh","year":"1967","journal-title":"Comput. J."},{"key":"ref_22","unstructured":"Asmuni, H., Garibaldi, E.K.B.J.M., Burke, E.K., and Garibaldi, J.M. (2005, January 5\u20137). Fuzzy Multiple Heuristic Ordering for Course Timetabling. The Proceedings of the 5 th United Kingdom Workshop on Computational Intelligence (UKCI05), London, UK."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1007\/11844297_40","article-title":"A New Neural Network Based Construction Heuristic for the Examination Timetabling Problem","volume":"Volume 4193","author":"Runarsson","year":"2006","journal-title":"Parallel Problem Solving from Nature\u2014PPSN IX"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1023\/B:ANOR.0000030684.30824.08","article-title":"Solving Examination Timetabling Problems through Adaptation of Heuristic Orderings","volume":"129","author":"Burke","year":"2004","journal-title":"Ann. Oper. Res."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1016\/S0377-2217(98)00364-6","article-title":"Constraint satisfaction problems: Algorithms and applications","volume":"119","author":"Brailsford","year":"1999","journal-title":"Eur. J. Oper. Res."},{"key":"ref_26","unstructured":"Di Gaspero, L., and Schaerf, A. (2001). Practice and Theory of Automated Timetabling III, Springer."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/S0377-2217(03)00100-0","article-title":"Using tabu search with longer-term memory and relaxation to create examination timetables","volume":"153","author":"White","year":"2004","journal-title":"Eur. J. Oper. Res."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1007\/978-3-540-45157-0_15","article-title":"GRASPing the Examination Scheduling Problem","volume":"Volume 2740","author":"Burke","year":"2003","journal-title":"Practice and Theory of Automated Timetabling IV"},{"key":"ref_29","unstructured":"Duong, T.A., and Lam, K.H. (2004, January 2\u20135). Combining Constraint Programming and Simulated Annealing on University Exam Timetabling. Proceedings of the International Conference RIVF\u201904, Hanoi, Vietnam."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1007\/3-540-44691-5_20","article-title":"New Algorithms for Examination Timetabling","volume":"Volume 1982","author":"Wagner","year":"2001","journal-title":"Algorithm Engineering"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1016\/S0305-0548(97)00101-9","article-title":"A Robust Simulated Annealing Based Examination Timetabling System","volume":"25","author":"Thompson","year":"1998","journal-title":"Comput. Oper. Res."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1007\/3-540-32363-5_13","article-title":"The Design of Memetic Algorithms for Scheduling and Timetabling Problems","volume":"Volume 166","author":"Hart","year":"2005","journal-title":"Recent Advances in Memetic Algorithms"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1109\/4235.752921","article-title":"A multistage evolutionary algorithm for the timetable problem","volume":"3","author":"Burke","year":"1999","journal-title":"IEEE Trans. Evol. Comput."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1007\/978-3-540-77345-0_23","article-title":"Ant Algorithms for the Exam Timetabling Problem","volume":"Volume 3867","author":"Burke","year":"2007","journal-title":"Practice and Theory of Automated Timetabling VI"},{"key":"ref_35","unstructured":"C\u00f4t\u00e9, P., Wong, T., and Sabourin, R. (2004, January 18\u201320). Application of a Hybrid Multi-Objective Evolutionary Algorithm to the Uncapacitated Exam Proximity Problem. Proceedings of the 5th International Conference on Practice and Theory of Automated Timetabling (PATAT 2004), Pittsburgh, PA, USA."},{"key":"ref_36","unstructured":"Erben, W. (2001). Practice and Theory of Automated Timetabling III, Springer."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/S0952-1976(99)00007-X","article-title":"Incorporating constraint propagation in genetic algorithm for university timetable planning","volume":"12","author":"Deris","year":"1999","journal-title":"Eng. Appl. Artif. Intell."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1016\/j.asoc.2009.08.011","article-title":"An informed genetic algorithm for the examination timetabling problem","volume":"10","author":"Pillay","year":"2010","journal-title":"Appl. Soft Comput."},{"key":"ref_39","unstructured":"Baptiste, P., Kendall, G., Kordon, A.M., and Sourd, F. (2007, January 28\u201331). Memetic algorithms and hyperhill-climbers. Proceedings of the 3rd Multidisciplinary International Conference on Scheduling: Theory and Applications, Paris, France."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Kendall, G., Burke, E.K., Petrovic, S., and Gendreau, M. (2005). Multidisciplinary Scheduling: Theory and Applications, Springer.","DOI":"10.1007\/0-387-27744-7"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"482","DOI":"10.1016\/j.ejor.2008.07.023","article-title":"A study of heuristic combinations for hyper-heuristic systems for the uncapacitated examination timetabling problem","volume":"197","author":"Pillay","year":"2009","journal-title":"Eur. J. Oper. Res."},{"key":"ref_42","first-page":"1273","article-title":"Hybridisations within a Graph Based Hyper-heuristic Framework for University Timetabling Problems","volume":"60","author":"Qu","year":"2009","journal-title":"Eur. J. Oper. Res."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1111\/j.1475-3995.2012.00862.x","article-title":"Parallel metaheuristics: recent advances and new trends","volume":"20","author":"Alba","year":"2013","journal-title":"Int. Trans. Oper. Res."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Lazarova, M., and Borovska, P. (2008, January 12\u201313). Comparison of Parallel Metaheuristics for Solving the TSP. Proceedings of the 9th International Conference on Computer Systems and Technologies and Workshop for PhD Students in Computing (CompSysTech \u201908), Gabrovo, Bulgaria.","DOI":"10.1145\/1500879.1500899"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/978-3-540-88908-3_13","article-title":"Parallel Approaches for Multiobjective Optimization","volume":"Volume 5252","author":"Branke","year":"2008","journal-title":"Multiobjective Optimization"},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Maitre, O., Baumes, L.A., Lachiche, N., Corma, A., and Collet, P. (2009, January 8\u201312). Coarse grain parallelization of evolutionary algorithms on GPGPU cards with EASEA. Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation (GECCO \u201909), Montreal, QC, Canada.","DOI":"10.1145\/1569901.1570089"},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Wong, M.L. (2009, January 8\u201312). Parallel multi-objective evolutionary algorithms on graphics processing units. Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers (GECCO \u201909), Montreal, QC, Canada.","DOI":"10.1145\/1570256.1570354"},{"key":"ref_48","unstructured":"Luong, T.V., Melab, N., and Talbi, E. GPU-based Parallel Hybrid Genetic Algorithms. Available online: http:\/\/www.gpgpgpu.com\/gecco2010\/0.pdf."},{"key":"ref_49","unstructured":"Yu, Q., Chen, C., and Pan, Z. (2005). Advances in Natural Computation, Springer. Lecture Notes in Computer Science 3612."},{"key":"ref_50","first-page":"24","article-title":"Implementation of Parallel Genetic Algorithm Based on CUDA","volume":"Volume 5821","author":"Cai","year":"2009","journal-title":"Advances in Computation and Intelligence"},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/978-3-642-12538-6_19","article-title":"Cellular Genetic Algorithm on Graphic Processing Units","volume":"Volume 284","author":"Pelta","year":"2010","journal-title":"Nature Inspired Cooperative Strategies for Optimization (NICSO 2010)"},{"key":"ref_52","unstructured":"NVIDIA. Available online: http:\/\/www.nvidia.in\/object\/gpu-computing-applications-in.html."},{"key":"ref_53","doi-asserted-by":"crossref","unstructured":"Ryoo, S., Rodrigues, C.I., Baghsorkhi, S.S., Stone, S.S., Kirk, D.B., and Hwu, W.M.W. (2008, January 20\u201323). Optimization Principles and Application Performance Evaluation of a Multithreaded GPU Using CUDA. Proceedings of the 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP \u201908), Salt LakeCity, UT, USA.","DOI":"10.1145\/1345206.1345220"},{"key":"ref_54","doi-asserted-by":"crossref","unstructured":"Torres, Y., Gonzalez-Escribano, A., and Llanos, D. (2011, January 4\u20138). Understanding the impact of CUDA tuning techniques for Fermi. Proceedings of the International Conference on High Performance Computing and Simulation (HPCS), Istanbul, Turkey.","DOI":"10.1109\/HPCSim.2011.5999886"},{"key":"ref_55","unstructured":"NVIDIA, Corporation. Tuning CUDATM Applications for FermiTM. Available online: https:\/\/wiki.zserv.tuwien.ac.at\/lib\/exe\/fetch.php?media=doku:cuda-docu:fermi_tuning_guide_1.3.pdf."},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"2365","DOI":"10.1002\/cpe.1776","article-title":"Design and implementation of an efficient integer count sort in CUDA GPUs","volume":"23","author":"Kolonias","year":"2011","journal-title":"Concurr. Comput.: Pract. Exp."},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/BFb0055884","article-title":"Some observations about GA-based exam timetabling","volume":"Volume 1408","author":"Burke","year":"1998","journal-title":"Practice and Theory of Automated Timetabling II"},{"key":"ref_58","unstructured":"Baker, J.E. Reducing bias and inefficiency in the selection algorithm. Proceedings of the Second International Conference on Genetic Algorithms and Their Applications."},{"key":"ref_59","unstructured":"Harris, M. (Optimizing Parallel Reduction in CUDA, 2007). Optimizing Parallel Reduction in CUDA, Technical Report, NVidia."},{"key":"ref_60","unstructured":"CUDA Toolkit Documentation v6.0. Available online: http:\/\/docs.nvidia.com\/cuda\/#axzz36HtAjyGN."},{"key":"ref_61","doi-asserted-by":"crossref","unstructured":"Burke, E.K., and Bykov, Y. (September, January 30). Solving Exam Timetabling Problems with the Flex-Deluge Algorithm. Proceedings of the 6th International Conference Practice and Theory of Automated Timetabling VI (PATAT 2006), Brno, Czech Republic.","DOI":"10.1007\/978-3-540-77345-0"},{"key":"ref_62","unstructured":"Burke, E.K., and Bykov, Y. (2008, January 18\u201322). A Late Acceptance Strategy in Hill-Climbing for Exam Timetabling Problems. Proceedings of the 7th International Conference on the Practice and Theory of Automated Timetabling (PATAT \u201908), University of Montreal, Montreal, QC, Canada."},{"key":"ref_63","unstructured":"Abdullah, S., Ahmadi, S., Burke, E.K., and Dror, M. (2004, January 18\u201320). Applying Ahuja-Orlin\u2019s Large Neighbourhood for Constructing Examination Timetabling Solution. Proceedings of the 5th International Conference on the Practice and Theory of Automated Timetabling (PATAT), Pittsburgh, PA, USA."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/7\/3\/295\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:13:16Z","timestamp":1760217196000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/7\/3\/295"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7,3]]},"references-count":63,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2014,9]]}},"alternative-id":["a7030295"],"URL":"https:\/\/doi.org\/10.3390\/a7030295","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2014,7,3]]}}}