×

zbMATH — the first resource for mathematics

The balanced academic curriculum problem revisited. (English) Zbl 1358.90113
Summary: The Balanced Academic Curriculum Problem (BACP) consists in assigning courses to teaching terms satisfying prerequisites and balancing the credit course load within each term. The BACP is part of the CSPLib with three benchmark instances, but its formulation is simpler than the problem solved in practice by universities. In this article, we introduce a generalized version of the problem that takes different curricula and professor preferences into account, and we provide a set of real-life problem instances arisen at University of Udine. Since the existing formulation based on a min-max objective function does not balance effectively the credit load for the new instances, we also propose alternative objective functions. Whereas all the CSPLib instances are efficiently solved with Integer Linear Programming (ILP) state-of-the-art solvers, our new set of real-life instances turns out to be much more challenging and still intractable for ILP solvers. Therefore, we have designed, implemented, and analyzed heuristics based on local search. We have collected computational results on all the new instances with the proposed approaches and assessed the quality of solutions with respect to the lower bounds found by ILP on a relaxed and decomposed problem. Results show that a selected heuristic finds solutions of quality at 9%–60% distance from the lower bound. We make all data publicly available, in order to stimulate further research on this problem.

MSC:
90C27 Combinatorial optimization
90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
Software:
BACP; CSPLib; EasyLocal++
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] A survey of very-large-scale neighborhood search techniques, Discrete Appl. Math., 123, 75-102, (2002) · Zbl 1014.68052
[2] etal., A racing algorithm for configuring metaheuristics, 11-18, (2002), San Mateo
[3] A quantitative approach for the design of Academic curricula, No. 4558, 279-288, (2007), Berlin
[4] Variable and value ordering when solving balanced Academic curriculum problems, pp., (2001)
[5] easylocal++: an object-oriented framework for flexible design of local search algorithms, Softw. Pract. Exp., 8, 33, 733-765, (2003)
[6] Neighborhood portfolio approach for local search applied to timetabling problems, J. Math. Model. Algorithms, 1, 5, 65-89, (2006) · Zbl 1103.90102
[7] Hybrid local search techniques for the generalized balanced Academic curriculum problem, No. 5296, 146-157, (2008), Berlin
[8] A new genetic local search algorithm for graph coloring, No. 1498, 745-754, (1998), Berlin
[9] Ehrgott, M.: Multicriteria Optimization, 2nd edn. Lecture Notes in Economics and Mathematical Systems. Springer, Berlin Heidelberg (2005) · Zbl 1132.90001
[10] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of [InlineEquation not available: see fulltext.]-Completeness. Freeman, New York (1979)
[11] Gent, I.P., Walsh, T.: CSPLib: a benchmark library for constraints. Technical report APES-09-1999. Available from http://csplib.cs.strath.ac.uk/. A shorter version appears in the Proceedings of the 5th International Conference on Principles and Practices of Constraint Programming (CP-99). LNCS, vol. 1713, pp. 480-481. Springer, Berlin (1999)
[12] Ejection chains, reference structures and alternating path methods for traveling salesman problems, Discrete Appl. Math., 1-3, 65, 223-253, (1996) · Zbl 0846.90117
[13] An introduction to variable neighbourhood search, 433-458, (1999), Dordrecht · Zbl 0985.90095
[14] Modelling a balanced Academic curriculum problem, 121-131, (2002)
[15] Hoos, H.: Stochastic local search—methods, models, application. Ph.D. thesis, Darmstadt University of Technology, Darmstadt, Germany (1999) · Zbl 0999.68050
[16] Hoos, H.H., Stützle, T.: Stochastic Local Search—Foundations and Applications. Morgan Kaufmann, San Mateo (2005) · Zbl 1126.68032
[17] Solving the balanced Academic curriculum problem with an hybridization of genetic algorithm and constraint propagation, No. 4029, 410-419, (2006), Berlin
[18] Applying iterated local search to the permutation flow shop problem, pp., (2001), Dordrecht
[19] A CP approach to the balanced Academic curriculum problem, pp., (2007)
[20] Comprehensive approach to student sectioning, Ann. Oper. Res., 1, 181, 249-269, (2010)
[21] Spread: a balancing constraint based on statistics, Sitges, Spain, 1-5 October 2005, Berlin · Zbl 1153.68475
[22] A survey of automated timetabling, Artif. Intell. Rev., 2, 13, 87-127, (1999)
[23] Measurability and reproducibility in timetabling research: discussion and proposals, No. 3867, 40-49, (2007), Berlin-Heidelberg
[24] The deviation constraint, No. 4510, 260-274, (2007), Berlin · Zbl 1214.90104
[25] Scalable load balancing in nurse to patient assignment problems, No. 5547, 248-262, (2009), Berlin
[26] Robust taboo search for the quadratic assignment problem, Parallel Comput., 4-5, 17, 443-455, (1991)
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.