Thesis UNA METAHEURISTICA PARA LA RESOLUCION DEL MACHINE REASSIGNMENT PROBLEM
Date
2017
Authors
CANALES ROJAS, DARÍO ANDRÉS
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
El Problema de Reasignaci´on de M´aquinas (MRP) fue propuesto en el marco de la competenciaROADEF/EURO en conjunto con Google en el a˜no 2012, y est´a definido por unconjunto de m´aquinas y procesos. Cada m´aquina est´a asociada con un conjunto de recursos,tales como CPU, RAM, Disco duro, y cada proceso tiene requerimientos de algunosde estos recursos. Inicialmente, cada proceso est´a asignado a una m´aquina espec´ifica, elobjetivo del problema es reasignar los procesos, de tal forma, que se mejore su distribuci´on y optimice el uso de las m´aquinas, los cuales est´an definidos por una funci´on objetivoespec´ifica. Adem´as, se debe cumplir con una serie de restricciones duras.En este trabajo se describe el problema en detalle, y se propone un algoritmo parasu resoluci´on, correspondiente a un enfoque colaborativo basado en dos metaheur´isticassimples y de f´acil implementaci´on: Hill Climbing y Simulated Annealing. Mediante experimentosse muestra que el enfoque propuesto permite obtener resultados competitivos en lasinstancias m´as 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.
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.
Description
Catalogado desde la version PDF de la tesis.
Keywords
COMBINATORIAL OPTIMIZATION , HILL CLIMBING , LOCAL SEARCH METAHEURISTICS , MACHINE REASSIGNMENT PROBLEM , MRP , ROADEF , SCHEDULING , SIMULATED ANNEALING