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

Descripción completa

Detalles Bibliográficos
Autores principales:	Aboytes–Ojeda, Mario, Laureano-Cruces, Ana Lilia, Ramírez-Rodríguez, Javier
Formato:	Online
Idioma:	spa
Publicado:	Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2013
Acceso en línea:	https://revistas.ucr.ac.cr/index.php/matematica/article/view/11661

id	RMTA11661
record_format	ojs
spelling	RMTA116612022-01-27T18:51:22Z Tabu search algorithm for a variation of the coloring problem Algoritmo de búsqueda tabú para una variante del problema de coloración Aboytes–Ojeda, Mario Laureano-Cruces, Ana Lilia Ramírez-Rodríguez, Javier robust coloring timetabling problems heuristics coloración robusta problemas de horarios heurísticas 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. Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2013-08-29 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion Article application/pdf https://revistas.ucr.ac.cr/index.php/matematica/article/view/11661 10.15517/rmta.v20i2.11661 Revista de Matemática: Teoría y Aplicaciones; Vol. 20 No. 2 (2013): Revista de Matemática: Teoría y Aplicaciones; 215-230 Revista de Matemática: Teoría y Aplicaciones; Vol. 20 Núm. 2 (2013): Revista de Matemática: Teoría y Aplicaciones; 215-230 Revista de Matemática; Vol. 20 N.º 2 (2013): Revista de Matemática: Teoría y Aplicaciones; 215-230 2215-3373 1409-2433 spa https://revistas.ucr.ac.cr/index.php/matematica/article/view/11661/10981 Derechos de autor 2013 Mario Aboytes–Ojeda, Ana Lilia Laureano-Cruces, Javier Ramírez-Rodríguez https://creativecommons.org/licenses/by-nc-sa/4.0
institution	Universidad de Costa Rica
collection	Revista de Matemática: Teoría y Aplicaciones
language	spa
format	Online
author	Aboytes–Ojeda, Mario Laureano-Cruces, Ana Lilia Ramírez-Rodríguez, Javier
spellingShingle	Aboytes–Ojeda, Mario Laureano-Cruces, Ana Lilia Ramírez-Rodríguez, Javier Algoritmo de búsqueda tabú para una variante del problema de coloración
author_facet	Aboytes–Ojeda, Mario Laureano-Cruces, Ana Lilia Ramírez-Rodríguez, Javier
author_sort	Aboytes–Ojeda, Mario
description	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.
title	Algoritmo de búsqueda tabú para una variante del problema de coloración
title_short	Algoritmo de búsqueda tabú para una variante del problema de coloración
title_full	Algoritmo de búsqueda tabú para una variante del problema de coloración
title_fullStr	Algoritmo de búsqueda tabú para una variante del problema de coloración
title_full_unstemmed	Algoritmo de búsqueda tabú para una variante del problema de coloración
title_sort	algoritmo de búsqueda tabú para una variante del problema de coloración
title_alt	Tabu search algorithm for a variation of the coloring problem
publisher	Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA)
publishDate	2013
url	https://revistas.ucr.ac.cr/index.php/matematica/article/view/11661
work_keys_str_mv	AT aboytesojedamario tabusearchalgorithmforavariationofthecoloringproblem AT laureanocrucesanalilia tabusearchalgorithmforavariationofthecoloringproblem AT ramirezrodriguezjavier tabusearchalgorithmforavariationofthecoloringproblem AT aboytesojedamario algoritmodebusquedatabuparaunavariantedelproblemadecoloracion AT laureanocrucesanalilia algoritmodebusquedatabuparaunavariantedelproblemadecoloracion AT ramirezrodriguezjavier algoritmodebusquedatabuparaunavariantedelproblemadecoloracion
_version_	1811744076063571968

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

Ejemplares similares