## 3 Simulated Annealing Algorithm with Cooperative Threads (SACT)
### Effective-Address Mechanism  
The thread _Hi_ carries out the _effective-address_ procedure every time that it finishes the execution of a SA. This _effective-address_ procedure is carried out between the solution \(S_{Hi,c}\) of _Hi_, obtained by the SA, and the best solution, \(S_{best}\), found by the \(n\) threads. The _effective-address_ procedure is the following:  
Figure 2: Generation of neighbors. The neighborhood structure \(N_{1}\)[31] is used in order to generate all the neighbors \(S^{\prime}\)_best_ of \(S_{best}\). These neighbors are always feasible because they only involve exchanging a pair of operations that belong to the critical path [31]. The similarity between each pair of solutions (schedules) \(S_{Hi\_c}\) and a neighbor \(S^{\prime}\)_best_ is measured based on the Hamming distance. This distance is the number of arcs (in the digraph for the solution that results from Figure 1) that have different addresses between \(S_{Hi\_c}\) and its neighbor \(S^{\prime}\)_best_. In other words, it is the number of differences in the order of execution of operations on each machine [12]. There is a high probability of choosing an \(S^{\prime}\)_best_ of \(S_{best}\) that has great similarity to \(S_{Hi\_c}\). This probability is generated in the following way. Three lists are created (\(L_{1}\), \(L_{2}\), \(L_{3}\)) that store the \(S^{\prime}\)_best_ neighbors (generated with \(S_{best}\)) according to the degree of similarity with \(S_{Hi\_c}\). The size of each list is different, \(L_{1}\) is the smallest, and thus the most similar to \(S_{Hi\_c}\) whereas \(L_{3}\) has the neighbors which are less similar to \(S_{Hi\_c}\). \(L_{1}\) is chosen with more frequency in order to direct the search toward a good solution space. The size of each list is assigned according to the problem to be solved and it is defined experimentally (trial and error). In order to select one of the 3 lists, a number \(\alpha\) at random with a value between 1 and 10 is generated. \(L_{1}\) is chosen if \(\alpha\) is between 1 and \(\alpha_{1}\). \(L_{2}\) is chosen if \(\alpha\) is between \(\alpha_{1}+1\) and \(\alpha_{2}\). \(L_{3}\) is chosen if \(\alpha\) is between \(\alpha_{2}+1\) and 10. The size of each interval is \(|1\) to \(\alpha\)\(\|>|\)\(\alpha_{1}+1\) to \(\alpha\)\(|2|>|\)\(\alpha_{2}+1\) to \(10|\). Once the list is chosen, the neighbor \(S^{\prime}\) is chosen randomly from the list. This is the solution that is used in the beginning of the new SA for the thread \(Hi\). The neighbor selected, \(S^{\prime}\)_best_, is the result of the _effective-address_ procedure carried out implicitly between \(S_{Hi\_c}\) and \(S_{best}\). Naturally, this _effective-address_ procedure is applied in each one of the n threads. Figure 3 presents the running threads in SACT. First, a symbolic representation (\(SR\)) of the JSSP is generated. Then, a random solution \(S_{Hi}\) of \(SR\) is generated for each \(Hi\) thread. At the beginning of the algorithm, the best global solution \(S_{best}\), has a very large initial value defined with a lower bound (LB), which is not less than the sum of the processing time of all operations that are executed on the JSSP. Each thread \(Hi\), independently executes an SA with its own initial solution \(S_{Hi}\). The optimized solution \(S_{Hi\_c}\) of \(Hi\), is obtained by the SA. Through critical sections, there is communication between threads to share and use the best global solution. There are two critical sections. In the first critical  
Figure 3: Communication of threads in SACT for sharing information using critical sections. section, the information about the best solution for each thread (\(S_{H\!I\_c}\)) is selected, and from those best solutions (\(S_{H\!I\_c}\) vs. \(S_{best}\)), one is chosen as the best global solution and is updated \(S_{best}\) with the best solution. This best global solution (\(S_{best}\)) is updated constantly, every time a thread enters the critical section with a better solution.