exposicion 1

PLANIFICACIÓN DE HORARIOS DE TRABAJO
RESUMEN: La planificación de los horarios de trabajo (Timetabling)
ha sido uno de los primeros problemas a los que se ha aplicado
los AGs con notable éxito. Como ejemplo de este tipo de
aplicaciones se puede citar el problema de la planificación de los
exámenes o de las clases en Universidades, la asignación de turnos de
trabajo en empresas, etc.

• En losproblemas de planificación horaria se busca que unos
eventos (e1, e2,...) puedan llevarse a cabo en unos intervalos de
tiempo prefijados (t1, t2,...). Por ejemplo, a la hora de planificar
las fechas de los exámenes en una universidad, se considera que
los eventos son los exámenes y los intervalos de tiempo
representan el día y hora de celebración del examen. Cuando se
realiza la planificaciónhoraria de los exámenes surgen una serie
de limitaciones al asignar los eventos a los intervalos de tiempo;
por ejemplo,

• puede haber una restricción del número de plazas, una limitación del
número de profesores, etc. En general, en los problemas reales se
puede considerarse que existen tres grupos de limitaciones a la
hora de diseñar la planificación (limitaciones fuertes, débiles y otrasrestricciones) estudiado por Fang en 1992. Por ejemplo, una limitación
fuerte puede ser: un mismo estudiante no puede tener más de dos
exámenes al mismo tiempo; una débil: preferencia por no tener dos
exámenes en la misma mitad del día; y una limitación del grupo de otras
restricciones puede ser: procurar que los exámenes se distribuyan de forma
homogénea a lo largo del periodo de exámenes. Cada uno deestos
grupos tendrá una ponderación diferente en la función de evaluación como
se verá posteriormente.

• 2. METODOLOGÍAS DE SOLUCIÓN.
• El tipo de codificación utilizada en estos problemas es muy
similar a la utilizada en los problemas de secuenciación
comentados en el apartado anterior. Para explicarlo utilizaremos
un ejemplo que consiste en la ordenación de doce exámenes de
forma que se puedanrealizar en diez intervalos de tiempo, un
ejemplo de esta codificación es (1,3,9,6,2,10,1,6,2,7,5,4). Cada uno de
los genes representa un examen, y el alelo representa en que
intervalo de tiempo debe celebrarse el examen. La interpretación
del genotipo es la siguiente, el primer gen indica que el primer
examen se debe celebrar en el primer intervalo temporal, el
segundo gen informa que el segundoexamen se tiene realizar en el
tercer intervalo temporal, etc.

La principal dificultad de este tipo de problema es el cálculo del fitness, pues su coste computacional es muy
elevado. Normalmente, para calcularlo se utiliza la fórmula:

Siendo Wj el peso que se da a cada una de las restricciones y
vj(c, t) una variable dicotómica que vale '1' si la restricción c
es violada por la solución t y '0' encaso contrario; asimismo,
en esta fórmula se suponen todas las penalizaciones
positivas, en caso contrario podría suceder que el fitness
fuese negativo y no se podría utilizar dicha función para
calcularlo. Con estas aclaraciones, se puede deducir que la
solución proporcionada por la función es 1, si y sólo si, son
satisfechas todas las limitaciones, en caso contrario su valor es
menor que launidad.

• La fase de selección de los criadores presenta algunas peculiaridades, se utiliza una
selección del tipo 'elitismo + ruleta'. Su funcionamiento se basa en el empleo del método de la
ruleta para la selección de las tres cuartas partes de los criadores, y el resto está compuesto por
los mejores resultados obtenidos hasta el instante actual, los cuales son introducidos
directamente en loscriadores.
• 
• Los operadores genéticos utilizados para este tipo de problema no tienen peculiaridades
destacables, para el cruce se suele utilizar el c' ruce simple', aunque en algunas ocasiones
también se utiliza el 'cruce uniforme'; en cuanto a la mutación, el método más utilizado
es la 'mutación numérica estacionaria' (Goldberg,89). En los parámetros de los AGs, la
principal característica es...