Instituto Tecnologico De Ciudad Madero

El problema de programación de horarios. Uso de una colonia de hormigas __________________________________________________________________________________

INSTITUTO TECNOLOGICO DE CIUDAD MADERO

ASIGNATURA: ANALISIS Y DISEÑO DE ALGORITMOS II PROFESOR: DR. RODOLFO PAZOS RANGEL PRESENTA: CALOCA CASTILLO JOSÉ DE JESÚS INVESTIGACION: EL PROBLEMA DE PLANIFICACION DE HORARIOS.

AGOSTO-DICIEMBRE 2009

1

El problema de programación de horarios. Uso de una colonia de hormigas __________________________________________________________________________________

Descripción del problema Todos los seres humanos que realizamos una actividad nos vemos en la necesidad de planificar, para recordar tareas derivadas de nuestra actividad principal. A menudo lo más simple es recordar mentalmente o anotarlo en algún sitio visible. Sin embrago en el ámbito empresarial resulta mucho mas complicado saber cuales serian las fechas de entrega exacta tiempos de holgura, etc. dado que en este tipo de sitios suele tener un costo elevado. La programación de horarios es un ejemplo palpable en una institución educativa como I.T.C.M. ya que las clases se imparten en una hora y sitio asignado y nadie mas puede ocupar ese sitio en ese lapso más que las personas a quienes se les asigno previamente. El problema de programación de horarios tiene sus orígenes en la segunda guerra mundial, donde la necesidad de abastecimiento a las operaciones militares era urgente. El Job Shop Scheduling Problem (en ingles) es un problema de optimización combinatoria que de acuerdo con Emmanuel Téllez Enríquez en su Tesis “Uso de una colonia de hormigas para resolver el problema de programación de horarios” “consiste, de forma genérica, en la asignación de un número determinado de actividades en un número finito de recursos disponibles. El objetivo al optimizar este problema es encontrar una permutación de dichas actividades que minimice el tiempo de término de todas las actividades en conjunto” (Pág. 6,2007)

Definición formal del problema Un JSSP clásico esta determinado por el tamaño m X j donde j es el numero de trabajos desde j= {J1, J2.... NJ} y M el conjunto de maquinas del problema desde {Mi…..Mm}. Donde deberá de existir una relación para cada J con una M La relación de cada trabajo con cada máquina conforma una relación binaria NJ --Mm llamada Operación (Jam).

1

El problema de programación de horarios. Uso de una colonia de hormigas __________________________________________________________________________________

Figura1. Representación grafica de la relación de tamaño j x m El total de operaciones del problema es denotado por OJM = {O1,1,O1,2,O1,3, . . . ,Oj,m}. El conjunto de operaciones O correspondientes al mismo trabajo es conocido como secuencia tecnológica S tal que S ={ Si....Sm } donde m es el numero de maquinas del problema por lo tanto para cada trabajo j tenemos una secuencia tecnológica OJS = {Oj1,Oj2,Oj3, . . . ,Ojs}. Esto debido a que el JSSP clásico se requiere que exista en cada secuencia tecnológica de trabajo por cada maquina del problema Cada operación (j,m) tiene asociado un tiempo denominado: tiempo de procesamiento, y es denotado por la letra t, este parámetro indica el tiempo requerido para el trabajo j en la maquina m. Representación de la soluciones Para la representación del modelo del problema Téllez usa un grafo disyuntivo como G=(V, C U D) . De donde se coloca un conjunto de V nodos representando las operaciones (trabajo maquina) y se añaden los tiempos de procesamiento de cada operación en la parte superior de cada una de ellas.

Figura 2. Construcción del grafo incluyendo nodos de inicio y término. Se coloca un conjunto de arcos conjuntivos C que indican la secuencia tecnológica de las operaciones.

2

El problema de programación de horarios. Uso de una colonia de hormigas __________________________________________________________________________________ Finalmente se añade el conjunto de arcos D disyuntivos que indican los pares de operaciones que se ejecutan en la misma máquina.

Figura 3. Grafo con los arcos conjuntivos y disyuntivos. Representación binaria. Al convertir los arcos disyuntivos en conjuntivos de un JSSP representado en el grafo el programa se convierte en semiactivo que según el mismo Téllez: “ Un programa semiactivo es el obtenido una selección completa consistente” (Pág. 13,2007) . Ejemplos de estos son los algoritmos evolutivos como el mismo sistema de colonia de hormigas abordado en esta investigación, métodos de aproximación como es el de búsqueda tabú. Para el etiquetado de cada uno de los arcos disyuntivos se usa un 0 o 1. Así un programa puede ser representado por una cadena de tamaño mj (j − 1) /2. La figura 2.8 muestra un ejemplo, donde un arco que conecta Oij y Okj (i < k) es etiquetado como 1 si el arco es dirigido de Oij a Okj (entonces Oij es procesada antes que Okj) o 0, si es el otro caso.

Figura 3. Representación binaria Por otra parte la representación por permutación consiste en conjunto de permutaciones de trabajos realizados por la maquina, donde hay m permutaciones de permutaciones del problema, la cadena que se forma es una matriz de secuencia de trabajos.

3

El problema de programación de horarios. Uso de una colonia de hormigas __________________________________________________________________________________ Las representaciones anteriores son apenas el esquema de codificación necesario para la resolución del problema, y se puede elegir el mas adecuado para la aplicación de la colonia de hormigas de acuerdo al tamaño del problema. Planes de trabajo. Se menciona en la sección anterior que un programa semiactivo presenta una selección, esto es con el fin de llevar a cabo el recorrido en el grafo equivalente a la solución. Una selección según Téllez es “es un conjunto de arcos dirigidos seleccionados de los arcos disyuntivos” (Pág. 12,2007) así una selección completa son todos los grafos disyuntivos seleccionados y completa consistente, si el grafo dirigido que resulta es acíclico. Importancia. Radica en que se presenta en casi todas las actividades de la vida cotidiana, como en este momento, mientras redacto estoy planificando (pensando la tareas que restan para el día de hoy). Sin embargo es difícil encontrar una solución óptima y de un coste bajo tanto de tipo computacional como de otro dado que las permutaciones se pueden incrementar en forma exponencial. En la sección siguiente abordaremos el sistema de hormigas y variantes como Ant Colony System.

sus

Sistema de hormigas (AS) Colonia de hormigas Las hormigas son capaces de seguir la ruta mas corta desde la colonia hasta una fuente de abastecimiento, al trasladarse cada una va dejando un rastro de feromona a lo largo de un camino seguido transmitiéndose información entre ellas. Al iniciar la búsqueda esta es realizada a ciegas ya que, pero si otras hormigas siguen los rastros de feromona estas seguirán el de mayor cantidad, que es donde se encuentra la mayor probabilidad de encontrar alimento.

Fig. 4. Comportamiento de las hormigas reales 4

El problema de programación de horarios. Uso de una colonia de hormigas __________________________________________________________________________________

En la figura 4a a las hormigas se les presenta un doble camino y deciden de forma aleatoria, en consecuencia se puede decir que la mitad irian a un lado y la otra al otro., como se muestra en la figura 4b, las que eligieron el camino mas corto llegaran mas rápido al otro extremo, dejando depositada mayor cantidad de feromona, la mayor densidad en la cantidad de feromona hace mas deseable ese camino. Considerando la evaporación de la feromona, hace que los caminos menos transitados sean cada vez menos deseables, por que resulta claro que al cabo de un tiempo todas las hormigas transiten por el camino mas corto como se muestra en la figura 4d.

La estructura genérica de un ACO es la siguiente: 1 procedimiento nueva_hormiga(id_hormiga) 2 inicializa_hormiga(id_hormiga) 3 L = actualiza_memoria_hormiga() 4 mientras (estado_actual ≠ estado_objetivo) 5 P = calcular_probabilidades_de_transición(A,L,W) 6 siguiente_estado = aplicar_política_decisión(P,W) 7 mover_al_siguiente_estado(siguiente_estado) si (actualización_feromona_en_línea_paso_a_paso) 8 depositar_feromona_en_el_arco_vistado() fin si 9 L = actualizar_estado_interno() 10 fin mientras si (actualización_feromona_en_línea_a_posteriori) 11 para cada arco visitado 12 depositar_feromona_en_el_arco_visitado() 13 fin para fin si 14 liberar_recursos_hormiga(id_Hormiga) 15 fin Procedimiento 1 2 3 4 5

procedimiento metaheurística_ACO() inicialización_de_parámetros mientras (criterio_de_terminación_no_satisfecho) programación_de_actividades hormigas_y_actividad()

5

El problema de programación de horarios. Uso de una colonia de hormigas __________________________________________________________________________________ 6 evaporación_de_feromona() 7 acciones_del_demonio() {opcional} 8 fin programación_de_actividades 9 fin mientras 10 fin procedimiento 1 2 3 4 5

procedimiento hormigas_y_actividad() repetir en paralelo desde k=1 hasta número_hormigas nueva_hormiga(k) fin repetir en paralelo fin procedimiento

Adaptación del AS a un JSSP 1 Fase de inicialización Inicializar contador de ciclos NC Para cada arco (i, j): valor inicial de _ij = c; donde c es una constante positiva pequeña __ij = 0 Colocar MAXH hormigas en N operaciones 2 Colocar la primera operación en lista tab´uk de cada hormiga 3 Repetir hasta llenar tabú Para cada hormiga: Elegir próxima operación a ser visitada según ecuación (4.1) Mover la hormiga a la próxima operación Insertar la operación en tabú 4 Repetir para cada hormiga k Calcular el makespan Lk del programa generado Guardar el programa de makespan mías chico hasta el ciclo NC : LNC 0 = min n LNC−1 0 mink {Lk} o Para cada arco (i, j) Calcular __ij según ecuación (4.3) 5 Para cada arco (i, j) Actualizar _ij según ecuación (4.2) __ij = 0 6 Aumentar el contador de ciclos NC Si NC < Ncmax entonces Vaciar tabú Ir a la fase 2 Sino Imprimir

6

El problema de programación de horarios. Uso de una colonia de hormigas __________________________________________________________________________________ En el planteamiento del problema al inicio se vio que, dos operaciones se realizan sobre un mismo arco con lo que no se puede saber si transito de i a j o de j a i con exactitud, lo que propone Téllez es utilizar arcos individuales de esta manera, si se puede determinar cuantas hormigas en pasado por el arco y así saber la precedencia de operaciones

Figura 5. Arcos individuales Como se observa, cuando se tienen arcos individuales se puede ver que en la operación i,j quedara depositada mayor cantidad de feromona que en i,k y al momento de hacer cálculos probabilístico , este arco será mas deseable para la siguiente operación. Esta es una de las principales modificaciones, ya que permite saber exactamente cuanta cantidad de feromona se a depositado. Otra modificación es la exploración en el 10 % de los ciclos de esta manera solo se quedaran, los ciclos en los que se observo mayor cantidad de feromona, y servirán de base para la exploración del restos haciendo el algoritmo menos extenuante. Dicha exploración se hace de foma aleatoria. Este algoritmo pretende resolver varios casos, así también propone un método en el que plantea explorar lo que Téllez llama distribución inversa, donde se caluca asi :

1/ valor de la feromona del arco

7

El problema de programación de horarios. Uso de una colonia de hormigas __________________________________________________________________________________ Esto es con el fin de que el algoritmo pueda visitar arcos no tan explorados, aumentando la feromona, en los arcos menos, explorados y por supuesto disminuyéndola en el resto. Otro mecanismo propuesto es el de actualización, en cierto porcentaje de hormigas, el cual pretende explorar de forma similar al anterior, es decir explorar arcos no tan visitados, con lo que se podrían incluir, hormigas con resultados malos. Todas las anteriores adecuaciones pretenden diversificar, como ya se pudo dar cuenta a los programas. Se pretende que el algoritmo ayude a calcular el desperdicio de tiempo, esto verificando la precedencia de operaciones, disminuyendo la cantidad de feromona en el arco (i,j) en forma proporcional según Téllez al desperdicio de tiempo. :

Figura 6. Desperdicio de tiempo. En la figura seis se muestra que la operación (0,1) precede a la (1,1) donde solo hubo un tiempo de holgura de 5 unidades entre J1 Y J3 lo que disminuye la feromona en un 5%. El cálculo queda dado por:

8

El problema de programación de horarios. Uso de una colonia de hormigas __________________________________________________________________________________ Y la nueva cantidad de feromona será:

De esta forma se espera que las hormigas no vayan por los arcos con mayor desperdicio de tiempo. Enseguida se muestra el pseudo codigo final

9

El problema de programación de horarios. Uso de una colonia de hormigas __________________________________________________________________________________ De acuerdo a el análisis de resultados el algoritmo no tuvo problema para instancias (10 × 5, 15 × 5 y 20 × 5), anque ante algoritmo de comparación con instancias (10 × 10, 15 x 10, 20x10 y 30 x 10), no logro alcanzar los mejores resultados. De cualquier forma es un algoritmo con un buen rendimiento que implementado, en una explosión demográfica promedio, puede dar resultados altos en comparación de algoritmos meramente puros o tradicionales del propio sistema de colonia de hormigas. Consultas Realizadas TELLEZ Emmanuel, Tesis. Uso de una Colonia de Hormigas para

resolver Problemas de Programación de Horarios, 2007 MENDEZ Evelyn, Meta heurística de Optimización mediante Colonias de Hormigas y Aplicaciones, 2007

10