×

zbMATH — the first resource for mathematics

Application of a real-world university-course timetabling model solved by integer programming. (English) Zbl 1168.90670
Summary: In this case study, we describe an integer programming (IP) approach, which has been implemented at the School of Economics and Management at Hannover University, Germany, to create the complete timetable of all courses for a term. Approximately 150 different weekly lectures, tutorials and seminars ranging from 5 to 650 students are taught by about 100 teachers. The decision problem is to assign these teaching groups to time slots and rooms so that several soft and hard constraints are met. It is modeled as an assignment problem with numerous types of constraints and about 100,000 binary or integer variables. An open source mixed-integer solver can be used to solve the problem to optimality within minutes whereas the commercial CPLEX solver takes only seconds. We also describe the implementation process and report results from an anonymous satisfaction survey among the faculty with respect to the new planning approach.

MSC:
90C90 Applications of mathematical programming
90B35 Deterministic scheduling theory in operations research
90C10 Integer programming
Software:
Cbc; CPLEX; FlopC++
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abdennadher S, Marte M (2000) University course timetabling using constraint handling rules. App Artif Intell 14:311–325 · Zbl 05386621 · doi:10.1080/088395100117016
[2] Asratian AS, De Werra D (2002) A generalized class-teacher-model for some timetabling problems. Eur J Oper Res 143:531–542 · Zbl 1082.05521 · doi:10.1016/S0377-2217(01)00342-3
[3] Baker KR, Magazine MJ, Polak GG (2002) Optimal block design models for course timetabling. Oper Res Lett 30:1–8 · Zbl 1030.90066 · doi:10.1016/S0167-6377(01)00116-X
[4] Burke EK, Petrovic S (2002) Recent research in automated timetabling. Eur J Oper Res 140:266–280 · Zbl 1001.90030 · doi:10.1016/S0377-2217(02)00069-3
[5] Carter MW, Laporte G (1998). Recent developments in practical course timetabling. In: Burke EK, Carter M (eds). Practice and theory of automated timetabling (PATAT) II, LNCS 1408. Springer, Berlin Heidelberg New York, pp. 3–19
[6] Daskalaki S, Birbas T, Housos E (2004) An integer programming formulation for a case study in university timetabling. Eur J Oper Res 153:117–135 · Zbl 1053.90078 · doi:10.1016/S0377-2217(03)00103-6
[7] De Werra D (1985) An introduction to timetabling. Eur J Oper Res 19(2):151–162 · Zbl 0553.90059 · doi:10.1016/0377-2217(85)90167-5
[8] Deris S, Omatu S, Ohata H, Samat PABD (1997) University timetabling by constraint-based reasoning: a case study. J Oper Res Soc 48:1178–1190 · Zbl 0895.90115
[9] Di Gaspero L, Schaerf A (2003). Multi-neighborhood local search with application of course timetabling. In: Burke EK, De Causmaecker P (eds). Practice and theory of automated timetabling (PATAT) IV, LNCS 2740. Springer, Berlin Heidelberg New York, pp. 262–275
[10] Dimopoulou M, Miliotis P (2001) Implementation of a university course and examination timetabling system. Eur J Oper Res 130:202–213 · Zbl 0985.90046 · doi:10.1016/S0377-2217(00)00052-7
[11] Forrest J, Lougee-Heimer R (2005) CBC user guide. http://www.coin-or.org/Cbc/cbcuserguide.html, access 02/05/2006, 12:26 p.m.
[12] Haase K, Scheel H, Sebastian D (2004) Hörsaalmanagement. Modell, Verfahren und Internetanwendung zur effizienten Vorlesungsplanerstellung. Wirtschaftsinformatik 46(2):87–95
[13] Hultberg TH (2003) A presentation of FLOPC++. http://projects.coin-or.org/FlopC++, access 05/02/2006, 12:14 p.m.
[14] Lange K (2005) Entscheidungsmodelle des Operations Research für die Stundenplangestaltung im universitären Bereich. Master’s thesis, School of Economics and Management, Hannover University
[15] Martin CH (2004) Ohio university’s college of business uses integer programming to schedule classes. Interfaces 34(6):460–465 · doi:10.1287/inte.1040.0106
[16] Petrovic S, Burke EK (2004) University timetabling. In: Leung JYT (ed) Handbook of scheduling: algorithms, models, and performance analysis, pp 45:1–45:23
[17] Rudová H, Murray K (2003). University course timetabling with soft constraints. In: Burke EK, De Causmaecker P (eds). Practice and theory of automated timetabling (PATAT) IV, LNCS 2740. Springer, Berlin Heidelberg New York, pp. 310–328
[18] Schaerf A (1999) A survey of automated timetabling. Artif Intell Rev 13(2):87–127 · Zbl 05467698 · doi:10.1023/A:1006576209967
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.