You are here: Projects » GBAC

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.

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.

- 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, pp. 146-157, Springer, 2008.
- M. Chiarandini, L. Di Gaspero, S. Gualandi, and A. Schaerf. The Balanced Academic Curriculum Problem Revisited. Journal of Heuristics, 18(1), pp. 1381-1231, Springer, 2012.

- 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), pp. 547-550, 2010.
- S. Ceschia, L. Di Gaspero, A. Schaerf. The Generalized Balanced Academic Curriculum Problem with Heterogeneous Classes.
*Annals of Operations Research*, pages 1-17, 2013. Online first. doi:10.1007/s10479-013-1358-8

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 | 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 |

Idea & Design by idea arts