Multi-neighbourhood Great Deluge for Google Machine Reassignment Problem

摘要

Google Machine Reassignment Problem (GMRP) is a recent real world problem proposed at ROADEF/EURO challenge 2012. The aim of this problem is to maximise the usage of the available machines by reassigning processes among those machines while a numerous constraints must be not violated. In this work, we propose a great deluge algorithm with multi-neighbourhood operators (MNGD) for GMRP. Great deluge (GD) algorithm is a single solution based heuristic that accept non-improving solutions in order to escape from the local optimal point. The proposed algorithm uses multi-neighbourhood operators of various characteristics to effectively navigate the search space. The proposed algorithm is evaluated on a total of 30 instances. Computational results disclose that our proposed MNGD algorithm performed better than GD with single neighbourhood operator. Furthermore, MNGD algorithm obtains best results compared with other algorithms from the literature on some instances.