The Generalized Balanced Academic Curriculum Problem

The Balanced Academic Curriculum Problem (BACP) consists in assigning courses to teaching periods satisfying prerequisites and balancing students' load. This problem has been originally proposed by Castro and Manzano and is listed as problem n. 30 of CSPlib.

However, the problem is actually simpler than the real problem that universities have to solve in practice, therefore we propose a generalization of the problem which applies, among others, to our institution (the School of Engineering at the University of Udine).

The formulation of the Generalized BACP consists of the following entities and constraints:

Courses: Each course has an integer number of credits and it has to be taught during the planning horizon of the university degree.
Periods: The planning horizon is composed by a given number of teaching periods that have to be assigned to courses. Periods are divided in years, and each year is divided in a fixed number of terms. For example, a 3-year degree organized in four trimesters per year has 12 periods.
Load limits: For each period there is a minimum and a maximum number of courses that can be assigned to it. Further, there are minimum and maximum limits also on the number of total credits per period.
Prerequisites: Based on their content, some courses have to be taught before other courses. This means that we are given a set of pairs of courses, such that the period assigned to the first course has to be strictly less than the period assigned to the second. Obviously, prerequisite relation is transitive and cannot contain cycles.
Curricula: First of all, in the formulation it is implicitly assumed that a student takes all courses without personal choices, whereas in practice a student can select among alternatives. Calling curriculum a set of courses representing a possible complete selection, we extend the problem by considering many curricula. Different curricula can share some of the courses.
Preferences: Professors can express preferences about their teaching periods. Specifically, a teacher can express preferences not for the year but for a specific term of the year. A preference of a course for a given term results in a penalty for any assignment of the course to a period which is not in that term. Preferences are not strict, and therefore they contribute to the objective function (soft constraints).

The problem consist in finding an assignment of courses to periods that satisfies the load limits and prerequisites. The objective function is a composition of preference violations and unbalanced load. In order to adhere more precisely to the real situation, the load component that we consider sums up all the deviations (positive and negative) from the average number of credits per period for each curriculum.

The Generalized Balanced Academic Curriculum Problem with Heterogeneous Classes

We propose and solve a further extension of the problem, obtained by relaxing one implicit assumption. In the original GBACP, courses are assigned to periods; for the GBACP-HC, instead, each course is assigned to a term and each course/curriculum pair is assigned to an academic year. As a result, the course is assigned to different periods in the various curricula, but it is taught once in the year in a single specific term.

It is also introduced a measure of how much heterogeneous are the students attending the same course. This is computed as the difference between the maximum and the minimum academic year in which the course is taught.

A solution of the GBACP-HC problem is an assignment of terms to courses and of academic years to course/curriculum pairs such that load limits and prerequisites are satisfied and the violations relating to load balancing, preferences, and heterogeneity are minimized. For the heterogeneity component, given that its importance can be subjective, we experiment with two different settings. In the first one, we set w_h = 1 so that its level of importance is the same as the balancing component (w_bl = 1) and five times less than the preference component (w_p = 5). In the second setting, instead, we considerably lower the impact of heterogeneity and we set w_h = 1/5.

Publications

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

L. Di Gaspero and A. Schaerf. Hybrid Local Search Techniques for the Generalized Balanced Academic Curriculum Problem. In Proceedings of HM2008, Fifth International Workshop on Hybrid Metaheuristics. Lecture Notes in Computer Science 5296, Springer 2008, pp. 146-157.
M. Chiarandini, L. Di Gaspero, S. Gualandi, and A. Schaerf. The Balanced Academic Curriculum Problem Revisited. Journal of Heuristics, 1-30-30. Springer Netherlands. doi: 10.1007/s10732-011-9158-2.

The Generalized Balanced Academic Curriculum Problem with Heterogeneous Classes

A. Schaerf, M. Chiarandini, L. Di Gaspero. Modelling and Solving the Generalised Balanced Academic Curriculum Problem with Heterogeneous Classes. In Barry McCollum, Edmund K. Burke and George White editors, Proceedings of the 8th International Conference on the Practice and Theory of Automated Timetabling (PATAT-2010), pages 547-550, 2010.
S. Ceschia, L. Di Gaspero, A. Schaerf. The Generalized Balanced Academic Curriculum Problem with Heterogeneous Classes. Submitted for publication.

Instances

The benchmark instances employed in our study consist of:

the three original CSPLib instances (translated in the GBAC format) called bcap8, bcap10, bcap12
ten new instances, called UD1-UD10, which are real cases from our university.
a toy example (for testing)

The following table summarizes the features of the instances and allow to download them. The file format is described in this page.

Instance	Courses	Periods (Years x Terms)	Curricula	Prerequisites	Preferences	Best solution of HM-2008	Best solution of Chiarandini et al.	Obtained by IP = Integer Programming LS = Local Search
bcap8	46	8 (4 x 2)	1	33	0	0	0	IP/LS
bacp10	42	10 (5 x 2)	1	33	0	0	0	IP/LS
bacp12	66	12 (6 x 2)	1	65	0	0	0	IP/LS
UD1	307	9 (3 x 3)	37	1383	90	397	258	LS
UD2	268	6 (2 x 3)	20	174	79	179	146	LS
UD3	236	9 (3 x 3)	31	1092	66	217	160	LS
UD4	139	6 (2 x 3)	16	188	40	396	396	IP/LS
UD5	282	6 (3 x 2)	31	397	54	278	211	LS
UD6	264	4 (2 x 2)	20	70	55	100	52	IP
UD7	302	9 (3 x 3)	37	1550	83		189	LS
UD8	208	6 (2 x 3)	19	149	60		42	LS
UD9	303	9 (3 x 3)	37	1541	85		202	LS
UD10	188	6 (2 x 3)	15	214	55		44	LS
toy	6	4 (2 x 2)	3	3	2		191	IP/LS

Solution validator

You can download the C++ source code of a solution validator.

AMPL files of the IP solver

You can download the source files of the IP solver.

The Generalized Balanced Academic Curriculum Problem with Heterogeneous Classes

For the GBACP-HC, we test our algorithm on the same ten benchmarks (UD1-UD10) already used for GBACP. The table reports our best results for the two different weight settings.

Instance	Courses	Periods (Years x Terms)	Curricula	Prerequisites	Preferences	Best solution of Ceschia et al. w_lb = 1 w_p = 5 w_h = 1	Best solution of Ceschia et al. w_lb = 1 w_p = 5 w_h = 1/5
UD1	307	9 (3 x 3)	37	1383	90	262	242.0
UD2	268	6 (2 x 3)	20	174	79	149	136.2
UD3	236	9 (3 x 3)	31	1092	66	167	162.2
UD4	139	6 (2 x 3)	16	188	40	325	324.2
UD5	282	6 (3 x 2)	31	397	54	101	60.6
UD6	264	4 (2 x 2)	20	70	55	52	40.8
UD7	302	9 (3 x 3)	37	1550	83	221	188.6
UD8	208	6 (2 x 3)	19	149	60	41	34.0
UD9	303	9 (3 x 3)	37	1541	85	216	182.8
UD10	188	6 (2 x 3)	15	214	55	44	39.4