Algoritmo de b?squeda tab? para una variante del problema de coloraci?n

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...

Full description

Main Authors: Aboytes Ojeda, Mario, Laureano Cruces, Ana Lilia, Ram?rez Rodr?guez, Javier
Format: Artículo
Language: Español
Published: 2015
Online Access: http://revistas.ucr.ac.cr/index.php/matematica/article/view/11661
http://hdl.handle.net/10669/13036
Summary: 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 ?ptima, 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.