{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T14:11:17Z","timestamp":1774966277959,"version":"3.50.1"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,3,11]],"date-time":"2024-03-11T00:00:00Z","timestamp":1710115200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,3,11]],"date-time":"2024-03-11T00:00:00Z","timestamp":1710115200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2025,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Examination timetabling is a problem well known to the scheduling community. Its simplest version, which is the uncapacitated examination timetabling problem, is easily described and comprehended. Nevertheless, proof of optimality is notoriously difficult even for moderate size problems. In this paper, we describe the effort that our team exercised in finally proving the optimality of the sta83 instance of Carter\u2019s dataset. The problem was decomposed naturally in three parts and for each part a different approach managed to prove optimality of the currently best known solution. This work also presents optimal solutions to subproblems that exist in various public datasets problems and two best known solutions of such problems.<\/jats:p>","DOI":"10.1007\/s10951-024-00805-0","type":"journal-article","created":{"date-parts":[[2024,3,11]],"date-time":"2024-03-11T20:02:34Z","timestamp":1710187354000},"page":"183-194","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A proven optimal result for a benchmark instance of the uncapacitated examination timetabling problem"],"prefix":"10.1007","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7892-046X","authenticated-orcid":false,"given":"Angelos","family":"Dimitsas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos","family":"Gogos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos","family":"Valouxis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vasileios","family":"Nastos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Panayiotis","family":"Alefragis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,3,11]]},"reference":[{"issue":"1","key":"805_CR1","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s10479-007-0178-0","volume":"153","author":"KI Aardal","year":"2007","unstructured":"Aardal, K. I., Van Hoesel, S. P., Koster, A. M., Mannino, C., & Sassano, A. (2007). Models and solution techniques for frequency assignment problems. Annals of Operations Research, 153(1), 79\u2013129.","journal-title":"Annals of Operations Research"},{"key":"805_CR2","unstructured":"Alefragis, P., Gogos, C., Valouxis, C., Housos, E.: (2021) \u201cA multiple metaheuristic variable neighborhood search framework for the uncapacitated examination timetabling problem,\u201d in Proceedings of the 13th International Conference on the Practice and Theory of Automated Timetabling-PATAT, vol.\u00a01, pp. 159\u2013171."},{"key":"805_CR3","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.cie.2014.11.010","volume":"86","author":"H Babaei","year":"2015","unstructured":"Babaei, H., Karimpour, J., & Hadidi, A. (2015). A survey of approaches for university course timetabling problem. Computers & Industrial Engineering, 86, 43\u201359.","journal-title":"Computers & Industrial Engineering"},{"key":"805_CR4","doi-asserted-by":"crossref","unstructured":"Battistutta, M., Ceschia, S., Cesco, F.D., Gaspero, L.D., Schaerf, A., Topan, E.: \u201cLocal search and constraint programming for a real-world examination timetabling problem,\u201d in International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research. Springer, pp. 69\u201381. (2020)","DOI":"10.1007\/978-3-030-58942-4_5"},{"key":"805_CR5","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2021.105300","volume":"132","author":"R Bellio","year":"2021","unstructured":"Bellio, R., Ceschia, S., Di Gaspero, L., & Schaerf, A. (2021). Two-stage multi-neighborhood simulated annealing for uncapacitated examination timetabling. Computers & Operations Research, 132, 105300.","journal-title":"Computers & Operations Research"},{"issue":"1","key":"805_CR6","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1137\/141000671","volume":"59","author":"J Bezanson","year":"2017","unstructured":"Bezanson, J., Edelman, A., Karpinski, S., & Shah, V. B. (2017). Julia: A fresh approach to numerical computing. SIAM Review, 59(1), 65\u201398.","journal-title":"SIAM Review"},{"key":"805_CR7","unstructured":"Burke, E.K., Bykov, Y.: \u201cSolving exam timetabling problems with the flex-deluge algorithm,\u201d in Proceedings of PATAT, vol. Citeseer, 2006, pp. 370\u2013372. (2006)"},{"key":"805_CR8","doi-asserted-by":"crossref","unstructured":"Carter, M. W., Laporte, G., & Lee, S. Y. (1996). Examination timetabling: Algorithmic strategies and applications. Journal of the Operational Research Society, 47(3), 373\u2013383.","DOI":"10.1057\/jors.1996.37"},{"key":"805_CR9","doi-asserted-by":"crossref","unstructured":"Ceschia, S., Di\u00a0Gaspero, L., Schaerf, A.: \u201cEducational timetabling: Problems, benchmarks, and state-of-the-art results,\u201d arXiv preprint[SPACE]arXiv:2201.07525, (2022).","DOI":"10.1016\/j.ejor.2022.07.011"},{"key":"805_CR10","doi-asserted-by":"crossref","unstructured":"Demeester, P., Bilgin, B., De Causmaecker, P., & Vanden Berghe, G. (2012). A hyperheuristic approach to examination timetabling problems: Benchmarks and a new problem from practice. Journal of Scheduling, 15, 83\u2013103.","DOI":"10.1007\/s10951-011-0258-5"},{"key":"805_CR11","doi-asserted-by":"crossref","unstructured":"Gogos, C., Dimitsas, A., Nastos, V., Valouxis, C., & \u201cSome insights about the uncapacitated examination timetabling problem,\u201d in,. (2021). 6th South-East Europe Design Automation, Computer Engineering, Computer Networks and Social Media Conference (SEEDA-CECNSM). IEEE,2021, 1\u20137.","DOI":"10.1109\/SEEDA-CECNSM53056.2021.9566258"},{"key":"805_CR12","unstructured":"IBM, \u201cIBM ILOG CPLEX,\u201d https:\/\/www.ibm.com\/products\/ilog-cplex-optimization-studio, 2022, version 22.1.1."},{"key":"805_CR13","unstructured":"Kristiansen, S., Stidsen, T.R.: \u201cA comprehensive study of educational timetabling, a survey,\u201d Department of Management Engineering, Technical University of Denmark.(DTU Management Engineering Report, vol.\u00a08, (2013)."},{"key":"805_CR14","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1016\/j.cor.2018.02.009","volume":"94","author":"N Leite","year":"2018","unstructured":"Leite, N., Fernandes, C. M., Melicio, F., & Rosa, A. C. (2018). A cellular memetic algorithm for the examination timetabling problem. Computers & Operations Research, 94, 118\u2013138.","journal-title":"Computers & Operations Research"},{"issue":"1","key":"805_CR15","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/s10951-008-0077-5","volume":"12","author":"R Qu","year":"2009","unstructured":"Qu, R., Burke, E. K., McCollum, B., Merlot, L. T., & Lee, S. Y. (2009). A survey of search methodologies and automated system development for examination timetabling. Journal of scheduling, 12(1), 55\u201389.","journal-title":"Journal of scheduling"},{"key":"805_CR16","doi-asserted-by":"crossref","unstructured":"Rahman, S. A., Bargiela, A., Burke, E. K., Ozcan, E., McCollum, B. (2009). Construction of examination timetables based on ordering heuristics. 24th international symposium on computer and information sciences. IEEE,2009, 680\u2013685.","DOI":"10.1109\/ISCIS.2009.5291905"},{"issue":"4","key":"805_CR17","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1109\/3468.769755","volume":"29","author":"A Schaerf","year":"1999","unstructured":"Schaerf, A. (1999). Local search techniques for large high school timetabling problems. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 29(4), 368\u2013377.","journal-title":"IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans"},{"issue":"2","key":"805_CR18","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1023\/A:1006576209967","volume":"13","author":"A Schaerf","year":"1999","unstructured":"Schaerf, A. (1999). A survey of automated timetabling. Artificial intelligence review, 13(2), 87\u2013127.","journal-title":"Artificial intelligence review"},{"key":"805_CR19","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2020.113943","volume":"165","author":"JS Tan","year":"2021","unstructured":"Tan, J. S., Goh, S. L., Kendall, G., & Sabar, N. R. (2021). A survey of the state-of-the-art of optimisation methodologies in school timetabling problems. Expert Systems with Applications, 165, 113943.","journal-title":"Expert Systems with Applications"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-024-00805-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-024-00805-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-024-00805-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T13:09:24Z","timestamp":1748869764000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-024-00805-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,11]]},"references-count":19,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,4]]}},"alternative-id":["805"],"URL":"https:\/\/doi.org\/10.1007\/s10951-024-00805-0","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,11]]},"assertion":[{"value":"18 January 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 March 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 December 2024","order":3,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":4,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Funding note has been included in this article.","order":5,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}