Modeling and Solving a Latin American University Course Timetabling Problem Instance

Abstract

Timetabling problem is a complex task that is performed by a number of institutions worldwide, which has been usually addressed as an optimization problem where every approach considers the particular constraints of each institution under consideration. In this paper, we describe, model, and propose a solution to the timetabling problem at the División Académica de Ciencias y Tecnologías de la Información of the Universidad Juárez Autónoma de Tabasco (UJAT), México. We modeled the specific constraints of this problem instance using the Object Constraint Language (OCL) of the Unified Modeling Language (UML), and we validated the model while using the state-of-the-art tool USE: UML-based Specification Environment. The solution strategy tackles the problem in two stages: (1) ACA: academic assignments, i.e., assign lectures to professors and (2) TTP: the timetabling process. We developed a Tabu Search customization named Tabu Search with Probabilistic Aspiration Criterion (TS-PAC) in order to solve the timetabling problem, and we developed a software prototype to test our proposal. Two feasible timetables for two different semesters were obtained according to the modeled constraints.

1. Introduction

Resource allocation is a widespread problem that is faced day by day, from organizing cashiers per shift in a supermarket to the tasking of air assets in an airport. In the academic context, a remarkable problem is the timetabling process, since it is a procedure that a large number of education institutions must perform at least once a year.

Timetabling is an NP-Complete problem [1], so there is no deterministic algorithm that finds an optimal solution in a reasonable time. However, it is possible to use alternative strategies in order to obtain acceptable solutions in a reasonable time. In general, these problems represent a challenge in Computer science, so there is a significant interest in finding efficient methods to solve these problems while using the least amount of resources, i.e., time and computational cost, while providing solutions that are close to the global optimum.

There are different variants of the timetabling problem in the literature, generally differing on the type of institution and its related constraints. Specifically, in this paper, we solve a representative case of the University Course Timetabling problem (UCTP) at the División Académica deCiencias y Tecnologías de la Información (DACyTI), one of 13 divisions of the Universidad Juárez Autónoma de Tabasco (UJAT), México. This timetabling problem instance can be seen as a representative of Latin American universities. However, our institution’s specific problem considers different constraints than other cases [2,3,4], so there is no similar solution in the literature when considering the particular constraints of the timetabling problem at the DACyTI.

2. Preliminaries

2.1. University Course Timetabling Problem

Timetabling is a common and recurring problem that has been extensively analyzed and represented, from the first models presented [5] to the more recently proposed ones [6]. Solution approaches include a full spectrum of strategies, such as mathematical optimization and heuristic algorithms. Either way, each strategy of a solution is raised from a different perspective, particular to the institution at issue, but all agree that the problem modeling is a critical part of creating any solution.

The general case of the timetabling problem, called school timetabling, can be defined as [7]:

• m classes $c_1,∆,c_m$.
• n teachers $t_1,∆,t_n$.
• p periods of time $1,∆,p$.
• a non-negative integer matrix $R_{m*n}$, called Requirements matrix, where $r_{ij}$ is the number of lectures given by teacher $t_j$ to class $c_i$.

The problem consists of assigning lectures to periods of time, such that no teacher or class is involved in more than one lecture at a time. The mathematical formulation is:

Find $x_{ijk}(i=1,∆,m;j=1,∆,n;k=1,∆,p)$ subject to:

$$\begin{array}{c}\hfill {\displaystyle \sum _{k=1}^p{x}_{ijk}=r_{ij}(i=1,∆,m;j=1,∆,n)}\end{array}$$

(1)

$$\begin{array}{c}\hfill {\displaystyle \sum _{j=1}^n{x}_{ijk}\le 1(i=1,∆,m;k=1,∆,p)}\end{array}$$

(2)

$$\begin{array}{c}\hfill {\displaystyle \sum _{i=1}^m{x}_{ijk}\le 1(j=1,∆,n;k=1,∆,p)}\end{array}$$

(3)

where $x_{ijk}=1$ if class $c_i$ and techer $t_j$ meet at period of time k, and $x_{ijk}=0$ otherwise.

These constraints compose the basic search problem, and any valid timetable represents the solution. However, this basic version of the problem does not consider courses sharing students or the teachers’ course preferences, just to mention some examples of constraints found in most universities.

The university course timetabling problem (UCTP) consists of scheduling a set of lectures for each course within a given number of classrooms and time periods [8] With the particularity that courses might have students in common, unlike school timetabling [9]. Finding a manual solution to the problem typically requires a considerable amount of time, in addition to the validation of an expert, since there may be specific constraints to be considered. These constraints can be of two types  [10]:

• Hard constraints: mandatory conditions, the violation of any of them implies a non-feasible timetable.
• Soft constraints: desirable conditions denoting user preferences; the violation of any of them affects the quality of a timetable.

The UCTP can be defined as [7]:

• q courses $K_1,∆,K_q$.
• Each K course consists of $k_i$ lectures.
• There are r curricula $S_1,\cdots ,S_r$, wich are groups of courses that have common students. Thus, courses in $S_l$ must be scheduled all at diferent times.
• A maximum number of lectures $l_k$ that can be scheduled at period k (that is, the number of rooms available at period k).
• A p number of periods of time $1,∆,P$.

In this case, we want to maximize the desirability of having a lecture of course $K_i$ at period of time k. The formal representation is:

Find $y_{ik}(i=1,∆,q;k=1,∆,p)$ subject to:

$$\begin{array}{c}\hfill {\displaystyle \sum _{k=1}^p{y}_{ik}=k_i(i=1,∆,q)}\end{array}$$

(4)

$$\begin{array}{c}\hfill {\displaystyle \sum _{i=1}^q{y}_{ik}\le l_k(k=1,∆,p)}\end{array}$$

(5)

$$\begin{array}{c}\hfill {\displaystyle \sum _{i\in S_i}{y}_{ik}\le 1(l=1,∆,r;k=1,∆,p)}\end{array}$$

(6)

$$\begin{array}{c}\hfill y_{ik}\in \left\{0,1\right\}(i=1,∆,q;k=1,∆,p)\end{array}$$

(7)

where $y_{ik}=1$ if a lecture of course $K_i$ is scheduled at period k, and $y_{ik}=0$ otherwise.

Objective function (8) is included in the problem definition in order to denote $d_{ik}$, which is the desirability of assign a lecture of course $K_i$ at period k.

$$\begin{array}{c}\hfill \mathrm{Max}.\sum _{i=1}^q\sum _{k=1}^p{d}_{ik}{y}_{ik}\end{array}$$

(8)

This model can be considered to be a general formulation for the university course timetabling problem. Our institution has many other particular policies that must be considered when generating the timetable. In the following section, we formulate these specific constraints.

Additionally, the typical approach for UCTP includes two stages: (1) to create a feasible solution and (2) to minimize the number of soft constraints violations in the feasible solution [11]. In our specific case, we will extend this approach by using these two stages twice in our proposal.

2.2. Object Constraint Language (OCL)

Modeling is a key part of software development. Models are essentially diagrams that communicate the desired structure and behavior of a system. Through models, we can understand the system we are developing, visualizing, and controlling the system’s architecture [12].

Nowadays, the Unified Modeling Language (UML) is the de facto software systems modeling language. It consists of an integrated set of diagrams for the specifcation, visualization, construction, and software systems documentation. UML represents a collection of best software engineering practices that were used in the modeling of large and complex systems. It uses mostly graphical notations in the form of diagrams to express different views of the system, for example [13]:

• Requirements: use case diagrams.
• System structure: class diagrams, component diagrams.
• System behavior: activity diagrams, sequence diagrams, state diagrams.

However, UML itself does not have ways for specifying detailed constraints for classes nor data types. To increase the UML expressiveness, the Object Constraint Language (OCL) emerges as a formal notation allowing for the description of additional restrictions on the elements in UML models and, thus, expressing all of the relevant aspects of a specification [14].

OCL is a language with no collateral effects that do not alter the model objects, but completes the different artifacts of the UML notation with formally expressed requirements. There are other languages that increase the expressivity of the UML, but OCL is the only one that is standardized [15].

OCL has been used to model problems in different fields. For example, to validate the safety properties of the San Francisco Metro system [16], to specify the smart card API Java Card [17], to state financial messaging business rules [18], or even to model guidelines for correct nutrition through healthy menus [19]. There are several tools for the validation and verification of OCL models, highlighting USE: UML-based Specification Environment [20], used for systems specification using UML models along with integrity constraints in OCL. It is one of the more robust free software tools to support OCL.

2.3. Tabu Search with Probabilistic Aspiration Criterion (TS-PAC)

Tabu Search is a versatile and efficient metaheuristic that can operate both deterministically and stochastically, which has been successfully used to solve different optimization problems [21]. It is conceptually more straightforward than other metaheuristics, and it can reach better results in less time than other algorithms [22]. Its versatility makes it a widely used technique to solve a wide variety of different types of problems, such as the transfer of patients between care units [23], the planning of electricity distribution systems [24], or even in the creation of fingerings for polyphonic piano music [25].

The main characteristic of Tabu Search is a short-term memory, called tabu list, which contains the list of moves recently applied. With this list, the algorithm disallows moves that can reverse the effect of recent moves, marking them with a forbidden status for a period of time. However, from time to time, a tabu move may reach a better solution. Thus, aspiration criteria are implemented in order to revoke the tabu status of a particular move [26]. Many approaches have been proposed, but the most widely used aspiration criterion consists in allowing a tabu move if it leads to a solution with a better objective value than the current best-known solution.

Tabu search moves across the search space using the concept of neighborhood, formally defined as [27]:   

$N\left(S\right)=$ {solutions obtained by applying a single local transformation to S}

where S denotes the current solution. In general, for any specific solution, there are many more possible neighborhood structures than search space definitions. There may be simple neighborhood structures, such as add or drop elements of the solution, to more complex features, such as swapping two elements of the solution based on a guided criterion that allows for the algorithm to explore different search space regions. Therefore, it is an essential component of the Tabu Search.

It has been demonstrated in the literature and real-life projects that Tabu Search finds good approximations to the optimal solution for significant combinatorial problems [28]. Specifically for the timetabling problem, Tabu Search has been used in order to generate timetables in several real-world scenarios  [29,30,31,32,33].

In this work, we employed the Tabu Search with Probabilistic Aspiration Criterion (TS-PAC) [34], used to solve the problem that is described in the First International Timetabling Competition [35]. When solving the 20 instances of this problem, the obtained results showed that the TS-PAC yields better solutions than the Tabu search with a common aspiration criterion.

The aspiration criterion, conveniently called "strategic oblivion", defines the way in which the tabu status of a particular movement is replaced or eliminated. The assumption is that if all the movements of the tabu list are forbidden, then cyclic solutions are avoided, but we can lose movements that may reach better solutions. Therefore, in some situations, it is useful to use a movement that is classified as tabu [21].

It is possible to design different aspiration criteria. Our proposal, The Probabilistic Aspiration Criterion, allows for applying a tabu movement if it improves the current solution considering the probability according to Equation (9).

$$\begin{array}{c}p=\left\{\begin{array}{cc}{\displaystyle \frac{\mathcal{GOAL}-f\left(s_i\right)}{\mathcal{GOAL}}}& \mathrm{if}\mathcal{GOAL}>0\hfill \\ \\ {\displaystyle \frac{f\left(s_i\right)}{\mathcal{INIT}}}& \mathrm{when}\mathcal{GOAL}=0\mathrm{and}\mathcal{INIT}>0\hfill \end{array}\right.\end{array}$$

(9)

where:

$\mathcal{GOAL}$ is the best-expected value in the objective function.

$f\left(s_i\right)$ equals the value of the objective function in the i-th iteration.

$\mathcal{INIT}$ is the initial value of the objective function, i.e., the value that the algorithm starts with.

Two probability criteria are used, because the problem can be modeled as maximization or minimization. In the first case, when modeling a problem as a maximization function, it is expected to reach in the objective function a value greater than 0. On the other hand, when it comes to minimizing, the expected value to be obtained in the objective function is 0 (that is, all of the constraints satisfied) and, therefore, the initial value of the objective function must be checked that is greater than 0 (otherwise we would already have the best solution).

The motivation of the TS-PAC arises from the concepts of diversification and intensification in the search process. We aim at choosing a tabu move with a higher probability when the algorithm is far from the feasible region, diversifying the search. This probability decreases when approaching the expected solution, intensifying the search near the optimal solution. Algorithm  describes the general process of the TS-PAC.

Algorithm 1: Tabu Search with Probabilistic Aspiration Criterion.

For example, the aspiration criterion in a maximization problem is with the probability $p=\frac{\mathcal{GOAL}-f\left(s_i\right)}{\mathcal{GOAL}}$. In this case, the user must define, a priori, the best possible value to reach by the algorithm. This value represents the best acceptable solution, denoted by $\mathcal{GOAL}$. We need to check whether $\mathcal{GOAL}>0$, otherwise it would be a minimization problem. When the search process is in its early stages, the probability of using a tabu move is higher, as there will be a significant difference in $\mathcal{GOAL}-f\left(s_i\right)$. Eventually, $f\left(s_i\right)$ will get close to $\mathcal{GOAL}$ and the probability of using a tabu move, in this case, will get lower.

The other case consists of a minimization problem, where the probability for the aspiration criterion is $p=\frac{f\left(s_i\right)}{\mathcal{INIT}}$ as long as $\mathcal{INIT}>0$, otherwise we would have reached the optimal solution ($\mathcal{INIT}=\mathcal{GOAL}=0$). When $\mathcal{INIT}>0$ the search starts and at each iteration i the probability to use a tabu move is high. However, as $f\left(s_i\right)$ gets near to 0, the probability of using a tabu move gets reduced.

We selected the Tabu Search algorithm, because it features characteristics that we consider advantages over other metaheuristics. Fist, it has fewer parameters than most metaheuristics. Additionally, it is among the fastest optimization algorithms. There are many open-source implementations in frameworks providing a robust generic functionality of the base algorithm. Finally, what we value the most is the possibility to program our own method of exploring the solution space via custom neighborhoods, allowing for more control of the search process.

3. Modeling the Timetabling Problem

Each semester, the administrative staff at the UJAT-DACyTI builds a timetable that satisfies as many constraints as possible. The timetabling process is currently done manually during a period in the range of weeks with a considerable working hours cost. Specifically at our institution, the timetabling process is carried out in four stages:

• The number of students who potentially want to take any course is determined through an online survey. This is known as the potential demand for each course.
• Subsequently, the required courses are offered.
• Next, each professor is asked for the list of courses they choose to teach in the following semester.
• Using these data, the ACademic Assignments [ACA] (allocation of professors to courses) are made considering each professor’s particular constraints, such as research projects, popularization of science, and extension activities.
• Finally, the TimeTabling Process [TTP] is performed.

Each stage involves a different amount of time and resources. In this research, we have modeled the last two stages of the process, that is, the constraints that are related to the timetabling problem. To describe these constraints, we designed OCL invariants from the domain model shown in Figure 1. The domain model includes the most representative elements of the timetabling problem, as well as specific attributes of the problem at UJAT:

• Professor: gives courses to groups of students. This entity has a predefined minimum and a maximum number of hours to teach during the semester, depending on her/his classification (visitor, emeritus, eventual, half-time, or full-time) and category (associate or titular).
• Course: includes a number of hours in a week and a level (Undergraduate or Postgraduate).
• Lecture: class given in a specific classroom during a certain period of time.
• Group: number of students who receive classes in common.
• Classroom: physical space with a specific capacity.

The Domain model of Figure 1 defines the following hard constraints that any valid timetable must satisfy:

• A single teacher teaches a specific course.
• A teacher must only teach one lecture at a time.
• A lecture belongs to a particular course.
• Lectures are taught in only one classroom at a time.
• A lecture is given to a particular group.

These constraints are the typical hard constraints that are considered in the literature. However, our institution has more constraints and those cannot be represented in this type of model. Accordingly, the specific constraints of the timetabling problem at the DACyTI are detailed in the form of OCL invariants in the next section.

3.1. ACA Model

It is common to found detailed examples on how to create timetables [36,37,38,39,40]. However, at our institution there is a stage, called Academic assignments (ACA), which is usually not considered in the literature. This stage is a particularity of some educational institutions, in which the availability of teachers generally varies each semester, and there is no concept of professorship as in other institutions.

In this particular case, the Staff Regulation of the UJAT [41] establishes the relations between the university and academic personnel (categories, classifications, functions, income, and promotions), based on the terms that were established by Section VIII of Article 3 of the Mexican Constitution [42] and by the Organic Law of the UJAT [43].

The Staff Regulation establishes the labor restrictions that are formally described below. A valid ACA must meet the following hard constraints, subject to the model that is shown in Figure 1:

ACA-HC1. The courses taught at the DACyTI can be at the undergraduate or postgraduate level.

context Course

  inv: level=’Undergraduate’ or level=’Postgraduate’

ACA-HC2. Professors may have one of the following classifications: eventual, half-time, and full time, and, in an extraordinary situation, visitor and emeritus.

context Professor

    inv: classification=’Eventual’ or

       classification=’Half-Time’ or

       classification=’Full-Time’ or

       classification=’Visitor’ or

       classification =’Emeritus’

ACA-HC3. Professors may have one associate or titular category, each with levels A, B, or C.

context Professor

  inv: category=’Associate’ or category=’Titular’

  inv: level=’A’ or level=’B’ or level=’C’

ACA-HC4. The following attribute is defined for the correct validation of the total hours taught by a professor:

context Professor

  def: numHours:Integer = academicLoad.numHours->sum()

ACA-HC5. Constraints that are presented in the Staff Regulation regarding the minimum number of class hours for each professor are not absolute, so a convenient method to assign this value is:

context Professor::setMinHours(hours:Integer)

    inv: hours>0 and minHours<=maxHours

    body: minHours=hours

ACA-HC6. Eventual professors can teach at most 19 hours of class.

context Professor

  inv: classification=’Eventual’ implies maxHours=19

ACA-HC7. Associate Full-time professors who teach undergrad courses exclusively can teach no more than 25 hours of class.

context Professor

  inv: classification=’Full-time’ and category=’Associate’

    and academicLoad->forAll(c:Course | c.level=’Undergraduate’)

               implies maxHours=25

ACA-HC8. Associate full-time professors who teach at least one postgraduate course can teach no more than 20 hours of class.

context Professor

  inv: classification=’Full-time’ and category=’Associate’

    and academicLoad->exists(c:Course | c.level=’Postgraduate’)

               implies maxHours=20

ACA-HC9. Titular full-time professors who teach undergrad courses exclusively can teach no more than 20 hours of class.

context Professor

inv: classification=’Full-time’ and category=’Titular’

    and academicLoad->forAll(c:Course | c.level=’Undergraduate’)

             implies maxHours=20

ACA-HC10. Titular full-time professors who teach at least one postgraduate course can teach no more than 10 hours of class.

context Professor

  inv: classification=’Full-time’ and category=’Titular’

    and academicLoad->exists(c:Course | c.level=’Postgraduate’)

               implies maxHours=10

ACA-HC11. Associate half-time professors teaching exclusively undergrad courses can teach no more than 15 hours of class.

context Professor

  inv: classification=’Half-time’ and category=’Associate’

    and academicLoad->forAll(c:Course | c.level=’Undergraduate’)

               implies maxHours=15

ACA-HC12. Associate half-time professors who teach at least one postgraduate course can teach no more than 10 h of class.

context Professor

  inv: classification=’Half-time’ and category=’Associate’

    and academicLoad->exists(c:Course | c.level=’Postgraduate’)

               implies maxHours=10

ACA-HC13. Titular half-time professors who teach undergrad courses exclusively can teach no more than 10 h of class.

context Professor

  inv: classification=’Half-time’ and category=’Titular’

    and academicLoad->forAll(c:Course | c.level=’Undergraduate’)

               implies maxHours=10

ACA-HC14. Titular half-time professors who teach at least one postgraduate course can teach no more than five hours of class.

context Professor

  inv: classification=’Half-time’ and category=’Titular’

    and academicLoad->exists(c:Course | c.level=’Postgraduate’)

               implies maxHours=5

ACA-HC15. The number of lecture hours by each professor must not exceed the maximum hours established.

context Professor

  inv: numHours<=maxHours

ACA-HC16. The number of lecture hours by each professor must be greater than or equal to the minimum hours assigned.

context Professor

  inv: numHours>=minHours

Regarding the desirable conditions (soft constraints) for a valid ACA, we have:

ACA-SC1. Professors choose the courses that they would like to teach in the next semester. It would be desirable to satisfy the course preferences of each professor.

context Professor

  inv: academicLoad->intersection(favorites)->notEmpty()

3.2. TTP Model

Once the ACA is defined, the timetable is created. We divide each course into one-hour length lectures and then assign each lecture to a classroom during a period of time, satisfying the following hard constraints:

TTP-HC1. The time period for a lecture corresponds to 1 hour. The number of hours of each course must be assigned to the same number of time periods.

context Course

  inv: numHours=lecture->size()

TTP-HC2. The period of time labeled as 0 corresponds to the start period of classes on Monday, and the period labeled as TOTAL_PERIODS represents the final time of the last session on Friday. Both the first and last hours are known as overflow areas, and this type of allocation is called a compact schedule [44].

context Lecture

  inv: start>=0 and start<TOTAL_PERIODS

TTP-HC3. TTP-HC3 When considering blocks of time of 1 hour, the initial time of a lecture must be less than the final time by one hour.

context Lecture

  inv: end=start+1

TTP-HC4. The capacity of the classroom must fit the number of students in the group that takes a lecture.

context Lecture

  inv: classroom.capacity >= academicLoad.group.numStudents

TTP-HC5. TTP-HC5 A group must not take more than one lecture at a time (for ease of definition, the invariant is associated with courses, as each course is tied to one and only one group).

context Course

  inv: lecture->forAll(

                l1:Lecture,l2:Lecture | l1<>l2 implies l1.start<>l2.start)

TTP-HC6. A professor must not teach more than one lecture at a time.

context Professor

  inv: lecture->forAll(

                l1:Lecture,l2:Lecture | l1<>l2 implies l1.start<>l2.start)

Regarding the soft constraints for this stage, we have considered:

TTP-SC1. In the DACyTI, the concept of morning or evening shift does not properly exist due to the flexible educational model [45]. In that sense, the professor’ shifts were modeled as preferences about the period of time they wished to teach their courses.

context Professor

  inv: preferredHours->includesAll( Lecture.start->asSet() )

TTP-SC2. In our model, time periods are considered to be blocks of one-hour length, so lectures of the same course scheduled during the same day must be in contiguous hours. The constant PERIODS_A_DAY, equivalent to TOTAL_PERIODS/five days a week, is used in this invariant.

context Lecture

  inv: let day= start div PERIODS_A_DAY in

         let lecturesPerDay= Lecture.allInstances()->

               select(academicLoad=self.academicLoad and

                 (start div PERIODS_A_DAY) = day)->

                    asSet()->sortedBy(start) in

                      lecturesPerDay->size() > 1 implies

                        lecturesPerDay->iterate(s; i:Integer=0 |

                          if i<lecturesPerDay->size()-1 and s.end=

                            lecturesPerDay->at(i+1).start

                          then i+1

                          else i

                          endif) = lecturesPerDay->size()

The complete specification along the model validation in the USE environment are publicly available at the Open Science Framework: https://osf.io/zuh3s/.

4. Solution Proposal

According to the previous section’s constraints, the solution to the timetabling problem at the DACyTI was divided into the ACA phase and the TTP phase. For both stages, the Tabu Search with Probabilistic Aspiration Criterion (TS-PAC) algorithm was implemented in order to find a feasible solution, i.e., feasible academic assignments and a feasible timetable, respectively.

4.1. ACA Solution

The Academic assignments (ACA) are generated in three stages: (1) the creation of an initial solution, (2) satisfaction of the hard constraints, and (3) maximizing the course preferences for each professor.

Before starting the optimization process, data preprocessing is performed in order to obtain useful information to improve the performance of the Tabu Search algorithm, and the data structures to facilitate satisfying the hard constraints are created:

• $n_p=$ number of professors.
• $n_c=$ number of courses.
• $C=\{c_1,\cdots ,c_{n_c}\}$ corresponds to the set of instances of entity Course.
• $P=\{p_1,\cdots ,p_{n_p}\}$ corresponds to the set of instances of entity Professor.
• $F_{n_p\times n_c}$ is the preference matrix where true represents professor p wants to teach the course c and false otherwise (Figure 2).
• ${\mathit{ACA}}_{n_c}$ is a vector that corresponds to the solution (the academic assignments) where each cell c contains the assigned professor (Figure 3).

4.1.1. Creating an Initial Solution

A greedy algorithm makes a fair distribution of all the courses among the available professors, assigning to each of them at least one course within their preferences. In this way, the ACA starts balanced and attempts to satisfy at least one course for each professor.

In this stage, the maximum and the minimum number of hours per teacher is not validated; we only get ensured that each course has an assigned professor.

4.1.2. Satisfying Hard Constraints

This stage consists of satisfying the hard constraints that may exist in the solution generated in the previous stage. The objective function to optimize during this stage is:

$$\mathrm{Min}.z=ac{a}_{h{c}_1}+ac{a}_{h{c}_2}$$

(10)

where:

$ac{a}_{h{c}_1}$ is the sum of unsatisfied constraints ACA-HC15.

$ac{a}_{h{c}_2}$ is the sum of unsatisfied constraints ACA-HC16.

In order to satisfy the hard constraints, the TS-PAC algorithm uses a neighborhood that consists of random swaps between two professors; those with a higher academic load than the allowed against those with a less academic load than the corresponding one:

$$\begin{array}{ccc}& {\mathit{ACA}-\mathit{Neighborhood}}_{h{c}_1}=\langle p,p^{\prime }\rangle & \\ & p,p^{\prime }\in P|\mathit{p}.\mathit{numHours}>\mathit{p}.\mathit{maxHours},{\mathit{p}}^{\prime }.\mathit{numHours}<{\mathit{p}}^{\prime }.\mathit{minHours},p\ne p^{\prime }\end{array}$$

An additional neighborhood ${\mathit{ACA}-\mathit{Neighborhood}}_{h{c}_2}=\langle p^x,p^{†}\rangle$, helps the TS-PAC to escape from local optimum, adding some perturbation to the current solution. It consists of random swaps of courses between a professor causing constraint ($p^x$) and a professor with a valid academic load ($p^{†}$).

The TS-PAC selects as the best element of neighborhood ${\mathit{ACA}-\mathit{Neighborhood}}_{h{c}_1}$ the tuple that minimizes the highest number of hard constraints, when considering tabu elements and the aspiration criteria defined in Equation (9). The objective function of Equation (10) is minimization, so $\mathcal{GOAL}=0$. If the search gets stuck in a local minimum, then an element from ${\mathit{ACA}-\mathit{Neighborhood}}_{h{c}_2}$ is randomly selected to add perturbation to the current solution.

This stage ends when all hard constraints are satisfied, although this may not always be possible, as we will show in Section 5.

4.1.3. Soft Constraints: Maximizing Professors’ Course Preferences

The objective function of this stage is to maximize the preferences in the courses that are assigned to professors, without violating any of the hard constraints satisfied in the previous stage:

$$\begin{array}{c}\hfill \mathrm{Max}.z=ac{a}_{sc}\\ \hfill \mathrm{subject}\mathrm{to}:\\ \hfill ac{a}_{h{c}_1}=0\\ \hfill ac{a}_{h{c}_2}=0\end{array}$$

(11)

where:

$ac{a}_{sc}$ is the sum of the professors’ preferences, as defined in ACA-SC1.

$ac{a}_{h{c}_1}$ and $ac{a}_{h{c}_2}$ correspond to the hard constraints described in the objective function of Equation (10).

The neighborhood designed for this stage consists of swaps of professors between a couple of courses, selecting teachers who do not have any preferred course in their academic load, but do have some favorite course:

$$\begin{array}{c}\begin{array}{c}{\mathit{ACA}-\mathit{Neighborhood}}_{s{c}_1}=\langle c,c^{\prime }\rangle \end{array}\\ \begin{array}{cc}c,c^{\prime }\in C|\hfill & |\mathit{c}.\mathit{professor}.\mathit{favorites}|>0,\hfill \\ & \mathit{c}.\mathit{professor}.\mathit{favorites}\cap \mathit{c}.\mathit{professor}.\mathit{academicLoad}=\varphi ,\hfill \\ & |{\mathit{c}}^{\prime }.\mathit{professor}.\mathit{favorites}|>0,\hfill \\ & {\mathit{c}}^{\prime }.\mathit{professor}.\mathit{favorites}\cap {\mathit{c}}^{\prime }.\mathit{professor}.\mathit{academicLoad}=\varphi ,\hfill \\ & \mathit{c}.\mathit{professor}\ne {\mathit{c}}^{\prime }.\mathit{professor}\hfill \end{array}\end{array}$$

An additional neighborhood ${\mathit{ACA}-\mathit{Neighborhood}}_{s{c}_2}=\langle p^x,p^{†}\rangle$ adds some perturbation to the current solution, randomly swapping courses between two professors ($p^x$ and $p^{†}$).

The TS-PAC selects as the best element of the neighborhoods the tuple that maximizes the professor’s preferences, when considering tabu elements and the aspiration criterion defined in Equation (9). The objective function of Equation (11) is maximization: all of the professors with a favorite course in his/her Academic load, so we set $\mathcal{GOAL}$ to $n_p$.

4.2. TTP Solution

During this phase, the same three-stage strategy is used: (1) the creation of an initial solution, (2) satisfaction of the hard constraints, and (3) maximizing professors’ shift preferences along with the number of lectures taught on the same day in contiguous hours.

First, data preprocessing is performed in order to create the necessary data structures used during the search process:

• $n_r=$ number of classrooms.
• $n_g=$ number of groups.
• $n_l=$ number of lectures.
• $R=\{r_1,\cdots ,r_{n_r}\}$ corresponds to the set of instances of entity Classroom.
• $G=\{g_1,\cdots ,g_{n_g}\}$ corresponds to the set of instances of entity Group.
• $L=\{l_1,\cdots ,l_{n_l}\}$ corresponds to the set of instances of entity Lecture.
• $H_{n_p\times \mathtt{TOTAL}\_\mathtt{PERIODS}}$ is a matrix where true represents that professor p desires to teach during that period of time, and false otherwise (Figure 4).
• ${\mathit{TTP}}_{n_r\times \mathtt{TOTAL}\_\mathtt{PERIODS}}$ is a matrix corresponding to the solution (the timetable), where each cell corresponds to a lecture or null otherwise. This data structure has the advantage of automatically satisfying constraints of type TTP-HC2 and TTP-HC3, while facilitating the evaluation of the remaining constraints (Figure 5).

4.2.1. Creating an Initial Solution

A greedy algorithm generates the initial solution, fully solving constraints of type TTP-HC1 assigning the most professors in their shift of preference (constraint TTP-SC1) and avoiding lectures in non-contiguous time periods as much as possible during the same day (constraint TTP-SC2).

4.2.2. Satisfying Hard Constraints

During this stage, the remaining hard constraints in the initial solution are satisfied without considering the soft constraints. The objective function to optimize is:

$$\begin{array}{c}\hfill \mathrm{Min}.z=tt{p}_{h{c}_4}+w·(tt{p}_{h{c}_5}+tt{p}_{h{c}_6})\end{array}$$

(12)

where:

$tt{p}_{h{c}_4}$ is the sum of unsatisfied constraints TTP-HC4.

$tt{p}_{h{c}_5}$ is the sum of unsatisfied constraints TTP-HC5.

$tt{p}_{h{c}_6}$ is the sum of unsatisfied constraints TTP-HC6.

w is a positive constant that is sufficiently large to give more weight to constraints of type TTP-HC5 and TTP-HC6.

In Equation (12) we want to minimize the total number of hard constraints; however, priority is given to constraints of type TTP-HC5 and TTP-HC6 (a group and a professor must not take more than one lecture at a time), since most of the classrooms are big enough to fit groups (TTP-HC4).

Three neighborhoods are used at this stage, corresponding to random swaps of lectures. The following neighborhood scheme aims to minimize constraints of type TTP-HC4 (classroom capacity fits the number of students of a group):

$$\begin{array}{c}\begin{array}{c}{\mathit{TTP}-\mathit{Neighborhood}}_{h{c}_1}=\langle l,l^{\prime }\rangle \end{array}\\ \begin{array}{cc}l,l^{\prime }\in L|\hfill & \mathit{l}.\mathit{classroom}.\mathit{capacity}<\mathit{l}.\mathit{course}.\mathit{group}.\mathit{numStudents},\hfill \\ & {\mathit{l}}^{\prime }.\mathit{classroom}.\mathit{capacity}>{\mathit{l}}^{\prime }.\mathit{course}.\mathit{group}.\mathit{numStudents}\hfill \end{array}\end{array}$$

Another neighborhood scheme that aims to minimize the constraints of type TTP-HC5 is (a group must not take more than one lecture at a time):

$$\begin{array}{c}\begin{array}{c}{\mathit{TTP}-\mathit{Neighborhood}}_{h{c}_2}=\langle l,l^{\prime }\rangle \end{array}\\ \begin{array}{cc}l,l^{\prime }\in L|\hfill & \mathit{l}.\mathit{course}={\mathit{l}}^{\prime }.\mathit{course},\mathit{l}.\mathit{start}={\mathit{l}}^{\prime }.\mathit{start},l\ne l^{\prime }\hfill \end{array}\end{array}$$

The last neighborhood scheme helps to minimize constraints of type TTP-HC6 (a professor must not teach more than one lecture at a time):

$$\begin{array}{c}\begin{array}{c}{\mathit{TTP}-\mathit{Neighborhood}}_{h{c}_3}=\langle l,l^r\rangle \end{array}\\ \begin{array}{cc}l,l^{\prime }\in L|\hfill & \mathit{l}.\mathit{professor}={\mathit{l}}^{\prime }.\mathit{professor},\mathit{l}.\mathit{start}={\mathit{l}}^{\prime }.\mathit{start},l\ne l^{\prime }\hfill \end{array}\end{array}$$

An additional neighborhood ${\mathit{TTP}-\mathit{Neighborhood}}_{h{c}_4}=\langle l^x,l^{†}\rangle$, helps the TS-PAC to escape from local optimum adding some perturbation to the current solution. It consists of random swaps of time periods between a lecture causing constraint ($l^x$) and a lecture correctly scheduled ($l^{†}$).

The algorithm selects the best element among the four neighborhoods that minimize the highest number of hard constraints, when considering tabu elements and the aspiration criterion. The objective function of Equation (12) for this stage is minimization ($\mathcal{GOAL}=0$), so the probability p of selecting a tabu movement depends on the value of $\mathcal{INIT}$ and $f\left(s_i\right)$ according to Equation (9).

For example, consider the following scenario where four lectures are scheduled:

Lecture A:	Lecture B:	Lecture C:	Lecture D:
professor $\Rightarrow p_1$	professor $\Rightarrow p_1$	professor $\Rightarrow p_{27}$	professor $\Rightarrow p_{54}$
course $\Rightarrow c_{35}$	course $\Rightarrow c_{87}$	course $\Rightarrow c_1$	course $\Rightarrow c_1$
start $\Rightarrow 1$	start $\Rightarrow 1$	start $\Rightarrow 19$	start $\Rightarrow 19$
end $\Rightarrow 2$	end $\Rightarrow 2$	end $\Rightarrow 20$	end $\Rightarrow 20$

In Figure 6, we can notice how Lecture A and Lecture B violate constraint TTP-HC6, since both lectures have Professor $p_1$ in common. Similarly, Lectures C and D violate constraint TTP-HC5, since both lectures belong to the same Course $c_1$ and, hence, belong to the same Group.

4.2.3. Soft Constraints: Maximizing Professors’ Shift Preferences and Contiguous Lectures

During this stage, we seek to maximize the shift preferences for each professor and, at the same time, maximize the number of lectures that are taught on the same day to be scheduled in contiguous hours. The objective function is:

$$\begin{array}{c}\hfill \mathrm{Max}.z=tt{p}_{s{c}_1}+(w·tt{p}_{s{c}_2})\\ \hfill \mathrm{subject}\mathrm{to}:\\ \hfill tt{p}_{h{c}_4}=0\\ \hfill tt{p}_{h{c}_5}=0\\ \hfill tt{p}_{h{c}_6}=0\end{array}$$

(13)

where:

$tt{p}_{s{c}_1}$ is the sum of professors preferences, as defined in TTP-SC1.

$tt{p}_{s{c}_2}$ is the sum of courses with contiguous sessions in a day defined in TTP-SC2.

w is a positive constant that is sufficiently large to give more weight to constraints of type TTP-SC2.

$tt{p}_{h{c}_4}$, $tt{p}_{h{c}_5}$ and $tt{p}_{h{c}_6}$ correspond to the hard constraints described in the objective function of Equation (12).

In Equation (13), the goal is to maximize the professors’ shift preferences (constraint TTP-SC1) while reducing the number of lectures that are scheduled in non-contiguous hours of the same day (constraint TTP-SC2). It is desired to satisfy this last constraint to a larger extend; for this reason, we assigned a higher priority while using a weight constant.

For this stage, a couple of neighborhoods were designed to reduce the number of soft constraints. The first neighborhood consists of swaps of lectures, where the assigned professor has no hour preference satisfied (TTP-SC1):

$$\begin{array}{c}\begin{array}{c}{\mathit{TTP}-\mathit{Neighborhood}}_{s{c}_1}=\langle l,l^{\prime }\rangle \end{array}\\ \begin{array}{cc}l,l^{\prime }\in L|\hfill & \mathit{l}.\mathit{start}\notin \mathit{l}.\mathit{professor}.\mathit{preferredHours},\hfill \\ & {\mathit{l}}^{\prime }.\mathit{start}\notin {\mathit{l}}^{\prime }.\mathit{profesor}.\mathit{preferredHours},\hfill \\ & l\ne l^{\prime }\hfill \end{array}\end{array}$$

The second neighborhood consists of swaps of lectures that are scheduled on the same day, but in non-contiguous hours (TTP-SC2):

$$\begin{array}{c}\begin{array}{c}{\mathit{TTP}-\mathit{Neighborhood}}_{s{c}_2}=\langle l,l^{\prime }\rangle \end{array}\\ \begin{array}{cc}l,l^{\prime }\in L|\hfill & \mathit{l}.\mathit{course}={\mathit{l}}^{\prime }.\mathit{course},\hfill \\ & \mathit{l}.\mathit{start}÷\mathtt{PERIODS}\_\mathtt{A}\_\mathtt{DAY}={\mathit{l}}^{\prime }.\mathit{start}÷\mathtt{PERIODS}\_\mathtt{A}\_\mathtt{DAY},\hfill \\ & |\mathit{l}.\mathit{start}-{\mathit{l}}^{\prime }.\mathit{end}|>0\hfill \end{array}\end{array}$$

An additional neighborhood ${\mathit{TTP}-\mathit{Neighborhood}}_{s{c}_3}=\langle l^x,l^{†}\rangle$ adds some perturbation to the current solution, randomly swapping periods between two lectures ($p^x$ and $p^{†}$).

The TS-PAC selects the best element among the three neighborhoods that maximizes the professor’s preferences and contiguous lectures of the same course, when considering the tabu elements and the aspiration criterion. The objective function of Equation (13) for this stage is maximization, so the probability p of selecting a tabu movement depends on the value of $\mathcal{GOAL}$ and $f\left(s_i\right)$ according to Equation (9). In most of the experiments, we set $\mathcal{GOAL}=n_l+n_c$.

For example, consider the following scenario where three lectures are scheduled:

Lecture X:	Lecture Y:	Lecture Z:	Professor 77:
professor $\Rightarrow p_{51}$	professor $\Rightarrow p_{51}$	professor $\Rightarrow p_{77}$	category ⇒ Associate
course $\Rightarrow c_{23}$	course $\Rightarrow c_{23}$	course $\Rightarrow c_{96}$	classification ⇒ Full-Time
start $\Rightarrow 0$	start $\Rightarrow 2$	start ⇒ TOTAL_PERIODS-1	preferredHours ⇒
end $\Rightarrow 1$	end $\Rightarrow 3$	end ⇒ TOTAL_PERIODS	$\{0,1,2,3,4,\cdots ,33\}$

In Figure 7, we can notice how Lecture X and Lecture Y violate constraint TTP-SC2, since the two lectures are scheduled in non-contiguous hours on the same day. Alongside, Lecture Z is violating constraint TTP-SC1, because it has been scheduled in a period of time not desired by the professor.

5. Tests and Results

We developed a software prototype to generate the timetable for the DACyTI, with one module for each of the two phases. We use the Open Java Development Kit, OpenJDK 8 [46] as a development platform, MariaDB [47] as the database management system, and our Tabu Search with Probabilistic Aspiration Criterion algorithm implementation over the OpenTS framework [48]. We made extensive use of the object-oriented programming (OOP) paradigm, organizing the prototype around objects, benefiting code reusability, scalability, and efficiency.

5.1. Software Prototype

Figure 8 shows the high-level design of our proposal, corresponding to the component diagram. It shows the static view of our prototype. The typical software layers (data, business, and presentation) are naturally separated into components with independent functionality.

Figure 9 shows the process diagram, where the components of the Bussiness logic are the central elements. This diagram shows the dynamic view of the prototype. The overall process starts when the event Request Timetable is fired. The ACA module inputs are the list of available professors and the list of courses. First, it minimizes the hard constraints and then maximizes the soft constraints. The resulting Academic assignments (ACA) are the inputs for the TTP module, along with the list of classrooms and periods of time. This module starts minimizing the hard constraints to continue with maximizing the soft constraints. The final output is the desired timetable.

Figure 10 and Figure 11 show the start window, used to configure the parameters of the algorithm: random seed, stop criterion (number of iterations, expected value in the objective function [$\mathcal{GOAL}$], total seconds, or number of iterations with no improvement), and maximization or minimization option. Both of the figures show a sample parameter setting used in the soft and hard constraints for the ACA phase, respectively.

Figure 12 shows the search process for the ACA phase. It displays the academic assignments at each iteration, showing the courses for each professor and the information relative to each teacher’s lecture hours. Additionally, it shows the current value of the objective function. When the algorithm ends, the hard constraints stage, it displays a dialogue box with the resulting ACA, which can be a feasible solution or a solution with a set of assignments that violate some hard constraints. The user must manually select to continue with the soft constraints stage or return to the configuration window to start the search again. At any time, it is possible to pause the search process and save the obtained ACA so far. At the end of the soft constraints stage, the resulting ACA is displayed.

Once the Academic assignments (ACA) are generated, the timetable phase starts. Figure 13 and Figure 14 serve to configure the algorithm’s parameters in the TTP phase (same parameters as in the ACA phase). Both figures show a sample configuration used in the soft and hard constraints for the TTP phase, respectively.

Figure 15 shows the search process for the TTP phase. It displays the timetable details: course, professor, classroom, day, and time, as well as the current value of the objective function. The user can pause the search process and see the number of constraints left and the elapsed time. Once the hard constraints stage has been completed, the resulting timetable is displayed, which can be a feasible solution or a timetable that violates some hard constraints. As in the ACA phase, the user must decide to continue to the soft constraints stage or return to the configuration window in order to start the search again. At any time, it is possible to pause the process and save the obtained timetable so far. At the end of the soft constraints stage, the resulting timetable is displayed.

5.2. Experiments

The tests include two real semesters at the DACyTI with different characteristics. We conducted the experiments on an Alienware M17x laptop with Intel Core i7@2GHz processor, 16GB in RAM, and Ubuntu 18.04 64-bit operating system. The Tabu Search with Probabilistic Aspiration Criterion (TS-PAC) parameter configuration for both school periods is:

• Start solution: through of a greedy algorithm. Different approaches to build an initial solution were used for the ACA phase hard constraints, ACA phase soft constraints, TTP hard constraints, and TTP soft constraints.
• Random seed: a set of random numbers were generated using the random.org platform. The best seed value was 10,769,230.
• Tabu list size: $t=\sqrt[]{\mathrm{number}\mathrm{of}\mathrm{courses}}$.
• Neighborhood: different neighborhood structures were designed for each phase.
• Aspiration criterion: the probabilistic aspiration criterion described in Section 2.3.
• Stop criterion: variable, since different objective functions were defined for each phase. Additionally, we had to relax hard constraints in order to obtain a feasible solution.

5.3. Results for the ACA Phase

Table 1. Data of the two test semesters for the ACA stage.

Data	Semester 1	Semester 2
Teaching staff ($n_p$)	107	106
Number of courses ($n_c$)	369	362
Number of professors with course preferences	107	91
Average of selected courses per professor	5	5

shows the data related to the ACA for the two test semesters. Creating the Academic assignments (ACA) requires the number of available professors, the number of courses to be offered, and the list of courses that each professor would like to teach. Satisfying the hard constraints involves the correct assignment of courses within the limits of each professor’s number of hours. The soft constraint stage seeks to maximize the professors’s course preferences as a whole, i.e., assign each professor at least one course in his preferences.

It is important to mention that each semester may vary the number of professors (some might temporarily leave pursuing postgraduate studies, or ask for a temporary unpaid leave holding government positions). Similarly, the number of courses is the most variable data, because each semester may vary the number of students who graduated and admitted to the university.

The associated constraints to this phase are distributed among entities as follows. We can notice that most of the restrictions in this phase are related to professors:

• Course: hard constraint ACA-HC1.
• Professor: hard constraints ACA-HC2 to ACA-HC16 and soft constraint ACA-SC1.

The results detailed in

Table 2. Results obtained in the ACA stage for both semesters.

Result	Semester 1	Semester 2
Unassigned courses	0	0
Professors with more hours than allowed	0	0
Professors with less hours than allowed	2 *	31
Professors with no satisfied preferences	2 *	9
Percentage of course preferences satisfied	98.13%	91.50%

* Professors with no academic load assigned.

show the violated constraints by the best solution found by the TS-PAC. In both semesters, most of the hard constraints were satisfied, but we could not reach a solution with zero hard constraints violation. Constraint ACA-HC16 was, in all tests, violated, meaning that some professors had fewer hours assignment than the permissible minimum. Thus, we needed to relax this hard constraint in order to continue to the soft constraint stage.

There are two professors with no academic load for the first test semester, i.e., no assigned coursesm, since the ACA was completed without requiring the total number of available professors. This may give a hint that there may be more professors than the required in the Faculty. All of the professors had a favorite course assigned (except for the two professors with no academic load), meaning that all of the soft constraints (constraint ACA-SC1) were satisfied.

In the second test semester, the number of teachers with fewer hours than the limit rises to 31, but there were no professors with unassigned courses. The percentage of satisfying preferences decreases this semester, since the number of professors with course preferences also decreased.

The logarithmic scale graph presented in Figure 16 displays the TS-PAC performance when evaluating the hard constraints for both semesters. In both cases, we set the stop criterion to a maximum number of iterations. The aggressive approach of the algorithm is remarkable. BT-PAC fast convergence is particularly due to the neighborhoods selected and the probabilistic aspiration criterion’s intensification strategy. Overall, the BT-PAC behavior is similar in both tests. However, convergence in semester 1 leads to most of the constraints being satisfied.

Figure 17 shows the performance of the algorithm when solving the soft constraints stage. Again, the behavior of the algorithm is similar in both semesters. Given that the objective function for this stage is maximization (Equation (11)), it is desired to satisfy, as far as possible, the professors’ course preferences. In this case, the stop criterion is $\mathcal{GOAL}=n_p$ (number of professors). From the plot, we can read that both curves, representing each of the test semesters, are progressive and continuous. The expected maximum value in the objective function represents all of the professors satisfied with a favorite course assigned, so the TS-PAC converges to an acceptable solution with a low computational cost.

5.4. Results for the TTP Phase

Table 3. Data of the two test semesters for the TTP stage.

Data	Semester 1	Semester 2
$\langle \mathrm{professor},\mathrm{course}\rangle$ tuples	369	362
Total lectures	1777	1716
Periods of time	60	50
Classrooms	43	43

shows the data that were related to the TTP for the two test semesters. Creating a timetable requires the Academic assignments (ACA), i.e., each $\langle \mathrm{professor},\mathrm{course}\rangle$ tuple, the number of groups, the available classrooms, and the number of periods of time. There is a main difference in both semesters: a reduction in the number of available time periods due to administrative issues. In the first semester, there were 12 periods of time per day (from 8 a.m. to 8 p.m.), but the second semester contains 10 periods per day (from 8 a.m. to 6 p.m.), both from Monday to Friday.

The associated constraints to this phase are distributed among entities, as follows. In this phase, we notice that more constraints are related to lectures:

• Course: hard constraint TTP-HC1 and TTP-HC5.
• Lecture: hard constraints TTP-HC2, TTP-HC3, and TTP-HC4. Soft constraint TTP-SC2.
• Professor: hard constraint TTP-HC6 and soft constraint TTP-SC1.

The results for this stage are shown in

Table 4. Results obtained in the TTP stage for both semesters.

Result	Semester 1	Semester 2
Professor clashes	0	0
Group clashes	0	0
Non-contiguous lectures	0	0
Percentage of shift preferences satisfied	88.87%	87.50%

. It is worth mentioning that none of the hard constraints considered are violated. All of the lectures were scheduled in a single period of time in a proper classroom, avoiding clashes. Regarding hard constraint TTP-HC4, it was easy to satisfy the constraint, because most of the classrooms are large enough to hold most of the courses.

Concerning soft constraints, the number of non-contiguous lectures on the same day were eliminated for both semesters (soft constraint TTP-SC2); this was our priority constraint. We also wanted to maximize the scheduling of lectures within each professor’s hour preferences, which was achieved in most cases (soft constraint TTP-SC1).

Figure 18 and Figure 19 show the performance of the TS-PAC when solving the hard constraints stage (minimization) and the soft constraints stage (maximization). We can notice that the behavior of the algorithm is very similar for both semesters. In the minimization stage (hard constraints), we set the stop criterion to $\mathcal{GOAL}=0$, as achieved in both semesters. For the maximization stage (soft constraints), the stop criterion was set to a maximum number of iterations.

According to the results that were obtained in the two test cases, we can claim that the Tabu Search with Aspiration Criterion algorithm effectively solves the timetabling problem at the DACyTI.

6. Conclusions

The timetabling process is a complex problem, because it is not usually possible to find an optimal solution in a reasonable time, mainly due to the constraints of the problem and the many possible combinations of its intrinsic elements.

In that sense, the proposal of a formal model representing the specific constraints of the University Course Timetabling Problem (UCTP) at a Latin American university is the first contribution of this research. The inherent hard and soft constraints of the problem were described using the UML and the OCL, both software specification languages considered as standard. More importantly, the proposed model is not tied to any particular solution strategy. We consider that our model is sufficiently flexible to allow for new constraints over the same domain, removing or modifying the existing ones. Even new entities, like substitute teachers or the concept of university chair, can be straightforwardly added.

In the literature, there are few cases in which the UCTP is described in two phases that we have called Academic assignments (ACA) and Timetable process (TTP). Separating our problem at the DACyTI into the ACA and TTP phases allows for us to tackle the problem by: (1) modeling specific constraints for each phase, (2) divide each phase into hard and soft constraints stages, specifying two objective functions for each phase, and (3) the design of specific neighborhoods for the Tabu Search algorithm in each phase. Besides, this two-phases technique represents a similar paradigm to the know-how of the personnel responsible for the timetabling process at our university, so it may optimize the manual work, so our prototype may help to optimize the manual work currently done.

We relied on the Tabu Searchm because it is a fast algorithm, easy to tune, and it allows a semi-deterministic search via the designed neighborhoods. In that sense, feasible timetables were generated in the order of minutes. We made a customization of the Tabu Search algorithm, the so-called Tabu Search with Probabilistic Aspiration Criterion (BT-PAC). The aspiration criterion is regularly not taken into account in the various variants of the Tabu Search algorithm presented in the literature. In this case, the proposed aspiration criterion allows for intensifying and diversifying the search in crucial situations, which improves the algorithm’s overall performance. Besides, Tabu Search can be easily implemented in an object-oriented programming language.

A multiplatform software prototype was developed to implement our proposal. This prototype was tested with two semesters of different characteristics in terms of the number of elements to be considered: professors, courses, and periods of time. In both semesters, quality solutions were obtained, satisfying most of the constraints. It is possible to adapt the prototype in order to solve the timetabling problem at other academic divisions of our university, or even in other universities with similar constraints. We exclusively used free software for the development of the prototype.

Among the future works, we have considered implementing a hybrid algorithm while using another metaheuristic in order to explore different areas of the solution space. It is also possible to design various neighborhood schemes to provide further diversity to the solutions generated by the algorithm. Regarding the software prototype, it is suggested to apply quality metrics and usability tests to enrich its functionality.

It is expected that the present model and proposed solution serve as a basis for modeling and solving other instances of the timetabling problem.