Abstract

The Google Machine Reassignment Problem (GMRP) presents a formidable challenge in combinatorial optimization, initially introduced by Google as part of the ROADEF/EURO 2012 Challenge. This problem revolves around the optimal reallocation of a set of processes to a designated set of machines, adhering to specified soft and hard constraints. These constraints encompass considerations like load balancing, efficient resource utilization, and the minimization of communication overhead. This survey comprehensively examines the extensive literature dedicated to addressing the intricacies of the GMRP. It emphasizes the multitude of algorithms and techniques proposed to grapple with this intricate problem. The survey elucidated the problem’s statement and its significance, particularly in contemporary computing landscapes marked by extensive data processing and the prevalence of cloud computing infrastructure. It navigates through the numerous challenges posed by the GMRP, highlighting the inherent complexity arising from the interplay of factors such as machine capacities, process dependencies, and communication constraints. The systematic categorization of diverse approaches is a key feature of the survey. It encompasses a spectrum of optimization techniques: mathematical methods, local search algorithms, population-based algorithms, hyperheuristics, and hybrid metaheuristics. The survey reveals that population-based algorithms emerge as a more viable solution among the various approaches investigated. This conclusion is drawn based on the findings obtained by the authors while conducting the survey.

Author: Andrew Ishaku Wreford, Isah Charles Saidu, Umar Muhammad Modibbo, Bolaji Asaju La’aro

Received on: September, 2023

Accepted on: January, 2024