A genetic algorithm in a schedule problem with special constraints

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

Descripción completa

Autores Principales: Pérez de la Cruz, Carlos, Ramírez Rodríguez, Javier
Formato: Artículo
Idioma: Español
Publicado: 2015
Acceso en línea: http://revistas.ucr.ac.cr/index.php/matematica/article/view/2095
http://hdl.handle.net/10669/12996
id RepoKERWA12996
recordtype dspace
spelling RepoKERWA129962017-08-08T18:50:25Z 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 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. 2015-05-19T18:59:44Z 2015-05-19T18:59:44Z 2011-07-08 00:00:00 2015-05-19T18:59:44Z info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion http://revistas.ucr.ac.cr/index.php/matematica/article/view/2095 http://hdl.handle.net/10669/12996 10.15517/rmta.v18i2.2095 es Revista de Matemática: Teoría y Aplicaciones Vol. 18 Núm. 2 2011 215-229 application/pdf
institution Universidad de Costa Rica
collection Repositorio KERWA
language Español
description 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.
format Artículo
author Pérez de la Cruz, Carlos
Ramírez Rodríguez, Javier
spellingShingle Pérez de la Cruz, Carlos
Ramírez Rodríguez, Javier
A genetic algorithm in a schedule problem with special constraints
author_sort Pérez de la Cruz, Carlos
title A genetic algorithm in a schedule problem with special constraints
title_short A genetic algorithm in a schedule problem with special constraints
title_full A genetic algorithm in a schedule problem with special constraints
title_fullStr A genetic algorithm in a schedule problem with special constraints
title_full_unstemmed A genetic algorithm in a schedule problem with special constraints
title_sort genetic algorithm in a schedule problem with special constraints
publishDate 2015
url http://revistas.ucr.ac.cr/index.php/matematica/article/view/2095
http://hdl.handle.net/10669/12996
_version_ 1605705975265755136
score 11.762393