# A Simple and Efficient Local Search Algorithm for the Machine Reassignment Problem
## 2 Related Work  
In this section, we briefly review some of the works presented for MRP related to this paper. A review of the main approaches is presented in [2]. The authors also propose a classification of the approaches. According to [2], the main features of approaches can be related to the use of local search to solve the problem or a collaboration of local search and exhaustive search approaches; the reduction in the size of neighborhoods given the complex nature of the problem; the inclusion of pre-processing steps to focus the search on specific areas of the space to analyze; and the incorporation of modifications to the objective function to assign more relevance to specific costs. In [3], a variable neighborhood search method is presented. The local search algorithm explores four types of neighborhoods: Shift, Swap, Chain, which attempts to move a series of processes at the same time, and \(BPR\) which tries to move big processes to a target machine while shifting processes to make sufficient space. The authors remark that moving big processes (concerning their requirements) in the early stages of the algorithm should be a priority. They also present a lower bound of the total cost function based on the individual lower bounds of load and balance costs. In [4], the authors improve their previous incorporating a restart procedure, a mechanism to deal with random seeds, and removing the exploration _Chain_ neighborhood. Team S38 have presented two models for MRP for competition [5]: A Mixed Integer Linear Programming (MILP) and a Constraint Programming (CP) model. Their strategy was to apply Large Neighborhood Search (LNS) to both models, using CPLEX software [6] in the MILP model and a custom specifically designed LNS in the CP case. Their LNS algorithm creates and solves sub-problems iteratively. In the MILP model, the subset of processes is reassigned considering a timeout; on the other hand, the CP LNS is divided into three main phases: selecting a sub-problem in which a subset of processes and machines are also selected; creating the sub-problem in the computer's memory, for which they evaluate the most efficient way to do it; and then optimize the sub-problem. In the last phase, they use a systematic search, with a stopping criterion based on the number of failures and a given threshold. In [7], improvements to the LNS algorithm proposed in [5] are presented. These include a complete analysis of parameter values, and a two-phase model of clustering of parameters and solving is incorporated. In [8], authors present a hybrid MIP-based large neighborhood search heuristic approach. It combines a Hill Climbing and a Large Neighborhood Search (LNS), which uses Mixed Integer Linear Programming (MIP) to solve sub-problems. Starting from the initial solution, it executes HC to improve the solution quickly and then uses LNS to perform additional improvements. In [9], a Simulated Annealing algorithm and lower bounds for the cost function are presented, obtained with the same formula as [3]. A search operator composed of two sub-moves is used. Shift and Swap are applied disjointedly according to a probability parameter. In [10], a Simulated Annealing-based hyper-heuristic approach is proposed. The general schema used is based on three phases. To generate the heuristics, four types of moves are considered: Shift, Swap, Backtracking (which consists of solving a sub-problem in a similar way to [5]), and Double Shift. In [11], authors model the MRP as a bin packing problem and introduce a local search-based heuristic to solve it. Their approach uses a multi-start system based on an Iterated Local Search framework. In [12], the problem is seen as a Vector Bin Packing perspective (VBP). In this case, the authors propose a generalization of VBP that allows distinct capacities of bins for each dimension. They analyze some structural properties of the MRP that allow decomposing it into smaller sub-problems and show that the studied heuristics are flexible enough to be adapted to the MRP.