Solución del problema de la designación generalizada usando el método de búsqueda tabú

Abstract

En el problema de designación generalizada el número de tareas es mayor que el de agentes y estos tienen capacidad de recursos limitados. El problema consiste en conocer qué agentes deben hacer las tareas sin violar su capacidad y maximizando sus ingresos. La solución del problema es planteado en tres etapas: en la primera se implementa una heurística constructiva, en la segunda una constructiva mejorada y en la tercera el método búsqueda tabú. La búsqueda tabú emplea estrategias de intensificación, usando para tal fin memoria de corto plazo, así como la estrategia de selección elite y criterios de aspiración. La efectividad de la metodología es verificada analizando casos de la literatura especializada. En varios de estos casos se obtiene la solución global y en el peor de ellos se llega a una solución que es el 97.9% respecto al óptimo global.