Algoritmo de búsqueda tabú para una variante del problema de coloración Translated title: Tabu search algorithm for a variation of the coloring problem

Abstract

El problema de coloración robusta generalizado (PCRG) resuelve problemas de horarios que consideran restricciones especiales. Al ser una generalización del problema de coloración robusta, que es a su vez una generalización del problema de coloración, el PCRG es entonces un problema NP-Completo, por lo que es necesario utilizar métodos aproximados para encontrar buenas soluciones en un tiempo de cómputo razonable. En este trabajo se presenta un algoritmo de búsqueda tabú para programar casos de 30 a 180 horas por semana, para algunos de ellos encuentra la solución ´optima, en otros casos, la solución obtenida supera a la mejor solución conocida. También se presentan ejemplos de mayor tamaño a los conocidos, obteniendo resultados muy competitivos, lo que se puede verificar por la ausencia de conflicto entre clases.

Translated abstract

The generalized robust coloring problem (GRCP) resolves timetabling problems that consider special constraints. As a generalization of the robust coloring problem, which is in turn a generalization of the coloring problem, the GRCP is then a NP-Complete problem, so it is necessary to use approximate methods to find good solutions in a reasonable computation time. This paper presents a tabu search algorithm to schedule cases from 30 to 180 hours per week, for some of them it found the optimal solution, in other cases, the solution obtained exceeds the best known solution. It also presents examples of greater size to the known, obtaining very competitive results, which can be verified by the absence of class conflict.