ALGORITMO DE RECOCIDO SIMULADO APLICADO AL PROBLEMA DE SECUENCIA MIENTO REGULAR

ALGORITMO DE RECOCIDO SIMULADO APLICADO AL

PROBLEMA DE SECUENCIA MIENTO REGULAR

1) Modelo

El objetivo es encontrar la secuencia de los trabajos a programar la minimiza el Makespan, que corresponde al tiempo en el cual el último trabajo es finalizado en la máquina m. El problema investigado usualmente es denotado por n/m/P/ Cmax y definido de la siguiente forma: Si se tienen los

tiempos de procesamiento p(i,j) para el trabajo i, en la máquina j, y la secuencia de trabajo [J1,J2,…,Jn]

donde se calcula el tiempo completo de procesamiento o Makespan C(Ji, j). Cada tarea debe pasar por todas las máquinas, siendo que todas las tareas tienen el mismo orden de procesamiento. Es decir, la secuencia de tareas en cada máquina es la misma. Por otro lado, cada máquina mi puede procesar sólo una tarea nj a la vez.

Por ejemplo, para un problema simple de 4 tareas y 3 máquinas, los tiempos de procesamiento P y la secuencia π tienen la forma mostrada en la siguiente figura Además, los máximos tiempos de procesamiento en cada máquina son definidos en el vector r.

Para encontrar el valor de la función objetivo, dada una secuencia π de tareas, se utiliza una

[pic 1]

matriz auxiliar Cmxn en la cual se almacenan los diferentes tiempos de procesamiento en forma secuencial. En la construcción de esta matriz se siguen los siguientes pasos:

1. Se obtiene el tiempo de procesamiento de la primera tarea en la primera máquina y se almacena en la matriz C.

                                  [pic 2] (1)

1. Usando la ecuación (2) se calcula el tiempo de procesamiento de todas las tareas en la primera máquina de la línea de producción, con jϵ[2,3,..,n]

                          [pic 3] (2)

1. Usando la ecuación (3) se calcula el tiempo de procesamiento de la primera tarea en cada una de las máquinas.

     [pic 4] (3)

1. Usando la ecuación (4), con jϵ{2,3,…,n}, e iϵ{2,3,…,m}, y con la información recopilada hasta el momento en la matriz C, se calcula el resto de sus elementos.

     [pic 5] (4)

También, es común incorporar restricciones en los tiempos de procesamiento de cada tarea, a fin de cumplir con tiempos de entrega. En este caso se cuenta con la información de tiempos máximos de entrega dados en un vector r de tamaño n. Una forma de evaluar la calidad de una alternativa de solución, teniendo en cuanta estas restricciones, es penalizando la función objetivo.

El problema de Flowshop que se describe puede ser representado gráficamente como se muestra en la Figura 2, donde se asume una secuencia

• = [4, 3, 1, 2]. Las barras debajo de cada máquina representan, proporcionalmente, los tiempos de procesamiento definidos en P.

En la siguiente se muestra una representación gráfica de la información contenida en la matriz C, en donde es fácil verificar cualquier violación de los tiempos máximos de entrega.

[pic 6]

2) Metodología

La idea original que dio lugar a la metaheurística denominada Recocido Simulado (RS), se encuentra en el Algoritmo de Metrópolis. Este algoritmo se basa en la técnica de Monte Carlo para generar una secuencia de estados del sólido en su proceso de enfriamiento. Si se tiene un estado actual del sólido i con energía Ei, entonces el subsiguiente estado j con energía Ej es generado aplicando un mecanismo de perturbación consistente en provocar una pequeña distorsión en el estado actual. Si la diferencia de energía entre estados, (Ej-Ei) , es menor o igual a cero, el estado j es aceptado como el estado actual. Si la diferencia de energía es mayor a cero, el estado j tiene una cierta probabilidad, Φji, de ser aceptado. Dicho valor es determinado por el factor de Boltzmann, tal como se expresa en la ecuación (5).

                                              [pic 7] (5)

donde T denota la temperatura, y KB es una constante física conocida como constante de Boltzmann. El algoritmo de RS es concebido para problemas de minimización y, por lo tanto, siempre se considera que existe un mejoramiento del estado

[pic 8]

Diagrama de Ganttcon m =3,n = 4 y π =[4, 3, 1, 2].

actual cuando Ej-Ei ≤ 0. Sin embargo, en términos generales, un mejoramiento existe cuando se presenta un decremento en la energía del sistema.

En optimización, un movimiento (paso de una alternativa a otra ubicada en su vecindario) será aceptado si éste mejora la función objetivo; o en caso contrario, si su probabilidad de aceptación es mayor que un número aleatorio uniformemente distribuido. Este tipo de estrategias permiten que el algoritmo escape de óptimos locales. Por otro lado, y con el fin de avanzar en la convergencia a una solución, en la medida en que evoluciona el método de optimización se disminuye la tempera-tura y se incrementa la longitud de la cadena. Con esto disminuye la probabilidad de aceptar soluciones de mala calidad. La codificación del problema define el espacio de búsqueda y por consiguiente la estructura de vecindad. Este aspecto juega un papel fundamental en la eficiencia del algoritmo debido al concepto de proximidad entre estados energéticos. En un sistema real un estado energético es una transformación continua del estado energético anterior, y por lo tanto, una pequeña perturbación produce un pequeño cambio energético. En un problema de optimización combinatoria, una inadecuada definición de un vecino podría, eventualmente, producir grandes diferencias con respecto a la función objetivo, lo cual es indeseable para el algoritmo de RS.

...