Neighbourhood Analysis: A Case Study on Google Machine Reassignment Problem

摘要

It is known that neighbourhood structures affect search performance. In this study we analyse a series of neighbourhood structures to facilitate the search. The well known steepest descent (SD) local search algorithm is used in this study as it is parameter free. The search problem used is the Google Machine Reassignment Problem (GMRP). GMRP is a recent real world problem proposed at ROADEF/EURO challenge 2012 competition. It consists in reassigning a set of services into a set of machines for which the aim is to improve the machine usage while satisfying numerous constraints. In this paper, the effectiveness of three neighbourhood structures and their combinations are evaluated on GMRP instances, which are very diverse in terms of number of processes, resources and machines. The results show that neighbourhood structure does have impact on search performance. A combined neighbourhood structures with SD can achieve results better than SD with single neighbourhood structure.