×

An ILP based heuristic for a generalization of the post-enrollment course timetabling problem. (English) Zbl 1349.90381

Summary: We consider a new timetabling problem arising from a real-world application in a private university in Buenos Aires, Argentina. In this paper we describe the problem in detail, which generalizes the Post-Enrollment Course Timetabling Problem (PECTP), propose an ILP model and a heuristic approach based on this formulation. This algorithm has been implemented and tested on instances obtained from real data, showing that the approach is feasible in practice and produces good quality solutions.

MSC:

90B35 Deterministic scheduling theory in operations research
90B90 Case-oriented studies in operations research
90C10 Integer programming
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bettinelli, Andrea; Cacchiani, Valentina; Roberti, Roberto; Toth, Paolo, An overview of curriculum-based course timetabling, TOP, 23, 2, 313-349 (2015) · Zbl 1319.90026
[2] Burke, Edmund K.; Marecek, Jakub; Parkes, Andrew J.; Rudov, Hana, A branch-and-cut procedure for the eudine course timetabling problem, Ann Oper Res, 194, 1, 71-87 (2012) · Zbl 1251.90276
[3] Burke, Edmund K.; Pham, Nam; Qu, Rong; Yellen, Jay, Linear combinations of heuristics for examination timetabling, Ann Oper Res, 194, 1, 89-109 (2012) · Zbl 1251.90119
[4] Cambazard, Hadrien; Hebrard, Emmanuel; O’Sullivan, Barry; Papadopoulos, Alexandre, Local search and constraint programming for the post enrolment-based course timetabling problem, Ann Oper Res, 194, 1, 111-135 (2012) · Zbl 1251.90120
[6] Ceschia, Sara; Di Gaspero, Luca; Schaerf, Andrea, Design, engineering, and experimental analysis of a simulated annealing approach to the post-enrolment course timetabling problem, Comput Oper Res, 39, 7, 1615-1624 (2011)
[7] Ceschia, Sara; Di Gaspero, Luca; Schaerf, Andrea, The generalized balanced academic curriculum problem with heterogeneous classes, Ann Oper Res, 218, 1, 147-163 (2014) · Zbl 1301.90032
[8] Chiarandini, Marco; Di Gaspero, Luca; Gualandi, Stefano; Schaerf, Andrea, The balanced academic curriculum problem revisited, J Heurist, 18, 1, 119-148 (2012) · Zbl 1358.90113
[10] Daskalaki, S.; Birbas, T., Efficient solutions for a university timetabling problem through integer programming, Eur J Oper Res, 160, 1, 106-120 (2005) · Zbl 1067.90135
[11] Gogos, Christos; Alefragis, Panayiotis; Housos, Efthymios, An improved multi-staged algorithmic process for the solution of the examination timetabling problem, Ann Oper Res, 194, 1, 203-221 (2012) · Zbl 1251.90149
[12] Jat, Sadaf Naseem; Yang, Shengxiang, A hybrid genetic algorithm and tabu search approach for post enrolment course timetabling, J Sched, 14, 6, 617-637 (2011)
[13] Kristiansen, Simon; Sørensen, Matias; Stidsen, Thomas R., Integer programming for the generalized high school timetabling problem, J Sched, 1-16 (2014), (English) · Zbl 1328.90056
[14] Lach, Gerald; Lübbecke, Marco E., Curriculum based course timetablingnew solutions to udine benchmark instances, Ann Oper Res, 194, 1, 255-272 (2012) · Zbl 1251.90160
[15] Lewis, Rhyd, A time-dependent metaheuristic algorithm for post enrolment-based course timetabling, Ann Oper Res, 194, 1, 273-289 (2012) · Zbl 1251.90164
[16] Lu, Zhipeng; Hao, Jin-Kao, Adaptive tabu search for course timetabling, Eur J Oper Res, 200, 1, 235-244 (2010) · Zbl 1190.90166
[17] Lübbecke, Marco E., Comments onan overview of curriculum-based course timetabling, TOP, 23, 2, 359-361 (2015) · Zbl 1319.90036
[18] McCollum, Barry; Schaerf, Andrea; Paechter, Ben; McMullan, Paul; Lewis, Rhyd; Parkes, Andrew J., Setting the research agenda in automated timetablingthe second international timetabling competition, INFORMS J Comput, 22, 1, 120-130 (2010) · Zbl 1243.90007
[19] Müller, Tomáš; Murray, Keith, Comprehensive approach to student sectioning, Ann Oper Res, 181, 1, 249-269 (2010)
[21] Nothegger, Clemens; Mayer, Alfred; Chwatal, Andreas; Raidl, Günther R., Solving the post enrolment course timetabling problem by ant colony optimization, Ann Oper Res, 194, 1, 325-339 (2012) · Zbl 1251.90174
[22] Sørensen, Matias; Dahms, Florian H. W., A two-stage decomposition of high school timetabling applied to cases in Denmark, Comput Oper Res, 43, 0, 36-49 (2014) · Zbl 1348.90313
[23] van den Broek, John; Hurkens, Cor, An ip-based heuristic for the post enrolment course timetabling problem of the itc2007, Ann Oper Res, 194, 1, 439-454 (2012) · Zbl 1251.90132
[24] van den Broek, John; Hurkens, Cor; Woeginger, Gerhard, Timetabling problems at the tu Eindhoven, Eur J Oper Res, 196, 3, 877-885 (2009) · Zbl 1176.90421
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.