Thesis:

Una Metaheurística para la resolución del Machine Reassignment Problem

El Problema de Reasignación de Máquinas (MRP) fue propuesto en el marco de la competencia ROADEF/EURO en conjunto con Google en el año 2012, y está definido por un conjunto de máquinas y procesos. Cada máquina está asociada con un conjunto de recursos, tales como CPU, RAM, Disco duro, y cada proceso tiene requerimientos de algunos de estos recursos. Inicialmente, cada proceso está asignado a una máquina específica, el objetivo del problema es reasignar los procesos, de tal forma, que se mejore su distribución y optimice el uso de las máquinas, los cuales están definidos por una función objetivo específica. Además, se debe cumplir con una serie de restricciones duras. En este trabajo se describe el problema en detalle, y se propone un algoritmo para su resolución, correspondiente a un enfoque colaborativo basado en dos metaheurísticas simples y de fácil implementación: Hill Climbing y Simulated Annealing. Mediante experimentos se muestra que el enfoque propuesto permite obtener resultados competitivos en las instancias más complejas, superando incluso a los mejores algoritmos de la competencia.

The Machine Reassignment Problem (MRP) was proposed in the context of the ROADEF/EURO competition with Google in the year 2012, and it’s defined by a set of machines anda set of processes. Each machine is associated with a set of resources, such as CPU, RAM,Hard disk, and each process has requirements of some of these resources. Initially, eachprocess is assigned to one specific machine, the objective of the problem is to reassign theprocesses, in such a way, that improves distribution and optimize the use of the machines,which are defined by a specific objective function. In addition, a series of hard constraintshave to be satisfied.In this work a description of the problem is presented, along with an algorithm tosolve it, consisting of a collaborative approach of two simple metaheuristics very easy toimplement: Hill Climbing and Simulated Annealing. In computational experiments it isshown that with the proposed approach achieves competitive results on the more complexinstances, surpassing even the best algorithms presented in the competence.