# Metaheuristic with Cooperative Processes for the University Course Timetabling Problem
## 1 Introduction
It becomes a complicated problem, mainly because the resources are always limited and constraints related to the availability of material resources (rooms, laboratories, support material, technologies and others) and human resources (teacher capacity, academic needs, student needs, time availability and others) have to be considered. Furthermore, every school timetabling is specific for a school year. It means that this schedule cannot be generally applied for the next school year since the circumstances and needs frequently change. The university course timetabling problem (UCTP) aims to distribute school resources in space and time to generate course timetabling per week. Course timetabling can be a table where the classes that are given in each room are scheduled, or it can also be timetabling that includes the courses for each student. Likewise, the representation of class timetabling can be one that contains the class schedules or courses depending on the different control restrictions imposed by a university. UCTP is a NP-complete problem [4; 12; 13]. In order to tackle NP-complete problems, approximate methods are frequently used. Because of the complexity of the UCTP, when it is applied to real-life practical problems, a parallel simulated annealing metaheuristic is implemented to obtain acceptable solutions, close to the optimal solution, in reasonable computation times. The first attempts to automate course timetabling were made in 1960, where techniques based on simulating design were used to obtain schedules by a manual simulation process [14]. The basic idea of this technique was to first schedule the classes with the highest degree of restrictions. Subsequently, at the beginning of the 1970s, more generic techniques began to be applied to solve the problem. Some of the best-known research includes algorithms based on integer programming [15] and network flow [16; 17; 18], among others. The UCTP problem has also been addressed as a transformation to the coloring graphs problem [19; 20], where the vertices represent events and edges represent conflicts. As well, heuristic approaches based on search techniques are presented. The solution methods vary from constraint satisfaction [21], simulated annealing [22; 23], genetic algorithms [24] and tabu search [25]. In [26], a complete study of a theoretical model for UCTP is presented, but they do not consider the teachers' constraint. They present benchmarks that can be solved by using various heuristics such as ant colony, iterated local search, genetic algorithms, simulated annealing and tabu search. The benchmark is used in this work for the tests by using the parallel simulated annealing algorithm. In [13], a very complete review of various types of timetabling programming and their formulations with genetic algorithms can be found [27; 28], including tabu search and constraint satisfaction. In [29], the construction of a timetabling programmer for academic institutions with a constraint programming model is presented. In [30], a model that applies tabu search with reinforced learning is presented. In [31], they present a model for UCTP with a three-phase approach. At the first phase, a feasible solution is created; in the second phase, they use simulated annealing to order the solution space created; and in the third phase, they also use simulated annealing with a neighborhood structure to improve the solution by the exchange of events. The algorithms of these optimization heuristics are generic and independent of the problem to be optimized and are known under the name of metaheuristics [32]. In [33], a practical case of UCTP is presented. A constructive heuristic is proposed to find solutions for a real-life instance, for the Faculty of Chemical Sciences and Engineering of the Autonomous University of the Morelos state, in Mexico City. In [34], the authors propose a solution of timetabling courses, for specific academic areas, of the Juarez Autonomous University of Tabasco, Mexico.