Optimizació n de la próducció n para próblemas de ‘Flów-Shóp’ Multióbjetivó Mediante la Utilizació n de Metaheurí sticas

Investigación de Operaciones Sesión 14 Tomado de: Oscar Abel San Martín Contreras

Introducción

Las Metaheurísticas son un medio eficiente para resolver problemas reales en un tiempo

aceptable. Al enfrentarse a un proceso de optimización, donde dadas ciertas condiciones y

limitaciones se trata de elegir de entre una serie de alternativas, la que nos entregue, en la

medida de lo posible, el mayor beneficio que se pueda obtener, pero el gasto de recursos

en determinar cual es la mejor opción, puede ser muy alto.

Dado esto, las técnicas, procedimientos y/o algoritmos que ayudan a resolver un problema

de optimización merecen un profundo análisis. Casi todo problema se enmarca en una

estructura común, como lo menciona B. Philippi (1988), “Por una parte deben existir

opciones o cursos de acción entre los cuales se debe poder escoger. Si la opción es única,

ciertamente el problema es muy simple”, otro punto es “que este proceso requiere el poder

comparar las ventajas y desventajas de los cursos de acción posibles”. Al saber qué es lo

que se quiere lograr, se puede tener claro los criterios de evaluación de las alternativas, y

de esta forma tomar una decisión.

Así, es imprescindible para una industria el contar con herramientas que le ayuden en este

proceso. Esto es porque habitualmente las alternativas posibles llegan a ser casi infinitas,

los criterios de evaluación pueden ser numerosos, las limitaciones variadas, etc.

Flow-Shop es un modelo de planificación de tareas, donde se tiene una serie de trabajos, y donde cada uno de ellos consiste a su vez en una serie de tareas que son llevadas a cabo por un conjunto de máquinas que deben seguir las siguientes características básicas: Cada máquina realiza una sola tarea y

para un trabajo a la vez. Las tareas requieren una sola tarea para

ser completadas (en caso de no utilizarse la máquina, su tiempo es cero).

Los trabajos pasan por cada máquina una sola vez.

El orden de las máquinas es siempre el mismo.

La evaluación de alternativas que

ayuden a industrias que procesen

trabajos en máquinas secuenciales (o

cualquier organización que tenga

procesos que se asimilen a

procesamiento lineal de trabajos), lo

que se llamará procesamiento de tipo

Flow-Shop, es un objetivo que se

persigue, para lograr optimizar sus

procesos de programación de tareas, y

así lograr un mejor uso de sus recursos

materiales y lograr eficiencia en la

producción.

Al comparar dos alternativas para la resolución de este tipo de problemas lo que se busca

es poder responder preguntas como ¿Cuál de las dos Metaheurísticas tiene un mejor

comportamiento?, ¿Cuál necesita mejoras para poder competir con la otras?, ¿Cuál es más

eficiente?, ¿Cuál es más eficaz?, entre otras.

También, el poder determinar formas en las cuales mejorar una, o ambas Metaheurísticas

de ser posible, es algo que se espera obtener. Además de entregar observaciones que

permitan trabajos futuros.

Justificación

En una industria, y en otras actividades, donde se ejecutan procesos en una forma

secuencial (Flow-Shop), es decir, se forma una cola en una línea de producción y estos

trabajos deben pasar por distintas máquinas en un mismo orden, se debe optimizar ciertos

objetivos, como son el tiempo total de procesos o lo relativo al momento de entrega de un

trabajo, entre otros. Si se combinan estos objetivos en un solo problema, se tiene un

problema de Flow-Shop Multiobjetivo. En la práctica los problemas Multiobjetivo son los

más comunes, dado que las decisiones, generalmente, se toman considerando más de un

aspecto.

Por esto es interesante estudiar cómo las Metaheurísticas nos ayudan en la solución de

este tipo de problemas. Esto debido a que los algoritmos de métodos exactos existentes

para encontrar soluciones óptimas, tienen un tiempo de proceso exponencial, porque

buscan en todo el espacio de soluciones y esto es ineficiente, y en algunos casos se vuelve

imposible.

Por otra parte las heurísticas no dan una certeza absoluta de qué tan buena es una

solución encontrada, pudiendo ésta ser, o no, mejorada.

Los problemas de tipo Flow-shop Multiobjetivo no han sido muy estudiados, son pocas las

publicaciones relacionadas con este tema específico, por lo que se hará una recopilación

bibliográfica tomando investigaciones similares aunque sólo consideren los temas

involucrados individualmente.

El motivo por el cual se implementarán y comparan una Metaheurística basada en

Simulated Annealing y otra en Algoritmos Genéticos, es porque:

Primero, prácticamente no hay publicaciones en las que Simulated Annealing resuelva este

tipo de problemas, y dado que para problemas con un solo objetivo se ha demostrado que

es una muy buena Metaheurística, vale la pena investigar su comportamiento en

problemas con más de un objetivo.

Segundo, los Algoritmos Genéticos han sido ampliamente investigados y son una muy

buena alternativa para solucionar problemas multiobjetivo y existen muchas publicaciones

al respecto. Tercero, es interesante la comparación entre estas dos muy distintas

Alternativas de solución para problemas multiobjetivo.

Capítulo 1. TEMAS RELACIONADOS

1.1 Optimización

Al tener una serie de alternativas entre las cuales poder elegir, lo natural e intuitivo es

querer elegir la mejor de ellas. El proceso de determinar cuál de éstas es la mejor,

considerando los criterios que se han establecido, el objetivo que se quiere lograr, las

ventajas y desventajas de cada opción, y todas las variables que puedan influir en la

decisión, se denomina optimización.

En general un problema de optimización se define como:

Optimizar f(X)

Sujeto a

gi(X) { ≤, = , ≥ } bi; i=1,…,m;

“Donde X es el vector de variables de decisión con n elementos {x1, x2,…, xn}; y las

funciones f(X) y gi(X) son funciones generales.

Cuando todos los elementos en el Vector X toman valores discretos, se conoce como un

problema de optimización combinatorio” (Moraga, 2002).

Así, por ejemplo, una persona tiene cierta cantidad de dinero, y está pensando en gastarlo

en varios productos, pero la suma de los precios de estos artículos es mayor que la

cantidad que posee, el modelo sería como sigue:

Maximizar el beneficio que le ofrecen los productos

Sujeto a

Precio producto1 + Precio producto2 +… + Precio producto n ≤ $ disponible

Con

Precio producto 1 = cant. 1

Precio producto 2 = cant. 2

---

Precio producto n = cant. N

En este sencillo ejemplo se pueden identificar las partes de la formulación de un modelo

del problema. La decisión que tome esta persona dependerá de los criterios que haya

definido para elegir, por ejemplo, si piensa que ciertos productos le son más necesarios, se

decidirá por estos, siempre que la suma de los precios no sea mayor a lo que dispone. Pero

si piensa que un producto que no necesita tanto, pero está muy barato y es una gran

oportunidad el adquirirlo, entonces si vale menos de lo que posee, se podría decidir por él.

Pero esta es una decisión muy simple. En la industria, las decisiones son muy complejas

(Moraga, 2002), en seguida se presenta un ejemplo:

En un sistema existen n tareas que deben ser procesadas, la idea es hacer la combinación para que el tiempo

total de procesamiento de estas tareas sea el mínimo.

Se asume que las n tareas están ya en el sistema para comenzar a ser procesadas en el tiempo R. Supongamos

que se tienen 5 tareas, con sus respectivos tiempos de proceso.

Tarea 1 = 180

Tarea 2 = 40

Tarea 3 = 200

Tarea 4 = 500

Tarea 5 = 250

Tarea 6 = 150

a) Aplicando la regla FIFO, se obtendría lo siguiente:

Solución

Tarea 1 - Tarea 2 - Tarea 3 - Tarea 4 - Tarea 5 - Tarea 6

Con un tiempo total de: 180 + 220 + 420 + 920 + 1170 + 1320 = 4230

b) Aplicando la regla SPT (tiempo de proceso más corto) se obtendría lo siguiente:

Solución:

Tarea 2 - Tarea 6 - Tarea 1 - Tarea 3 - Tarea 5 – Tarea 4

Con un tiempo total de: 40 + 190 + 370 + 570 + 820 + 1320 = 3310

Aquí podemos ver que usando la regla SPT se logra una mejor solución que utilizando la

regla FIFO.

Pero el total de combinaciones que se puede conseguir en este problema está dado por

factorial del número de trabajos, eso sería 6! = 720 combinaciones posibles. Lo que

muestra que analizar todas las posibles secuencias de trabajos puede resultar un trabajo

arduo, y a veces imposible.

A continuación se presenta una tabla donde se muestren las combinaciones posibles para

el número de trabajos que se indica:

Tabla 1.1: Número de soluciones posibles para el número de trabajos dado

Nro. Tareas Nro. De combinaciones Posibles

6

7

8

…

20

21

22

23

24

25

…

30

31

32

720

5.040

40.320

….

432.902.008.176.640.000

51.090.942.171.709.400.000

1.124.000.727.777.610.000.000

25.852.016.738.885.000.000.000

620.448.401.733.239.000.000.000

15.511.210.043.331.000.000.000.000

….

265.252.859.812.191.000.000.000.000.000.000

8.222.838.654.177.920.000.000.000.000.000.000

263.130.836.933.694.000.000.000.000.000.000.000

Por lo que se puede ver, aún con el computador más potente, resulta imposible poder

esperar el proceso para la tomar la decisión de cual es la mejor solución, ya que, por

ejemplo, para computar todas las posibles soluciones para 32 tareas, esto es 32! =

1.6*1035, suponiendo que “una computadora puede examinar mil millones de secuencias

por segundo, ¡tomaría 8.4 * 1015 siglos!” (Sipper y Bulfin, 1998). Para 16 tareas se calcula

aproximadamente en 8 meses el procesamiento de las combinaciones posibles para

determinar cuál será la óptima (Sipper y Bulfin, 1998).

Como en la industria muy pocos sistemas de planificación consideran tan pocos trabajos, y

no se puede disponer del tiempo para esperar los resultados de algoritmos exactos, dado

la limitada capacidad de proceso de los computadores, se hace necesario elaborar nuevos

procedimientos que permitan realizar este procesamiento en un tiempo aceptable, así

nacen las heurísticas.

1.2 Heurísticas

Una Heurística es una técnica que busca soluciones (ojalá cercanas al óptimo) a un costo

computacional razonable, pero no garantiza que la solución encontrada en realidad está

cerca del óptimo, ni da indicios de qué tan buena es. Es importante mencionar que una

heurística no considera todas las combinaciones posibles para determinado problema,

sólo unas pocos.

En general una heurística puede ser clasificada como Heurística de Construcción o

Heurística de Búsqueda local.

1.2.1 Heurísticas de Construcción

Lleva a cabo una secuencia estructurada de iteraciones, en la que se toman en cuenta

todos los aspectos que se considerarán para la toma de la decisión y se termina con una

solución factible. Se tiene una función que evalúa la calidad de la solución.

Una heurística de construcción, o regla, es un procedimiento que sistemáticamente asigna

valores a cada xi (i=1,…, n) en un número finito de pasos.

Algunas heurísticas de construcción son:

• FIFO (primero en llegar, primero en salir)

• SPT (Tiempo de proceso más pequeño)

• LPT (Tiempo de proceso más grande)

1.2.2 Heurísticas de Búsqueda Local

Para definir qué es búsqueda local, se requiere especificar un vecindario local. La

búsqueda se realiza desde una solución inicial que se modifica a través de operadores.

Dada una solución X, los elementos del vecindario de X son aquellas soluciones X’ que

pueden ser obtenidas aplicando sobre X una modificación elementaría conocida como

“movida”, y no se suele guardar historia del camino recorrido. Una movida, por ejemplo,

puede ser el “intercambio” o la “inserción”.

Supongamos que tenemos la siguiente secuencia de tareas:

X = Tarea 1 – Tarea 2 – Tarea 3 – Tarea 4 – Tarea 5

Un intercambio se refiere a tomar dos tareas de esta secuencia y poner una en la posición

de la otra y viceversa. Así, por ejemplo, las siguientes secuencias serían vecinos de X:

X’ = Tarea 2 – Tarea 1 – Tarea 3 – Tarea 4 – Tarea 5

X’ = Tarea 1 – Tarea 3 – Tarea 2 – Tarea 4 – Tarea 5

X’ = Tarea 4 – Tarea 2 – Tarea 3 – Tarea 1 – Tarea 5

Etc.

Una inserción constaría de tomar una tarea de la secuencia y ponerla en cualquier otra

posición de la lista. Por ejemplo:

X’ = Tarea 2 – Tarea 3 – Tarea 4 – Tarea 1 – Tarea 5

X‘= Tarea 1 – Tarea 5 – Tarea 2 – Tarea 3 – Tarea 4

X’ = Tarea 5 – Tarea 1 – Tarea 2 – Tarea 3 – Tarea 4

Etc.

Pero desafortunadamente, los problemas a los cuales se enfrentan las industrias en sus

líneas de producción requieren de sistemas que entreguen soluciones mucho más

cercanas al óptimo que las que puede elaborar una heurística común. Así entonces, es

necesario considerar el uso de Metaheurísticas para la programación de la producción.

1.3 Metaheurísticas

En esta sección se interiorizará un poco en lo referente a las Metaheurísticas, pero no se

especificará ninguna, ya que existirá un capítulo completo dedicado al análisis de

Metaheurísticas.

“Una Metaheurística es un técnica de resolución iterativa que guía a una heurística

subordinada combinando de forma inteligente diferentes técnicas de exploración del

espacio de búsqueda; y utilizando estrategias de aprendizaje para estructurar la

información con objeto de encontrar de forma eficiente soluciones cercanas al óptimo”

(Osman y Laporte, 1996).

Las Metaheurísticas tienen que tener como un objetivo el escapar a óptimos locales que

pueda encontrar, con el fin de recorrer de forma basta todo el espacio de soluciones.

Una Metaheurística puede presentarse como:

Meta heurística = Construcción + Búsqueda Local + Estrategias y mecanismos para evitar

óptimos locales.

Una Metaheurística puede usar cualquier heurística o algoritmo subordinado que

entregue una solución inicial y factible para la etapa de construcción.

La búsqueda local puede utilizar una heurística de búsqueda local, esto es mediante

inserción, intercambio u otra, para definir la vecindad de la solución inicial. Y así evaluar el

primer vecino que se encuentre, el primero que mejore la solución, un vecino aleatorio,

etc.

Como estrategias para evitar óptimos locales se pueden mencionar las siguientes:

Permitir movimientos de empeoramiento de la solución actual.

Modificar la estructura de entornos.

Volver a comenzar la búsqueda desde otra solución inicial.

Diversificación, (alejarse del punto actual).

Algunas Metaheurísticas bien conocidas son:

1.3.1 Algoritmos Genéticos

Esta Metaheurística tiene su base, y nace, sobre la teoría de la evolución de las especies.

La idea es que en una población de individuos (soluciones iniciales), ésta es sometida a

acciones aleatorias, con las que se generan nuevos individuos (soluciones evolucionadas)

de los cuales se seleccionan los más aptos para que sigan evolucionando.

Construcción Generación Aleatoria + Búsqueda Local Cruzamiento & Mutación

1.3.2 Simulated Annealing

El nombre de esta Metaheurística nace del proceso de templado (Annealing) de los

metales.

Donde se calienta un metal y luego controladamente se va enfriando, si este proceso se

realiza rápidamente, el metal puede presentar imperfecciones, si se hace gradualmente las

propiedades de este metal serán mejores.

Esta Metaheurística utiliza un parámetro que va disminuyendo en cierta cantidad, según el

cual se realiza una búsqueda local, eligiendo un vecino cada vez que disminuye este

parámetro, mientras menor sea el valor de éste menos posibilidades de elegir un mal

vecino existen, el proceso se realiza hasta que este parámetro llegue a cero.

Construcción Generación Aleatoria + Búsqueda Local Probabilidad de aceptar malas

soluciones.

1.3.3 Tabú Search

La idea básica del método, es la de explorar el espacio de búsqueda de todas las soluciones

factibles por una secuencia de movimientos. Un movimiento de una solución a otra es el

mejor disponible, es decir, de todas las soluciones a las que se puede pasar se escoge la

que mejore más el o los objetivos deseados. Sin embargo, para escapar de un óptimo local

y para prevenir los ciclos, algunos movimientos, en una iteración en particular, son

clasificados como prohibidos o tabú. Los movimientos en tabú están basados en la historia

de la secuencia de movimientos a corto y largo término. Una implementación simple, por

ejemplo, puede clasificar un movimiento como tabú si el movimiento contrario ha sido

hecho recientemente o frecuentemente. Algunas veces, cuando es favorable, un

movimiento tabú puede ser realizado a pesar de todo.

Construcción Generación Aleatoria + Búsqueda Local Lista Tabú LTM, Criterio de

aspiración.

1.3.4 Meta-Raps

Meta-RaPS es una Metaheurística que realiza un proceso de búsqueda de soluciones un

número determinado de veces, en cada iteración construye una solución factible, a través

de la utilización de reglas de prioridad usadas en forma aleatoria y luego utiliza búsqueda

local y un proceso de mejoramiento. Cada vez que realiza el proceso mantiene la mejor

solución encontrada hasta ese momento.

Construcción Generación Aleatoria + Búsqueda Local Combinación aleatoria de

reglas.

1.4 Multiobjetivo

En la sección de optimización, se explicó de manera simple en que consistía encontrar “la

mejor” solución para un problema. Para un mejor entendimiento sólo se mencionó que

existía un Objetivo, que estaba en función de ciertas variables, cada una con una

ponderación, en base a la cual se tomaba una decisión, dependiendo de cual combinación

de variables optimizaba este objetivo, es decir, lo maximizaba o minimizaba según el caso,

y que esta combinación fuera factible de elaborar, o sea, que cumpla con las restricciones

del problema.

Pero en muchos casos un problema puede tener varias Funciones Objetivo, como por

ejemplo, se podría querer maximizar la utilidad, o minimizar los tiempos totales de

proceso, minimizar los retardos en las entregas, maximizar la calidad total, etc.

En estos casos, entonces, a parte de todas las variables que intervienen en la toma de

decisiones, también se hace preciso considerar que se logren todos los objetivos

presentados para ese problema.

En este estudio se analizan sólo Funciones Objetivo que se requiere sean minimizadas, ya

que para procesos industriales, en lo referente a programación de la producción

generalmente, se desean minimizar Objetivos como los que se mencionan a continuación

(Pinedo, 1995):

Cmax (Makespan)

Tardanza Total o Tardiness (Tmax)

Máximo Retraso(Lmax)

1.4.1 Cmax (Makespan)

Se representa como Cmax, se define como el máximo entre un conjunto de valores, máx.

(C1,…, Cn), donde Ci es el tiempo de término de procesar el trabajo i. Cmax se entiende

como el tiempo del último trabajo en salir del sistema.

Supongamos un proceso donde se tiene tres trabajos para ser procesados en una

máquina, con los tiempos de procesamiento que se indican:

Trabajo Tiempo de

Proceso

Tiempo

Acumulado Ci

1 12 12 12

2 10 22 34

3 5 27 49

Supongamos que los trabajos están listos en el sistema para empezar a ser procesados, y

que el pasar de un trabajo a otro no tiene un tiempo significativo. Entonces, cuando el

trabajo 1 es procesado han pasado 12 unidades de tiempo (u/t), luego al procesar el

trabajo 2, este permaneció 12 u/t en el sistema más las 10 u/t que requiere para ser

procesado, por lo que su tiempo total de permanencia en el sistema es de 22 u/t, con lo

que la suma del trabajo 1 más el trabajo 2 es de 34 u/t. Para el trabajo tres se hace el

mismo cálculo, con lo que el tiempo de permanencia en el sistema es de 27 u/t., y al

calcular el Cmax este da un total de 49 u/t.

Si se busca una mejor programación de estos trabajos, se podría llegar a lo siguiente,

donde se aprecia que el Cmax es menor:

Trabajo Tiempo de

Proceso

Tiempo

Acumulado Ci

2 10 10 10

3 5 15 25

1 12 27 42

1.4.2 Tardanza Total

Se representa por T. Indica la suma de las tardanzas que podrían tener los trabajos que

deben realizarse. Para entenderlo se tomará el ejemplo anterior y se le agregará los

tiempos de entrega de los trabajos.

Trabajo Tiempo de

Proceso

Tiempo

Entrega

Tiempo

Acumulado Ci Ti

1 12 17 12 12 -5

2 10 -2 22 34 36

3 5 6 27 49 43

79

La idea siempre es que los trabajos se terminen a tiempo, por lo que se hace imperioso

tener un buen programa que permita que esto se cumpla.

La tardanza se expresa de la siguiente forma:

T = Σ max (0, Ci – Ti)

Donde Ci indica el tiempo de salida del trabajo i del sistema, y Ti indica en tiempo de

entrega de ese trabajo, por lo que el cálculo sería el siguiente:

T = max ( 0 , 12 – 17 ) + max ( 0 , 34 – (-2) ) + max ( 0 , 49 – 6 )

T = 79

Para el otro programa se tendría lo siguiente:

Trabajo Tiempo de

Proceso

Tiempo

Entrega

Tiempo

Acumulado Ci Ti

2 10 -2 10 10 12

3 5 6 15 25 19

1 12 17 27 42 25

56

T = max ( 0 , 10 – (-2) ) + max ( 0 , 25 – 6 ) + max ( 0 , 42 – 17 )

T = 56

Con estos dos ejemplos se puede ver claramente que el segundo programa de producción

es mejor que el primero, porque para ambos objetivos este programa es mejor, pero hasta

el momento nada nos indica si se ha llegado al mejor ya que pueden existir mejores

programas.

Pero puede darse el caso de encontrar una solución que sólo sea mejor en uno de los

objetivos. En ese caso no se puede decir cuál de las soluciones es mejor que la otra, y eso

se llamará solución no dominadas.

Un problema multiobjetivo, suele tener una función objetivo de la siguiente forma:

Max o Min Z = f(x) = (f1(x), f2(x), ..., fn(x)),

Donde cada fi(x) representa un objetivo, diremos entonces que una solución domina a otra

sí:

Es mejor en todos los objetivos.

Es mejor en al menos un objetivo e igual en los demás.

De esto nace lo que se denomina Curva de Pareto, generada de las soluciones no

dominadas al graficarlas.

A continuación se muestra un gráfico de la Curva de Pareto para un problema con

objetivos de Cmax (makespan) y Tardanza Total (tardiness).

Gráfico 1.1. Curva de pareto para objetivos de Cmax y Tardiness.

Las siete soluciones unidas por una línea dominan a todas las demás, pero ninguna de ellas

puede ser considerada mejor que cualquier otra que se encuentre en la curva.

1.4.3 Retardo Máximo

Se define como la sumatoria de las diferencias entre el tiempo de término de un trabajo y

su fecha de entrega. Por lo tanto, en el ejemplo que se ha usado, se tiene lo siguiente:

Trabajo Tiempo de

Proceso

Tiempo

Entrega(di)

Tiempo

Acumulado Ci Ti

Li

Ci - di

1 12 17 12 12 -5 -5

2 10 -2 22 34 36 36

3 5 6 27 49 43 43

79

T = max {12 – 17, 34 – (-2), 43 – 6}

T = 43

Y para el otro programa se tiene:

Trabajo Tiempo de

Proceso

Tiempo

Entrega(di)

Tiempo

Acumulado Ci Ti

Li

Ci - di

2 10 -2 10 10 12 12

3 5 6 15 25 19 19

1 12 17 27 42 25 25

56

Lmax = max {10 – (-2), 25 – 6, 42 – 17}

Lmax = 25

1.5 Flow-Shop

Un aspecto importante dentro de la investigación, es el que tiene que ver con la

programación de la producción para problemas de tipo Flow-Shop.

Generalmente los objetivos que se busca minimizar en estos problemas son el makespan y

la tardanza total.

Un problema de tipo Flow-Shop es básicamente uno en el cual se presentan n trabajos T1,

T2,…, Tn. Cada trabajo consta de cierto número de tareas t1, t2,…, tn, para ser programados

en m máquinas m1, m2,…, mn, los cuales deben pasar por las máquinas en un mismo

orden, cada trabajo posee un tiempo de proceso para cada máquina y una fecha de

entrega, por lo que los trabajos deben programarse de forma que estén listos antes de

esta fecha.

Para ejemplificar un problema de programación de tipo Flow-Shop, se considerará una

línea de montaje automotriz simplificada, la que dispone de tres procedimientos

principales: armado, pintura y montaje, cada uno de los cuales es realizado por una

máquina.

A este proceso pueden llegar varios trabajos que llamaremos órdenes de trabajo, cada una

con una fecha de entrega, y una cantidad de automóviles, es decir, que por ejemplo una

orden puede tener 50 automóviles asignados y otra orden 20. Así entonces, cada

automóvil sería una tarea.

El proceso automatizado comienza considerando un patrón guardado en un computador,

el que es modificado según el trabajo que se quiera realizar, es decir, el diseño del

automóvil que se fabricará. Cada máquina recibe las partes esenciales para su labor desde

una máquina suministradora.

La máquina de Armado tiene como función la unión de las partes que han sido recibidas,

de acuerdo con su respectiva forma y modelo, o sea, la carrocería, puertas, pisos,

cubiertas, etc. La operación central es la soldadura autógena y el recubrimiento de

uniones para mejorar la presentación. Adicionalmente, se realizan actividades de

pulimento, impermeabilización y limpieza.

La máquina de Pintura, protege al vehículo de la corrosión y le da un aspecto reluciente. El

vehículo seudo-ensamblado, se desengrasa y luego se laca y se cubre con fosfato para que

absorba mejor la pintura. Después de varios enjuagues se aplican varias capas de

anticorrosivo. Las últimas capas de pintura corresponden a acrílico brillante. La aplicación

de estas sustancias se hace en cámaras especiales que pueden operar de diversas formas,

de acuerdo con el nivel tecnológico de las empresas.

La máquina de Montaje, realiza la parte del proceso en la cual se ensamblan las partes

mecánicas, el motor, los ejes, el sistema de frenos, tapetes y accesorios. Después de este

proceso los automóviles están listos para ser entregados.

Figura 1.1. Modelo de producción secuencial de una automóvil.

Entonces, el problema de este sistema es el establecer qué trabajo se hace en qué

momento, es decir, realizar el proceso de programación de la producción.

1.6 Programación de la Producción

La programación de la producción se refiere a la secuencia en la que los trabajos serán

procesados, de manera de lograr los tiempos que se desea cumplir, y satisfacer todas las

restricciones que se tenga, como pueden ser el uso de las máquinas, los tiempos de

entrega, etc.

En la sección 2.1 se hizo una pequeña introducción a lo referente a programación de la

producción, pero ahora se pasa a explicar de mejor forma.

Un programa se puede representar como una secuencia de números donde cada número

indica el orden en que se ejecutará ese trabajo; por ejemplo, la secuencia 1 – 2 – 3, indica

que el trabajo 1 es el primero en procesarse, luego el 2, y por último el 3. Por otro lado, la

secuencia 3 – 2 – 1 indica que el primer trabajo en procesarse es el 3, después el 2, y

finalmente el 1.

1.6.1Aspectos importantes

Para realizar la programación hay tres aspectos importantes que deben considerarse: los

trabajos, las máquinas y la medición.

1.6.1.1 Trabajo

“Los trabajos son actividades a realizar” (Sipper y Bulfin, 1998). Los trabajos que se pueden

identificar en el ejemplo de la línea de montaje automotriz, de la sección anterior, son las

órdenes de automóviles que se deben realizar. Si nos imaginamos una papelera, los

trabajos serían las diversas órdenes de papeles y cartones que debe producir, y en una

fábrica de ropa serían los conjuntos de prendas iguales que se deben hacer.

Un trabajo siempre debería tener un tiempo de proceso y una fecha en la que debe estar

terminado. Para el presente análisis supondremos que un trabajo una vez que comienza a

ser procesado no se detiene hasta que es terminado.

Otras características que puede poseer un trabajo, según Sipper y Bulfin (1998), son que:

Puede depender de otro trabajo, o sea, que no puede realizarse antes de que

termine otro. Esto es lo que sucede en el procesamiento tipo Flow-Shop, donde las

tareas se ejecutan en un único orden.

Puede poseer una fecha de inicio, antes de la cual no puede comenzar el proceso.

1.6.1.2 Máquinas

“Las Máquinas procesan los trabajos” (Sipper y Bulfin, 1998). Las máquinas en la industria

son literalmente máquinas o robots, pero en una pista de aterrizaje en un aeropuerto, un

bus en una empresa de transporte, una mesa en un casino, también pueden considerarse

máquinas.

Las máquinas pueden clasificarse como sigue (Sipper y Bulfin, 1998):

1.6.1.2.1 Una sola máquina

Se tiene una sola máquina para procesar todos los trabajos, esta máquina sólo puede

procesar un trabajo a la vez, y una vez que termina uno puede continuar con el siguiente.

1.6.1.2.2 Máquinas paralelas

Son varias máquinas idénticas en el sentido de que pueden realizar los mismos

procesamientos. Así entonces, un trabajo se podría realizar en cualquiera de ellas para

quedar terminado, y el tiempo de proceso es el mismo indiferente de la máquina en que

se procese.

1.6.1.2.3 Talleres de producción continua

Es donde se encuentran diferentes máquinas y los trabajos, para ser completados, deben

pasar una vez por cada una y en el mismo orden, es decir, si numeramos las máquinas

como 1, 2 y 3, un trabajo no puede pasar a la máquina 2 si no ha pasado por la 1, y no

podrá pasar a la 3 si no ha terminado en la 2.

Interesa de sobremanera este forma de producción, ya que es en este tipo de

procesamiento el énfasis del análisis que se está realizando, es decir, un procesamiento de

tipo Flow-Shop.

1.6.1.2.4 Producción intermitente

Es similar al de producción continua, es decir, existen varias máquinas distintas, pero los

trabajos no deben pasar una vez por cada una ni en el mismo orden necesariamente. Es

decir, un trabajo podría pasar por la máquina 1 y luego por la 2, pero nunca por la 3, en

cambio otro solo podría pasar por la 3.

1.6.1.2.5 Plantas abiertas

Son en los cuales da lo mismo por qué máquina pasan primero los trabajos, en caso de que

deban pasar por más de una. Un ejemplo es un taller mecánico, donde un automóvil que

ingresa, y da lo mismo que reparación se realice primero.

1.6.1.3 Medición

La medición se refiere a cómo evaluamos si nuestro programa de producción es el más

adecuado, es decir, cómo podemos determinar si es el mejor programa que podemos

tener o, en su defecto, uno que sea lo suficientemente bueno.

Maximizar utilidad o minimizar costos, son los objetivos que cualquier empresa persigue,

pero “desafortunadamente, es difícil estimar los parámetros financieros que relacionen un

programa con costo o ganancia” (Sipper y Bulfin, 1998). Por esto, las medidas que se

utilizan son generalmente las mencionadas en la sección 1.4.

A continuación se presenta formalmente la notación que se utilizará en la investigación en

lo que tiene que ver con los elementos de un problema de programación de la producción

(Sipper y Bulfin, 1998):

n = número de trabajos que serán procesados

m = número de máquinas

pik = tiempo de proceso del trabajo i en la máquina k ( pi si m = 1)

ri = tiempo de liberación de la orden del trabajo i

di = fecha de entrega del trabajo i

wi = ponderación (importancia o valor) del trabajo i respecto a los otros trabajos

En un programa específico, se define para cada trabajo i:

Ci = tiempo de terminación del trabajo i

Fi = Ci – ri, tiempo de flujo del trabajo i (Fi > 0)

Li = Ci –di, retraso del trabajo i (Li < 0 denota anticipación)

Ti = max (0, Li), tardanza del trabajo i

Ei = max (0, -Li), adelanto del trabajo i

Cmax = max i = 1,n {Ci}, tiempo máximo de terminación de todos los

trabajos (makespan)

Lmax = max i = 1,n {Li}, retraso máximo de todos los trabajos

Tmax = max i = 1,n {Ti}, tardanza máxima de todos los trabajos

1.6.2 Supuestos

El primero de los supuestos que se debe considerar es el de disponibilidad, que quiere

decir que los trabajos están listos y dispuestos para ser procesados en la línea de

producción, es decir, ri= 0.

También se supone la certidumbre de los datos, es decir, que en ningún problema se

podría argumentar el desconocimiento de los datos exactos.

Otro supuesto que ya se mencionó en una sección anterior, es que un trabajo una vez

comenzado no se detiene hasta que está terminado.

La precedencia entre los trabajos no existe, es decir, son trabajos totalmente

independientes.

Capítulo 2. METAHEURÍSTICAS PARA

PROGRAMACIÓN DE PRODUCCIÓN EN PROBLEMAS

DE TIPO FLOW-SHOP MULTIOBJETIVO

No existen algoritmos exactos que puedan resolver problemas reales con más de un

objetivo en un tiempo razonable (Baesler, et al., 2005). En muchas ocasiones encontrar

una solución óptima para un solo objetivo es imposible, producto de la complejidad de los

problemas. Es por esto que las Metaheurísticas surgen como una buena alternativa para

resolver problemas multiobjetivo.

La mayoría de los desarrollos para la solución de problemas multiobjetivo están ligados a

Algoritmos Genéticos (AG), a diferencia de las implementadas basadas en Simulated

Annealing, por lo que en el presente capítulo se presentarán dos metaheurísticas, una

basada en cada tema.

2.1 Algoritmos Genéticos

Algoritmo genético es una técnica de búsqueda basada en la teoría de la evolución de

Darwin, es decir, procesos de selección natural y evolución genética. “Esta técnica se basa

en los mecanismos de selección que utiliza la naturaleza, de acuerdo a los cuales los

individuos más aptos de una población son los que sobreviven, al adaptarse más

fácilmente a los cambios que se producen en su entorno. Hoy en día se sabe que estos

cambios se efectúan en los genes (unidad básica de codificación de cada uno de los

atributos de un ser vivo) de un individuo, y que los atributos más deseables del mismo se

transmiten a sus descendientes, cuando éste se reproduce sexualmente”,

(REDCIENTIFICA.COM).

2.1.1 Características principales

Población de individuos: Representan las soluciones del problema a resolver. Cada

solución es un cromosoma, por ejemplo:

C = [4 2 3 1]

En un problema de tipo Flow Shop, significa que el primer trabajo en procesarse será el 4

después el 2, posteriormente el 3 y finalmente el 1.

Operadores Genéticos: Selección Natural, Evolución Genética y Cambios Adaptativos, los

que son simulados por la selección (mejores individuos o soluciones), cruce o

recombinación (consiste en producir un nuevo individuo a partir de los genes de dos

padres) y mutación (consiste en intercambiar el orden de las de los genes en un individuo,

lo que en un problema de Flow Shop, sería cambiar la secuencia de los trabajos en una

solución), respectivamente.

Función de Aptitud (o función de fitness): Determina la adaptación del individuo al medio

(solución al problema), es decir que tan buena es la solución.

2.1.2 Algoritmo Genético Simple

1. Elegir aleatoriamente una población de individuos

2. Evaluar la aptitud (fitness) de cada individuo

3. Repetir hasta alcanzar condición de terminación

4. Seleccionar los individuos más aptos para reproducir

5. Combinar pares de individuos aleatoriamente

6. Aplicar el operador de recombinación

7. Aplicar el operador de mutación

8. Evaluar la aptitud (fitness) de cada individuo

9. Fin

El Algoritmo se podría mostrar gráficamente así:

Figura 2.1. Secuencia de algoritmo genético.

2.1.3 Algunos Algoritmos Genéticos Multiobjetivo

La primera implementación de un AG Multiobjetivo fue desarrollada por Schaffer en 1984,

denominado VEGA (Vector Evaluated Genetic Algorithm). “Esta implementación tiene la

idea de crear sub-poblaciones seleccionando los individuos de acuerdo con cada objetivo.

Suponiendo que se tengan N individuos y se necesita optimizar k objetivos, se generan k

sub-poblaciones con N / k individuos cada una. Luego esas sub-poblaciones son cruzadas y

se le realizan operaciones de mutación para crear una nueva población” (Pappa, 2002).

Posteriormente Goldberg en 1989, “incorpora el concepto de dominancia dentro del

proceso de selección de individuos en el AG”, (Baesler, et al., 2005). Su idea era utilizar el

concepto de dominancia para separar a los individuos en grupos llamados ranking, donde

cada ranking contendrá solo soluciones no dominadas. Así el primer ranking contendrá las

soluciones no dominadas del conjunto de soluciones y se les asignará el valor de fitness

más elevado, el segundo ranking será compuesto de las soluciones no dominadas del

conjunto de soluciones, no considerando las soluciones del ranking anterior. El valor de

fitness de este ranking será menor que el anterior pero superior que el siguiente. El

proceso continúa hasta que no existan individuos en la población. Además, Goldberg

introdujo el concepto de formación de nichos y la utilización de una función fitness

compartido, compuesta de dos medidas, la función objetivo y el índice de la densidad de

población del nicho al que ese individuo pertenece. Un nicho es la división de la población

en especies, que reúne a individuos de características similares, se usa para reducir la

competición por recursos y obtener sub-poblaciones estables, cada una de ellas

concentrada en un nicho de búsqueda, (Pappa, 2002).

A continuación se muestran dos Algoritmos Genéticos que siguen los conceptos

desarrollados por Schaffer y Goldberg. La principal diferencia entre estos algoritmos

consiste en la forma en que el valor de la función de aptitud (fitness) es atribuido a los

individuos de la población.

2.1.3.1 MultiObjective Genetic Algorithm (MOGA)

Fonseca y Fleming fueron los creadores de MOGA en 1993. La idea es asignar una jerarquía

a los individuos, la que es igual al número de individuos de la población que lo dominan

más uno, es decir, los individuos de la frontera de Pareto tienen un valor de jerarquía igual

a 1, ya que no son dominados por ninguna solución. El valor de la función de aptitud se

puede entender como:

Aptitud = 1 / (valor de jerarquía)

Su funcionamiento puede ser resumido en 3 etapas:

Primero, ordenar toda la población de acuerdo a los individuos no dominados. El proceso

continua hasta que todos los individuos de la población han sido clasificados.

Luego los individuos pertenecientes a al jerarquía 1 reciben un valor de ranking igual a 1,

los individuos del jerarquía 2 y siguientes reciben un valor de ranking igual al número de

soluciones que las dominan más. Por ejemplo, si la frontera de Pareto posee 3 elementos,

los individuos del jerarquía 2 tendrán un valor de ranking igual a (3 + 1) = 4.

Finalizado el proceso de ordenación, la función de aptitud es atribuida a cada solución de

acuerdo con su ranking.

2.1.3.2 Multiobjetive Optimization using Non-Dominated Sorting in Genetic Algorithms

(NSGA)

Este algoritmo fue propuesto por Srinivas y Deb (1994). Es similar a MOGA, la principal

diferencia está en la forma en que se atribuye la función de aptitud a cada individuo y en

el uso de la estrategia de fitness compartido, (Pappa, 2002). Al igual que MOGA, se basa

en la clasificación de individuos en varias capas o frentes. El valor de la función de fitness

para cada individuo en el primer frente es igual a N, donde N es el número de individuos

de la población. Luego se utiliza una estrategia de fitness compartido, a cada individuo se

le atribuye una función de fitness compartido dividiendo el valor anteriormente atribuido

por el contador del nicho (número de individuos del nicho). Es guardado el valor de fitness

compartido. Después se identifican los individuos no dominados del segundo frente, y se

le asigna un nuevo valor de función de fitness, que es más pequeño que la función de

fitness compartido del primer frente, es decir, el guardado anteriormente menos un valor

pequeño, y así hasta que no queden más individuos. Puesto que los individuos en el primer

frente tienen el valor de fitness mayor, consiguen siempre más copias que el resto de la

población.

2.1.4 Algoritmo Genético Multiobjetivo a Implementar

El AG a implementar tiene la misma estructura de un AG simple, en que se considera todos

los elementos relacionados con un AG, es decir, creación de la población inicial, selección

natural, mutación, recombinación, función de aptitud y criterio de término. El aspecto más

importante en esta implementación, es la forma en la que se asigna el fitness a los

individuos, en la cual se usan los conceptos de dominancia y nicho.

A continuación se muestran los aspectos más importantes del AG desarrollado:

2.1.4.1 Representación

Cada solución, o individuo, es representado mediante un vector, el cual posee valores

entre 1 y en número de trabajos que posea el problema, como se muestra a continuación

para un problema con 7 trabajos:

7 5 1 4 3 2 6

El cuál indica la secuencia de proceso de los trabajos, por lo que no puede existir un

individuo en el cual se repita algún trabajo, ni con un valor en la secuencia superior al

número de trabajos.

2.1.4.2 Población Inicial

La población inicial es generada en forma aleatoria, es decir, considerando el tamaño de la

población, se crean individuos diferentes en base a la generación de números aleatorios,

cumpliendo con la representación anterior, por lo que cada vez que el algoritmo es

ejecutado, la población inicial es siempre distinta. Por ejemplo, si existiera un problema de

7 trabajos, y una población de 4 individuos, la población podría ser la siguiente:

7 5 1 4 3 2 6

2 3 5 6 7 6 1

6 5 7 3 1 4 2

1 2 7 3 4 6 5

O bien esta otra:

1 5 6 4 7 2 3

3 5 4 6 7 2 1

7 1 2 3 5 4 6

5 4 1 2 3 6 7

O cualquier otra combinación.

2.1.4.3 Selección

A cada individuo se le asigna una probabilidad de selección de acuerdo con su fitness,

luego mediante una ruleta se seleccionan los individuos para el cruzamiento, y así pasar a

la siguiente generación. Los individuos seleccionados son la mitad de la población.

También es preciso mencionar una estrategia de elitismo, la cual elije a todos los

individuos que se encuentren en la Frontera de Pareto para que pasen a la siguiente

generación. A continuación se presenta un ejemplo:

Supóngase que se tienen los siguientes individuos, con el fitness indicado en la tabla:

Tabla 2.1: Fitness de los individuos y probabilidad de selección

Individuo Fitness Probabilidad de

Selección

Probabilidad

Acumulada

1 100 100/640 0.16 0.16

2 100 100/640 0.16 0.32

3 100 100/640 0.16 0.48

4 80 80/640 0.13 0.61

5 75 75/640 0.11 0.72

6 60 60/640 0.09 0.81

7 50 50/640 0.08 0.89

8 40 40/640 0.06 0.95

9 20 20/640 0.03 0.98

10 15 15/640 0.02 1.00

Suma Fitness 640 1.00

La probabilidad de que un individuo sea seleccionado para pasar a la siguiente generación

está dada por su fitness, dividido por la suma de los fitness de cada individuo, así, por

ejemplo, la probabilidad de seleccionar al individuo número 1, es : 100 / 640 = 0.16. El

mismo cálculo es realizado para cada individuo de la población. Así, como podemos ver en

el siguiente gráfico, cada individuo posee una probabilidad se selección que depende de

qué tan buena solución es.

Gráfico 2.1: Probabilidades de Selección y Ruleta

Así, la selección por ruleta se puede visualizar como el proceso de elegir un número

aleatorio entre 0 y 1, y elegir al individuo que está en ese rango, para lo cuál ayuda el

cálculo de la probabilidad acumulada. Por ejemplo, un número aleatorio x=0.28, nos indica

que el individuo a seleccionar es el segundo ya que su probabilidad acumulada es 0.32, y

cualquier valor aleatorio entre 0.17 y 0.32, indicaría la selección de éste.

Ya que es posible que más de una vez la elección de un número aleatorio coincida con un

mismo individuo, no hay problema en que éste sea seleccionado más de una vez. Además,

como se mencionó anteriormente, los individuos de la Frontera de Pareto, pasan

automáticamente a la siguiente generación, lo que en este ejemplo, significaría que los

individuos 1, 2 y 3 son seleccionados en primer lugar, y para completar la mitad de la

población que tiene que ser seleccionada, se realiza el proceso de la ruleta.

2.1.4.4 Cruzamiento

El proceso de cruzar los individuos seleccionados en la fase anterior, consiste en elegir

primeramente dos individuos de forma aleatoria, luego una posición en ellos, y

posteriormente, concatenar cada uno de las partes obtenidas (alelos). Por ejemplo, con los

siguientes padres:

7 5 1 4 3 2 6

2 3 5 6 7 6 1

Y aleatoriamente elegir la posición 4, se obtendrían los siguientes hijos:

7 5 1 4 7 6 1

2 3 5 6 3 2 6

Dado que los hijos son soluciones infactibles para el problema puesto que hay trabajos

repetidos y otros que no aparecen, estos individuos deben ser modificados. En el primer

hijo, no aparece el trabajo 2 ni el 3 y está repetido el trabajo 7 y el 1, y en el hijo dos el

único trabajo no repetido es el 5, faltando por aparecer los trabajos 1, 4 y 7. Para

solucionar esto, aleatoriamente se elijen los trabajos faltantes y se colocan en una posición

donde haya un trabajo repetido. Así se puede llegar a la siguiente configuración de los

individuos, la que cumple con ser una solución factible:

7 5 2 4 3 6 1

2 4 5 6 7 3 1

2.1.4.5 Mutación

La mutación es un procedimiento simple en el que simplemente se toman aleatoriamente

dos posiciones dentro de la secuencia, y esos valores son intercambiados entre sí, lo que

se conoce como intercambio de pares. La cantidad de individuos que son objeto de

mutación depende de una probabilidad de mutación, que generalmente es un valor

pequeño. El siguiente es un ejemplo:

3 5 4 6 7 2 1

En la secuencia anterior, se han elegido los trabajos 4 y 2 para ser intercambiados y con

ello logar un cambio en los objetivos que se busca mejorar, con lo que el individuo mutado

sería el que se ve a continuación:

3 5 2 6 7 4 1

2.1.4.6 Fitness (función de aptitud)

El fitness indica qué tan buena es una solución con respecto a las demás. Esta medida se

calcula considerando los valores de cada objetivo a evaluar. La implementación a realizar

considera los objetivos Cmax y Tardanza.

En primer término se divide la población en varios ranking, utilizando los conceptos

incorporados por Goldberg en 1989, donde el primer ranking está constituido por las

soluciones no dominadas del conjunto de soluciones, el segundo ranking será compuesto

de las soluciones no dominadas, no considerando las soluciones del ranking anterior, y así

sucesivamente hasta que todos los individuos hayan sido clasificados. Posteriormente, a

cada ranking le es asignado un fitness inicial, es decir que cada individuo de ese ranking

posee el mismo fitness, dado que desde una perspectiva multiobjetivo, las soluciones no

dominadas entre sí, son iguales.

Pero además, Goldberg introdujo los conceptos de formación de nichos y la utilización de

una función fitness compartido, los que también son considerados en la asignación de un

fitness final a cada individuo. La idea es darles un mayor fitness a aquellos individuos que

estén más alejados de los demás dentro de un mismo ranking y un fitness menor a

aquellos que estén más cercanos, todo esto ayuda a reducir la competición por recursos y

obtener sub-poblaciones estables.

2.1.4.6.1 Cálculo Fitness Inicial

El procedimiento para calcular el fitness inicial, así como el final, es extraído del Capítulo 5

de la Obra de Deb (2001), “Multi-Objective Optimization using Evolutionary Algorithms”,

donde el fitness inicial se define como sigue:

Donde N es el número de individuos de la población y μ(ri) es la cantidad de individuos en

el ranking i.

Para verlo claramente se presenta el siguiente ejemplo (Deb, 2001), que sólo posee seis

individuos, cuyos datos se presentan en la siguiente tabla:

Tabla 2.2: Ranking de los individuos

Solución Cmax Tardanza Ranking

1 0.31 6.10 1

2 0.43 6.79 2

3 0.22 7.09 1

4 0.59 7.85 4

5 0.66 3.65 1

6 0.83 4.23 2

El gráfico de estas soluciones muestra cada curva de soluciones, es decir, cada ranking:

Gráfico 2.2: Ranking de las soluciones

Con estos datos se puede calcular el fitness inicial de la siguiente forma, utilizando la

formula anteriormente vista:

F1 = 6 – 0 – 0.5 (3 – 1) = 5

F2 = 6 – 3 – 0.5 (2 – 1) = 2.5

F4 = 6 – 3 – 2 – 0.5 (1 – 1) = 1

Lo que indica que para el primer ranking, el fitness es de 5, para el segundo es 2.5, y 1 es

para el último.

2.1.4.6.2 Cálculo Fitness Final

En esta etapa se modifican los valores iniciales del fitness de cada individuo. Lo que se

intenta, es dar un mejor fitness a aquellos individuos que se encuentran más aislados y

“castigar” a aquellos individuos que se encuentren reunidos en un nicho, disminuyendo su

fitness. El cálculo es bastante complicado, y para su completo entendimiento, hace falta

un análisis profundo. Aun así, se explica y se presenta un ejemplo (Deb, 2001).

En primer término, se debe calcular la distancia entre las soluciones de cada ranking

utilizando la siguiente fórmula:

La que indica la distancia entre el individuo j y el individuo i. Donde, fkmax y fkmin son el

máximo y mínimo valor del objetivo k. Luego, el contador del nicho para el individuo i, es la

sumatoria de las distancias de i a cada individuo de ese ranking, aplicando la función Sh, es

decir:

Donde μ(ri) es el número de soluciones del ranking ri. Y la función Sh se define como sigue:

Sh (dij) = 1 – (dij / σshare) ; Si dij < σshare

En cualquier otro caso Sh (dij) = 0. La idea es que la función entregue un valor entre 0 y 1,

como medida de qué tan cerca están los individuos, siendo un valor cercano a uno

indicador de que los individuos muy cercanos, y un valor cercano a cero indica que se

encuentran más distantes.

El valor de σshare algunos autores lo utilizan como un parámetro el cual se va modificando

para ver los efectos que produce, otros, para un determinado número de individuos dan

un valor fijo. Para el caso que se presenta se optó por calcular el valor de σshare, que

dependerá de tres valores; n que es el número de objetivos que se analizan que este caso

es 2; q, que es un valor fijo que puedo variar entre 5 y 10; y r, que es:

Donde, fkmax y fkmin son el máximo y mínimo valor del objetivo k. Así σshare, que indica qué

valor se considera como límite para determinar si un individuo pertenece, o no, a un

mismo nicho, se calcula de la siguiente manera:

A continuación, se continúa con el ejemplo anterior, al que se le aplicará el proceso para

obtener el fitness final, para la primera curva. Asumiendo un f1max = 1, f1min =0.1, f2max =10,

f2min =1.

d13 = √ ( (0.31 – 0.22) / (1 – 0.1) )2 + ( (6.1 – 7.09) / (10 – 1) )2 = √ 0.0221 = 0.149

d15 = √ ( (0.31 – 0.66) / (1 – 0.1) )2 + ( (6.1 – 3.65) / (10 – 1) )2 = √ 0.2253 = 0.475

d35 = √ ( (0.22 – 0.66) / (1 – 0.1) )2 + ( (7.09 – 3.65) / (10 – 1) )2 = √ 0.3851 = 0.6206

Suponiendo un σshare = 0.5:

Sh (d13) = 0.702, Sh (d15) = 0.05, Sh (d35) = 0

Así, el contador de nicho para los individuos del primer ranking, serían los siguientes:

nc1 = 1 + 0.702 + 0.05 = 1.752

nc3 = 1 + 0.702 + 0 = 1.702

nc5 = 1 + 0.05 + 0 = 1.050

Posteriormente se calcula un Fitness Compartido dividiendo el fitness inicial por el

contador de nicho de ese individuo. Además, se debe calcular un factor del ranking, el cual

es el fitness inicial de los individuos por el número de individuos de este ranking, dividido

por la suma de los fitness compartidos, lo que en este caso sería, (5 x 3) / (2.854 + 2.938 +

4.762) = 1.421.

Después de esto, se multiplica el fitness compartido de cada individuo por el factor recién

calculado, y se obtiene el fitness final. Lo que sería:

Individuo 1: 2.854 * 1.421 = 4.056

Individuo 3: 2.938 * 1.421 = 4.176

Individuo 5: 4.762 * 1.421 = 6.768

Esto, muestra cómo, desde un fitness inicial de 5 para cada individuo de este ranking, se

llegó a un fitness final diferenciado, en el que los individuos que se encontraban más

cercanos, son “castigados”, y el individuo más alejado es beneficiado en su fitness.

2.2 Simulated Annealing

Simulated Annealing es una Metaheurística que en la solución de problemas de un solo

objetivo ha sido probada ampliamente, pero no así en el ámbito multiobjetivo.

Como se mencionó en un Capítulo anterior, Simulated Annealing es una analogía del

proceso de templado de los metales, donde un metal es calentado hasta cuando empieza

a derretirse y se disminuye su temperatura controladamente. En la fase de mayor

temperatura las partículas se mueven aleatoriamente y, a medida que la temperatura

disminuye, estas partículas se mueven en forma más ordenada. Así, el proceso de

enfriamiento se puede ver como la búsqueda de soluciones, donde, en un comienzo, el

pasar de una solución a otra peor es frecuente, pero a medida que la temperatura

disminuye, son menos las soluciones peores que son aceptadas como nueva solución

obtenida. Si el enfriamiento se realiza en forma muy rápida se produce fragilidad en los

metales, lo que en el algoritmo significaría el obtener un óptimo local.

2.2.1 MOSARTS

A continuación se presenta la “metaheurística denominada MultiObjective Simulated

Annealing with Random Trajectory Search (MOSARTS). Esta técnica se basa en el

Algoritmo Simulated Annealing, con la diferencia que introduce la utilización de memoria

de corto y largo plazo para realizar una búsqueda que permita balancear el esfuerzo entre

todos los objetivos involucrados en el problema”, (Baesler, et al., 2005).

La idea en la cual se basa esta metaheurística es en la aceptación de soluciones inferiores,

lo que en el ámbito Multiobjetivo significa una solución dominada, utilizando la siguiente

norma:

P (Y, X, T) = Min {1, emax j { λ j ( f j (X) – f (Y)) / T}}

Este valor indica la probabilidad de aceptación de una solución Y dada una solución X a

una temperatura T. El parámetro λ representa el peso de la función objetivo j con respecto

a la importancia total.

63

La mayor diferencia entre los enfoques de Simulated Annealing Multiobjetivo está dada

por

la forma en que se define la probabilidad de aceptación de una nueva solución dominada.

Esta metaheurística se sitúa en el argumento de seleccionar un solo objetivo en cada

iteración, que se llamará Objetivo Referente (OR), y en base a éste continuar con el

proceso de búsqueda en esa iteración, así no es necesario modificar la estructura de

Simulated Annealing para el caso de un solo objetivo. Se incorporan mecanismos

inteligentes como memoria de corto y largo plazo que permiten elegir una dirección en la

cuál centrarse en cada iteración. “La probabilidad de aceptación de una solución inferior

sigue siendo definida por la variación de la función objetivo con respecto a la solución

anterior y por la temperatura actual del sistema” (Baesler et al., 2005), donde se tiene una

temperatura diferente para cada objetivo.

La memoria de largo plazo indica como ha evolucionado históricamente cada objetivo en

forma individual. La memoria de corto plazo indica cuanto mejoró un objetivo en la última

iteración (Baesler et al., 2005).

Una vez que se ha encontrado una solución inicial, dígase X0, se evalúa un vecino de X0,

dígase X1. Esto se realiza comparando cada objetivo de la solución X1 con respecto a la

solución anterior X0. Es aquí donde podría darse uno de los siguientes escenarios:

Todos los objetivos mejoran

Todos los objetivos empeoran

Algunos objetivos mejoran y otros empeoran

En el caso en que todos los objetivos mejoren, significa que la nueva solución es mejor

quela anterior, o sea, X1 domina a X0, por lo que X1 es aceptada para continuar la búsqueda

en esa dirección.

Si todos los objetivos empeoran, es decir, si X0 domina a X1, se evalúa una función de

aceptación para ver si se admite esta nueva solución para continuar la búsqueda desde

ahí.

Esta función de aceptación se referirá a un solo objetivo, por lo que será necesario

seleccionar previamente un Objetivo Referente (OR) para guiar el proceso.

En el último caso, donde ninguna solución domina a la otra, se elige un OR, si esté objetivo

mejora en X1 con respecto a X0, X1 es aceptada, en caso contrario, se debe evaluar una

función de aceptación que siempre depende de la temperatura particular de ese objetivo

en el momento actual de la búsqueda.

2.2.2 Obtención del Objetivo Referente

El OR se elige dependiendo de una Función de Selección (FS). Esta función de selección

“no emplea tan solo el criterio obvio de selección aleatoria, sino que incorpora también la

mejora o detrimento de cada objetivo, es decir, el desempeño, tanto en la última etapa de

la evaluación (desempeño inmediato o memoria de corto plazo), como en todo el trayecto

recorrido (desempeño histórico o memoria de largo plazo)” (Baesler et al., 2005). La FS

utiliza dos parámetros arbitrarios que indican la importancia que el Tomador de Decisiones

le concede a cada uno de los desempeños, o sea, qué tan importante considera la

memoria de largo y corto plazo.

La estructura de la función de selección será la siguiente:

FSi = w1 * F1 + w2 * F2

Donde:

W1 = Ponderación arbitraria de importancia de la memoria de largo plazo.

W2 = Ponderación arbitraria de importancia de la memoria de corto plazo.

F1 = Ti / Timax

F1 = Función de Probabilidad de selección de un objetivo dependiendo de su desempeño

histórico (memoria de largo plazo) (Baesler et al., 2005).

Ti = Temperatura actual del sistema para el objetivo i.

Timax = Temperatura de inicio del objetivo i.

La función F1 tiene por misión dar una mayor probabilidad de selección a aquellos

objetivos que no han tenido un buen desempeño, es decir, que en todo el proceso de

construcción de soluciones no han mejorado lo suficiente. Los objetivos que han mejorado

bastante tienen relacionado un Ti mucho menor que Timax, ya que el Ti disminuye cada vez

que el objetivo i mejora. Así entonces, la razón Ti / Timax es elevada cuando el objetivo i no

ha sido explorado suficientemente.

F2 = 1 – (λC%i / Σ λC%i)

F2 = “Función de Probabilidad de selección de un objetivo según el desempeño reciente

(memoria de corto plazo)” (Baesler et al., 2005).

λC%i = Variación porcentual del objetivo i.

Lo que la función F2 plantea, es asignarle una mayor probabilidad de selección como OR a

aquellos objetivos que en la última iteración hayan tenido un mejoramiento significativo.

Los objetivos que más mejoraron en la última iteración tendrán una razón λC%i / Σ λC%i

mayor. Esta variación se mide en porcentaje ya que las escalas de los objetivos son

distintas, y se deben comparar entre sí.

Así, cada objetivo tendrá una función de selección,

FSi = w1 * F1 + w2 * F2

Para seccionar el OR, se calcula la Probabilidad de Selección (PS) para cada objetivo, como

sigue:

PSi = FSi / ΣFSi

Se cumple que ΣPSi = 1. Así entonces, se genera un número aleatorio entre 0 y 1, para

escoger cual será el OR.

2.2.3 Algoritmo MOSARTS, MultiObjective Simulated Annealing with

Random Trajectory Search. (Baesler, et al., 2005).

Los pasos que se pueden visualizar son los siguientes.

1. Definir solución inicial X0

2. Evaluar objetivos Fi (X0)

3. Definir vecino de X0 como X1

4. Evaluar objetivos Fi(X1)

5. Comparar los objetivos de X0 con los de X1

6. Si X1 domina a X0, hacer X0 = X1 y volver a 3. En caso contrario ir a 7.

7. Obtener función de selección FS, Probabilidad de Selección PS, y Objetivo

Referente OR. Ir a 8.

8. Si OR mejora, hacer X0 = X1, actualizar temperatura particular de Ti. Volver a 3. En

caso contrario ir a 9.

9. Calcular función de selección particular FAP exp ((λC/Ti)) para el OR.

10. Si FAP rechaza la solución, volver a 3. En caso contrario ir a 11.

11. Hacer X0 = X1, actualizar temperatura particular Ti del OR. Volver a 3.

Capítulo 3. COMPARACION INDIVIDUAL DE

AMBAS METAHEURISTICAS

Las dos Metaheurísticas fueron implementadas en lenguaje C++, para poder realizar

experimentos y hacer las respectivas comparaciones entre ambas.

En primer lugar se realizó un análisis individual, para determinar cuales son los mejores

parámetros, que se ajustan a cada implementación para posteriormente, considerando

dos problemas de prueba, compararlas entre ellas, y poder determinar cuál tiene un mejor

desempeño.

El análisis preliminar para determinar los mejores parámetros considerará un problema

Flow-Shop de 49 trabajos que deben ser procesados en 15 máquinas, el cual será probado

con varias combinaciones de parámetros, y la combinación de parámetros que entregue

los mejores resultados, será la que se utilice para comparar con la otra Metaheurística.

Dado que en los problemas multiobjetivo no se genera una solución individual, sino que

una curva de soluciones, y como las soluciones son no-dominadas, no se puede decir que

una es mejor que otra, y los criterios de comparación pueden ser variados, pero se

considerarán los siguientes:

El Número de soluciones en la Curva de Pareto. Es deseable una Frontera de Pareto de

alta densidad, esto es porque finalmente la decisión de cuál solución es la que se elige

depende de un tomador de decisiones, el que podría preferir soluciones mejores en un

objetivo, en contraste con otro que preferiría una solución mejor en otro objetivo, por

ejemplo si se tiene la siguiente frontera de Pareto:

Gráfico 3.1: Ejemplo curva de Pareto con pocas soluciones

El número de posibilidades de elegir una solución es reducido, y sólo se pueden elegir

extremos, o sea, una buena solución para la Tardanza pero mala para el Cmax, o viceversa,

por lo que se hace más deseable una Curva de soluciones como la que sigue, ya que se

pueden elegir soluciones intermedias:

Gráfico 3.2: Ejemplo curva de Pareto con varias soluciones

Otra medida de comparación será el Porcentaje de Soluciones en una Nueva Frontera de

Pareto generada por las curvas que se están comparando. Este método fue propuesto

Hyun, et al. (1998). Su idea era comparar dos Metaheurísticas creando una nueva Frontera

de Pareto, que estaría compuesta por las soluciones no-dominadas entregadas por cada

una, y ver cuantas de las soluciones de la nueva Frontera pertenecen a una Metaheurística

y cuantas a la otra, esta nueva curva a lo menos tendrá la cantidad de soluciones de la

Metaheurística con menos soluciones y a lo más la suma de ambas. Por ejemplo, si la curva

de una Metaheurística tiene 5 soluciones, y la otra 7, la nueva curva tendrá un mínimo de

5 soluciones y un máximo de 12 (5 + 7) soluciones. En este mismo ejemplo, si en la nueva

curva hay 10 soluciones, y 3 pertenecen a la Metaheurística 1 y las otras 7 a la

Metaheurística 2, se entenderá que la Metaheurística 2 es mejor que la 1.

Este mismo proceso se utilizará para comparar curvas de una misma Metaheurística en

caso de que sea difícil decidir cual combinación de parámetros es la mejor, considerando

los otros criterios de comparación.

El Promedio Valores de los Objetivos de todas las curva de pareto obtenidas en el proceso

de experimentación, es importante para analizar como se comporta una Metaheurística.

Otros criterios de comparación menos concluyentes y menos importantes, pero que sirven

para decidir son: la desviación estándar en el número de soluciones de la Frontera de

Pareto obtenidas en un conjunto de ejecuciones de una Metaheurística; La cantidad de

Curvas distintas generadas; y El máximo número de soluciones.

3.1 Parámetros para Algoritmo Genético

Los parámetros a probar en el AG son la cantidad de individuos, el número de

generaciones y la probabilidad de mutación. Para ello, se harán combinaciones de

parámetros y con cada una de ella se ejecutará el programa 10 veces, para ver como se

comporta. Los parámetros para las combinaciones serán los siguientes:

Tabla 3.1: Parámetros a combinar

Individuos 100 200 300

Generaciones 100 150 300 500

%Mutación 1 3 5 10 15

Con estos parámetros se realizarán todas las combinaciones posibles y se determinará cual

es la mejor. Es decir, se tendrán 60 combinaciones, cada cual se ejecutará 10 veces, y así

se obtendrán las mejores combinaciones de parámetros.

Después de ejecutar todos estos experimentos, se extrae la siguiente información:

Cantidad Curvas Distintas, Máximo Número de Soluciones, Mínimo Número de Soluciones,

Promedio del Número de Soluciones y Desviación Estándar, y se ordenarán por el valor

promedio del número de soluciones.

Así se obtuvo la siguiente tabla, que contiene las mejores combinaciones, en la cuál

además, se muestra el promedio de ambos objetivos considerados:

Tabla 3.2: Resultados experimentos con parámetros para AG

Ind

ivid

uo

s

Gen

era

cio

nes

%M

uta

ció

n

Pro

m. N

um

.

Solu

cio

nes

Des

via

ció

n

Esta

nd

ar

Ca

nt.

Cu

rva

s

Ma

x. N

um

.

Solu

cio

nes

Min

. Nu

m.

Solu

cio

nes

Pro

m. C

ma

x

Pro

med

io

Tard

an

za

300 150 10 7.2 1.8 6 9 4 3,685.7 15,447

300 500 10 7.1 2.0 5 9 4 3,660.7 14,851

100 100 15 6.3 2.3 7 11 4 3,692.9 17,153

300 150 15 6.2 2.2 7 11 3 3,649.0 15,420

300 150 5 6.1 1.7 6 8 3 3,700.1 16,301

Las demás soluciones poseían un Promedio de Número de Soluciones inferior a 5.5 y estás

poseían los mejores promedios de Cmax y Tardanza, además los Máximos y Mínimos de

Número de Soluciones son superiores a la media, que fueron 6.6 y 2.5 respectivamente.

Posterior a este análisis se tomaron los resultados entregados por las 4 primeras

combinaciones, y con éstos se generó una sola curva para realizar el análisis propuesto por

Hyun et al. (1998). Así se obtuvieron 10 gráficos como el siguiente:

Gráfico 3.3: Ejemplo de combinación de Curvas de Pareto Obtenidas

Con los que se pudo generar la siguiente tabla con los datos que muestra:

Tabla 3.3: Resultados comparativos de mejores combinaciones

100-100-15 300-150-10 300-150-15 300-500-10

1 --- --- --- 1.00

2 --- --- 0.50 0.50

3 --- --- --- 1.00

4 --- 0.58 0.42 ---

5 --- 0.69 --- 0.31

6 --- --- 0.43 0.57

7 --- --- --- 1.00

8 --- 0.13 0.38 0.50

9 --- --- --- 1.00

10 --- 0.09 0.645 0.27

Promedio 0 14.92% 23.57 61.52%

Lo que nos demuestra que la mejor combinación de parámetros es la de 300 individuos,

500 generaciones y 10 % de mutación. Por lo que estos serán los parámetros que se

utilizarán para comparar esta Metaheurística versus MOSARTS.

3.2 Parámetros para Simulated Annealing (MOSARTS)

Para el caso de Simulated Annealing los parámetros a determinar son las Memorias de

Largo y Corto Plazo para cada objetivo analizado, es decir, para la Tardanza y el Cmax.

De la misma forma que para el caso del AG, se harán combinaciones de parámetros y con

cada una de estas combinaciones se ejecutará el programa 10 veces, para ver como se

comporta. Las combinaciones de estos parámetros deben sumar 1 para cada objetivo, por

lo que todas las combinaciones a probar son las siguientes:

Tabla 3.4: Combinaciones para parámetros de MOSARTS

Memoria C/P

Cmax

Memoria L/P

Cmax

Memoria C/P

Tardanza

Memoria C/P

Tardanza

0.2 0.8 0.2 0.8

0.2 0.8 0.5 0.5

0.2 0.8 0.8 0.2

0.5 0.5 0.2 0.8

0.5 0.5 0.5 0.5

0.5 0.5 0.8 0.2

0.8 0.2 0.2 0.8

0.8 0.2 0.5 0.5

0.8 0.2 0.8 0.2

Cantidad de Curvas Distintas, Máximo Número de Soluciones, Mínimo Número de

Soluciones, Promedio del Número de Soluciones y Desviación Estándar, son los datos que

se extraen al ejecutar el programa con cada una de las combinaciones. Además se calcula

el promedio de las curvas generadas por cada combinación de parámetros.

Tabla 3.5: Resultados experimentos con parámetros para MOSARTS

Combinación Promedio

Num. Sol

Desviación

Estándar

Cantidad

Curvas

Max. Num

Soluciones

Max. Num.

Soluciones

Prom.

Cmax

Prom.

Tard.

0.2 – 0.8 – 0.2 – 0.8 4.3 1.5 7 6 1 4,018 25,842

0.2 – 0.8 – 0 .5 – 0.5 5.7 2.0 5 7 1 4,026 26,196

0.2 – 0.8 – 0.8 – 0.2 5.2 1.2 5 6 4 4,032 25,446

0.5 – 0.5 – 0.2 – 0.8 3.9 1.4 7 6 2 3,976 24,734

0.5 – 0.5 – 0.5 – 0.5 2.6 1.0 5 5 2 3,987 24,959

0.5 – 0.5 – 0.8 – 0.2 3.3 1.3 6 6 1 3,991 24,905

0.8 – 0.2 – 0.2 – 0.8 4.2 1.2 6 6 2 3,979 24,904

0.8 – 0.2 – 0.5 – 0.5 3.9 2.0 7 7 2 4,013 24,815

0.8 – 0.2 – 0.8 – 0.2 4.1 1.6 7 7 2 4,003 25,047

4.1 1.5 6.1 6.2 1.9 4,002.70 25,205.40

Observando el Promedio del Número de Soluciones generadas por la Metaheurística, se

puede decir que hay dos combinaciones superiores a las demás, las que tienen un

promedio de 5.7 y 5.2. A su vez, existen cuatro combinaciones que tienen un promedio de

Cmax y Tardanza inferior al promedio, las que también se puede decir que son buenas

combinaciones. Por este motivo se compararán estas seis combinaciones utilizando el

método de Hyun et al. (1998). El siguiente gráfico es un ejemplo de cómo todas las curvas

generan una nueva, la que muestra cuáles curvas domina la nueva frontera.

Gráfico 3.4: Ejemplo combinación de Curvas de Pareto Obtenidas

Así, se obtuvieron los siguientes resultados:

Tabla 3.6: Resultados comparativos de mejores combinaciones

0.2

– 0

.8 –

0.5

– 0

.5

0.2

– 0

.8 –

0.8

– 0

.2

0.5

– 0

.5 –

0.2

– 0

.8

0.2

– 0

.8 –

0.5

– 0

.5

0.5

– 0

.5 –

0.8

– 0

.2

0.8

– 0

.2 –

0.2

– 0

.8

1 -- 0.33 -- 0.17 0.33 0.17

2 -- -- 0.17 -- -- 0.83

3 -- -- 0.17 -- -- 0.83

4 -- -- 0.67 -- -- 0.33

5 -- -- 0.4 0.14 0.14 0.57

6 -- -- 0.50 -- 0.50 --

7 -- -- -- 0.50 0.25 0.25

8 0.5 -- 0.50 -- -- --

9 -- 0.20 0.20 -- 0.20 0.40

10 -- 0.29 0.43 -- 0.14 0.14

Promedio 5.00% 8.19% 27.71% 8.10% 15.69% 35.31%

Los promedios obtenidos indican que la tercera y sexta combinación son las mejores, es

decir, que para la Tardanza se debe tener una ponderación de la Memoria de Largo Plazo

alta, en este caso, 0.8 u 80%, y una ponderación pequeña para la Memoria de corto Plazo,

o sea, un 20%. Pero no queda claro cuales son mejores parámetros para el objetivo Cmax.

Por este motivo se realizó una comparación con el método de Hyun, et al. (1998), entre

estas dos combinaciones solamente, para ver cuál de ellas era mejor. Los resultados se

presentan en la siguiente tabla:

Tabla 3.7: Resultados comparativos de las dos mejores combinaciones

0.5 – 0.5 – 0.2 – 0.8 0.8 – 025 – 0.2 – 0.8

1 0.25 0.75

2 0.17 0.83

3 0.17 0.83

4 0.67 0.33

5 0.20 0.80

6 1.00 0.00

7 0.25 0.75

8 1.00 0.00

9 0.50 0.50

10 0.83 0.17

Promedio 50.33 49.76

Lo que deja empatadas a ambas combinaciones. Dado esto, se optó por considerar cuál de

ellas presenta una mayor densidad de las Curvas de Pareto:

Tabla 3.8: Comparación de las mejores combinaciones para MOSARTS

Combinación Prom.

Num.Sol

Desviación

Estándar

Cant.

Curvas

Max.

Num.Sol

Min.

Num.Sol

Prom.

Cmax

Prom

Tard.

0.5-0.5-0.2-0.8 3.9 1.4 7 6 2 3,976 24,734

0.8-0.2-0.2-0.8 4.2 1.2 6 6 2 3,979 24,904

Así es como se determinó que la combinación de 80 %, 20 % para las memorias de Largo y

Corto Plazo, respectivamente, en el Objetivo Cmax, serán consideradas para la

comparación con el Algoritmo Genético.

3.2.1 Comparación de MOSARTS versus Simulated Annealing Simple

La diferencia entre MOSARTS y una implementación normal de Simulated Annealing es la

introducción de una memoria de largo y corto plazo para la elección de un Objetivo

Referente que guíe la búsqueda, la que para Simulated Annealing realiza observando el

comportamiento de todos los objetivos al mismo tiempo.

Así, es interesante comparar estas dos formas de Simulated Annealing para ver en qué

medida aporta MOSARTS a la resolución de problemas. Para la comparación se utilizaron

los mismos métodos vistos anteriormente, y los resultados obtenidos se muestran a

continuación:

Tabla 3.9: Comparación entre MOSARTS y Simulated Annealing Simple

Metaheuristica Prom.

Num.Sol

Desv.

Estandar

Cant.

Curvas

Max.

Num.Sol

Mix.

Num.Sol

Prom.

Cmax

Prom.

Tard

SA Simple 4.3 1.3 7 6 2 4,027.0 26,574.2

MOSARTS 3.6 1.1 9 5 1 3,987.4 25,541.7

Como se puede observar, MOSARTS muestra una ventaja en cuanto a los promedios de los

objetivos, aun cuando, el promedio de número de soluciones de las curvas de pareto es

inferior. Además, utilizando el método de Hyun et al. (1998), se obtuvieron los siguientes

resultados:

Tabla 3.10: Resultados comparativos entre MOSARTS y Simulated Annealing simple

Experto MOSARTS SA SIMPLE

1 0.67 0.33

2 0.33 0.67

3 0.80 0.20

4 0.50 0.50

5 1.00 0.00

6 0.60 0.40

7 0.80 0.20

8 1.00 0.00

9 1.00 0.00

10 0.80 0.20

PROMEDIO 75% 25%

Los resultados expuestos indican que, al generar una Curva de Pareto uniendo las dos

curvas generadas individualmente por ambas Metaheurísticas, en promedio, un 75 % de

las soluciones pertenecen a MOSARTS y sólo un 25% a Simulated Annealing simple.

Esto nos muestra que MOSARTS es un mejor método que el uso de Simulated Annealing

simple, por lo que es un aporte en el estudio de las Metaheurísticas, y resolución de

problemas combinatorios, y refuerza el interés por compararla con otra técnica más

sofisticada como lo es Algoritmos Genéticos.

Capítulo 4. COMPARACION ENTRE MOSARTS

(SIMULATED ANNEALING) Y UN ALGORITMO

GENÉTICO MULTIOBJETICO

Para la comparación entre ambas Metaheurísticas se utilizarán los mismos criterios a los

que se recurrió para la comparación entre distintos parámetros. Así, cada una será

ejecutada diez veces para ver su comportamiento en comparación con la otra. Se utilizarán

dos problemas de prueba uno grande, el mismo utilizado anteriormente, de 49 trabajos y

máquinas, y otro más pequeño de 20 trabajos y 10 máquinas.

4.1 Comparación para Problema Grande

De los datos obtenidos al ejecutar ambas Metaheurísticas 10 veces, se extrajo la siguiente

información:

Tabla 4.1: Comparación entre MOSARTS (SA) y Algoritmo Genético

Meta

Heurística

Prom.

Num.Sol

Desviación

Estándar

Cant.

Curvas

Max.

Num.Sol

Min.

Num.Sol

Prom.

Cmax

Prom.

Tard.

AG 5.4 2.5 8 9 2 3,658.7 15,008.6

S.A 3.6 1.1 9 5 1 3,987.4 25,541.7

Como se puede observar, el Algoritmo Genético, supera ampliamente en lo que respecta

al Promedio del Número de Soluciones de las Curvas de Pareto generadas y al Promedio de

los Objetivos que se desean minimizar. Por este motivo, se muestra a continuación un

gráfico en el cual están todas las curvas obtenidas en el proceso de comparación, para ver

una visión general del comportamiento de ambas metaheurísticas:

Gráfico 4.1: Comparación entre MOSARTS y Algoritmos Genéticos

Como se puede observar, todas las soluciones de las Curvas de Pareto generadas por el

Algoritmos Genético dominan a las generadas por MOSARTS en ambos objetivos.

4.2 Comparación para Problema Pequeño

Para el caso del problema mas pequeño MOSART no presenta muchas mejorías, aunque

en un primer análisis se ve una mayor densidad en las curvas generadas por esta

Metaheurística:

Tabla 4.2: Comparación entre MOSARTS (SA) y Algoritmo Genético

Meta

Heurística

Prom.

Num.Sol

Desviación

Estándar

Cant.

Curvas

Max.

Num.Sol

Min.

Num.Sol

Prom.

Cmax

Prom.

Tard.

AG 3.5 1.3 10 6 2 392.8 637.2

S.A 5.1 2.3 9 11 2 401.9 800.7

Pero el promedio de los objetivos sigue siendo peor. Además de las 10 iteraciones en que

fue comparado, sólo en una se logró superar al AG, obteniendo el 57% de la curva

generada por la combinación de las curvas de ambas Metaheurísticas, en el resto de las

iteraciones el AG siempre fue superior. Esto se puede apreciar en el siguiente gráfico

donde se muestran las soluciones de todas las curvas generadas durante la comparación:

Gráfico 4.2: Comparación entre MOSARTS y Algoritmo Genético para problema pequeño

4.3 Comentarios de la Comparación

Por lo visto en análisis comparativo, el Algoritmo Genético supera ampliamente a la

implementación de MOSARTS, sobretodo en el problema más grande. Pero uno de los

aspectos no mencionados, es el tiempo de ejecución de los programas. Mientras que para

el problema grande AG tiene un promedio de ejecución de 45 segundos, MOSARTS sólo

ocupa 0.75 segundos en promedio. Esto da una clara oportunidad a MOSARTS, para

modificaciones futuras que puedan incorporar nuevos mecanismos tendientes a explorar

mejor el espacio de soluciones, sin llegar a acercarse siquiera al tiempo que toma el AG en

ejecutarse.

Otro punto importante de mencionar es que el tiempo de ejecución de MOSARTS depende

de la Temperatura y de cómo ésta va disminuyendo. Como resultado de la comparación se

ve una gran diferencia en el objetivo de la Tardanza, lo que hace pensar en cómo mejorar

este objetivo. Así, se puede intentar que la temperatura vaya disminuyendo más

lentamente para este objetivo, y de esta forma aumentar el número de soluciones

analizadas.

Realizando este nuevo experimento, que aproximadamente iguala los tiempos de ambas

Metaheurísticas, los resultados tampoco son muy alentadores para MOSARTS, ya que

aunque los promedios de los ambos objetivos disminuyeron de 3987,4 y 25541,7 a 3952,2

23439,4, las diferencias siguen siendo notorias, como se puede observar en el siguiente

gráfico:

Gráfico 4.3: Comparación entre MOSARTS y Algoritmo Genético

En este punto, no parece prudente volver a probar el algoritmo usando un valor de

disminución de la temperatura inferior, ya que aumentaría el tiempo de proceso por sobre

el AG, y no se ven grandes mejorías.

Capítulo 5. CONCLUSIONES Y COMENTARIOS

Generalmente las decisiones de cómo proceder en la elaboración de la secuencia que

seguirán los trabajos en el momento de procesarse, se toman en base a más de objetivo

que se desea optimizar, lo que hace que los problemas de programación de la producción

aumenten su complejidad, y pasan a llamarse Problemas de Optimización Multiobjetivo.

Estos problemas combinatorios, que se presentan en la industria, requieren un gran

esfuerzo de planificación.

Un Problema de Optimización Multiobjetivo es de tipo Flow-Shop si los trabajos que se

deben realizar deben seguir el mismo orden de paso por cada máquina que interviene en

el proceso. Los problemas Flow-Shop se ven claramente en Celulosas, Papeleras,

Madereras, Armadura de Automóviles, entre otras empresas.

Dada la complejidad exponencial de los problemas combinatorios, los algoritmos exactos

no pueden entregar una solución óptima en un tiempo aceptable, debido a la limitada

capacidad de proceso de los computadores. Y, aunque esta capacidad de proceso fuera

mucho mayor, tampoco podrían.

Las heurísticas nacen para intentar encontrar buenas soluciones en un tiempo aceptable,

pero no indican qué tan cerca de la solución óptima se encuentran. Por esto, aparecen las

Metaheurísticas, que se pueden entender como heurísticas, pero con mecanismos para

evitar caer en óptimos locales. Metaheurísticas basadas en Simulated Annealing y

Algoritmos Genéticos, en el ámbito de un solo objetivo, han sido ampliamente probadas, y

han entregado resultados muy buenos, lo que hacía presumir que, aplicadas a problemas

con más de un objetivo, se conseguirán resultados superiores. Lo que fue conseguido por

el Algoritmo Genético en un mayor grado que MOSARTS.

Las Metaheurísticas están sujetas al ingreso de parámetros, de los cuales depende en

muchas ocasiones el buen o mal desempeño de éstas, por lo que se debe experimentar el

ingreso de distintas combinaciones de estos parámetros para determinar cuál

combinación es la que más ayuda a obtener las mejores soluciones. Por esto, es

interesante la inclusión de mecanismos de ajuste automático de parámetros, para ambas

Metaheurísticas, que permitan obtener la mejor combinación de éstos, y así entregar

mejores soluciones.

La creación de una Curva de Pareto formada por la unión de dos de ellas, para luego

cuantificar el número de soluciones aportadas desde cada Metaheurística, método

introducido por Hyun, et al. (1998), es una muy buena medida para la comparación, ya que

indica claramente si existe superioridad de alguna Metaheurística en relación con otra.

En la literatura existente, por lo general el parámetro porcentaje de mutación siempre

está asociado a un valor pequeño de aproximadamente un 5% o menor, sin embargo, las

mejores combinaciones en la etapa de experimentación incluían valores como 10% o 15%.

De todos los datos extraídos al ejecutar las Metaheurísticas, el que mejor indica la calidad

de las soluciones entregadas, es el promedio de los valores de los objetivos analizados,

esto se ve en el análisis de parámetros y en la comparación de las Metaheurísticas, ya que

siempre fue mejor uno de los ítems con buenos promedios en estas columnas. Si bien

MOSARTS entrega mejores soluciones que Simulated Annealing simple, esto no es

suficiente para igualarse, o superar, a las soluciones entregadas por el Algoritmo Genético,

que siempre fue superior, por lo que se hace preciso alguna modificación a MOSARTS para

poder competir con algoritmos más sofisticados.

MOSARTS posee un tiempo de ejecución mucho menor que el Algoritmo Genético, por lo

que se ve como una oportunidad para realizar mejoras al algoritmo y que seguir siendo

mejor que otras Metaheurísticas en el uso del tiempo. A su vez, una posible mejora para el

Algoritmo Genético, claro que con un menoscabo en el tiempo de ejecución, y el hecho de

perder su esencia, sería convertirlo en un algoritmo híbrido mediante la incorporación de

heurísticas de búsqueda local.

NOMENCLATURA

• FIFO : First In First Out

• SPT : Short Process Time

• LPT : Long Process Time

• Ci : Tiempo de terminación de un trabajo

• Cmax : Tiempo de terminación del último trabajo en el sistema

• Tmax : Tardanza Total

• Lmax : Retardo máximo

• u/t : unidades de tiempo

• SA : Simulated Annealing

• AG : Algoritmo(s) Genético(s)

• VEGA : Vector Evaluated Genetic Algorithm

• MOGA : MultiObjective Genetic Algorithm

• NSGA : Multiobjetive Optimization using Non-Dominated Sorting in Genetic

Algorithms

• NPGA : Niched Pareto Genetic Algorithm

• MOSARTS: MultiObjective Simulated Annealing with Random Trajectory Search

• OR : Objetivo Referente

• FS : Función de Selección

• PS : Probabilidad de Selección

• FAP : Función de Selección Particular