# Metaheuristic with Cooperative Processes for the University Course Timetabling Problem
## 3 Simulated Annealing with Cooperative Processes (SACP)  
In this work, the simulated annealing metaheuristic (SA) is used due to the great capacity it presents to obtain good local optimums through the procedure known as the acceptance criterion that allows to improve the solution quickly, escaping from the local optimum. Unlike population-based metaheuristics that require working with a population of solutions to optimize through exploration of the solutions space, SA only requires an initial solution to perform optimization through exploitation of the solutions space. Because this metaheuristic presents an asymptotic convergence over time, in this work, a cooperation of processes is applied to improve the obtaining of results in shorter times, performing a search with exploitation and exploration procedures in the space of solutions. Exploitation is carried out by applying local search to each SA and exploration is carried out by generating a cooperation of distributed processes that executes each of the SA with quenching-type restarts and cooperating with each other to direct the search toward a space of good solutions. This section presents the simulated annealing (SA) metaheuristics with processes cooperation. Figure 2 presents a flow diagram of the algorithm. The algorithm generates a SA with restart for each process \(i\), so that in each term of an SA the cooperation between a pair of solutions is carried out. This is the best solution TTSA\({}_{i}\) of SA obtained by the process \(i\) vs. the best solution obtained by all processes, BTT\({}_{i}\). The full explanation of the algorithm is shown:  
1. The algorithm begins its execution in process zero by reading the input file that contains the instance information of the problem to be solved. 2. The information is stored in a data matrix represented in Figure 1.
3. The data types are defined below using the MPI protocol to be able to work with n processes. 4. The information received in process \(i\) = 0 is sent to each one of the \(n\) processes generated using collective communication through the MPI-Bcast function. 5. At the beginning, each process i generates a feasible random initial solution TT\(i\). To generate this feasible solution, the Constructive Approach Algorithm is used. This is presented in [33]; this solution is passed to SA. 6. At the end of each process \(i\) in SA a solution optimized TTSA\({}_{i}\) is obtained and collected in process \(i\) = 0 through each process \(i\). The best solution \(bs_{i}\) = \(f\)(TTSA\({}_{i}\)) obtained by the cost function (Equation (1)) in SA, through an arrangement of best solutions, BS = Set (\(bs_{0}\),..., \(bs_{n.1}\)) and also the number of process npi = ranki that corresponds to the psi solution by means of a number of processes array, NP = Set(\(mp_{0}\),..., \(mp_{n-1}\)). Collective communication with MPI_Gather is applied to send the best cost value psi (best solution) of each process \(i\), to the process \(i\) = 0 and thus obtain the BS array located in process \(i\) = 0. 7. Applying collective communication with MPI_Bcast, the BS array containing the cost of each solution and its Process Number NP, is sent to each process \(i\). 8. On each process \(i\) the cost of the best global solution \(bs_{i}\) = min (BS) is located in BS, which is the same in each process \(i\). However, it is necessary to know in all processes the best number of process \(bm_{i}\) = \(f\) (BS, NP), which contains \(bs_{i}\), in order to evaluate the Hamming distance in each process. 9. In the \(bm_{i}\) process, the best solution of all processes is found in the TTSA\({}_{i}\) array. This solution is called Best Timetabling BTT\({}_{i}\) = \(f\) (bnpi, TTSAi). 10. Applying point-to-point communication with MPI_Send, the BTT\({}_{i}\) array is sent to the process \(i\) = 0 and it is received with MPI_Recv. 11. In process \(i\) = 0, applying collective communication with MPI_Bcast, the best BTT\({}_{i}\) solution is distributed to all the processes. 12.