Revista de Matema´tica: Teor´ıa y Aplicaciones 2011 18(2) : 215–229
cimpa – ucr issn: 1409-2433
un algoritmo gene´tico para un
problema de horarios con
restricciones especiales
a genetic algorithm in a schedule
problem with special constraints
Carlos Pe´rez de la Cruz∗
Javier Ram´ırez Rodr´ıguez†
Received: 23 Feb 2010; Revised: 23 Nov 2010;
Accepted: 1 Feb 2011
∗Posgrado en Ingenier´ıa en Sistemas, Universidad Nacional Auto´noma de
Me´xico, Circuito Exterior, Ciudad Universitaria, Me´xico D. F., Me´xico. E-Mail:
larsoinde@hotmail.com
†Departamento de Sistemas, Universidad Auto´noma Metropolitana – Azcapotzalco.
Avenida San Pablo 180, Colonia Reynosa Tamaulipas, 02200 Me´xico D. F., Me´xico.
E-Mail: jararo@correo.azc.uam.mx
215
216 c. pe´rez — j. ram´ırez
Resumen
En Ramı´rez (2001) se introdujo el problema de coloracio´n robusta
generalizado (PCRG), el cual resuelve problemas de horarios que con-
sideran 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 coloracio´n robusta, en que dada una gra´fica y un nu´mero fijo de
colores, no necesariamente el nu´mero croma´tico, considera la distan-
cia entre colores como penalizacio´n de las aristas complementarias.
Se demostro´ que el problema es NP-Completo, por lo que es nece-
sario utilizar me´todos aproximados para encontrar buenas soluciones
en un tiempo razonable. En este trabajo se presenta un h´ıbrido de
un algoritmo gene´tico con uno de bu´squeda local para casos de 30 a
120 horas por semana, se demuestra que para algunos la solucio´n es
o´ptima y en otros se encuentran soluciones muy prometedoras.
Palabras clave: horarios; restricciones especiales; heurist´ıcas.
Abstract
Ramı´rez (2001) introduced the generalized robust coloring prob-
lem (GRCP), this problem lets solve timetabling problems which con-
siders 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 comple-
mentary 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.
Keywords: timetabling; special constrains; heuristics.
Mathematics Subject Classification: 05C15, 90C59, 68T20.
1 Introduccio´n
La asignacio´n de horarios es un problema muy comu´n en la planeacio´n de
actividades en todas las empresas, poder modelar y resolver estos proble-
mas de una manera ma´s precisa permite lograr mejoras significativas en
los procesos. Existen modelos en los cuales se ven reflejadas restricciones
tales como que dos o ma´s procesos o actividades no puedan compartir un
recurso, muchos de estos modelos no contemplan restricciones en cuanto a
que´ tan lejos en el tiempo deben estar estas actividades.
Rev.Mate.Teor.Aplic. (ISSN 1409-2433) Vol. 18(2): 215–229, July 2011
un algoritmo gene´tico para un problema de horarios 217
En Ramı´rez (2001) se introdujo el problema de coloracio´n robusta ge-
neralizado (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. Se demostro´ que el problema
es NP- Completo, por lo que es necesario utilizar me´todos aproximados
para encontrar buenas soluciones, en Lara et al. (2010) se presenta un
procedimiento gloto´n aleatorizado, GRASP por sus siglas en ingle´s.
En este trabajo se presenta un algoritmo gene´tico para el PCRG que
encuentra mejores soluciones para algunos casos reportados en Lara et al.
(2010) y como el algoritmo gene´tico y caso reportados en Ramı´rez (2001)
encuentra la solucio´n o´ptima. En la seccio´n 2 se recuerdan algunas defini-
ciones dadas en Ramı´rez (2001); en la Seccio´n 3 se presenta un problema
simplificado y se describe el algoritmo gene´tico para el PCRG; en la Seccio´n
4 se presentan resultados computacionales y se demuestra que la solucio´n
encontrada para algunos casos es o´ptima; finalmente en la seccio´n 5 se
presentan algunas conclusiones.
2 Definiciones
i. Problema de Coloracio´n Robusta (PCR).
Dada una gra´fica G = (V,A) con |V | = n, k > 0, entero y una
matriz de penalizaciones P = {pij , (i, j) ∈ A¯}, el PCR busca con-
struir una coloracio´n va´lida C: V → {1, 2, ..., k}, donde k no es
necesariamente el mı´nimo, que cuente con el menor grado de rigidez,
R(C), entendie´ndose por rigidez de la coloracio´n C a la suma de las
penalizaciones de las aristas complementarias cuyos extremos esta´n
igualmente coloreados, el objetivo es:
minR(C) =
∑
{i,j}∈A¯,C(i)=C(j)
pij
s.a. C(i) 6= C(j) ∀{i, j} ∈ A.
Distintas penalizaciones de las aristas complementarias permiten obtener
coloraciones va´lidas con diferentes propiedades.
ii. Dada una k-coloracio´n C sobre una gra´fica G = (V,A), se define una
k-distancia d como una distancia en el conjunto de colores {1, 2, ..., k}
iii. Problema de Coloracio´n Robusta Generalizada (PCRG).
El PCRG busca construir una coloracio´n va´lida con un nu´mero fijo
de colores (no necesariamente el mı´nimo) que cuente con el menor
nu´mero violaciones a restricciones del tipo “debe haber al menos d
Rev.Mate.Teor.Aplic. (ISSN 1409-2433) Vol. 18(2): 215–229, July 2011
218 c. pe´rez — j. ram´ırez
d´ıas entre dos eventos de un mismo tipo”. Para esto se define el
d¯-grado de rigidez generalizado de la k-coloracio´n (C), siendo d¯ ≥ 0
, como la suma de las penalizaciones de las aristas complementarias
cuyos extremos esta´n pintados con colores que tienen una distancia
menor o igual d¯.
Rd¯(C) =
∑
{i,j}∈A¯,d(C(i),C(j))≤d¯
pij
s.a C(i) 6= C(j) ∀{i, j} ∈ A.
Al igual que el PCR, lo que se busca es encontrar la coloracio´n con
menor grado de rigidez generalizada.
3 Resolviendo el PCRG con un h´ıbrido de algo-
ritmo gene´tico y bu´squeda local
Un algoritmo gene´tico ba´sico consta de las siguientes etapas:
1. Generacio´n de la poblacio´n inicial.
De manera aleatoria se crean posibles soluciones (cromosomas) que
en conjunto formara´n la poblacio´n inicial.
2. Evaluacio´n de los elementos de la poblacio´n.
Los elementos de la poblacio´n son evaluados por medio de una funcio´n
de aptitud.
3. Producir una nueva generacio´n.
Se aplican los operadores gene´ticos de cruce y mutacio´n y se actualiza
la poblacio´n.
El algoritmo desarrollado en este trabajo considera una cuarta etapa
en la cual se realiza una bu´squeda local en las vecindades de los individuos
de la poblacio´n en cada generacio´n.
El siguiente ejemplo es presentado en Ramı´rez (2001) y en Lara et al.
(2010). Se trata de planificar los cursos de un diplomado que consta de
15 materias distribuidas en tres mo´dulos. Los estudiantes se inscribira´n al
mo´dulo que sea de su intere´s y de manera obligatoria llevara´n todas las
clases de las materias de dicho mo´dulo:
Rev.Mate.Teor.Aplic. (ISSN 1409-2433) Vol. 18(2): 215–229, July 2011
un algoritmo gene´tico para un problema de horarios 219
Mo´dulo Materia Nu´mero de clases
a la semana
I A,B,C 3
K 1
II D,E 3
F,G 2
III H,I,J 2
L,M,N,O 1
A la administracio´n le toca planificar las clases en los horarios y salones
disponibles de modo que; clases de la misma materia o del mismo mo´dulo
no se impartan a la misma hora y adema´s debera´ de haber al menos 2
d´ıas entre clases de la misma materia. Para este ejemplo, en cada d´ıa se
cuenta con tres horarios diferentes y se debe procurar no utilizar ma´s de
dos salones.
Los d´ıas ha´biles en la semana son: lunes, martes, mie´rcoles, jueves y
viernes.
Representacio´n de la solucio´n
De acuerdo al ejemplo citado, y ya que cada materia tiene un nu´mero de
clases que deben ser impartidas, a cada una de ellas se les puede etiquetar
de la siguiente manera:
Materia Clase Etiqueta
A 1 1
A 2 2
A 3 3
B 1 4
B 2 5
B 3 6
...
...
...
O 1 30
A las horas disponibles tambie´n se les puede etiquetar de manera
ana´loga:
Rev.Mate.Teor.Aplic. (ISSN 1409-2433) Vol. 18(2): 215–229, July 2011
220 c. pe´rez — j. ram´ırez
D´ıa Hora Etiqueta
lunes 1 1
lunes 2 2
lunes 3 3
martes 1 4
martes 2 5
martes 3 6
...
...
...
viernes 3 15
La solucio´n se representa asigna´ndole a cada uno de los ve´rtices (clases)
un color que representa la hora en que sera´n impartidas.
Un ejemplo de una solucio´n es:
Clase con etiqueta # Hora con etiqueta #
1 3
2 9
3 15
...
...
30 1
En esta solucio´n la clase de la materia A etiquetada con 1 se impartira´
en la hora etiquetada con 3, esto es en la tercera hora del lunes, la clase de
la materia A etiquetada con 2 se impartira´ en la hora etiquetada con 9, esto
es en la tercera hora del mie´rcoles, la clase de la materia A etiquetada con
3 se impartira´ en la hora etiquetada con 15, que corresponde a la tercera
hora del viernes etc.
Si a dos o ma´s clases se les asigna impartirse a la misma hora, aun
sin saber cual es e´sta, diremos que pertenecen al mismo conjunto. Por
taman˜o de conjunto se entendera´ en este caso por el nu´mero de clases que
lo conforman.
Creacio´n de la poblacio´n inicial
Se crea una poblacio´n inicial de taman˜o 20, utilizando el siguiente proce-
dimiento:
Se crea una solucio´n que cumpla con la familia de restricciones del tipo
“la clase x no puede darse a la misma hora que la clase y”, de manera
aleatoria. Esto dara´ como resultado conjuntos que contienen clases que se
impartira´n a la misma hora. La familia de restricciones del tipo: “debe
haber d d´ıas entre clases de la misma materia” se corrige con el algoritmo.
Rev.Mate.Teor.Aplic. (ISSN 1409-2433) Vol. 18(2): 215–229, July 2011
un algoritmo gene´tico para un problema de horarios 221
Tomando el ejemplo de las 30 clases:
a1 a2 a3 b1 b2 b3 c1 c2 c3 k1 d1 d2 d3 e1 e2 e3 f1 f2 g1 g2 h1 h2 i1 i2 j1 j2 l1 m1 n1 o1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
a1 1
a2 2 1
a3 3 1 1
b1 4 1 1 1
b2 5 1 1 1 1
b3 6 1 1 1 1 1
c1 7 1 1 1 1 1 1
c2 8 1 1 1 1 1 1 1
c3 9 1 1 1 1 1 1 1 1
k1 10 1 1 1 1 1 1 1 1 1
d1 11 0 0 0 0 0 0 0 0 0 0
d2 12 0 0 0 0 0 0 0 0 0 0 1
d3 13 0 0 0 0 0 0 0 0 0 0 1 1
e1 14 0 0 0 0 0 0 0 0 0 0 1 1 1
e2 15 0 0 0 0 0 0 0 0 0 0 1 1 1 1
e3 16 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1
f1 17 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1
f2 18 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
g1 19 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
g2 20 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1
h1 21 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
h2 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
i1 23 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
i2 24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
j1 25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
j2 26 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1
l1 27 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1
m1 28 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
n1 29 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
o1 30 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1
Los unos representan las restricciones de que dos conjuntos no se puedan
unir, los ceros que si se puedan unir. Se elige al azar un cero, y se unen los
conjuntos asociados en caso de que el conjunto resultante sea de taman˜o
menor o igual al ma´ximo fijado, por ejemplo:
Supongamos que se elige al cero que relaciona la clase de la materia A
etiquetada con 1 y la clase de la materia D etiquetada con 12. Se unira´n
dichos conjuntos y se agregaran las restricciones derivadas de esa unio´n.
a1 a2 a3 b1 b2 b3 c1 c2 c3 k1 d1 d3 e1 e2 e3 f1 f2 g1 g2 h1 h2 i1 i2 j1 j2 l1 m1 n1 o1
d2
1 2 3 4 5 6 7 8 9 10 11 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
12
a1,d2 1,12
a2 2 1
a3 3 1 1
b1 4 1 1 1
b2 5 1 1 1 1
b3 6 1 1 1 1 1
c1 7 1 1 1 1 1 1
c2 8 1 1 1 1 1 1 1
c3 9 1 1 1 1 1 1 1 1
k1 10 1 1 1 1 1 1 1 1 1
d1 11 1 0 0 0 0 0 0 0 0 0
d3 13 1 0 0 0 0 0 0 0 0 0 1
e1 14 1 0 0 0 0 0 0 0 0 0 1 1
e2 15 1 0 0 0 0 0 0 0 0 0 1 1 1
e3 16 1 0 0 0 0 0 0 0 0 0 1 1 1 1
f1 17 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1
f2 18 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1
g1 19 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
g2 20 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
h1 21 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
h2 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
i1 23 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
i2 24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
j1 25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
j2 26 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1
l1 27 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1
m1 28 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
n1 29 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
o1 30 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1
Rev.Mate.Teor.Aplic. (ISSN 1409-2433) Vol. 18(2): 215–229, July 2011
222 c. pe´rez — j. ram´ırez
Si ese conjunto ya tiene el nu´mero ma´ximo de elementos que se per-
miten (para conjuntos que forman las soluciones de la poblacio´n inicial este
nu´mero ma´ximo es el doble del nu´mero de clases por hora permitidas =
4), se an˜aden nuevas restricciones (unos) con el fin de evitar que se unan
nuevos elementos a ese conjunto. En caso de que la unio´n de dos conjun-
tos de co´mo resultado un conjunto de taman˜o mayor al ma´ximo fijado, se
reparten al azar los elementos de este ultimo conjunto de tal manera que se
creara un conjunto que cuente con el nu´mero ma´ximo de elementos fijado
y otro conjunto que contendra´ los elementos sobrantes. Para el conjunto
con el nu´mero ma´ximo de elementos se an˜aden unos con el fin de que no
se puedan an˜adir ma´s elementos.
So´lo en caso de que este nu´mero ma´ximo se hubiera fijado como 2, los
unos que se tendr´ıan que agregar ser´ıan los marcados con rojo en la figura
de abajo:
a1 a2 a3 b1 b2 b3 c1 c2 c3 k1 d1 d3 e1 e2 e3 f1 f2 g1 g2 h1 h2 i1 i2 j1 j2 l1 m1 n1 o1
d2
1 2 3 4 5 6 7 8 9 10 11 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
12
a1,d2 1,12
a2 2 1
a3 3 1 1
b1 4 1 1 1
b2 5 1 1 1 1
b3 6 1 1 1 1 1
c1 7 1 1 1 1 1 1
c2 8 1 1 1 1 1 1 1
c3 9 1 1 1 1 1 1 1 1
k1 10 1 1 1 1 1 1 1 1 1
d1 11 1 0 0 0 0 0 0 0 0 0
d3 13 1 0 0 0 0 0 0 0 0 0 1
e1 14 1 0 0 0 0 0 0 0 0 0 1 1
e2 15 1 0 0 0 0 0 0 0 0 0 1 1 1
e3 16 1 0 0 0 0 0 0 0 0 0 1 1 1 1
f1 17 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1
f2 18 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1
g1 19 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
g2 20 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
h1 21 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
h2 22 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
i1 23 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
i2 24 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
j1 25 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
j2 26 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1
l1 27 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1
m1 28 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
n1 29 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
o1 30 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1
La eleccio´n de ceros, unio´n de conjuntos y actualizacio´n de unos se lleva
a cabo hasta que ya no queda cero alguno por elegir.
Evaluacio´n de la soluciones de la poblacio´n inicial
A los conjuntos, se les asigna al azar un nu´mero (que representa una hora)
de tal manera que cada hora disponible quede asignada a un conjunto. Se
evalu´a la solucio´n de acuerdo al nu´mero de restricciones que son violadas
(estas restricciones son del tipo x clase debe darse a m d´ıas de distancia o
ma´s de y clase).
Rev.Mate.Teor.Aplic. (ISSN 1409-2433) Vol. 18(2): 215–229, July 2011
un algoritmo gene´tico para un problema de horarios 223
Por ejemplo a un conjunto formado por alguna de las clases de la mate-
ria A (supongamos la etiquetada con 1) y alguna de las clases de la materia
D (supongamos la etiquetada con 12), se les asigna al azar que se impartan
a la quinta hora, esto es, las dos clases se impartira´n a la segunda hora del
martes: (1,5), (12,5)
A otro conjunto formado por alguna de las clases de la materia A
(supongamos la etiquetada con 2) y la clase de la materia O etiquetada
con 30 se les asigna al azar la novena hora, esto es, las dos clases de este
conjunto se impartira´n la tercera hora del mie´rcoles: (2,9), (30,9).
Ya que clases de la misma materia deben de ser impartidas a dos d´ıas
de distancia, el que se asigne impartir dos clases de la materia A en d´ıas
consecutivos genera un violacio´n al tipo de restricciones ”x clase debe de
darse a m d d´ıas de distancia o ma´s de y clase”. Por lo que una solucio´n
que presente esta asignacio´n sera´ penalizada en su evaluacio´n, y as´ı se ira´
penalizando a las soluciones por el nu´mero de restricciones que violen de
este tipo. De esta forma la funcio´n de aptitud que evaluara´ que´ tan buena
es una solucio´n sera´ el grado de rigidez generalizado.
Rd¯(C) =
∑
{i,j}∈A¯,d(C(i),C(j))≤d¯
pij.
Bu´squeda local en la poblacio´n inicial
Se evalu´a la mejora de intercambiar la hora asignada de dos conjuntos
cualquiera. Si hay mejora, se realiza el intercambio que resulta mejor
evaluado y se actualiza la evaluacio´n de la solucio´n.
Se repite el procedimiento anterior hasta que no haya mejora posible
con este k2 intercambio.
Operadores gene´ticos
Cruce
Para generar nuevos elementos en la poblacio´n se ordenan las soluciones de
manera aleatoria (para taman˜o de poblacio´n 20 hay 20! formas de hacerlo),
y ya que esta´n ordenadas las soluciones se toman en forma creciente, de
dos en dos, y para cada 1 de las 10 parejas se realiza lo siguiente:
Fase 1 Clases que tuvieron el mismo color en cada una de las soluciones
(individuos), aunque no sea precisamente el mismo color en las dos solu-
ciones, con una probabilidad grande se creara un conjunto en que el estas
clases pertenezcan al mismo.
P =MID ∗ PG
Rev.Mate.Teor.Aplic. (ISSN 1409-2433) Vol. 18(2): 215–229, July 2011
224 c. pe´rez — j. ram´ırez
Si en el conjunto al que pertenecen las clases en el padre mejor evaluado
ninguno de sus elementos genero violacio´n, MID = 1, en caso contrario
MID = 0.3.
Si no ocurre que algunas clases tuvieran el mismo color en cada una
de las soluciones (individuos), pero en el padre mejor evaluado estas clases
aparecen en algu´n conjunto.
P =MID ∗ (PG− .15)
En este caso, si en el conjunto al que pertenecen las clases en el padre
mejor evaluado ninguno de sus elementos genero violacio´n, MID = 1, en
caso contrario MID = 0.5.
Fase 2 Supongamos que producto de la fase 1 se crearon 3 conjuntos, el
primer conjunto formado por la clase de la materia A etiquetada con 1 y
la clase de la materia D etiquetada con 12, el segundo conjunto formado
por la clase de la materia B etiquetada con 6 y la clase de la materia J
etiquetada con 25 y un tercer conjunto formado por la clase de la materia
E etiquetada con 14 y por la clase de la materia J etiquetada con 26,
podr´ıamos representar esto como:
a1 a2 a3 b1 b2 b3 c1 c2 c3 k1 d1 d3 e1 e2 e3 f1 f2 g1 g2 h1 h2 i1 i2 l1 m1 n1 o1
d2 j1 j2
1 2 3 4 5 6 7 8 9 10 11 13 14 15 16 17 18 19 20 21 22 23 24 27 28 29 30
12 25 26
a1,d2 1,12
a2 2 1
a3 3 1 1
b1 4 1 1 1
b2 5 1 1 1 1
b3,j1 6,25 1 1 1 1 1
c1 7 1 1 1 1 1 1
c2 8 1 1 1 1 1 1 1
c3 9 1 1 1 1 1 1 1 1
k1 10 1 1 1 1 1 1 1 1 1
d1 11 1 0 0 0 0 0 0 0 0 0
d3 13 1 0 0 0 0 0 0 0 0 0 1
e1,j2 14,26 1 0 0 0 0 0 0 0 0 0 1 1
e2 15 1 0 0 0 0 0 0 0 0 0 1 1 1
e3 16 1 0 0 0 0 0 0 0 0 0 1 1 1 1
f1 17 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1
f2 18 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1
g1 19 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
g2 20 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
h1 21 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0
h2 22 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1
i1 23 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1
i2 24 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1
l1 27 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1
m1 28 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 1
n1 29 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 1 1
o1 30 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 1 1 1
A partir de este punto se elige al azar un cero, se unen conjuntos y se
actualizan unos con el mismo procedimiento como se crearon los elementos
de la poblacio´n inicial, con la diferencia que el ma´ximo nu´mero de elemen-
tos que puede contener un conjunto varia cada vez que se elige un cero de
la siguiente manera
n.m.e = (No.declasesporhorapermitidas) + INT (RND() ∗HOLG+ .5).
Rev.Mate.Teor.Aplic. (ISSN 1409-2433) Vol. 18(2): 215–229, July 2011
un algoritmo gene´tico para un problema de horarios 225
HOLG es la holgura en el nu´mero clases por hora permitidas que se puede
fijar para permitir que algunos conjuntos tengan ma´s elementos de los
permitidos. En la mayor´ıa de los problemas sirvio´ HOLG = 0, pero
para aquellos que no se encontro´ una solucio´n con cero violaciones se puso
HOLG = 1.
Despue´s de que la solucio´n esta´ formada, a los conjuntos se les asigna
al azar un nu´mero (que representa una hora) de tal manera que cada hora
disponible quede asignada a un conjunto y se evalu´a la solucio´n tal y como
se hizo anteriormente con los miembros de la poblacio´n inicial.
Bu´squeda local
Se evalu´a la mejora de que dos conjuntos cualesquiera intercambien el
nu´mero que les fue asignado (hora). Si hay mejora, el intercambio mejor
evaluado se realiza y se actualiza la evaluacio´n de la solucio´n.
Se repite el procedimiento anterior hasta que no haya mejora posible
con este k2 intercambio.
Se evalu´a la mejora de que dos clases cualquiera intercambien su con-
junto contenedor, siempre y cuando no se violen restricciones del tipo “x
clase no puede darse a la misma hora que y clase”. Si hay mejora, el
intercambio mejor evaluado se realiza y se actualiza la evaluacio´n de la
solucio´n.
Se repite el procedimiento anterior hasta que no se encuentre mejora
alguna con este intercambio.
Se evalu´a la mejora de cambiar una clase cualquiera cuyo conjunto
contenedor tuviese un taman˜o mayor al ”nu´mero de clases por hora per-
mitidas”, a un conjunto cuyo taman˜o fuese menor al “nu´mero de clases
por hora permitidas”, siempre y cuando no se violen restricciones del tipo
”x clase no puede darse a la misma hora que y clase”. Si hay mejora o no
se modifica la evaluacio´n de individuo, el cambio mejor evaluado se realiza
y se actualiza la evaluacio´n de la solucio´n.
Se repite el procedimiento anterior hasta que no se encuentre un cambio
que al menos no modifique la evaluacio´n del individuo.
Actualizacio´n de la siguiente generacio´n
Si la solucio´n generada es parecida al mejor de los padres, es igualmente
evaluada y cada hora fue asignada de manera igual o ma´s homoge´neamente,
se cambia en la poblacio´n el padre mejor evaluado por el hijo.
Si no pasa lo anterior, la solucio´n generada es igualmente evaluada que
el peor de los padres y cada hora fue asignada de manera igual o ma´s
Rev.Mate.Teor.Aplic. (ISSN 1409-2433) Vol. 18(2): 215–229, July 2011
226 c. pe´rez — j. ram´ırez
homoge´neamente se cambia en la poblacio´n el padre peor evaluado por el
hijo.
Si la solucio´n generada es mejor evaluada que cualquiera de los padres,
se cambia en la poblacio´n el padre peor evaluado por el hijo.
Si no se logra nada de los tres pa´rrafos anteriores permanecen en la
poblacio´n ambos padres y el hijo se desecha.
4 Cota del ejemplo citado y resultados computa-
cionales
Cota del ejemplo citado
Conside´rese el problema con el que se ha venido trabajando (ver
pa´gina 219).
Proposicio´n 1 No existe una solucio´n en la que se asignen las horas a las
clases de manera homoge´nea (para este ejemplo cada hora ser´ıa asignada
dos veces) sin violar alguna de las restricciones.
Demostracio´n por contraejemplo:
Supongamos que existe una solucio´n donde se violen cero restricciones y
en la que las horas son asignadas ma´ximo 2 veces. Existen 5 materias de
tres clases que deben ser repartidas en lunes, mie´rcoles y viernes para que
no se viole ninguna restriccio´n. Ya que cada hora so´lo puede ser asignada
a cuando ma´s dos materias, so´lo quedar´ıa libre por asignar una hora del
lunes, una hora del mie´rcoles y una hora del viernes.
En el mejor de los casos podr´ıamos elegir que´ hora queda libre* en cada
uno de esos tres d´ıas, por ejemplo:
Hora/d´ıa lunes martes mie´rcoles jueves viernes
1 - * * - - *
2 - - - - - -
3 - - - - - -
Por otro lado, al so´lo haber 3 horas libres por asignar en lunes, mie´rcoles
y viernes, forzosamente tres(/) de las 5 materias de dos clases debera´n
de ser programadas para ser impartidas en martes y jueves. Utilizando
el principio del palomar podemos inferir que al menos una de esas tres
materias corresponde al mo´dulo III.
Hora/d´ıa lunes martes mie´rcoles jueves viernes
1 - * / * - / - *
2 - - / - - / - -
3 - - / - - / - -
Rev.Mate.Teor.Aplic. (ISSN 1409-2433) Vol. 18(2): 215–229, July 2011
un algoritmo gene´tico para un problema de horarios 227
De esta forma lo podemos ver como que existen so´lo tres casos, las
tres materias anteriores pertenecen al mo´dulo 3 o dos de las tres mate-
rias pertenecen al mo´dulo 3 o so´lo una de las tres materias pertenece al
mo´dulo 3.
Analizando el caso en que las tres materias pertenecen al mo´dulo 3
quedar´ıan por asignar del mo´dulo 3 las cuatro materias de una sola clase.
Ya que clases del mismo mo´dulo no deben de impartirse a la misma hora
so´lo quedar´ıan libres por asignar a estas cuatro clases la hora libre del
lunes, la hora libre del mie´rcoles y la hora libre del viernes. Por lo que
en este caso no hay forma de lograr una asignacio´n con cero restricciones
violadas.
Hora/d´ıa lunes martes mie´rcoles jueves viernes
1 - * H no (L o M
o N o O)
* - H no (L o M
o N o O)
- *
2 - - I no (L o M
o N o O)
- - I no (L o M
o N o O)
- -
3 - - J no (L o M
o N o O)
- - J no (L o M
o N o O)
- -
Analizando el caso en que dos de las materias pertenecen al mo´dulo 3,
por ejemplo:
Hora/d´ıa lunes martes mie´rcoles jueves viernes
1 - * F * * - F * - *
2 - - H no (L o M
o N o O)
- - H no (L o M
o N o O)
- -
3 - - I no (L o M
o N o O)
- - I no (L o M
o N o O)
- -
Quedar´ıan por asignar del mo´dulo 3 las cuatro materias de una sola
clase y una de las materias de dos clases; en total seis clases. Ya que clases
del mismo mo´dulo no deben de impartirse a la misma hora so´lo quedar´ıan
libres por asignar a estas 6 clases la hora libre del lunes, la hora libre del
mie´rcoles, la hora libre del viernes, una de las horas del martes y una de
las horas del jueves, en total 5 horas. Por lo que en este caso no hay forma
de lograr una asignacio´n con cero restricciones violadas.
Analizando el caso en que so´lo una materia pertenece al mo´dulo 3, por
ejemplo:
Hora/d´ıa lunes martes mie´rcoles jueves viernes
1 - * F * * - F * - *
2 - - G * - - G * - -
3 - - H no (L o M
o N o O)
- - H no (L o M
o N o O)
- -
Rev.Mate.Teor.Aplic. (ISSN 1409-2433) Vol. 18(2): 215–229, July 2011
228 c. pe´rez — j. ram´ırez
Quedar´ıan por asignar del mo´dulo 3 las cuatro materias de una sola
clase y dos de las materias de dos clases; en total ocho clases. Ya que clases
del mismo mo´dulo no deben de impartirse a la misma hora so´lo quedar´ıan
libres por asignar a estas 8 clases la hora libre del lunes, la hora libre del
mie´rcoles, la hora libre del viernes, dos de las horas del martes y dos de
las horas del jueves, en total 7 horas. Por lo que en este caso no hay forma
de lograr una asignacio´n con cero restricciones violadas.
En los tres casos no hay forma de lograr una asignacio´n con cero res-
tricciones violadas, por lo que podemos concluir que no existe tal solucio´n
bajo las consideraciones antes planteadas.
Del mismo modo podemos concluir que una solucio´n donde no se violen
ninguno de los dos tipos de restricciones mencionadas en ente trabajo, debe
permitir al menos que en una hora sean impartidas 3 materias. Y en caso
de que se logre esto permitiendo que so´lo en una hora se den 3 clases, esta
solucio´n sera´ la o´ptima.
Resultados computacionales
La tabla 1 muestra los resultados computacionales para distintas instan-
cias. Para una de las dos instancias (EDDC96441) en las que el GRASP
no pudo encontrar una solucio´n con cero violaciones en la que cada hora
fuese asignada un nu´mero igual de veces, el Algoritmo Gene´tico logro en-
contrarla; para la otra instancia (ED4) se demostro´ que aunque hay una
clase fuera de lugar (fue asignada una hora a ma´s clases de las permitidas)
en las soluciones encontradas con GRASP y el Algoritmo Gene´tico (AG),
no hay mejor solucio´n que pueda ser encontrada.
# ve´rtices Instancia # colores ¬GRASP ¬AG o´ptimo
30 ED4 15 1 1 s´ı
30 A42 15 0 0 s´ı
60 ECA864 20 0 0 s´ı
60 976532 20 0 0 s´ı
90 EDDC96441 30 1 0 s´ı
90 DCB875322 30 0 0 s´ı
120 EEDCCBA87644 30 0 0 s´ı
Tabla 1: Resultados computacionales para distintas instancias. La
columna ¬GRASP indica el No. de clases “fuera de lugar” con GRASP y la
columna ¬AG el No. de clases “fuera de lugar” con el algoritmo gene´tico.
Rev.Mate.Teor.Aplic. (ISSN 1409-2433) Vol. 18(2): 215–229, July 2011
un algoritmo gene´tico para un problema de horarios 229
5 Conclusiones
Basados en los resultados anteriores se puede concluir que utilizar el Al-
goritmo Gene´tico desarrollado en este trabajo es una buena opcio´n para
problemas de asignacio´n de horarios con restricciones adicionales del tipo
“debe haber al menos d d´ıas entre dos eventos”.
En el desarrollo del algoritmo se manejo´ holgura en el nu´mero de colo-
res (horas) y holgura en el nu´mero de clases permitidas por hora; con tal
de obtener soluciones en las que no se violaran ninguno de los siguientes
dos tipos de restricciones: dos eventos no pueden realizarse el mismo d´ıa
y debe haber al menos d d´ıas entre dos eventos. Al parecer dejar que al-
gunos miembros de la poblacio´n tuviesen un nu´mero de colores mayor al
establecido no aporto nada de informacio´n pero dejar en algunas soluciones
holgura en el nu´mero de clases permitidas por hora aporto valiosa infor-
macio´n que permitio´ llegar al o´ptimo ma´s ra´pidamente para las instancias
citadas.
Referencias
[1] Lara, P.; Lo´pez, R.; Ramı´rez, J.; Ya´n˜ez, J. (2010) “SA model for
timetabling problems with period spread constraints”, Journal of
Operational Research Society 173: 1–6.
[2] Ramı´rez-Rodr´ıguez, J. (2001) Extensiones del Problema de Colo-
racio´n de Grafos. Tesis de Doctorado, Universidad Complutense
de Madrid, Madrid.
[3] Grimaldi, R. (2009) Matema´ticas Discreta y Combinatoria, Una
introduccio´n con Aplicaciones. Prentice Hall, Me´xico.
[4] Ya´n˜ez, J.; Ramı´rez, J. (2003) “The Robust Coloring Problem”,
European Journal of Operational Research 148(3): 546–558.
Rev.Mate.Teor.Aplic. (ISSN 1409-2433) Vol. 18(2): 215–229, July 2011