Solution to the Balanced Academic Curriculum Problem Using Tabu Search
Lorna V. Rosas-Téllez, José Luis Martínez Flores, Vittorio Zanella-Palacios · 2012
The Balanced Academic Curriculum Problem (BACP) is a constraint satisfaction problem classified as (Non-deterministic Polynomial-time Hard) NP-Hard. This problem consists in the allocation of courses in the periods that are part of a curriculum such that the prerequisites are satisfied and the load of courses is balanced for the students. This paper presents the solution for a modified BACP where the academic loads and number of curses may be the same or different for each one of the periods and allows having some courses in a specific period. This problem is modeled as an integer programming problem and is proposed the use of Tabu search with short-term memory for its solution because it is not possible to find solutions for all the instances of this modified problem with an exact method.