Un algoritmo genético para un problema de horarios con restricciones especiales

En Ramírez (2001) se introdujo el problema de coloración robusta generalizado (PCRG), el cual resuelve problemas de horarios que consideran restricciones del tipo: dos eventos no pueden realizarse a la misma hora y debe haber al menos d días entre dos eventos. El PCRG es una coloración robusta, en q...

Descripción completa

Detalles Bibliográficos
Autores principales:	Pérez de la Cruz, Carlos, 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) 2011
Acceso en línea:	https://revistas.ucr.ac.cr/index.php/matematica/article/view/2095

id	RMTA2095
record_format	ojs
spelling	RMTA20952022-01-26T18:00:59Z A genetic algorithm in a schedule problem with special constraints Un algoritmo genético para un problema de horarios con restricciones especiales Pérez de la Cruz, Carlos Ramírez Rodríguez, Javier timetabling special constrains heuristics horarios restricciones especiales heuristícas Ramírez (2001) introduced the generalized robust coloring problem (GRCP), this problem lets solve timetabling problems which considers constraints such as: two events can not be assigned at the same time and there must be at least d days between two events.The GRCP deals with a robust coloring for a given graph with a fixed number of colors, not necessarily the chromatic number and considers the distance between colors as the penalization of complementary edges. It was shown that the problem is NP-complete, so it is necessary to use approximate methods to find good solutions in a reasonable time. This paper presents a hybrid of a genetic algorithm with a local search for cases of 30-120 hours per week; it is shown that for some cases the found solution is optimal and in other cases the solutions are very promising. En Ramírez (2001) se introdujo el problema de coloración robusta generalizado (PCRG), el cual resuelve problemas de horarios que consideran restricciones del tipo: dos eventos no pueden realizarse a la misma hora y debe haber al menos d días entre dos eventos. El PCRG es una coloración robusta, en que dada una gráfica y un número fijo de colores, no necesariamente el número cromático, considera la distancia entre colores como penalización de las aristas complementarias.Se demostró que el problema es NP-Completo, por lo que es necesario utilizar métodos aproximados para encontrar buenas soluciones en un tiempo razonable. En este trabajo se presenta un híbrido de un algoritmo genético con uno de búsqueda local para casos de 30 a 120 horas por semana, se demuestra que para algunos la solución es óptima y en otros se encuentran soluciones muy prometedoras. Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2011-08-01 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion Article application/pdf https://revistas.ucr.ac.cr/index.php/matematica/article/view/2095 10.15517/rmta.v18i2.2095 Revista de Matemática: Teoría y Aplicaciones; Vol. 18 No. 2 (2011): Revista de Matemática: Teoría y Aplicaciones; 215-229 Revista de Matemática: Teoría y Aplicaciones; Vol. 18 Núm. 2 (2011): Revista de Matemática: Teoría y Aplicaciones; 215-229 Revista de Matemática; Vol. 18 N.º 2 (2011): Revista de Matemática: Teoría y Aplicaciones; 215-229 2215-3373 1409-2433 spa https://revistas.ucr.ac.cr/index.php/matematica/article/view/2095/2058 Derechos de autor 2011 Carlos Pérez de la Cruz, 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	Pérez de la Cruz, Carlos Ramírez Rodríguez, Javier
spellingShingle	Pérez de la Cruz, Carlos Ramírez Rodríguez, Javier Un algoritmo genético para un problema de horarios con restricciones especiales
author_facet	Pérez de la Cruz, Carlos Ramírez Rodríguez, Javier
author_sort	Pérez de la Cruz, Carlos
description	En Ramírez (2001) se introdujo el problema de coloración robusta generalizado (PCRG), el cual resuelve problemas de horarios que consideran restricciones del tipo: dos eventos no pueden realizarse a la misma hora y debe haber al menos d días entre dos eventos. El PCRG es una coloración robusta, en que dada una gráfica y un número fijo de colores, no necesariamente el número cromático, considera la distancia entre colores como penalización de las aristas complementarias.Se demostró que el problema es NP-Completo, por lo que es necesario utilizar métodos aproximados para encontrar buenas soluciones en un tiempo razonable. En este trabajo se presenta un híbrido de un algoritmo genético con uno de búsqueda local para casos de 30 a 120 horas por semana, se demuestra que para algunos la solución es óptima y en otros se encuentran soluciones muy prometedoras.
title	Un algoritmo genético para un problema de horarios con restricciones especiales
title_short	Un algoritmo genético para un problema de horarios con restricciones especiales
title_full	Un algoritmo genético para un problema de horarios con restricciones especiales
title_fullStr	Un algoritmo genético para un problema de horarios con restricciones especiales
title_full_unstemmed	Un algoritmo genético para un problema de horarios con restricciones especiales
title_sort	un algoritmo genético para un problema de horarios con restricciones especiales
title_alt	A genetic algorithm in a schedule problem with special constraints
publisher	Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA)
publishDate	2011
url	https://revistas.ucr.ac.cr/index.php/matematica/article/view/2095
work_keys_str_mv	AT perezdelacruzcarlos ageneticalgorithminascheduleproblemwithspecialconstraints AT ramirezrodriguezjavier ageneticalgorithminascheduleproblemwithspecialconstraints AT perezdelacruzcarlos unalgoritmogeneticoparaunproblemadehorariosconrestriccionesespeciales AT ramirezrodriguezjavier unalgoritmogeneticoparaunproblemadehorariosconrestriccionesespeciales AT perezdelacruzcarlos geneticalgorithminascheduleproblemwithspecialconstraints AT ramirezrodriguezjavier geneticalgorithminascheduleproblemwithspecialconstraints
_version_	1811744082744049664

Un algoritmo genético para un problema de horarios con restricciones especiales

Ejemplares similares