×

zbMATH — the first resource for mathematics

The generalized balanced academic curriculum problem with heterogeneous classes. (English) Zbl 1301.90032
Summary: We propose an extension of the generalized balanced academic curriculum problem (GBACP), a relevant planning problem arising in many universities. The problem consists of assigning courses to teaching terms and years, satisfying a set of precedence constraints and balancing students’ load among terms. Differently from the original GBACP formulation, in our case, the same course can be assigned to different years for different curricula (i.e., the predetermined sets of courses from which a student can choose), leading to a more complex solution space.
The problem is tackled by both Integer Programming (IP) methods and combinations of metaheuristics based on local search. The experimental analysis shows that the best results are obtained by means of a two-stage metaheuristic that first computes a solution for the underlying GBACP and then refines it by searching in the extended solution space.

MSC:
90B35 Deterministic scheduling theory in operations research
90C11 Mixed integer programming
90C59 Approximation methods and heuristics in mathematical programming
Software:
BACP; CSPLib; EasyLocal++
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aarts, E. H. L., & Korst, J. (1989). Simulated annealing and Boltzmann machines. New York: Wiley. · Zbl 0674.90059
[2] Birattari, M.; Stützle, T.; Paquete, L.; Varrentrapp, K.; Langdon, W. B. (ed.); Cantú-Paz, E. (ed.); Mathias, K. (ed.); Roy, R. (ed.); Davis, D. (ed.); Poli, R. (ed.); Balakrishnan, K. (ed.); Honavar, V. (ed.); Rudolph, G. (ed.); Wegener, J. (ed.); Bull, L. (ed.); Potter, M. A. (ed.); Schultz, A. C. (ed.); Miller, J. F. (ed.); Burke, E. (ed.); Jonoska, N. (ed.), A racing algorithm for configuring metaheuristics, 11-18, (2002), New York
[3] Burke, E. K.; Mareček, J.; Parkes, A. J.; Rudová, H., A branch-and-cut procedure for the Udine course timetabling problem, Annals of Operations Research, 194, 71-87, (2012) · Zbl 1251.90276
[4] Castro, C., & Manzano, S. (2001). Variable and value ordering when solving balanced academic curriculum problems. In 6th workshop of the ERCIM working group on constraints.
[5] Castro, C.; Crawford, B.; Monfroy, E., A quantitative approach for the design of Academic curricula, No. 4558, 279-288, (2007), Berlin
[6] Černý, V., Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm, Journal of Optimization Theory and Applications, 45, 41-51, (1985) · Zbl 0534.90091
[7] Chiarandini, M.; Di Gaspero, L.; Gualandi, S.; Schaerf, A., The balanced Academic curriculum problem revisited, Journal of Heuristics, (2011) · Zbl 1358.90113
[8] Cioppa, T. M.; Lucas, T. W., Efficient nearly orthogonal and space-filling Latin hypercubes, Technometrics, 49, 45-55, (2007)
[9] Conover, W. (1999). Practical nonparametric statistics (3rd ed.). New York: Wiley.
[10] Di Gaspero, L.; Schaerf, A., Easylocal++: an object-oriented framework for flexible design of local search algorithms, Software, Practice & Experience, 33, 733-765, (2003)
[11] Di Gaspero, L.; Schaerf, A.; Blesa Aguilera, M. (ed.); Blum, C. (ed.); Cotta, C. (ed.); Fernández Leiva, A. (ed.); Gallardo Ruiz, J. (ed.); Roli, A. (ed.); Sampels, M. (ed.), Hybrid local search techniques for the generalized balanced Academic curriculum problem, No. 5296, 146-157, (2008), Berlin
[12] Gent, I. P., & Walsh, T. (1999). CSPLib: a benchmark library for constraints (Technical report). APES-09-1999. Available from http://csplib.cs.strath.ac.uk/. A shorter version appears in Lecture notes in computer science: Vol. 1713. Proceedings of the 5th international conference on principles and practices of constraint programming (CP-99) (pp. 480-481). Berlin: Springer.
[13] Hnich, B.; Kızıltan, Z.; Walsh, T.; Jussien, N. (ed.); Laburthe, F. (ed.), Modelling a balanced Academic curriculum problem, 121-131, (2002)
[14] Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 671-680, (1983) · Zbl 1225.90162
[15] Lambert, T.; Castro, C.; Monfroy, E.; Saubion, F., Solving the balanced Academic curriculum problem with an hybridization of genetic algorithm and constraint propagation, No. 4029, 410-419, (2006), Berlin
[16] McCollum, B.; Schaerf, A.; Paechter, B.; McMullan, P.; Lewis, R.; Parkes, A. J.; Di Gaspero, L.; Qu, R.; Burke, E. K., Setting the research agenda in automated timetabling: the second international timetabling competition, INFORMS Journal on Computing, 22, 120-130, (2010) · Zbl 1243.90007
[17] Monette, J.; Schaus, P.; Zampelli, S.; Deville, Y.; Dupont, P.; Benhamou, B. (ed.); Choueiry, B. (ed.); Hnich, B. (ed.), A CP approach to the balanced Academic curriculum problem, (2007)
[18] Sanchez, S. M. (2005). NOLH designs spreadsheet. http://diana.cs.nps.navy.mil/SeedLab/. Visited on May 13, 2011. Last updated on April 7, 2006.
[19] van Laarhoven, P. J. M., & Aarts, E. H. L. (1987). Simulated annealing: theory and applications. Norwell: Reidel/Kluwer. · Zbl 0643.65028
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.