# A Simple and Efficient Local Search Algorithm for the Machine Reassignment Problem
## 4 Our Approach: SMaRT
### Preprocessing of the Data  
The following methods are implemented to preprocess the data. The data come from the problem instances available at Roadef competence. In each instance, the information of processes, machines, services, and neighborhoods are read and analyzed by the algorithm to allow the following analyses:  
**Filtering the domain of the processes:** We analyze each process to determine whether it is possible to assign it to each machine, removing those where the process cannot be assigned from its domain. This is achieved by considering the transient resources of the machines, which is occupied even after all processes are moved to another machine. Accordingly, considering the transient usage, the machines whose available space is not enough for a process are removed.  
**Identifying processes that are fixed to their initial machine:** After the domain filter, we look for those processes whose transient resources requirement is so high that they can only stay on their initial machine since there is no other machine with enough available space for them (in terms of the transient resources). These processes are not considered to perform moves to generate new solutions, but they stay fixed on the initial machine during the whole algorithm execution. Moreover, a machine with a fixed process is removed from the domain of the rest of the processes from the same service (spreading the conflict constraint), which are rechecked to see whether this change in domain causes them to become stuck on their machines, and so on. This causes a reduction in the search space by using only a subset of processes and machines to generate new solutions.  
**Calculating the lower bound of the cost function:** This is achieved by calculating the lower bound of the load cost and balance cost, as proposed in [3; 4; 5; 9; 28].  
**Calculating a size measure for the processes:** To sort the processes, we use a size measure for each one, which is calculated as the weighted sum of the requirements of each resource. The weights are related to the shortage level of each resource, and there is a relationship between the total requirement for that resource among all processes and the total capacity among all machines. This method to determine the size of a process was proposed in [12], appearing as a better alternative than the size of a process as a sum of its requirements. This measure allows us to prioritize those processes that not only have more requirements but also require more from the scarce resources. Mathematically, the size is calculated as  
\[Size(p)=\sum_{r\in\mathcal{R}}R(p,r)\cdot\beta_{r};\text{ \ where }\beta_{r}=\frac{\sum_{p\in\mathcal{P}}R(p,r)}{\sum_{m\in\mathcal{M}}C(m,r)} \tag{2}\]  
Preprocessing processes are executed considering their effect on all other preprocessing steps. Fixed processes can determine the impossibility of assigning some other processes to these machines during the filtering domain step. These cascade effects are considered until a stable stage is reached.  
All the information computed during the preprocessing phase is stored using proper data structures in order to be efficiently used during the search processes of next steps.  
Figure 1: General structure of the SMaRT algorithm.