Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

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. © 2016 Elsevier Ltd

Registro:

Documento: Artículo
Título:An ILP based heuristic for a generalization of the post-enrollment course timetabling problem
Autor:Méndez-Díaz, I.; Zabala, P.; Miranda-Bront, J.J.
Filiación:Departamento de Computación, FCEyN, Universidad de Buenos Aires, Argentina
Consejo Nacional de Investigaciones Científicas y Técnicas, Argentina
Palabras clave:Integer programming; Matheuristic; University timetabling; Heuristic methods; Integer programming; Buenos Aires , Argentina; Course timetabling; Heuristic approach; ILP modeling; Matheuristic; Real-world; Timetabling problem; University timetabling; Scheduling
Año:2016
Volumen:76
Página de inicio:195
Página de fin:207
DOI: http://dx.doi.org/10.1016/j.cor.2016.06.018
Título revista:Computers and Operations Research
Título revista abreviado:Comp. Oper. Res.
ISSN:03050548
CODEN:CMORA
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03050548_v76_n_p195_MendezDiaz

Referencias:

  • Bettinelli, A., Cacchiani, V., Roberti, R., Toth, P., An overview of curriculum-based course timetabling (2015) TOP, 23 (2), pp. 313-349
  • Burke, E.K., Marecek, J., Parkes, A.J., Rudov, H., A branch-and-cut procedure for the eudine course timetabling problem (2012) Ann Oper Res, 194 (1), pp. 71-87
  • Burke, E.K., Pham, N., Qu, R., Yellen, J., Linear combinations of heuristics for examination timetabling (2012) Ann Oper Res, 194 (1), pp. 89-109
  • Cambazard, H., Hebrard, E., O'Sullivan, B., Papadopoulos, A., Local search and constraint programming for the post enrolment-based course timetabling problem (2012) Ann Oper Res, 194 (1), pp. 111-135
  • Michael, W.C., A comprehensive course timetabling and student scheduling system at the University of Waterloo (2001), pp. 64-82. , In: Practice and theory of automated timetabling III;; Ceschia, S., Di Gaspero, L., Schaerf, A., Design, engineering, and experimental analysis of a simulated annealing approach to the post-enrolment course timetabling problem (2011) Comput Oper Res, 39 (7), pp. 1615-1624
  • Ceschia, S., Di Gaspero, L., Schaerf, A., The generalized balanced academic curriculum problem with heterogeneous classes (2014) Ann Oper Res, 218 (1), pp. 147-163
  • Chiarandini, M., Di Gaspero, L., Gualandi, S., Schaerf, A., The balanced academic curriculum problem revisited (2012) J Heurist, 18 (1), pp. 119-148
  • Chiarandini, M., Fawcett, C., Holger, H.H., A modular multiphase heuristic solver for post enrolment course timetabling (2008), In: Proceedings of PATAT;; Daskalaki, S., Birbas, T., Efficient solutions for a university timetabling problem through integer programming (2005) Eur J Oper Res, 160 (1), pp. 106-120
  • Gogos, C., Alefragis, P., Housos, E., An improved multi-staged algorithmic process for the solution of the examination timetabling problem (2012) Ann Oper Res, 194 (1), pp. 203-221
  • Jat, S.N., Yang, S., A hybrid genetic algorithm and tabu search approach for post enrolment course timetabling (2011) J Sched, 14 (6), pp. 617-637
  • Kristiansen, S., Sørensen, M., Stidsen, T.R., Integer programming for the generalized high school timetabling problem (2014) J Sched, pp. 1-16. , (English)
  • Lach, G., Lübbecke, M.E., Curriculum based course timetabling: new solutions to udine benchmark instances (2012) Ann Oper Res, 194 (1), pp. 255-272
  • Lewis, R., A time-dependent metaheuristic algorithm for post enrolment-based course timetabling (2012) Ann Oper Res, 194 (1), pp. 273-289
  • Lu, Z., Hao, J.-K., Adaptive tabu search for course timetabling (2010) Eur J Oper Res, 200 (1), pp. 235-244
  • Lübbecke, M.E., Comments on: an overview of curriculum-based course timetabling (2015) TOP, 23 (2), pp. 359-361
  • McCollum, B., Schaerf, A., Paechter, B., McMullan, P., Lewis, R., Parkes, A.J., Setting the research agenda in automated timetabling: the second international timetabling competition (2010) INFORMS J Comput, 22 (1), pp. 120-130
  • Müller, T., Murray, K., Comprehensive approach to student sectioning (2010) Ann Oper Res, 181 (1), pp. 249-269
  • Murray, K., Müller, T., Rudová, H., Modeling and solution of a complex university course timetabling problem (2007), pp. 189-209. , In: Practice and theory of automated timetabling VI; Nothegger, C., Mayer, A., Chwatal, A., Raidl, G.R., Solving the post enrolment course timetabling problem by ant colony optimization (2012) Ann Oper Res, 194 (1), pp. 325-339
  • Sørensen, M., Dahms, F.H.W., A two-stage decomposition of high school timetabling applied to cases in Denmark (2014) Comput Oper Res, 43, pp. 36-49
  • van den Broek, J., Hurkens, C., An ip-based heuristic for the post enrolment course timetabling problem of the itc2007 (2012) Ann Oper Res, 194 (1), pp. 439-454
  • van den Broek, J., Hurkens, C., Woeginger, G., Timetabling problems at the tu Eindhoven (2009) Eur J Oper Res, 196 (3), pp. 877-885

Citas:

---------- APA ----------
Méndez-Díaz, I., Zabala, P. & Miranda-Bront, J.J. (2016) . An ILP based heuristic for a generalization of the post-enrollment course timetabling problem. Computers and Operations Research, 76, 195-207.
http://dx.doi.org/10.1016/j.cor.2016.06.018
---------- CHICAGO ----------
Méndez-Díaz, I., Zabala, P., Miranda-Bront, J.J. "An ILP based heuristic for a generalization of the post-enrollment course timetabling problem" . Computers and Operations Research 76 (2016) : 195-207.
http://dx.doi.org/10.1016/j.cor.2016.06.018
---------- MLA ----------
Méndez-Díaz, I., Zabala, P., Miranda-Bront, J.J. "An ILP based heuristic for a generalization of the post-enrollment course timetabling problem" . Computers and Operations Research, vol. 76, 2016, pp. 195-207.
http://dx.doi.org/10.1016/j.cor.2016.06.018
---------- VANCOUVER ----------
Méndez-Díaz, I., Zabala, P., Miranda-Bront, J.J. An ILP based heuristic for a generalization of the post-enrollment course timetabling problem. Comp. Oper. Res. 2016;76:195-207.
http://dx.doi.org/10.1016/j.cor.2016.06.018