Multi-neighborhood local search optimization for machine reassignment problem

• We study the machine reassignment problem (MRP), the topic of the Google ROADEF/EURO Challenge 2012.
• We propose a multi-neighborhood local search (denoted as MNLS) for solving the MRP.
• MNLS consists of three primary and one auxiliary neighborhood structures.
• MNLS employs an efficient neighborhood partition search mechanism with respect to the three primary neighborhoods.
• MNLS performs favorably in comparison with the current best results in both the challenge and the literature.

As the topic of the Google ROADEF/EURO Challenge 2012, machine reassignment problem (denoted as MRP) is an important optimization problem in load balance of cloud computing. Given a set of machines and a set of processes running on machines, the MRP aims at finding a best process-machine reassignment to improve the usage of machines while satisfying various hard constraints. In this paper, we present a metaheuristic algorithm based on multi-neighborhood local search (denoted as MNLS) for solving the MRP. Our MNLS algorithm consists of three primary and one auxiliary neighborhood structures, an efficient neighborhood partition search mechanism with respect to the three primary neighborhoods and a dynamic perturbation operator. Computational results tested on 30 benchmark instances of the ROADEF/EURO Challenge 2012 and comparisons with the results in the challenge and the literature demonstrate the efficacy of the proposed MNLS algorithm in terms of both effectiveness and efficiency. Furthermore, several key components of our MNLS algorithm are analyzed to gain an insight into it.