{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,22]],"date-time":"2026-06-22T10:13:29Z","timestamp":1782123209305,"version":"3.54.5"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,2,15]],"date-time":"2022-02-15T00:00:00Z","timestamp":1644883200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,2,15]],"date-time":"2022-02-15T00:00:00Z","timestamp":1644883200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"University of Applied Sciences and Arts Western Switzerland"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2022,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This article presents a mixed-integer programming model for solving the university timetabling problem which considers the allocation of students to classes and the assignment of rooms and time periods to each class. The model was developed as part of our participation in the International Timetabling Competition 2019 and produced a ranking of second place at the competition. Modeling a timetabling problem as a mixed-integer program is not new. Our contribution rests on a number of innovative features adapted to this problem which allow for a reduction in the number of variables and constraints of the mixed-integer program to manageable levels achieving a reasonable computational performance. The proposed algorithm consists of a first-stage method to obtain an initial feasible solution and a second-stage local search procedure to iteratively improve the solution value, both of which involve the optimization of mixed-integer programming problems.<\/jats:p>","DOI":"10.1007\/s10951-021-00715-5","type":"journal-article","created":{"date-parts":[[2022,2,15]],"date-time":"2022-02-15T04:39:42Z","timestamp":1644899982000},"page":"391-404","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":41,"title":["A mixed-integer programming approach for solving university course timetabling problems"],"prefix":"10.1007","volume":"25","author":[{"given":"Efstratios","family":"Rappos","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eric","family":"Thi\u00e9mard","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stephan","family":"Robert","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jean-Fran\u00e7ois","family":"H\u00eache","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,2,15]]},"reference":[{"issue":"1","key":"715_CR1","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/S0166-218X(01)00338-9","volume":"123","author":"RK Ahuja","year":"2002","unstructured":"Ahuja, R. K., Ergun, \u00d6., Orlin, J. B., & Punnen, A. P. (2002). A survey of very large-scale neighborhood search techniques. Discrete Applied Mathematics, 123(1), 75\u2013102.","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"715_CR2","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/s11750-015-0366-z","volume":"23","author":"A Bettinelli","year":"2015","unstructured":"Bettinelli, A., Cacchiani, V., Roberti, R., & Toth, P. (2015). An overview of curriculum-based course timetabling. TOP, 23(2), 313\u2013349.","journal-title":"TOP"},{"issue":"1","key":"715_CR3","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s10479-010-0707-0","volume":"194","author":"A Bonutti","year":"2012","unstructured":"Bonutti, A., De Cesco, F., Di Gaspero, L., & Schaerf, A. (2012). Benchmarking curriculum-based course timetabling: formulations, data formats, instances, validation, visualization, and results. Annals of Operations Research, 194(1), 59\u201370.","journal-title":"Annals of Operations Research"},{"issue":"1","key":"715_CR4","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/j.ejor.2010.01.044","volume":"206","author":"E Burke","year":"2010","unstructured":"Burke, E., Eckersley, A., McCollum, B., Petrovic, S., & Qu, R. (2010). Hybrid variable neighbourhood approaches to university exam timetabling. European Journal of Operational Research, 206(1), 46\u201353.","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"715_CR5","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0377-2217(85)90167-5","volume":"19","author":"D de Werra","year":"1985","unstructured":"de Werra, D. (1985). An introduction to timetabling. European Journal of Operational Research, 19(2), 151\u2013162.","journal-title":"European Journal of Operational Research"},{"key":"715_CR6","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/j.cor.2014.06.023","volume":"52","author":"\u00c1P Dorneles","year":"2014","unstructured":"Dorneles, \u00c1. P., de Ara\u00fajo, O. C., & Buriol, L. S. (2014). A fix-and-optimize heuristic for the high school timetabling problem. Computers and Operations Research, 52, 29\u201338.","journal-title":"Computers and Operations Research"},{"key":"715_CR7","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1016\/j.cor.2016.04.016","volume":"74","author":"GH Fonseca","year":"2016","unstructured":"Fonseca, G. H., Santos, H. G., & Carrano, E. G. (2016). Integrating matheuristics and metaheuristics for timetabling. Computers and Operations Research, 74, 108\u2013117.","journal-title":"Computers and Operations Research"},{"key":"715_CR8","doi-asserted-by":"crossref","unstructured":"Hwang, K.S., Lee, K.M., Jeon, J. (2004) A practical timetabling algorithm for college lecture-timetable scheduling. In: Lecture notes in computer science, pp. 817\u2013825. Springer.","DOI":"10.1007\/978-3-540-30134-9_109"},{"key":"715_CR9","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/s10479-016-2151-2","volume":"252","author":"A Kiefer","year":"2017","unstructured":"Kiefer, A., Hartl, R. F., & Schnell, A. (2017). Adaptive large neighborhood search for the curriculum-based course timetabling problem. Annals of Operations Research, 252, 255\u2013282.","journal-title":"Annals of Operations Research"},{"key":"715_CR10","first-page":"91","volume-title":"Studies in computational intelligence","author":"JH Kingston","year":"2013","unstructured":"Kingston, J. H. (2013). Educational timetabling. In A. Uyar & E. U. N. Ozcan (Eds.), Studies in computational intelligence (pp. 91\u2013108). Springer."},{"key":"715_CR11","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/978-3-540-48584-1_9","volume-title":"Evolutionary scheduling","author":"R Lewis","year":"2007","unstructured":"Lewis, R., Paechter, B., & Rossi-Doria, O. (2007). Metaheuristics for university course timetabling. In K. P. Dahal, K. C. Tan, & P. I. Cowling (Eds.), Evolutionary scheduling (pp. 237\u2013272). Berlin Heidelberg: Springer."},{"issue":"4","key":"715_CR12","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1007\/s10732-018-9371-3","volume":"24","author":"M Lindahl","year":"2018","unstructured":"Lindahl, M., S\u00f8rensen, M., & Stidsen, T. R. (2018). A fix-and-optimize matheuristic for university timetabling. Journal of Heuristics, 24(4), 645\u2013665.","journal-title":"Journal of Heuristics"},{"issue":"2","key":"715_CR13","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/s10462-011-9262-6","volume":"39","author":"SA MirHassani","year":"2013","unstructured":"MirHassani, S. A., & Habibi, F. (2013). Solution approaches to the course timetabling problem. Artificial Intelligence Review, 39(2), 133\u2013149.","journal-title":"Artificial Intelligence Review"},{"issue":"1","key":"715_CR14","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/s10479-014-1643-1","volume":"239","author":"T M\u00fcller","year":"2016","unstructured":"M\u00fcller, T., & Rudov\u00e1, H. (2016). Real-life curriculum-based timetabling with elective courses and course sections. Annals of Operations Research, 239(1), 153\u2013170.","journal-title":"Annals of Operations Research"},{"key":"715_CR15","unstructured":"M\u00fcller, T., Rudov\u00e1, H., M\u00fcllerov\u00e1, Z. (2018) University course timetabling and international timetabling competition 2019. In: PATAT 2018\u2014Proceedings of the 12th international conference on the practice and theory of automated timetabling (PATAT 2018)."},{"issue":"1","key":"715_CR16","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/s10479-013-1321-8","volume":"218","author":"N Pillay","year":"2014","unstructured":"Pillay, N. (2014). A survey of school timetabling research. Annals of Operations Research, 218(1), 261\u2013293.","journal-title":"Annals of Operations Research"},{"key":"715_CR17","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/978-1-4419-1665-5_13","volume-title":"Handbook of Metaheuristics","author":"D Pisinger","year":"2010","unstructured":"Pisinger, D., & Ropke, S. (2010). Large neighborhood search. In M. Gendreau & J. Y. Potvin (Eds.), Handbook of Metaheuristics (pp. 399\u2013419). US, Boston, MA: Springer."},{"issue":"1","key":"715_CR18","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. G., & 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"},{"issue":"2","key":"715_CR19","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/s10951-010-0171-3","volume":"14","author":"H Rudov\u00e1","year":"2011","unstructured":"Rudov\u00e1, H., M\u00fcller, T., & Murray, K. (2011). Complex university course timetabling. Journal of Scheduling, 14(2), 187\u2013207.","journal-title":"Journal of Scheduling"},{"issue":"2","key":"715_CR20","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"},{"issue":"4","key":"715_CR21","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1093\/comjnl\/23.4.307","volume":"23","author":"G Schmidt","year":"1980","unstructured":"Schmidt, G., & Str\u00f6hlein, T. (1980). Timetable construction-an annotated bibliography. The Computer Journal, 23(4), 307\u2013316.","journal-title":"The Computer Journal"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-021-00715-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-021-00715-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-021-00715-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,29]],"date-time":"2022-07-29T07:01:52Z","timestamp":1659078112000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-021-00715-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,15]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["715"],"URL":"https:\/\/doi.org\/10.1007\/s10951-021-00715-5","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,15]]},"assertion":[{"value":"2 November 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 February 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}