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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Universidad de Costa Rica
2011-07-01
|
| Series: | Revista de Matemática: Teoría y Aplicaciones |
| Online Access: | https://revistas.ucr.ac.cr/index.php/matematica/article/view/2095 |
| _version_ | 1827886907760050176 |
|---|---|
| author | Carlos Pérez de la Cruz Javier Ramírez Rodríguez |
| author_facet | Carlos Pérez de la Cruz Javier Ramírez Rodríguez |
| author_sort | Carlos Pérez de la Cruz |
| collection | DOAJ |
| 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. |
| first_indexed | 2024-03-12T20:10:39Z |
| format | Article |
| id | doaj.art-664196d6a258429d88be786ec6240b43 |
| institution | Directory Open Access Journal |
| issn | 2215-3373 |
| language | English |
| last_indexed | 2024-03-12T20:10:39Z |
| publishDate | 2011-07-01 |
| publisher | Universidad de Costa Rica |
| record_format | Article |
| series | Revista de Matemática: Teoría y Aplicaciones |
| spelling | doaj.art-664196d6a258429d88be786ec6240b432023-08-02T01:45:04ZengUniversidad de Costa RicaRevista de Matemática: Teoría y Aplicaciones2215-33732011-07-0118221522910.15517/rmta.v18i2.20951993a genetic algorithm in a schedule problem with special constraintsCarlos Pérez de la Cruz0Javier Ramírez Rodríguez1Universidad Nacional Autónoma de MéxicoUniversidad Autónoma Metropolitana, Departamento de SistemasRamí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.https://revistas.ucr.ac.cr/index.php/matematica/article/view/2095 |
| spellingShingle | Carlos Pérez de la Cruz Javier Ramírez Rodríguez a genetic algorithm in a schedule problem with special constraints Revista de Matemática: Teoría y Aplicaciones |
| title | 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_short | a genetic algorithm in a schedule problem with special constraints |
| title_sort | genetic algorithm in a schedule problem with special constraints |
| url | https://revistas.ucr.ac.cr/index.php/matematica/article/view/2095 |
| work_keys_str_mv | AT carlosperezdelacruz ageneticalgorithminascheduleproblemwithspecialconstraints AT javierramirezrodriguez ageneticalgorithminascheduleproblemwithspecialconstraints AT carlosperezdelacruz geneticalgorithminascheduleproblemwithspecialconstraints AT javierramirezrodriguez geneticalgorithminascheduleproblemwithspecialconstraints |