DESAFÍO GOOGLE UNA HIPERHEURÍSTICA PARA EL PROBLEMA DE REASIGNACIÓN DE MÁQUINAS

Abstract

En esta memoria se presenta el problema de reasignacion de maquinas propuesto por el grupo ROADEF en cooperacion con la Sociedad Europea de Investigacion de Operaciones (EURO) y Google Inc, durante su desafo del a~no 2012. El objetivo de este trabajo es el dise~no e implementaci on de una hiperheurstica para resolver dicho problema, con la motivacion de evaluar si este metodo es capaz de entregar soluciones de buena calidad. Se propone una hiperheurstica, llamada HH-MRP, compuesta de dos heursticas de bajo nivel. Estas heursticas son evaluadas periodicamente con el n de seleccionar la que provee mejores resultados y aplicarla hasta la siguiente competicion entre las dos heursticas. De este modo, el algoritmo puede adaptar su comportamiento dinamicamente de acuerdo a la instancia del problema. Las evaluaciones muestran que la colaboracion entre las dos heursticas de bajo nivel mejoraron signicativamente los resultados obtenidos, en comparacion al uso de una sola de ellas. El algoritmo se benecia de la colaboracion entre ambas heursticas y la auto-adaptacion durante su ejecucion. Los resultados obtenidos en 5 minutos de ejecucion (lmite de tiempo establecido para el desafo) son comparables a los de otros algoritmos existentes ejecutandolos en el mismo computador.