# A Simple and Efficient Local Search Algorithm for the Machine Reassignment Problem
## 4 Our Approach: SMaRT
### Simulated Annealing (SA)  
Algorithm 3 shows the main structure of the SMaRT procedure. It runs after HC2 (Line 2) and works only with feasible solutions. The general purpose of this step is to allow the algorithm to visit other regions of the search space by using dynamic temperature control to properly manage the diversification and intensification during the search process. To achieve this, efficiently and adaptively, the initial temperature is established using a distance measure between the current evaluation function value and the theoretical lower bound value (Line 19). ```
Data:\(max_{m}\), \(max_{p}\), \(MaxProcessesWap\), \(T_{increase}\), \(Ibr\), \(Ibc\), \(CoolingFactor\) Result: Best found solution \(s_{best}\)
1\(T\gets 0\);
2\(s_{curr}\gets HC2(HC1(max_{m},max_{p}),MaxProcessesSwap)\);
3\(s_{init}\gets s_{curr}\);
4\(s_{best}\gets s_{curr}\);
5\(coolingIt\gets 1\);
6\(woImpIt\gets 1\);
7 while\(time()<Time_{limit}\)do
8\(s_{new}\gets getNeighborShiftSwap(MaxProcessesSwap,s_{curr})\);
9 if\(f(s_{new})<f(s_{curr}))\)then
10\(s_{curr}\gets s_{new}\);
11\(woImpIt\gets 1\);
12
13 else
14 if\(random(0,1)<e^{\frac{-A}{T}}\)then
15\(s_{curr}\gets s_{new}\);
16\(woImpIt\gets 1\);
17
18 end if
19\(woImpIt\gets woImpIt+1\);
20 if\(woImpIt==lbr\)then
21\(T\gets T+T_{increase}\cdot(Score_{LB}(s_{curr}))^{2}\);
22\(woImpIt\gets 1\);
23
24 end if
25
26 end if
27 if\(f(s_{curr})<f(s_{best})\)then
28\(s_{best}=s_{curr}\);
29 end if
30\(Ibc\gets Ibc+1\);
31 if\(coolingIt==lbc\)then
32\(T\gets T\cdot CoolingFactor\);
33\(coolingIt\gets 1\);
34
35 end if
36
37 end if
38 return\(s_{best}\);
```  
**Algorithm 3**SMaRT algorithm  
The algorithm uses two mechanisms as parameter control: cooling and reheating. The cooling mechanism is performed after a given number of iterations to reduce the level of diversification of the search (Line 28). On the other hand, after a given number of iterations without improvement of the solution, the reheating mechanism is used to increase the diversification level and allow the algorithm to scape from local optima (Line 19). Simulated Annealing uses, as the second HC, Shift and Swap moves. The difference is in the selection mechanism and the temperature control. After generating the best neighbor of Shift and Swap, the difference between the selected neighbor and the current solution is evaluated:If the difference is negative or zero, that is, it improves or maintains the value of the objective function, the neighbor is immediately accepted (Line 10). 2. If the difference is positive, the acceptance of the neighbor is determined using the temperature criteria (Line 14). That is, the probability of acceptance is \(P(accept(s_{new}))=e^{\frac{\Sigma}{t}}\), where \(\Delta\) is the difference in the objective function value, and \(T\) is the current temperature. Parameter Control Mechanisms  
The temperature is controlled as follows:  
1. Initial temperature: Since SA explores almost the same neighborhood as HC2, the starting point of SA may be a local optimum. For this, a high initial temperature is established, based on a parameter called \(T_{increase}\) and considering the value of the objective function concerning the total cost's lower bound as follows: \[T_{i+1}=T_{i}+T_{increase}\cdot Score_{LB}(s_{curr})^{2},\] (3) where \[Score_{LB}(s_{curr})^{2}=\left[\frac{f(s_{curr})-(LB_{LoadCost}+LB_{Balntec Cost})}{f(s_{ini})}\cdot 100\right]^{2}\] (4) According to Equation (4), the temperature increases by taking the parameter \(T_{increase}\), and amplifying it or decreasing it depending on how distant the current solution is concerning the cost lower bound and the initial solution. If the value of the objective function is too close to the lower bound, \(Score_{LB}\) takes a value \(\in[0,1]\), where its square value is \(\ll\)1 and \(T_{increase}\) decreases due to this factor. With this, the algorithm accepts solutions of worse quality but very close to the current solution, maintaining the exploitation of the nearby zone instead of moving too far from other regions of the search space.