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:
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.
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.
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.
The benchmark instances employed in our study consist of:
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 |
|Best solution of |
Chiarandini et al.
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||55||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|
You can download the C++ source code of a solution validator.
You can download the source files of the IP solver.
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|