A Large Neighborhood Search approach for the Machine Reassignment Problem in data centers

Thumbnail Image
Souza, Filipe
Grimes, Diarmuid
O'Sullivan, Barry
Journal Title
Journal ISSN
Volume Title
Springer Cham
Research Projects
Organizational Units
Journal Issue
One of the main challenges in data centre operations involves optimally reassigning running processes to servers in a dynamic setting such that operational performance is improved. In 2012, Google proposed the Machine Reassignment Problem in collaboration with the ROADEF/Euro challenge. A number of complex instances were generated for evaluating the submissions. This work focuses on new approaches to solve this problem. In particular, we propose a Large Neighbourhood Search approach with a novel, domain-specific heuristic for neighborhood selection. This heuris tic uses the unbalanced resource usage on the machines to select the most promising processes in each iteration. Furthermore, we compare two search strategies to optimise the sub-problems. The first one is based on the concept of Limited Discrepancy Search, albeit tailored to large scale problems; and the second approach involves the standard combination of constraint programming with random restart strategies. An empirical evaluation on the widely studied instances from ROADEF 2012 demonstrates the effectiveness of our approach against the state-of the-art, with new upper bounds found for three instances.
LNS , Neighbourhood selection , Machine reassignment problem , Limited discrepancy search
Souza, F., Grimes, D. and O’Sullivan, B. (2023) ‘A large neighborhood search approach for the data centre machine reassignment problem’, AICS2022, in L. Longo and R. O’Reilly (eds) Artificial Intelligence and Cognitive Science. Cham: Springer Nature Switzerland, pp. 397–408. https://doi.org/10.1007/978-3-031-26438-2_3