# A Simple and Efficient Local Search Algorithm for the Machine Reassignment Problem
## 4 Our Approach: SMaRT
### Hill Climbing  
The goal of the first step is to improve the objective function by moving the largest processes from the machines with the highest load cost. Algorithm 1 shows the structure of the first Hill Climbing (HC1). ```
Data:\(max_{m}\), \(max_{p}\) Result: Best found solution \(s_{best}\)
1\(s_{curr}\gets initialSol()\) ;
2\(s_{best}\gets s_{curr}\);
3 while\(time()<Time_{limit}\)do
4 improved\(\leftarrow False\); \(machines\gets sortByCostLoadDescending()\);
5\(overloaded_{machines}\leftarrow machines[1..max_{m}]\);
6\(allocable_{machines}\gets machines[max_{m}+1..end]\);
7 for\(m\in overloaded_{machines}\)do
8\(allocated_{processes}\leftarrow Allocated(m)\);
9\(allocated_{processes}\leftarrow sortBySumOfPoneratedRequirements()\);
10\(topWeighted_{processes}\gets allocated_{processes}[1..max_{p}]\);
11\(s_{curr}\gets BestImprovementShift(topWeighted_{processes},allocable_{machines})\);
12 if\(s_{curr}\
eq\emptyset\)then
13\(s_{best}\gets s_{curr}\);
14\(improved\leftarrow True\);
15 break ;
16
17 end if
18
19 end for
20
21 end for return\(s_{best}\);
```  
**Algorithm 1**HC1 algorithm  
This HC phase uses a move called the Size Discriminant Excluding Shift (SDES) that works as follows:  
* Select the \(max_{m}\) machines loaded most (ordered by total cost) and from them select the \(max_{p}\) processes with the largest size, ordered by the size according to Equation (2) (line 5). The ordered lists of machines are stored in proper data structures that are initialized during the preprocessing considering fixed processes and are updated according to the structure of current solution. * With the selected processes, make a shift movement, moving them to other machines (excluding the \(max_{m}\) most loaded machines of that iteration), maintaining the feasibility, and looking for the best improvement from all possible reassignments (Line 11). * Once the SDES shift is applied in the current iteration, the machines are reordered, and a new iteration starts. The selection criteria are the following:
* Choose the first machine within the most overloaded \(max_{m}\) in which at least one process can be moved to any of the remaining \(max_{m}-1\) machines and produce an improvement. When checking the possible moves for each process, choose the move that makes the best improvement among all processes on the same machine. The algorithm stops when no more improving neighbors can be found or when the time limit is reached (Lines 3 and 19). Once HC1 stops, the candidate solution obtained is given to the second HC. Algorithm 2 shows the structure of the second Hill Climbing (HC2). ```
Data:\(MaxProcessesSwap\) Result: Best found solution \(s_{best}\)
1\(s_{best}\gets HC1()\);
2 while\(time()<Time_{limit}\)do
3\(s_{new}\gets BestImprovementShiftSwap(MaxProcessesSwap,s_{best})\);
4 if\(s_{new}\
eq\emptyset\)then
5 return\(s_{best}\);
6
7 else
8\(s_{best}\gets s_{new}\);
9\(RandomizeProcessesShiftSwap()\);
10
11 end if
12
13 end while return\(s_{best}\);
```  
**Algorithm 2**HC2 algorithm  
HC2 continues the search using swap and shift moves:  
* Shift of processes: A process is removed from one machine and inserted into another. This movement provides variability because it increases and decreases the number of processes in a machine. * Swap of processes: Two processes from different machines are removed and assigned to the other machine. This move causes larger changes in the candidate solution in only one step and increases diversification. The mechanism to generate a new solution is as follows:  
1. Generate a new neighbor by applying shift to the current solution. 2. Generate a new neighbor by applying a swap to the same current solution. 3. Selection criteria: The best neighbor generated from both moves is selected when it is better than the current solution. Ties are broken by choosing the swap move, which gives more diversity (Line 3). The number of processes considered to swap is limited to a maximum number established by a parameter called \(MaxProcessesSwap\).