programaciÓn de talleres de producciÓn seriales …
TRANSCRIPT
1
PROGRAMACIÓN DE TALLERES DE PRODUCCIÓN SERIALES HÍBRIDOS
(FLEXIBLES) CON MÚLTIPLES OBJETIVOS MEDIANTE
METAHEURÍSTICAS: COLONIAS DE HORMIGAS
ELYN LIZETH SOLANO CHARRIS
UNIVERSIDAD DEL NORTE
DIVISIÓN DE INGENIERÍAS
MAESTRIA EN INGENIERÍA INDUSTRIAL
BARRANQUILLA
2008
2
PROGRAMACIÓN DE TALLERES DE PRODUCCIÓN SERIALES HÍBRIDOS
(FLEXIBLES) CON MÚLTIPLES OBJETIVOS MEDIANTE
METAHEURÍSTICAS: COLONIAS DE HORMIGAS
ELYN LIZETH SOLANO CHARRIS
MONOGRAFÍA DE GRADO
Presentado como requisito para optar al título de Magíster en Ingeniería Industrial
Director
Ph. D Ing. Carlos D. Paternita Arboleda
UNIVERSIDAD DEL NORTE
DIVISIÓN DE INGENIERIAS
MAESTRIA EN INGENIERIA INDUSTRIAL
BARRANQUILLA
2008
3
Nota de Aceptación:
____________________________________
____________________________________
____________________________________
____________________________________
____________________________________
____________________________________
____________________________________
Ph. D. Ing. Carlos D. Paternina Arboleda
Director del Proyecto
____________________________________
Ph. D. Ing. Ángel León González
Coordinador Programa Maestría
Ingeniería Industrial
____________________________________
Ph.D., Mat. Agustín Barrios
Profesor Departamento de Matemáticas
Jurado
____________________________________
M.Sc. Carlos Ardila
Profesor, Departamento Ing. de Sistemas
Jurado
4
“A mis padres y a mi hermana, por brindarme el apoyo necesario para salir adelante
y cumplir mis propósitos profesionales, gracias por acompañarme en este viaje lleno
de tropiezos y alegrías donde ustedes han sido la principal fuente de inspiración para
mi lucha”.
5
AGRADECIMIENTOS
Con el presente proyecto de tesis, quiero agradecer a mi Director Ph. D Ing. Carlos D.
Paternina Arboleda por sus sugerencias para trabajar en esta temática, su apoyo, y
paciencia.
A mi amigo Ingeniero de Sistemas Alfredo José Pérez Martínez, por su invaluable
colaboración y apoyo incondicional.
Y a todos aquellos que hicieron participe de esta tesis por sus sugerencias y motivación.
6
RESUMEN
En el presente proyecto se desarrolló una aplicación computacional de colonias de
hormiga para la solución del problema HFK, (PM(l)
)lk
=1 || Fl(Cmax, C ), definido como un
flowshop flexible con K estaciones, M(l) máquinas idénticas, por cada estación (etapa)
l. El programa optimiza a través de Metaheurísticas dos objetivos en producción:
minimiza el lapso (Cmax) de producción y la suma de tiempos de terminación ( C ). De
acuerdo a lo anterior, los modelos de apoyo para la Toma de Decisiones (Decision
Support Models, DSM) sirven de soporte para la programación de operaciones en
empresas con sistemas de producción flexibles en serie y múltiples objetivos de
programación.
7
TABLA DE CONTENIDO
Pág.
1. INTRODUCCIÓN 11
1.1 FORMULACIÓN DEL PROBLEMA 11
1.1.1 Planteamiento del Problema 11
1.2 OBJETIVOS 13
1.2.1 Objetivo General 13
1.2.2 Objetivos Específicos 13
1.3 ALCANCES Y LIMITACIONES 13
1.3.1 Alcances 13
1.3.2 Limitaciones 14
1.4 MARCO DE REFERENCIA 14
1.4.1 Marco Teórico 14
1.4.1.1 Programación De Operaciones En Planta 17
1.4.1.2 Optimización Multi-objetivo 20
1.4.1.2.1 Función Objetivo 20
1.4.1.2.2 Restricciones 20
1.4.1.2.3 Vector objetivo 21
1.4.1.2.4 Soluciones no comparables 21
1.4.1.2.5 Mínimo Global 21
1.4.1.2.6 Mínimo Local 21
1.4.1.2.7 Máximo Global 22
1.4.1.2.8 Máximo Local 22
1.4.1.2.9 Dominancia de Pareto 22
1.4.1.2.10 Conjunto Pareto 22
1.4.1.2.11 Frente de Pareto 22
1.4.1.3 Heurísticas y Metaheurísticas 22
1.4.1.3.1 Algoritmos Evolutivos 24
1.4.1.3.1.1 Inicialización de la población 27
1.4.1.3.1.2 Función de Evaluación (Fitness) 28
1.4.1.3.1.3 Selección 28
8
1.4.1.3.1.4 Cruce (Crossover) 29
1.4.1.3.1.5 Mutación 30
1.4.1.3.2 Strenght Pareto Evolutionary Algoritm 2 31
1.4.1.3.3 Meta-Heurísticas De Colonias De Hormiga 32
1.5 METODOLOGIA 35
1.5.1 Tipo de estudio 35
1.5.2 Método de Investigación 35
1.5.3 Fuentes y Técnicas 36
1.5.4 Tratamiento de la información 36
2. SUPUESTOS BÁSICOS Y DISEÑO DEL ALGORITMO HÍBRIDO
ANT- COLONY 37
2.1 SUPUESTOS BÁSICOS 37
2.2 DISEÑO DEL ALGORITMO HÍBRIDO ANT- COLONY 38
2.2.1 Construir_solucion 39
2.2.2 Evaluar_solucion 39
2.2.3 Actualizar_Frente_Pareto 39
2.2.4 Actualizar_Feromonas 39
2.2.5 Reiniciar_ feromonas 40
3. EXPERIMENTACIÓN Y ANÁLISIS DE RESULTADOS 41
3.1 DESCRIPCIÓN DEL LOS ARCHIVOS DE ENTRADA 41
3.2 CARACTERÍSTICAS DEL EXPERIMENTO 42
3.3 CONFIGURACIÓN DE PARÁMETROS 42
3.4 RESULTADOS OBTENIDOS 43
3.5 COMPARACIÓN DE RESULTADOS 50
3.6 ANÁLISIS DE LOS RESULTADOS 62
4. CONCLUSIÓN Y TRABAJOS FUTUROS 66
4.1 CONCLUSIONES 66
4.2 TRABAJOS FUTUROS 66
ANEXOS 67
BIBLIOGRAFÍA 98
9
LISTA DE TABLAS
Pág.
Tabla 1. Escenario Flowshop Flexible 41
Tabla 2. Resultados iteración 1-5 44
Tabla 3. Resultados iteración 6-10 45
Tabla 4. Resultados iteración 11-15 46
Tabla 5. Resultados iteración 16-20 47
Tabla 6. Resultados iteración 20-25 48
Tabla 7. Resultados iteración 26-30 49
Tabla 8. Porcentajes diferenciales iteración 1-5 53
Tabla 9. Porcentajes diferenciales iteración 6-10 54
Tabla 10. Porcentajes diferenciales iteración 11-15 55
Tabla 11. Porcentajes diferenciales iteración 16-20 57
Tabla 12. Porcentajes diferenciales iteración 21-25 58
Tabla 13. Porcentajes diferenciales iteración 26-30 60
Tabla 14. Coordenadas del Frente de Pareto obtenido con la herramienta
MHFACO 65
10
LISTA DE FIGURAS
Pág.
Figura 1. Sistema Flowshop Flexible 18
Figura 2. Representación de un Algoritmo Genético 26
Figura 3. Esquema de un Algoritmo Genético 27
Figura 4. Ejemplo de ejecución de un algoritmo genético 27
Figura 5. Las hormigas y el camino más corto 33
Figura 6. Imagen “Parámetros para la ejecución del Algoritmo” 43
Figura 7. Resultados del Cmax presentados por el LEKIN ® 51
Figura 8. Resultados del C presentados por el LEKIN ® 52
Figura 9. Frente de Pareto obtenido con la herramienta MHFACO 64
11
1. INTRODUCCIÓN
1.1 FORMULACIÓN DEL PROBLEMA
1.1.1 Planteamiento del Problema
La mayoría de problemas de optimización del mundo real tienen varios objetivos que
deben satisfacerse de manera simultánea, los cuales se encuentran sujetos a ciertas
restricciones propias de su entorno.
Ante la presencia de problemas de optimización con varios objetivos, la perspectiva o
concepción de lo que significa un óptimo, cambia con respecto a los problemas de
optimización que presentan un solo objetivo, ya que en la optimización mono-objetivo
la solución del problema es única, mientras en los problemas multi-objetivo la solución
no es necesariamente única, sino que, podría ser un conjunto de soluciones.
Para evidenciar este hecho, se toma como caso de implementación el siguiente
problema de programación de operaciones1:
Datos:
n, Número de trabajos
k, Número de estaciones
)(lM , l =1, …, k, Número de máquinas por estación
)(l
ip , i =1, …, n, l =1, …, k el tiempo de procesamiento de el trabajo Ji en la estación l
, =0, …, 1, peso
Variables:
vujiX ,,,, i, j = 1, …,n, u=1, …, )(vM , v =1, …k, variable binaria, igual a 1 si el trabajo
Ji es procesado en la posición j en la máquina uM en la estación v, 0 de otra forma
)(l
iC , i = 1, …, n, l =1, …, k, tiempo de terminación del trabajo Ji en la estación l
maxC , Makespan
1 T’kind, Billaut. “Multicriteria scheduling theory, models and algorithms”
12
C , suma de los tiempos de terminación de los trabajos
Objetivo: Minimizar max)1( CC
Restricciones:
)(
1 1
,,, ,...,1,,...,1,1
vM
m
n
l
vmli kvniX (A)
n
i
v
vmli nlkvMmX1
)(
,,, ,...,1,,...,1,,...,1,1 (B)
nunikvvMmHVXpXC vmui
u
l
n
j
v
jvmlj
v
i ,...1,,...,1,,...,1),(,...,1),)1(( ,,,
1 1
)(
,,,
)(
(C)
kvnipCC v
i
v
i
v
i ,...,1,,...,1,1 (D)
niCC k
i ,...,1,)(
max (E)
n
i
k
iCC1
)( (F)
El programa optimiza el siguiente problema HFK, (PM(l))l
k=1 || Fl(Cmax, C ), definido como
un flowshop flexible con k estaciones, M(l)
máquinas idénticas, por cada estación (etapa)
l; donde los dos objetivos en producción son: minimizar el lapso (Cmax) de producción
y la suma de tiempos de terminación ( C ).
La restricción (A) expresa el hecho de que todos los trabajos deben ser procesados en
cada estación. La restricción (B) implica el hecho que debe haber un trabajo en la
posición l en cada máquina. La restricción (C) y (D) permiten calcular los tiempos de
terminación en cada estación. Finalmente, la restricción (E) y (F) definen los criterios
Cmax y C que serán minimizados.
De acuerdo a lo anterior, el modelo planteado surge de la necesidad de dar solución al
problema mencionado y, para esto, se plantea una alternativa de solución a través de
Metaheurísticas: Colonias de Hormiga de concepción Multi-objetivo, que permita
optimizar la programación de operaciones en empresas con sistemas de producción
flexibles en serie y múltiples objetivos de programación.
13
1.2 OBJETIVOS
1.2.3 Objetivo General
Resolver el problema de programación de operaciones en empresas con sistemas de
producción flexibles en serie y múltiples objetivos de programación mediante la
aplicación de la metaheurística Ant Colony.
1.2.4 Objetivos Específicos
Diseñar e implementar sistemas de apoyo para la Toma de Decisiones (Decision
Support System, DSM) que sirvan de soporte para la programación de operaciones en
empresas con sistemas de producción flexibles en serie y múltiples objetivos de
programación.
Implementar una herramienta computacional que cumpla la función de facilitar la
aplicación de los DSM diseñados, y realizar de manera efectiva la actividad de
programación de operaciones en planta.
Comparar los resultados obtenidos por la herramienta propuesta, con los resultados
obtenidos con la herramienta de dominio público LEKIN ®.
1.3 ALCANCES Y LIMITACIONES
1.3.1 Alcances
El proyecto de la presente propuesta cumple con los siguientes objetivos específicos:
El desarrollo de una aplicación de colonias de hormigas para minimizar el lapso
(Cmax) de producción y la suma de tiempos de terminación ( C ) en entornos de
producción flexibles en serie y con múltiples objetivos de programación.
14
Diseño e implementación del sistema DSM, el cual implica el desarrollo de los
siguientes aspectos:
1. Modelos de optimización necesarios para realizar en forma optimizada la
programación de operaciones.
2. Herramientas de programación de operaciones.
3. Entrega de resultados y documentación relacionada con los modelos
desarrollados.
Adicionalmente, el conjunto de modelos implementado permitirá la aplicación de la
herramienta en empresas que cumplan con el entorno de producción en estudio, esto a
su vez facilitará la elaboración de planes gruesos de contingencia con relación a su
sistema productivo.
1.3.2 Limitaciones
El proyecto se encuentra limitado al desarrollo de algoritmos para la programación de
operaciones en empresas con entornos de producción flexibles en serie. No se tendrán
en cuenta en principio para este problema restricciones sobre el taller de producción o
sobre órdenes de producción, tiempos de liberación de las órdenes de producción, y
tiempos de alistamiento.
1.4 MARCO DE REFERENCIA
1.4.1 Marco Teórico
Gran parte de los problemas del mundo real implican la optimización simultánea de
varios objetivos que generalmente presentan conflictos entre ellos; es decir, la mejora en
uno conduce a un deterioro en el otro. La presencia de tales tipos de problemas es tan
significativa, que consume gran parte de nuestro tiempo cotidiano de decisión. Se trata,
por ejemplo, de escoger el medio ideal para llegar al trabajo, establecer el orden de
nuestras tareas, elegir el restaurante para el almuerzo, hacer las compras en el
supermercado, preparar la cena y la distribución de actividades en el tiempo de ocio
restante. También es el mismo tipo de problemas que enfrentan los ingenieros y
técnicos a la hora de diseñar e implementar sistemas de todo tipo: existen múltiples
objetivos a cumplir y se espera lograrlos todos en la medida de lo posible.
15
Aunque la mayoría de los problemas de decisión involucran este tipo de situaciones, las
propuestas computacionales que se han presentado para resolverlos habitualmente se
limitan a convertir el problema de objetivos múltiples en uno con objetivo único.
Esta reducción es debida a los modelos matemáticos empleados y puede realizarse de
varias maneras, por ejemplo se prioriza uno de los objetivos y los demás se colocan
como restricciones, o también se genera un objetivo compuesto otorgando pesos a los
objetivos en juego y armando una suma ponderada de los mismos. De todos modos,
ninguna de estas reducciones refleja fielmente al problema y, por tanto, tampoco otorga
soluciones completamente satisfactorias.
Se pone como ejemplo el problema de la compra de un automóvil. El comprador desea
un automóvil óptimo y por tanto no puede preocuparse solamente en minimizar el
precio del auto, ya que también le interesan otros factores. Si se tratase de un problema
de objetivo único, se conformaría con llamar a todos los distribuidores y hacer una lista
de precios (sin considerar marcas, modelos, tamaño, confort, etc.) y escogería el
automóvil de menor precio sin mayores complicaciones. Sin dudas, el modelo
matemático que está empleando en su búsqueda ¡no es el más apropiado!. Por ende, los
resultados tampoco son satisfactorios, y por ahorrarse unos pesos inicialmente, el
comprador acaba gastando todos sus ahorros en combustible y costos de mantenimiento.
Sin embargo, el estado actual de la ciencia podría generar mejores resultados ya que
existen modelos matemáticos que se ajustan mejor a la naturaleza de éstos problemas.
Tales modelos provienen de un área de la Investigación de Operaciones conocida como
optimización con objetivos múltiples o multiobjetivo.
En los problemas de optimización de un solo objetivo (SOPs, del inglés Single
Objective Problem) el resultado óptimo deseado está claramente definido. Partiendo del
ejemplo anterior el objetivo sería minimizar precio del automóvil, y el resultado sería el
automóvil con menor precio. Sin embargo, esta condición no se cumple para los
problemas de optimización multiobjetivo (MOPs, por sus siglas en inglés:
Multiobjective Optimization Problem) donde, en vez de un único óptimo, contamos con
todo un conjunto de soluciones de compromiso.
16
Para evidenciar este hecho se vuelve al ejemplo del problema de la compra de un
automóvil. El comprador tiene varios objetivos que desearía alcanzar, pero también
múltiples restricciones. En cuanto a objetivos podríamos mencionar: minimizar el costo
del automóvil, la cantidad de combustible consumida en una distancia dada, los gastos
de mantenimiento implicados, etc. Además, deseará maximizar el confort, el espacio, la
confiabilidad, la seguridad, tiempo transcurrido entre mantenimientos, costos de
reventa, etc. Cuando se plantean las restricciones descubrimos que este comprador
cuenta con un presupuesto limitado, desea un vehículo fabricado en la región y confía
más en algunas marcas que en otras. Los conflictos que surgen entre los objetivos
mencionados son obvios e inmediatamente –considerando la propia experiencia– surgen
posibles soluciones. Así tenemos el automóvil que tiene el menor precio, pero está
bastante alejado de los objetivos relacionados al confort, la seguridad y la confiabilidad.
También tenemos el de costo superior a los demás pero con óptimas características,
aunque amplio consumo de combustible. Así podemos citar numerosos ejemplos. Entre
éstos se encuentran los automóviles promedio, que cumplen con las restricciones dadas
y que implican una solución de compromiso entre todos los factores en juego. Entre
ellos no se puede decir que alguno sea mejor, ya que al alterar un factor para mejorarlo,
estamos empeorando otro. Así, en un problema de optimización multiobjetivo cotidiano,
resulta evidente la existencia de múltiples soluciones y la imposibilidad de decidir cuál
de ellas es mejor si se consideran todos los objetivos al mismo tiempo. En el caso del
comprador, para realizar su elección deberá necesariamente contar con algún criterio,
posiblemente de índole subjetiva, que le permita optar por una u otra alternativa.
Se dice que las soluciones de un problema con objetivos múltiples son óptimas porque
ninguna otra solución, en todo el espacio de búsqueda, es superior a ellas cuando se
tienen en cuenta todos los objetivos al mismo tiempo, i.e. ningún objetivo puede
mejorarse sin degradar a los demás.
Al conjunto de estas soluciones óptimas se conoce como soluciones Pareto óptimas. Su
nombre les fue dado en honor al ingeniero y economista Wilfredo Pareto, quien fue el
primero en definir un nuevo criterio de optimalidad para los problemas en que existen
múltiples objetivos a cumplir, y persisten conflictos al realizar la optimización
simultánea de los mismos. A partir de este concepto se establece, como requisito para
17
afirmar que una situación es mejor que otra, el que en ella no se disminuya a nadie, pero
se mejore a alguno; es decir que una situación será mejor que otra sólo si en la nueva es
posible compensar las pérdidas de todos los perjudicados... y aún queda un sobrante. En
todo otro caso, según Pareto, para decidir se requiere un juicio de valor y la ciencia no
puede guiarnos.
El presente capítulo presente las definiciones necesarias que fundamentan teóricamente
el presente proyecto.
1.4.1.1 Programación De Operaciones En Planta
La programación de la producción ha sido uno de los temas de investigación más
recurrentes en el área de administración de operaciones durante la última mitad de siglo
XX. Debido a la cada vez más fuerte competencia en los mercados, para muchas
empresas se ha hecho necesarios amplias su portafolio de productos, buscando de esta
manera satisfacer a más clientes potenciales. Este cambio aparentemente trae consigo
grandes problemas de planeación y el control de los sistemas productivos: Un número
amplio de referencias implica mayores niveles de inventario o mayores exigencias en
cuanto a capacidad instalada, lo que a su vez implica mayores costos operacionales. Si
a estos problemas se le suma una pobre programación de la producción, estos se pueden
ver multiplicados.
Debido a estas razones y a la gran complejidad que implica encontrar una solución al
problema de la programación de la producción, éste ha sido el tema de muchos
proyectos de investigación durante los últimos cuarenta años.
Programar es el proceso de organizar, elegir y dar tiempos al uso de recursos para llevar
a cabo todas las actividades necesarias, para producir las salidas deseadas en los tiempos
deseados, satisfaciendo a la vez un gran número de restricciones de tiempo y relaciones
entre las actividades y los recursos.
La enorme cantidad de combinaciones existentes en un sistema productivo, hacen
imposible la evaluación de todos los posibles programas para la determinación de el
programa de operaciones optimo, incluso implementando el mas poderoso sistema de
18
computo que pueda ser adquirido en la actualidad. Lo anterior impulsó el desarrollo de
técnicas inteligentes de optimización, las cuales no están diseñadas bajo la premisa de
obtener la solución óptima de un problema, sino en cambio, sacrificar un pequeño
margen de exactitud en beneficio de no requerir una desmesurada potencia de cómputo.
Un importante grupo de técnicas de optimización inteligentes son las denominadas
heurísticas y metaheurísticas.
Los países industrialmente desarrollados, poseen cerca de 30 años de investigación y
desarrollo en esta área, gran parte de estos desarrollos se gestan en las universidades.
Los países industrializados, son productores y distribuidores de esta tecnología.
Colombia se encuentra en una posición de consumidor, pero solo un pequeño grupo de
empresas, localizado en el sector de los grandes contribuyentes posee capacidad de
adquisición.
En esta investigación se estudia y se propone una nueva metodología para resolver el
problema de secuenciar apropiadamente n actividades independientes y disponibles
simultáneamente en N estaciones ó etapas con mj maquinas en paralelo. Esto es la
solución al sistema productivo flowshop flexible.
Figura 1. Sistema Flowshop Flexible.
Cada trabajo será procesado en cada etapa una sola vez. Además, todos los trabajos
serán procesados en la primera estación, luego en la segunda estación hasta completar la
secuencia. El tiempo de procesamiento para cada producto en cada estación estará
compuesto el tiempo de alistamiento de la máquina, el tiempo en que la máquina
transforma al producto, es decir lo procesa y el tiempo para retirar el producto de la
máquina, antes de colocar el siguiente.
19
La función Objetivo de interés es minimizar makespan Cmax y la suma de los tiempos
de terminación de los trabajos simultáneamente. También es ampliamente conocido
como lapso. Definido de otra forma, es el tiempo en donde la última actividad deja al
sistema.
A pesar que el problema flowshop flexible con múltiples maquinas ha sido estudiado en
otras investigaciones, a la fecha no se encontraron instancias publicadas para este tipo
de problemas. Sin embargo, durante la investigación se generaron varias instancias que
pueden ser utilizadas por otros investigadores para sus futuros análisis. Incluyendo
medidas desempeño de la heurística y el valor óptimo para cada conjunto de datos.
Una de las principales limitaciones para comparar la heurística con el óptimo es lo
extenso del espacio de posibles secuencias para el problema en estudio. De allí que para
n productos, N estaciones y Mj maquinas por estación (con n > mj; para todo j tal que j
= 1, 2,.. N). El numero total de soluciones o secuencias viene dada por la ecuación:
N
j jjj mmmn
nn
1 )!()!1()!(
)!()!1(
Observemos que para una de las instancias de la investigación: problema con 7
productos, 5 estaciones y 3, 4, 3, 2 y 2 maquinas en cada estación respectivamente, el
problema esta sujeto a un espacio de 1.52 x 1020 posibles secuencias. Si se cuenta con
un equipo de computo que pueda procesar un billón de secuencias por segundo, dicho
equipo finalizará su labor en 4 años y 10 meses.
El problema de estudio es aún un problema abierto en la literatura. La mayor cantidad
de información asume trabajos no idénticos y máquinas paralelas idénticas (ver por
ejemplo los trabajos de Guinet y Solomon, Gupta, Gupta y Tung , Lee y Vairaktarakis.
Desouki et al. Propone un procedure O(n log n) basado en la regla LST para resolver un
problema más sencillo mono-objetivo: F1(Q1) | rj, pj = 1, | Cmax. T´kindt y Billaut
presentan una propuesta más cercana al problema de interés de esta investigación, pero
sólo introducen el modelo matemático de programación entera binaria con ponderación
de objetivos.
20
1.4.1.2 Optimización Multi-objetivo
La optimización multi-objetivo puede ser definida como el problema de encontrar un
vector de variables de decisión que satisfacen restricciones y optimiza un vector de
funciones cuyos elementos representan las funciones objetivo. Estas definiciones
aparecen en los trabajos de Coello y Deb.
Se desea encontrar un vector de decisión:
Tnxxxx ,...,, 21
con nRx
, que deberá satisfacer restricciones de desigualdad:
0)( xg i
wi ,...,2,1
y optimizar el vector de funciones
Tb xfxfxfxf )(),...,(),()( 21
que generalmente cumple con bRxf )(
. El conjunto de todas las soluciones que
satisfacen la condición es conocido como dominio de soluciones factibles, y se
representa como , en general nR . El correspondiente conjunto imagen o se
define como:
xRxf bo
)(
1.4.1.2.1 Función Objetivo: Denotada con f, función objetivo convierte los vectores de
decisión en un espacio K-dimensional llamado Espacio Objetivo, kRZ ( R , el
conjunto de los números reales). f es un conjunto de funciones T
kffff ),...,,( 21 .
1.4.1.2.2 Restricciones: En todo problema de optimización con restricciones, el
entorno, la disponibilidad de recursos o las características inherentes al problema,
21
imponen sobre éste un conjunto de restricciones, que deben ser satisfechas al solucionar
el problema, con el fin de tener soluciones factibles.
Las restricciones están dadas en términos de las variables de decisión y de los
operadores de(<, , , > y 0) . Una posible forma de enunciar restricciones sería:
ri(x) >=0; i=1, 2, …, m
si(x) <=0; i=1, 2, …, p
gi(x) =0; i=1, 2, ..., k
donde m+p+k debe ser menor que el número de variables de decisión n, para que
puedan existir grados de libertad a optimizar.
1.4.1.2.3 Vector objetivo: (vector de criterio, punto): Denotado con z representa la
imagen en el espacio objetivo de un vector de decisión a través de f.
T
kkk xfxfxfzzzxfZ ))(),...(),((),...,()( 221121
1.4.1.2.4 Soluciones no comparables: Dados u, v, si u v ni v u, se dice que
son soluciones no comparables, lo que se denota como u ~ v.
1.4.1.2.5 Mínimo Global: Dada la función f, supongamos que θ el conjunto de
soluciones factibles es diferente de vacío, entonces x*, es llamado un mínimo global si
para toda x θ, se tiene que:
f(x*) f(x)
1.4.1.2.6 Mínimo local: Dada la función f, supongamos que θ el conjunto de soluciones
factibles es diferente de vacío, entonces x*, es llamado un mínimo local si para toda
x I θ, se tiene que:
f(x*) f(x)
22
1.4.1.2.7 Máximo Global: Dada la función f, supongamos que θ el conjunto de
soluciones factibles es diferente de vacío, entonces x*, es llamado un mínimo global si
para toda x θ, se tiene que:
f(x*) (x)
1.4.1.2.8 Máximo local: Dada la función f, supongamos que θ el conjunto de soluciones
factibles es diferente de vacío, entonces x*, es llamado un mínimo local si para toda
x θ, se tiene que:
f(x*) f(x)
1.4.1.2.9 Dominancia de Pareto: Sean dos soluciones u , v . Se dice que u domina
a v (denotado como u v) si es mejor o igual que v en cada uno de los objetivos y
estrictamente mejor en al menos un objetivo.
Como ejemplo, en un contexto de minimización u v si y solo si:
)(,...2,1,...,2,1)()( ufjbivfuf jii < )(vf j
1.4.1.2.10 Conjunto Pareto: El conjunto de todas las soluciones x
no dominadas en
se denomina Conjunto Pareto, lo que se denota como CP. Las soluciones x
que
pertenecen a CP se denotarán como x*.
1.4.1.2.11 Frente de Pareto: La imagen del Conjunto Pareto a través de la función f
se
denomina Frente Pareto, denotado por Y.
1.4.1.3 Heurísticas y Metaheurísticas
En general existe una gran cantidad de problemas que se consideran difíciles de
resolver. La dificultad de los problemas está caracterizada por la teoría de complejidad
computacional.
23
Se sabe que muchos problemas son NP-duros, esto es, el tiempo que requieren para
resolver una instancia de ese problema crece en el peor de los casos de manera
exponencial con respecto al tamaño de la instancia.
Por lo mismo, muchas veces se tienen que solucionar usando métodos de solución
aproximados, que regresan buenas soluciones (inclusive a veces óptimas) a bajo costo
computacional.
Las heurísticas proviene de la palabra griega eureka, utilizada por Arquímedes, y ha
sido utilizado para agrupar un conjunto de algoritmos de búsqueda basados en
estructuras repetitivas, con los cuales se dirigen procesos de decisión2. En términos
generales, una heurística es el procedimiento repetitivo que identifica una solución
factible, con la cual se espera acercarse a la solución óptima. Muchas de las estrategias
de búsqueda podrían usarse, aunque algunas pueden resultar ser demasiado costosas o
quedar atrapadas en mínimos locales.
Las metaheurísticas se proponen como métodos, determinísticos o estocásticos para
salir de mínimos locales, es decir, son estrategias maestras que permiten resolver de
manera inteligente un problema3. El término metaheurísticas se obtiene de anteponer a
heurística el sujeto meta, que significa más allá o a un nivel superior, lo que concuerda
con la descripción que Crainic y Toulouse (2003) hacen de estas técnicas al afirmar que
modifican otras heurísticas para producir mejores soluciones que las encontradas de la
manera clásica.
Algunas de las propiedades deseables para una metahuerística son:
Simplicidad: debe de ser simple y basada en un principio claro que pueda ser
aplicable en general.
Precisión: debe de estar formulada en términos matemáticos precisos.
2 Burke, E., Kendall, G., Newall, J., Hart, E., Ross, P. and Schulenburg, S., Hyper-heuristics: an
emerging direction in modern search technology., En: Glover, F. y Kochenberger, G. (Eds.). Handbook
of metaheuristics. Kluwer academic publisher, 2003.
2 Melián, B., Moreno, J. y Moreno, M., Metaheurísticas: una visión global. Inteligencia Artificial.,
Revista Iberoamericana de Inteligencia Artificial, No.19, 2003, pp. 7-28
24
Coherencia: todos los pasos deben de seguir en forma natural los principios de la
metaheurística.
Eficiencia: debe de tomar un tiempo razonable de tiempo.
Efectividad: debe de encontrar las soluciones óptimas para la mayoría de los
problemas de prueba en donde se conoce su solución.
Robustes: debe de ser consistente en una amplia variedad de instancias.
Amigable: debe de ser claramente expresada, fácil de entender y fácil de usar, y
con la menor cantidad de parámetros posibles.
Innovación: debe de poder atacar nuevos tipos de aplicaciones.
La mayoría de la metaherísticas cumplen con solo algunas de las propiedades arriba
mencionadas.
1.4.1.3.1 Algoritmos Evolutivos
Los algoritmos genéticos (en adelante AGs) son métodos adaptativos que se emplean
principalmente para la resolución de problemas de búsqueda y optimización. Se
enmarcan dentro de la rama de Inteligencia Artificial conocida como Computación
Evolutiva o Algoritmos Evolutivos. Esta rama trata el estudio de los fundamentos y
aplicaciones de técnicas heurísticas de búsqueda que emplean los principios de la
evolución natural. Existen otras técnicas que junto con los AGs pertenecen a esta rama,
las más importantes son; Programación Evolutiva, Estrategias Evolutivas, Programación
Genética y Sistemas Clasificadores. Las diferencias entre estas técnicas se basan
principalmente en los diferentes operadores que emplean y en las distintas técnicas de
selección y reproducción de los individuos de la población.
Los AGs son muy potentes y efectivos sobre todo para aquellos problemas con un gran
espacio de búsqueda y para los que no existe una técnica específica para resolverlo.
Podemos aprovecharnos de los AGs para realizar tareas muy complejas que de otra
forma sería muy difícil, o imposible, llevarlas a cabo con un enfoque más determinista;
problemas basados en variables con interdependencias muy complejas, en ingeniería
para optimizaciones numéricas de algunos problemas no lineales que resultan muy
difíciles de resolver por métodos analíticos, son muy eficientes para el control de robots,
e incluso resultan muy útiles para el ajuste de los pesos de las conexiones de redes
neuronales, etc.
25
Cuando se va a aplicar un Algoritmo Genético (AG) para resolver un problema, el
primer movimiento que se debe hacer es codificar dicho problema en un cromosoma
artificial. Los cromosomas artificiales pueden ser cadenas de unos y ceros, listas de
parámetros o hasta códigos complejos, pero la clave que debemos tener en mente es que
la maquinaria genética manipulará una representación finita de soluciones, no las
soluciones por sí mismas. Otro componente que se debe tener en cuenta cuando
intentamos resolver un problema es el procedimiento o los medios para discriminar las
soluciones buenas de las malas. La idea es que algo debe determinar la aptitud hacia el
propósito de una solución. Esa determinación la logra la función de evaluación o
función de Fitness, que será usada por el AG para guiar la evolución de las generaciones
futuras. Una vez codificado el problema de manera cromosómica y teniendo los medios
para discriminar las buenas soluciones de las malas, se está en condiciones de
evolucionar soluciones para nuestro problema mediante la creación de una población
inicial de soluciones posibles. Esta población puede ser creada aleatoriamente o
utilizando algún conocimiento previo de buenas soluciones posibles, pero la idea
principal es que se partirá la búsqueda desde una población y no desde un punto. Con la
población en su lugar, los operadores genéticos pueden procesar la población
iterativamente para crear una secuencia de poblaciones que esperanzadamente
contendrán más y mejores soluciones para el problema en cuestión. Existe una amplia
variedad de operadores utilizados en un AG, pero en general son selección,
recombinación (o crossover) y mutación.
El operador de selección aporta mayor supervivencia a los mejores individuos, en
términos del problema. Es el mecanismo conocido como “supervivencia del más apto”.
Su idea principal es la de seleccionar preferentemente las mejores soluciones. Por
supuesto, si solo se eligieran las mejores soluciones en forma repetida de la población
inicial, se esperaría hacer un poco más que simplemente ocupar la población con los
mejores de la primera generación. Por lo tanto, la mera selección de los mejores no es
suficiente, y deben hallarse los medios para crear nuevos y posiblemente mejores
individuos. Es aquí cuando aparecen la recombinación y la mutación.
La Recombinación es un operador genético que combina bits y partes de soluciones
padres para formar nuevos y posiblemente mejores descendientes. De nuevo, existen
26
muchos caminos para lograrla, y alcanzar una performance competente depende de su
aplicación apropiada. Mientras la recombinación crea un nuevo individuo mediante la
cruza de material genético, la mutación actúa simplemente modificándolo. Existen
muchas variaciones para la mutación, pero la idea principal es que un descendiente sea
idéntico a su progenitor excepto en uno o más cambios en sus genes. De esta manera, la
mutación representa un movimiento al azar en los alrededores de una solución
particular.
Figura 2. Representación de un Algoritmo Genético
Fuente: CASTRO VENTURA, Yanina Katherine; CERNA ALVARADO, Rolando Carlos; ZUTTA
MALAGA, Nelly Jasmín. Algoritmos Genéticos.
Esquema de un Algoritmo Genético:
Paso 1: t=0; generar una población aleatoria P={x1,...,xn}
Paso 2: calcular f(x1),...,f(xn)
Paso 3: t=t+1; aplicar los procedimientos de
- selección
- cruce
- mutación
generando una nueva población P’={x’1,...,x’n}
Paso 4: reemplazar P por P’
Paso 5: si no se cumple un criterio de optimalidad ir al paso 3
27
Figura 3. Esquema de un Algoritmo Genético
Fuente: CASTRO VENTURA, Yanina Katherine; CERNA ALVARADO, Rolando Carlos; ZUTTA
MALAGA, Nelly Jasmín. Algoritmos Genéticos.
La idea de los AG consiste en aplicar estas ideas sobre conjuntos de soluciones de un
problema matemático, logrando nuevas y mejores soluciones.
Figura 4. Ejemplo de ejecución de un algoritmo genético
Fuente: CASTRO VENTURA, Yanina Katherine; CERNA ALVARADO, Rolando Carlos; ZUTTA
MALAGA, Nelly Jasmín. Algoritmos Genéticos.
1.4.1.3.1.1 Inicialización de la población. La inicialización de la población determina
el proceso de creación de los individuos para el primer ciclo del algoritmo.
Normalmente, la población inicial se forma a partir de individuos creados
aleatoriamente. Se puede crear también utilizando alguna técnica heurística pero los
28
pocos estudios que existen sobre este tema indican que el AG tenderá a converger más
rápidamente pero con el riesgo de que el algoritmo converja hacia un óptimo local. 4
Las poblaciones iniciales creadas aleatoriamente pueden ser sembradas con
cromosomas buenos para conseguir una evolución más rápida, si se conocen a priori, el
valor de estas “semillas” buenas.
1.4.1.3.1.2 Función de Evaluación (Fitness). La evaluación es la unión entre el GA y
el mundo externo. La evaluación se realiza a través de una función que representa de
forma adecuada el problema y tiene como objetivo suministrar una medida de aptitud de
cada individuo en la población actual. La función de evaluación es para un GA lo que el
medio ambiente es para los seres humanos. Las funciones de evaluación son específicas
de cada problema. En el ejemplo, la función matemática f(x)=x2 mide la aptitud de cada
individuo. C1 es un individuo más apto que C2. 5
Un buen diseño de la función de evaluación (también conocida como función objetivo o
función de adaptación) resulta extremadamente importante para el correcto
funcionamiento de un AG. Esta función determina el grado de adaptación o
aproximación de cada individuo al problema y por lo tanto permite distinguir a los
mejores individuos de los peores. A esta puntuación en función de su proximidad a la
mejor solución del problema se le denomina fitness.
1.4.1.3.1.3 Selección. Este operador es una versión artificial del concepto de selección
natural (Darwin). La función objetivo está asociada al beneficio, utilidad o bondad que
desea optimizarse La selección es el mecanismo por el cual soluciones más próximas al
óptimo (individuos mejor adaptados ) tienen mayor probabilidad de sobrevivir y ser
elegidos (seleccionados) para reproducirse.
Supongamos que, en una determinada iteración del algoritmo, tenemos un conjunto de
soluciones, que denominaremos población:
4 http://www.ica.ele.puc-rio.br/publicacoes/download/cnf_0111.pdf
4 Ibid 3
29
ZSxxxxP jr ,,...,, 21
y que cada una de ellas (que denominamos individuos) tiene un valor de la función
objetivo
)(),...,(),( 21 rxfxfxf
La selección supone que cuanto mayor sea )( ixf , mayor sea la probabilidad ip de que
ix sea elegido y se reproduzca.6 Una manera sencilla de hacer esto es tomar:
r
j
j
i
i
xf
xfp
1
)(
)(
Se debe garantizar que los mejores individuos tienen una mayor posibilidad de ser
padres (reproducirse) frente a los individuos menos buenos. De tal forma, hay que ser
cuidadosos para dar una oportunidad de reproducirse a los individuos menos buenos.
Éstos pueden incluir material genético útil en el proceso de reproducción. Esta idea nos
define la presión selectiva que determina en qué grado la reproducción está dirigida por
los mejores individuos. 7
1.4.1.3.1.4 Cruce (Crossover). Se denomina técnica de cruce a la forma de calcular el
genoma del nuevo individuo en función del genoma del padre y de la madre. El
operador de cruce es fuertemente responsable de las propiedades del algoritmo genético,
y determinará en gran medida la evolución de la población.8
Después de seleccionar a los individuos que engendrarán a la siguiente generación, llega
el momento de cruzarlos (crossover) entre ellos, y al igual que en la naturaleza, el
proceso consiste en crear a los descendientes a partir del intercambio de material
genético de sus padres. Existen dos técnicas principales; intercambio a partir de un solo
6 http://lfc.uah.es/olmeda/CNeuronal/Tema4A.pdf , Computación Neuronal
7 http://sci2s.ugr.es/docencia/bioinformatica/Bioinformatica-Tema_10.pdf, Bioinformatica
8 http://www.orcero.org/irbis/disertacion/node1.html , Varios
30
punto de cruce y a partir de dos puntos de cruce. En ambas técnicas se obtienen dos
descendientes fruto del cruce.
Para ciertos problemas es necesario emplear una técnica de cruzamiento especializada
que controle el proceso de intercambio genético evitando que se codifiquen en él
soluciones inválidas.
Independientemente de la técnica de cruce que se emplee, se suele implementar la
reproducción en un AG como un valor porcentual que indica la frecuencia con la que se
deben realizar los cruces, y los que no se crucen pasarán como réplicas de si mismos a
la siguiente generación (hay que tener también en cuenta que existe la posibilidad de
que se produzca una mutación durante la replicación del código).
Esto nos lleva a una técnica muy importante desarrollada hace unos cuantos años
conocida como elitismo. Consiste en que el mejor individuo de la población permanece
inalterable generación tras generación (ni siquiera se le aplica ningún tipo de mutación)
hasta que aparece un individuo con un fitness mejor que lo sustituye. Su importancia
reside en que de esta forma nunca se pierde la mejor solución encontrada hasta el
momento.9
1.4.1.3.1.5 Mutación. Da la posibilidad de recuperar material "genético" perdido en el
continuo proceso de reproducción y crossover. Durante la fase de cruce se aplica el
operador de mutación; aleatoriamente se modifican uno o más genes de los individuos
descendientes de la anterior generación. Esto se realiza para aumentar la diversidad
genética que favorece la aparición de individuos con un código genético distinto con la
posibilidad de que sea mejor, es especialmente importante la mutación cuando la
población, después de un cierto número de generaciones, tiende a converger hacia un
óptimo local. No es conveniente abusar del operador de mutación si no queremos que el
AG se convierta en un algoritmo de búsqueda al azar.
9 www.texelfactory.com/extras/Genetic_Algorithms_1.pdf , Javier Ventoso
31
Igual que sucede en la fase de cruce (reproducción), el proceso de mutación suele
implementarse como un valor porcentual y se ha comprobado que el ajuste correcto del
porcentaje de mutación es de vital importancia para el correcto funcionamiento del AG.
1.4.1.3.2 Strength Pareto Evolutionary Algorithm 2
El SPEA 2 es un algoritmo genético evolutivo utilizado para Optimización
Multiobjetivo creado por Zitzler, Laumanns y Thiele10
en el año 2001. Este algoritmo
mejora al algoritmo SPEA propuesto por Zitzler, Laumanns en 1999.
SPEA 2 mantiene una población elitista en la que guarda los mejores elementos de la
población en cada generación. Los elementos de la población elitista pueden estar
conformados por elementos no dominados exclusivamente, o por la combinación de
elementos no dominados y los mejores elementos no dominados, esto se debe a que en
el SPEA 2 la población elitista es de tamaño fijo.
Las principales diferencias entre el SPEA y el SPEA2 son las siguientes:
Un esquema mejorado de asignación de Fitness que toma en cuenta a cuántos
individuos domina un individuo y por cuántos individuos es dominado ese
individuo.
Una técnica de estimación de densidad del vecino más cercano.
Un nuevo método de truncamiento en la población elitista que garantiza la
preservación de soluciones en el Frente Pareto.
A continuación, se muestra el esquema del SPEA 2.
Entrada: N (Tamaño de la Población)
N (Tamaño del archivo)
T (Número máximo de Generaciones)
10
ZITZLER, Eckart; LAUMANNS, Marco and THIELE Lotear. SPEA2: Improving the Strength Pareto
Evolutionary Algorithm. Zurich: Swiss Federal Institute of Tecnology (ETH), 2000. Computer
Engineering and Networks Laboratory (TIK) Report No.
32
Salida: A (Conjunto de no dominado)
Paso 1. Inicialización: Generar la población inicial oP y crear el archivo vacío
(Conjunto Externo)
oP Φ. Colocar t=0
Paso 2. Asignación del Fitness: Calcular los valores de fitness de los individuos en
tP y tP
Paso 3. Selección Ambiental: Copiar todos los individuos no dominados de tP y tP a
1tP . Si el tamaño de 1tP excede a N , reducir 1tP mediante el operador de
truncamiento, de lo contrario, si el tamaño de 1tP < N , entonces llenar con
individuos dominados de tP y tP .
Paso 4. Terminación: Si Tt o se satisface otro criterio de paro entonces retorne el
conjunto A de soluciones no dominadas tomadas de 1tP .
Paso 5. Selección: Realizar torneo binario con reemplazo en 1tP para llenar el
conjunto de apareamiento.
Paso 6. Cruzamiento: Aplicar los operadores de recombinación y cruzamiento al
conjunto de apareamiento y construir 1tP . Incrementar t=t+1 e ir al paso 2.
1.4.1.3.3 Metaheurísticas De Colonias De Hormiga
El proyecto MOSCA (dirigido por Luca Gambardella, director del IDSIA en Suiza) es
una herramienta integrada de planificación, programación y control de sistemas de
producción y distribución que brinda soporte a procesos de desarrollo sostenible.
MOSCA se basa en colonias de hormiga como herramienta principal de optimización
por sus características particulares de complejidad computacional y calidad de
soluciones encontradas. A continuación se presenta una breve introducción a la meta-
heurística de colonias de hormiga.
33
Originalmente propuesto por Dorigo y Gambardella, las Colonias de Hormigas es una
propuesta de fines de los ochenta. Esta técnica es una metaheurística destinada
originalmente a problemas de optimización combinatoria y basada en la teoría de
optimización mediante procedimientos de aprendizaje reforzado. El algoritmo principal
es realmente un sistema multiagentes en el que las interacciones de bajo nivel entre
agentes simples (llamados "hormigas") producen, en su conjunto, un comportamiento
mucho más complejo, correspondiente a toda la colonia de hormigas. La idea se inspiró
en colonias reales de hormigas.
Las hormigas reales son capaces de encontrar el camino más corto entre una fuente de
comida y su nido - por ejemplo - sin usar mecanismos visuales, sino sólo explotando el
rastro de Feromona.
Una forma en que las hormigas explotan la feromona para encontrar el camino más
corto entre dos puntos es el que se muestra en la figura 5.
Figura 5. Las hormigas y el camino más corto
En a) las hormigas llegan a un punto en el cual deben decidirse por uno de los dos
caminos a seguir. En b) se realiza una elección de camino, la que puede ser aleatoria, al
haber bajos niveles de feromona, o guiada, al haber una diferencia notable entre la
cantidad de feromona depositada en cada camino. En c), dado que la velocidad de una
hormiga se considera aproximadamente constante, es claro sostener que las hormigas
que eligieron el camino más corto se demorarán menos que las otras en llegar hasta el
otro extremo, lo cual genera una mayor acumulación de feromona en el camino más
34
circulado. En d), la feromona acumulada en mayor cantidad en el camino más corto y
más circulado guía a las hormigas a la fuente de alimento de la forma más rápida.
Desde la perspectiva de la Inteligencia Artificial, las colonias de hormigas son
realmente técnicas de búsqueda local con registro histórico (como la búsqueda tabú) de
las rutas recorridas más y/o menos promisorias. Combinada con algoritmos evolutivos y
con aprendizaje mediante reforzamiento, esta técnica ha sido aplicada recientemente
con gran éxito a problemas de diseño en ingeniería, a optimización combinatoria y a
optimización no lineal en general.
El pseudo-codigo de las Metaheurísticas Colonias de Hormigas Genérico11
se muestra a
continuación:
Procedimiento
Inicializar_Parametros ( )
While not condicion_parada ( )
Generacion= Generacion + 1
for ant = 1 to m //m es la cantidad de hormigas
Construir_solucion ( )
Evaluar_solucion ( )
Actualizar_Frente_Pareto
Actualizar_Feromonas ( )
Actualizar_Conjunto_Pareto ( )
End for
End While
End
11
PACIELLO CORONEL, Julio Manuel; MARTÍNEZ SANTACRUZ, Héctor Daniel; LEZCANO RÍOS,
Christian Gerardo; BARÁN CEGLA, Benjamín. Algoritmos de Optimización Multi-Objetivos basados
en Colonias De Hormigas.
35
Procedimiento Construir_solucion
Sol=
While existen_estados_no_visitados ( )
siguiente= seleccionar_siguiente_estado ( )
sol= sol siguiente
marcar_como_visitado siguiente
if (actualización_paso_a_paso)
actualizar_feromonas_paso_a_paso ( )
End While
End
1.5 METODOLOGIA
1.5.1 Tipo de estudio
El tipo de estudio enmarcado en el proyecto se considera de tipo descriptivo, aplicativo,
ya que dentro de la investigación, es necesario llegar a los factores o variables que
desencadenan el problema, así mismo, se plantea como solución factible la aplicación e
implementación del algoritmo propuesto para dar solución al problema de programación
de operaciones en empresas con sistemas de producción flexibles en serie y múltiples
objetivos de programación, procediendo a la descripción última de su utilización y los
beneficios que surgen de la aplicación del sistema.
1.5.2 Método de Investigación
El método de investigación principal utilizado en la realización del proyecto es el
método analítico, el cual se basa en la identificación de las variables del problema. En
este caso, se hace necesario el análisis de los componentes del sistema.
36
1.5.3 Fuentes y Técnicas
La información requerida para el proyecto se toma de fuentes secundarias diversas
como textos, prensa, documentos, revistas e Internet y de fuentes primarias como
entrevistas con las personas con conocimientos en el área manejada.
1.5.4 Tratamiento de la información
La información, materia prima principal de la investigación, se clasifica teniendo en
cuenta la que esté relacionada con el DSM utilizado en algunos escenarios del problema
planteado.
37
2. SUPUESTOS BÁSICOS Y DISEÑO DEL ALGORITMO HÍBRIDO
ANT- COLONY
2.1 SUPUESTOS BÁSICOS
Los supuestos básicos de los que parten la mayor parte de soluciones propuestas son las
siguientes (Sipper, 1997):
Los tiempos de operación son conocidos con certidumbre.
Los tiempos de cambio de referencias son conocidos e independientes del orden
de procesamiento.
Todos los trabajos que se van a procesar están disponibles en tiempo cero.
Sólo se consideran restricciones de precedencia entre las operaciones de un
mismo trabajo.
Una vez que el trabajo está montado en una máquina, éste no puede ser
interrumpido.
Aunque en algunos casos, estos supuestos no se ajustan mucho a la realidad,
tratar de relajarlos implicaría una complejidad aún mayor en el ya bastante
complejo problema.
Adicionalmente existen en la realidad condiciones frecuentes tales como:
Operaciones que se realizan fuera del taller (recubrimientos superficiales,
tratamientos térmicos, etc.)
Restricciones de recursos: Las herramientas y/o dispositivos y operarios son
recursos limitados que suelen ser compartidos por máquinas de una estación o
estaciones diferentes.
Lotes de transporte: Cuando un trabajo está conformado por K piezas idénticas,
la cantidad de piezas que se producen después de cada setup en cada máquina la
denominaremos Lote, y la cantidad de piezas que se transportan entre máquinas
la denominaremos Lote de transporte, el cual no necesariamente es igual al Lote,
38
por el contrario, el desempeño del sistema aumenta cuando el tamaño del lote de
transporte se aproxima a la unidad.
2.2 DISEÑO DEL ALGORITMO HÍBRIDO ANT- COLONY
La metaheurística para diseñar algoritmos de optimización basados en colonias de
hormigas no fue concebida para tratar problemas multiobjetivo, por lo tanto se tiene que
proponer una modificación que permita resolver el modelo propuesto en este trabajo. A
continuación se presenta la adaptación del algoritmo:
Procedimiento
Inicializar_Parametros ( )
While not condicion_parada ( )
Generacion= Generacion + 1
repeat para cada hormiga k
Construir_solucion ( )
Evaluar_solucion ( )
End repeat
Actualizar_Frente_Pareto
Actualizar_Feromonas ( )
If (no_cambio (CP, K') //sin cambios en K'
generaciones
Reiniciar_ feromonas ( )
End While
End
Para resolver el modelo planteado con anterioridad, se utilizará el grafo de construcción
AQ(r, s) que tiene componentes AQ = r (nodos de la red) y s (enlaces entre los nodos).
A cada enlace lij L se le asocia un vector feromona 2Rf
ijs donde Ff y 0< s 2 ,
esto quiere decir que para cada flujos maneja un vector de feromonas independiente.
39
Las soluciones candidatas S son conjuntos de árboles que representa a una secuencia de
Ff . Cada uno de lo árboles serán conjuntos de caminos que inician en una fuente sf
y finalizan en un destino ff Tt .
2.2.1 Construir_solucion. En este procedimiento se construyen soluciones del
problema. Para construir una solución factible al modelo planteado, se necesita,
inicialmente, construir un conjunto de árboles factibles, los cuales son un conjunto de
caminos factibles que tomaría desde el nodo fuente sf hacia los destinos ff Tt .
La construcción de una solución, es un proceso iterativo que construye árboles para
cada flujo. Igualmente, los árboles se construyen iterativamente, a partir del nodo
fuente y de los destinos de un flujo se construyen los caminos. Así, cuando se tiene una
solución completa factible, se agrega en la lista de soluciones.12
2.2.2 Evaluar_solucion. La evaluación de la solución consiste en revisar la
optimalidad de las soluciones construidas por las hormigas con referencia a los
objetivos planteados en el problema a resolver.
2.2.3 Actualizar_Frente_Pareto. Es el método mediante el cual, en cada iteración i, a
partir de los elementos en la lista de soluciones y del frente de Pareto encontrado hasta
el momento, encuentra todos los elementos no dominados actualizando la lista del
Frente Pareto.
2.2.4 Actualizar_Feromonas. En este procedimiento la actualización se puede hacer
de varias formas, una es como hace el Ant System. La actualización y evaporación de
feromonas se realiza según la ecuación:
jiji ,, )1(
12
ARDILA HERNÁNDEZ, Carlos J. Diseño y análisis comparativo del algoritmo híbrido Ant Colony-
Evolutivos con respecto al algoritmo Ant Colony en la solución de un problema de optimización
Multiobjetivo en Redes ópticas. 2006.
40
donde representa el coeficiente de evaporación, y se calcula como:
)(
1
xf k
con bk ,...,2,1 en el caso de realizar una actualización basada en un solo objetivo.
Para el caso de actualización considerando los b objetivos al mismo tiempo, se calcula:
b
k
k xf1
)(
1
Ahora bien, la que minimiza la función por consiguiente aporta más feromona. Este
esquema extendido a varias matrices de feromonas, una por cada objetivo debido a su
forma de actualización llega un momento en el que no mejora porque no se le están
haciendo presión a las soluciones para que se muevan, es decir, el algoritmos aunque
evoluciona, llega un punto en que no evoluciona más, por lo cual, se hizo necesario
utilizar otra metodología para realizar la actualización de la feromona, en este caso, el
esquema con el que trabaja SPEA 2.
En esta caso, SPEA 2 clasifica las soluciones por frentes, una vez que eso pasa entonces
SPEA 2 selecciona las k mejores soluciones de la clasificación, teóricamente esas
soluciones son las del Frente de Pareto, pero si no hay soluciones en el frente, SPEA 2
llena los restantes espacios del frente con las siguientes soluciones, entonces, las k
soluciones son las que actualizan las feromonas.
2.2.5 Reiniciar_ feromonas. Es un mecanismo de control de convergencia al
algoritmo, que consiste en reiniciar la tabla de feromonas si durante K' generaciones,
con K' definido a priori, no se encontraron soluciones no dominadas. De esta manera, se
favorece la exploración de nuevos caminos. Este mecanismo ayuda a continuar la
búsqueda ante situaciones de convergencia como óptimos locales. En la nueva
propuesta, se reinicializa la tabla de feromonas de manera a continuar la ejecución.
41
3. EXPERIMENTACIÓN Y ANÁLISIS DE RESULTADOS
Para la ejecución del algoritmo se adaptaron dos problemas que cumplieran con las
características esenciales para ser resueltos, y se ejecutó 30 veces el algoritmo. Las
soluciones óptimas en cada iteración y la mejor encontrada por el algoritmo propuesto
son conocidas. En esta instancia el tiempo de procesamiento de los trabajos en cada
máquina por estación esta dado en minutos. Se asume que no hay tiempo de
alistamiento entre máquinas por estación, fechas de liberación de órdenes de trabajo y
fechas de entrega. A continuación se presentan brevemente la descripción de los
archivos de entrada, las características del experimento, la configuración de los
parámetros, los resultados obtenidos, la comparación de los resultados obtenidos y por
último el análisis de los resultados.
3.1 DESCRIPCIÓN DE LOS ARCHIVOS DE ENTRADA
Para la realización del experimento se tomó como prueba un escenario flowshop
flexible, estableciendo un archivo de entrada con el siguiente formato:
Número de Estaciones
Número de Trabajos
Número de máquinas por estación
Tiempos de procesamiento de cada trabajo en cada máquina
A continuación se muestran la tabla que describen los datos de entrada del escenario de
flowshop planteado:
Tabla 1. Escenario Flowshop Flexible
# de Estaciones 2
# de Trabajos 16
# de máquinas en la estación k 1 2
T. p. del trabajo i en la máquina 1 de la estación 1 5 9 3 5 3 2 9 3 7 5 3 2 4 4 9 7
T. p. del trabajo i en la máquina 2 de la estación 2 9 2 7 8 5 3 5 5 3 3 4 9 7 5 8 2
T. p. del trabajo i en la máquina 3 de la estación 2 9 2 7 8 5 3 5 5 3 3 4 9 7 5 8 2
42
3.2 CARACTERÍSTICAS DEL EXPERIMENTO
El experimento toma las características establecidas, y se analiza el comportamiento de
los resultados luego de haber definido las parámetros para la ejecución del algoritmo:
Número de Hormigas. Es un número natural que indica cuantas soluciones se
van a construir en cada iteración del algoritmo.
Número de Generaciones. Es el número de iteraciones de las medidas de aptitud
y la creación de una nueva población.
Soluciones en el Frente Elitista. Es un número natural. Como es sabido SPEA 2
mantiene un frente elitista de cierto número de soluciones que pueden ser todas
no dominadas entre si, o pueden ser no dominadas con las mejores dominadas.
Este número no es necesariamente el número de soluciones que va a dar como
resultado el algoritmo propuesto, pero si es el máximo de soluciones si todas las
soluciones que encuentre son no dominadas.
Tipo de Dominancia (Fuerte o Débil). De acuerdo a los objetivos que se
pretenden optimizar, esta opción permite escoger el tipo de dominancia a utilizar
al momento de evaluar dos o más soluciones.
3.3 CONFIGURACIÓN DE PARÁMETROS
En este tipo de técnicas de optimización, la configuración de parámetros es
definitivamente un aspecto de mucha incidencia sobre los resultados. El anterior
numeral lista algunos de los parámetros configurables del algoritmo propuesto,
respectivamente. A excepción del tipo de dominancia, el cual siempre será utilizado con
dominancia fuerte. Estos son:
Número de hormigas. Se verificó con = 50,10, 200; encontrando en general
mejores soluciones con = 100.
43
Número de Generaciones. Se verificó con = 30, 50, 100; encontrando en general
mejores soluciones con = 50.
Soluciones en el Frente Elitista. Se verificó con = 10, 30, 50, 70; encontrando en
general mejore soluciones con = 10.
Figura 6. Imagen “Parámetros para la ejecución del Algoritmo”
3.4 RESULTADOS OBTENIDOS
Las Tablas 2, 3, 4, 5, 6, 7 resumen los resultados de las 30 corridas con algoritmo
MHFACO (Hybrid Multiobjective Flowhop using Ant Colony) propuesto al ser
aplicado en el escenario planteado de un flowshop flexible:
44
Tabla 2. Resultados iteración 1-5
Iteración Cmax (f1) TotalCompletion (f2)
1
94 819
93 929
82 962
87 940
94 819
2
85 806
84 879
83 970
85 806
3
86 986
87 913
93 902
99 864
86 986
4
85 959
86 834
85 959
5
83 974
85 864
83 974
45
Tabla 3. Resultados iteración 6-10
Iteración Cmax (f1) TotalCompletion (f2)
6
82 976
84 958
85 829
82 976
7
96 873
83 981
84 975
85 918
87 913
89 907
96 873
8
82 919
89 855
82 919
9
88 887
84 1020
87 951
86 954
85 1008
88 887
10
96 859
86 894
83 908
96 859
46
Tabla 4. Resultados iteración 11-15
Iteración Cmax (f1) TotalCompletion (f2)
11
87 895
88 891
82 920
91 794
87 895
12
84 976
85 911
91 890
95 885
84 976
13
98 882
97 899
87 901
86 977
85 987
98 882
14
82 909
85 828
82 909
15
82 909
85 828
82 909
93 911
91 920
97 907
82 952
47
Tabla 5. Resultados iteración 16-20
Iteración Cmax (f1) TotalCompletion (f2)
16
90 847
86 867
85 894
85 948
82 955
90 847
17
83 956
87 890
90 863
83 956
18
87 822
82 943
87 822
19
82 913
86 904
88 899
93 885
82 913
20
82 913
86 904
88 899
93 885
82 913
48
Tabla 6. Resultados iteración 21-25
Iteración Cmax (f1) TotalCompletion (f2)
21
91 864
84 919
85 881
91 864
22
86 965
87 933
83 986
88 915
90 880
86 965
23
89 870
85 971
92 856
89 870
24
83 935
84 889
87 869
83 935
25
95 836
93 849
82 866
81 940
95 836
49
Tabla 7. Resultados iteración 26-30
Iteración Cmax (f1) TotalCompletion (f2)
26
85 983
96 897
84 984
92 913
86 924
88 922
89 919
85 983
27
85 1053
92 896
87 903
85 1053
28
89 839
93 821
85 933
89 839
29
90 887
89 926
82 965
90 887
30
85 952
86 935
95 890
88 933
89 922
109 887
85 952
50
3.5 COMPARACIÓN DE RESULTADOS
La aplicación computacional de colonias de hormiga propuesta para la optimización de
los dos objetivos en producción mencionados en el desarrollo del documento:
minimización del lapso (Cmax) de producción y la suma de los tiempos de terminación
(C), en un entorno flowshop flexible, no ha sido implementado con anterioridad.
En esta sección se compara los resultados obtenidos mediante la herramienta propuesta,
con los resultados obtenidos con el software de dominio público LEKIN ® diseñando
en Stern School of business, de la Universidad de New Cork en un proyecto dirigido por
el profesor Michael L. Pinedo y el profesor asociado Xiuli Chao, para la resolución de
problemas de scheduling con un solo objetivo a optimizar. El análisis comparativo se
hizo con base al problema planteado, hallando el % diferencial entre los resultados
obtenidos para el makespan entre los dos métodos, y de igual forma con la suma de los
tiempos de terminación. El porcentaje diferencial se calculó de la siguiente manera:
Primer Paso: Obtener el porcentual del resultado obtenido con el algoritmo propuesto
Vs. resultado obtenido con el LEKIN®.
%100*_._Pr__max
max
maxlekinC
propuestoCLekinVsopuestoCPorcentual
%100*_._Pr__lekinC
propuestoCLekinVsopuestoCPorcentual
51
Segundo Paso: Obtener la diferencia porcentual entre los resultados obtenidos con las
herramientas mencionadas.
opuestoPorcentualValorLekinPorcentualValorLekinVsopuestoCporcentualDiferencia Pr_____._Pr___ max
opuestoPorcentualValorLekinPorcentualValorLekinVsopuestoCporcentualDiferencia Pr_____._Pr___
Los resultados presentado por el LEKIN ® se presentan en las figuras 7 y 8 para cada
uno de los objetivos a optimizar maxC ,C
Figura 7. Resultados del Cmax presentados por el LEKIN ®
52
Figura 8. Resultados del C presentados por el LEKIN ®
A partir de los resultados obtenidos con el LEKIN ® a continuación se presentan en las
Tablas 8, 9, 10, 11, 12, 13, los porcentajes diferenciales con referencia a los resultados
de las 30 corridas con el algoritmo MHFACO.
53
Tabla 8. Porcentajes diferenciales iteración 1-5
Iteración Cmax (f1) Porcentual
Propuesto Vs. Lekin Diferencia % TotalCompletion (f2)
Porcentual Propuesto Vs. Lekin
Diferencia %
1
94 115 -15 819 137 -37
93 113 -13 929 156 -56
82 100 0 962 161 -61
87 106 -6 940 157 -57
94 115 -15 819 137 -37
2
85 104 -4 806 135 -35
84 102 -2 879 147 -47
83 101 -1 970 162 -62
85 104 -4 806 135 -35
3
86 105 -5 986 165 -65
87 106 -6 913 153 -53
93 113 -13 902 151 -51
99 121 -21 864 145 -45
86 105 -5 986 165 -65
4
85 104 -4 959 161 -61
86 105 -5 834 140 -40
85 104 -4 959 161 -61
5
83 101 -1 974 163 -63
85 104 -4 864 145 -45
83 101 -1 974 163 -63
54
Tabla 9. Porcentajes diferenciales iteración 6-10
Iteración Cmax (f1) Porcentual
Propuesto Vs. Lekin Diferencia % TotalCompletion (f2)
Porcentual Propuesto Vs. Lekin
Diferencia %
6
82 100 0 976 163 -63
84 102 -2 958 160 -60
85 104 -4 829 139 -39
82 100 0 976 163 -63
7
96 117 -17 873 146 -46
83 101 -1 981 164 -64
84 102 -2 975 163 -63
85 104 -4 918 154 -54
87 106 -6 913 153 -53
89 109 -9 907 152 -52
96 117 -17 873 146 -46
8
82 100 0 919 154 -54
89 109 -9 855 143 -43
82 100 0 919 154 -54
9
88 107 -7 887 149 -49
84 102 -2 1020 171 -71
87 106 -6 951 159 -59
86 105 -5 954 160 -60
85 104 -4 1008 169 -69
88 107 -7 887 149 -49
10
96 117 -17 859 144 -44
86 105 -5 894 150 -50
83 101 -1 908 152 -52
96 117 -17 859 144 -44
55
Tabla 10. Porcentajes diferenciales iteración 11-15
Iteración Cmax (f1) Porcentual
Propuesto Vs. Lekin Diferencia % TotalCompletion (f2)
Porcentual Propuesto Vs. Lekin
Diferencia %
11
87 106 -6 895 150 -50
88 107 -7 891 149 -49
82 100 0 920 154 -54
91 111 -11 794 133 -33
87 106 -6 895 150 -50
12
84 102 -2 976 163 -63
85 104 -4 911 153 -53
91 111 -11 890 149 -49
95 116 -16 885 148 -48
84 102 -2 976 163 -63
13
98 120 -20 882 148 -48
97 118 -18 899 151 -51
87 106 -6 901 151 -51
86 105 -5 977 164 -64
85 104 -4 987 165 -65 98 120 -20 882 148 -48
14
82 100 0 909 152 -52
85 104 -4 828 139 -39
82 100 0 909 152 -52
15
82 100 0 952 159 -52
86 105 -5 937 157 -39
89 109 -9 935 157 -52
93 113 -13 911 153 -53
56
91 111 -11 920 154 -54
97 118 -18 907 152 -52
82 100 0 952 159 -59
57
Tabla 11. Porcentajes diferenciales iteración 16-20
Iteración Cmax (f1) Porcentual
Propuesto Vs. Lekin Diferencia % TotalCompletion (f2)
Porcentual Propuesto Vs. Lekin
Diferencia %
16
90 110 -10 847 142 -42
86 105 -5 867 145 -45
85 104 -4 894 150 -50
85 104 -4 948 159 -59
82 100 0 955 160 -60
90 110 -10 847 142 -42
17
83 101 -1 956 160 -60
87 106 -6 890 149 -49
90 110 -10 863 145 -45
83 101 -1 956 160 -60
18
87 106 -6 822 138 -38
82 100 0 943 158 -58
87 106 -6 822 138 -38
19
82 100 0 913 153 -53
86 105 -5 904 151 -51
88 107 -7 899 151 -51
93 113 -13 885 148 -48
82 100 0 913 153 -53
20
91 111 -11 864 145 -45
84 102 -2 919 154 -54
85 104 -4 881 148 -48
91 111 -11 864 145 -45
58
Tabla 12. Porcentajes diferenciales iteración 21-25
Iteración Cmax (f1) Porcentual
Propuesto Vs. Lekin Diferencia % TotalCompletion (f2)
Porcentual Propuesto Vs. Lekin
Diferencia %
21
91 111 -11 864 145 -45
84 102 -2 919 154 -54
85 104 -4 881 148 -48
91 111 -11 864 145 -45
22
86 105 -5 965 162 -62
87 106 -6 933 156 -56
83 101 -1 986 165 -65
88 107 -7 915 153 -53
90 110 -10 880 147 -47
86 105 -5 965 162 -62
23
89 109 -9 870 146 -46
85 104 -4 971 163 -63
92 112 -12 856 143 -43
89 109 -9 870 146 -46
24
83 101 -1 935 157 -57
84 102 -2 889 149 -49
87 106 -6 869 146 -46
83 101 -1 935 157 -57
59
Iteración Cmax (f1) Porcentual
Propuesto Vs. Lekin Diferencia % TotalCompletion (f2)
Porcentual Propuesto Vs. Lekin
Diferencia %
25
95 116 -16 836 140 -40
93 113 -13 849 142 -42
82 100 0 866 145 -45
81 99 1 940 157 -57
95 116 -16 836 140 -40
60
Tabla 13. Porcentajes diferenciales iteración 26-30
Iteración Cmax (f1) Porcentual
Propuesto Vs. Lekin Diferencia
% TotalCompletion (f2)
Porcentual Propuesto Vs. Lekin
Diferencia %
26
85 104 -4 983 165
96 117 -17 897 150 -50
84 102 -2 984 165 -65
92 112 -12 913 153 -53
86 105 -5 924 155 -55
88 107 -7 922 154 -54
89 109 -9 919 154 -54
85 104 -4 983 165 -65
27
85 104 -4 1053 176 -76
92 112 -12 896 150 -50
87 106 -6 903 151 -51
85 104 -4 1053 176 -76
28
89 109 -9 839 141 -41
93 113 -13 821 138 -38
85 104 -4 933 156 -56
89 109 -9 839 141 -41
29
90 110 -10 887 149 -49
89 109 -9 926 155 -55
82 100 0 965 162 -62
90 110 -10 887 149 -49
61
Iteración Cmax (f1) Porcentual
Propuesto Vs. Lekin Diferencia %
TotalCompletion (f2)
Porcentual Propuesto Vs. Lekin
Diferencia %
30
85 104 -4 952 159 -59
86 105 -5 935 157 -57
95 116 -16 890 149 -49
88 107 -7 933 156 -56
89 109 -9 922 154 -54
109 133 -33 887 149 -49
85 104 -4 952 159 -59
62
3.6 ANÁLISIS DE LOS RESULTADOS
De acuerdo con los resultados obtenidos, en los que se muestra el comportamiento del
algoritmo propuesto al ser probado, se optimizan las dos funciones objetivos
mencionadas con anterioridad y cuya solución se ve alcanzada con metaheurísticas.
Para esto se propone la integración de procedimientos evolutivos del algoritmo SPEA2
en el Ant Colony, creando un algoritmo híbrido denominado MHFACO.
Partiendo de la premisa de que los modelos de optimización Ant-Colony, son realmente
un sistema multi-agente destinado originalmente a problemas de optimización
combinatoria y basada en la teoría de optimización mediante procedimientos de
aprendizaje reforzado, este algoritmo presenta muy buenas soluciones en la
optimización de problemas combinatorios tipo NP-hard.
Debido a lo anteriormente mencionado, la aplicación de modelos de optimización Ant-
Colony en la programación de operaciones de un entorno flowshop flexible parece
razonable y promisorio como se puede observar en la comparación de los resultados
presentados por la herramienta propuesta Vs. Resultado del LEKIN ® en las Tablas 8,
9, 10, 11, 12, 13.
Ahora bien, tomando como referencia las tablas donde se encuentra la comparación de
los resultados en las diferentes iteraciones, el algoritmo propuesto para el problema
resuelto, presenta una buena aproximación al resultado obtenido por el LEKIN®, en
donde se encuentra una diferencia porcentual para f1 que varía desde el 0% como la
mejor aproximación ( 82max C ), hasta un -21% para la solución más alejada ( 99max C )
al resultado obtenido por la herramienta utilizada como punto de comparación; y para el
caso de f2, la diferencia porcentual varía entre -35% y -65%, tomando como la mejor
solución la que nos da como diferencia porcentual el valor de -35% ( 806C ) y como la
solución más alejada la que nos da como diferencia porcentual el valor de -65%
( 986C ).
De igual forma se analizaron los resultados presentados en las iteraciones 6-30 en donde
se encuentra una diferencia porcentual para f1 que varía desde el 0% como la mejor
63
aproximación ( 82max C ), hasta un -33% para la solución más alejada ( 109max C ) al
resultado obtenido por la herramienta utilizada como punto de comparación; y para el
caso de f2, la diferencia porcentual varía entre -33% y -65%, tomando como la mejor
solución la que nos da como diferencia porcentual el valor de -35% ( 794C ) y como la
solución más alejada la que nos da como diferencia porcentual el valor de -65%
( 986C ).
En estos resultados, se observa para cada modelo, que los resultados obtenidos de los
promedios de las 30 iteraciones durante la ejecución del algoritmo MHFACO, dominan
en algunos casos débilmente y en otros más fuertemente a los resultados producidos
por la herramienta LEKIN ®. El hecho anterior nos da bases para afirmar que el
algoritmo MHFACO esta convergiendo a buenas soluciones, determinando en ellas
mejores resultados con respecto al primer objetivo ( maxC ) a optimizar que con respecto
al segundo ( C ), lo cual teóricamente es sustentable debido a que en las soluciones de un
problema con objetivos múltiples se tienen en cuenta todos los objetivos al mismo
tiempo, por lo cual, ningún objetivo puede mejorarse sin degradar a los demás. Luego
se establece como para afirmar que una situación o solución es mejor que otra, el que en
ella no se disminuya a nadie, pero se mejore a alguno; es decir que una situación será
mejor que otra sólo si en la nueva es posible compensar las pérdidas de todos los
perjudicados y aún queda un sobrante.
El hecho anterior nos da bases para afirmar que el algoritmo MHFACO esta
convergiendo a la solución verdadera, aunque desconocida, con mejor aproximación y
esto confirmará mediante al análisis funcional de las soluciones obtenidas a través de la
siguiente métrica: el Spacing (S), donde el frente de Pareto real este será asociado con el
frente de Pareto producido por el algoritmo propuesto. A continuación se presenta la
definición de la métrica nombrada:
SPACING (S)
La métrica S, nos indica qué tan bien están distribuidas las soluciones sobre el frente de
Pareto.
64
N
i
didN
S
1
2)(1
1
Donde dNjixfxfxfxfxfxfdjijiji
ji ;,...,2,1,;)()()()()()(min 3312211
es la media de todos
los di y N es el número de vectores en Yknown.
A continuación se presenta el resultado obtenido por la herramienta MHFACO, el cual
se evaluará mediante la métrica de desempeño “Spacing”:
Figura 9. Frente de Pareto obtenido con la herramienta MHFACO
65
Tabla 14. Coordenadas del Frente de Pareto obtenido con la herramienta MHFACO
CMax TotalCompletion
83 935
84 889
87 869
83 935
Teniendo en cuenta la formulación matemática del Spacing, las distancias de cada punto
en le frente exceptuando el último punto por ser igual al primero, y la distancia
promedio se presentan a continuación:
20Ad
20Bd
20Cd
20d
Luego S sería:
0)202020202020(13
1 222
S
Por lo tanto, como el valor del Spacing evaluado da como resultado un valor de cero,
esto nos estaría asegurando un buena distribución de los elementos del knownY , debido a
que para esta métrica un valor de 0 significa que todos los elementos de knownY están
equidistantemente espaciados.
66
4. CONCLUSIÓN Y TRABAJOS FUTUROS
4.1 CONCLUSIONES
En la presente investigación se desarrolló una herramienta computacional para la
programación de operaciones en empresas con sistemas de producción flexibles en
serie, optimizando en ellos 2 objetivos. En producción se minimiza el lapso (Cmax) de
producción y la suma de tiempos de terminación ( C ), cuya solución se alcanza a través
de una propuesta de integración de procedimientos evolutivos del algoritmo SPEA2 en
el Ant Colony, creando un algoritmo hibrido denominado MHFACO. Para la
implementación de esta herramienta, durante la investigación, se generaron varias
instancias que pueden ser utilizadas por otros investigadores para sus futuros análisis.
De acuerdo con los resultados discutidos en la referencia 3, en los que se muestra el
comportamiento del algoritmo propuesto Vs. El resultado obtenido con la herramienta
LEKIN ®, se puede concluir:
El algoritmo MHFACO tuvo muy buenos resultados, al aplicar la métrica de
desempeño: Spacing, donde presenta soluciones distribuidas y espaciadas
uniformemente.
Los resultados obtenidos de los promedios de las 30 iteraciones durante la
ejecución del algoritmo MHFACO, esta convergiendo a buenas soluciones,
determinando en ellas mejores resultados con respecto al primer objetivo ( maxC )
a optimizar que con respecto al segundo ( C ).
4.2 TRABAJOS FUTUROS
Implementar el algoritmo MHFACO, en entorno sistemas de producción
flexibles con máquinas con diferentes velocidades.
Introducir tiempos de alistamiento dependientes de la secuencia
Introducir limitación de buffers al flujo de producto
Preparar módulos para flujo re-entrante de órdenes de producción en el taller
67
ANEXOS
68
ANEXO 1. FRENTE PARETO ITERACIÓN 1
CMax TotalCompletion
94 819
93 929
82 962
87 940
94 819
69
ANEXO 2. FRENTE PARETO ITERACIÓN 2
CMax TotalCompletion
85 806
84 879
83 970
85 806
70
ANEXO 3. FRENTE PARETO ITERACIÓN 3
CMax TotalCompletion
86 986
87 913
93 902
99 864
86 986
71
ANEXO 4. FRENTE PARETO ITERACIÓN 4
CMax TotalCompletion
85 959
86 834
85 959
72
ANEXO 5. FRENTE PARETO ITERACIÓN 5
CMax TotalCompletion
83 974
85 864
83 974
73
ANEXO 6. FRENTE PARETO ITERACIÓN 6
CMax TotalCompletion
82 976
84 958
85 829
82 976
74
ANEXO 7. FRENTE PARETO ITERACIÓN 7
CMax TotalCompletion
96 873
83 981
84 975
85 918
87 913
89 907
96 873
75
ANEXO 8. FRENTE PARETO ITERACIÓN 8
CMax TotalCompletion
82 919
89 855
82 919
76
ANEXO 9. FRENTE PARETO ITERACIÓN 9
CMax TotalCompletion
88 887
84 1020
87 951
86 954
85 1008
88 887
77
ANEXO 10. FRENTE PARETO ITERACIÓN 10
CMax TotalCompletion
96 859
86 894
83 908
96 859
78
ANEXO 11. FRENTE PARETO ITERACIÓN 11
CMax TotalCompletion
87 895
88 891
82 920
91 794
87 895
79
ANEXO 12. FRENTE PARETO ITERACIÓN 12
CMax TotalCompletion
84 976
85 911
91 890
95 885
84 976
80
ANEXO 13. FRENTE PARETO ITERACIÓN 13
CMax TotalCompletion
98 882
97 899
87 901
86 977
85 987
98 882
81
ANEXO 14. FRENTE PARETO ITERACIÓN 14
CMax TotalCompletion
82 909
85 828
82 909
82
ANEXO 15. FRENTE PARETO ITERACIÓN 15
CMax TotalCompletion
82 952
86 937
89 935
93 911
91 920
97 907
82 952
83
ANEXO 16. FRENTE PARETO ITERACIÓN 16
CMax TotalCompletion
90 847
86 867
85 894
85 948
82 955
90 847
84
ANEXO 17. FRENTE PARETO ITERACIÓN 17
CMax TotalCompletion
83 956
87 890
90 863
83 956
85
ANEXO 18. FRENTE PARETO ITERACIÓN 18
CMax TotalCompletion
87 822
82 943
87 822
86
ANEXO 19. FRENTE PARETO ITERACIÓN 19
CMax TotalCompletion
82 913
86 904
88 899
93 885
82 913
87
ANEXO 20. FRENTE PARETO ITERACIÓN 20
CMax TotalCompletion
91 864
84 919
85 881
91 864
88
ANEXO 21. FRENTE PARETO ITERACIÓN 21
CMax TotalCompletion
86 965
87 933
83 986
88 915
90 880
86 965
89
ANEXO 22. FRENTE PARETO ITERACIÓN 22
CMax TotalCompletion
89 870
85 971
92 856
89 870
90
ANEXO 23. FRENTE PARETO ITERACIÓN 23
CMax TotalCompletion
83 935
84 889
87 869
83 935
91
ANEXO 24. FRENTE PARETO ITERACIÓN 24
CMax TotalCompletion
95 836
93 849
82 866
81 940
95 836
92
ANEXO 25. FRENTE PARETO ITERACIÓN 25
CMax TotalCompletion
85 983
96 897
84 984
92 913
86 924
88 922
89 919
85 983
93
ANEXO 26. FRENTE PARETO ITERACIÓN 26
CMax TotalCompletion
85 1053
92 896
87 903
85 1053
94
ANEXO 27. FRENTE PARETO ITERACIÓN 27
CMax TotalCompletion
89 839
93 821
85 933
89 839
95
ANEXO 28. FRENTE PARETO ITERACIÓN 28
CMax TotalCompletion
90 887
89 926
82 965
90 887
96
ANEXO 29. FRENTE PARETO ITERACIÓN 29
CMax TotalCompletion
85 952
86 935
95 890
88 933
89 922
109 887
85 952
97
ANEXO 30. FRENTE PARETO ITERACIÓN 30
CMax TotalCompletion
83 932
88 856
87 869
105 855
83 932
98
BIBLIOGRAFÍA
Fábregas, Aldo, Rodrigo Wadnipar, Carlos D. Paternina-Arboleda y Alfonso
Mancilla. Simulación de Sistemas Productivos. Ediciones Uninorte. 2004.
OPERATION SCHEDULING, WITH APLICATIONS IN
MANUFACTURING AND SERVICES. Pinedo-Chao. Irwin-Mc Graw Hill.
1999.
FORMULATING THE SINGLE MACHINE SEQUENCING PROBLEM
WITH RELEASE DATES AS A MIXED INTEGER PROGRAM. Martin E.
DYER. Department of Computer Studies, University of Leeds, Leeds, LS29JT,
UK.
SCHEDULING WITH RELEASE DATES ON A SINGLE MACHINE TO
MINIMIZE TOTAL WEIGHTED COMPLETION TIME. H. Belouadah.
Faculty of Mathematical Studies, University of Southampton, UK.
IEOR E4406: Facilities Layout and Planning. Lecture 8. Planar Single Faciliy
Location.
IEOR E4406: Facilities Layout and Planning. Lecture 11. Planar Multi Faciliy
Location.
INTELIGENT DYNAMIC CONTROLS POLICIES FOR SERIAL
PRODUCTIO LINES. Carlos D. Paternina A., Tapas K. Das, Industrial and
Management System Enginneering Department. University of South Florida.
Tampa, FL 33620.
SCHEDULING TO MINIMIZE AVERAGE COMPLETION TIME: OFF-LINE
AND ON-LINE APPROXIMATION ALGORITHMS. Leslie A. Hall, Andres S.
Schulz, David B. Shmoys, Joel Wein. Matehmatics of operations research. Vol
22, No 3, August 1997.
A COMPARISON BETWEEN BASIC CYCLIC SCHEDULING AND
VRIABLE CYCLIC SCHEDULING IN A TWO-STAGE HYBRID FLOW
SHOP. Hitoshi Tsubone, Masahito Susuki. Tokyo Metropolitan Institute of
Tecnology, 6-6 Asahigaota, Hino, Tokyo, 191-0065, Japan.
99
LOCAL SEARCH ALGORITHMS FOR THE MULTIPROCESOR FLOW
SHOP SHEDULING PROBLEM. Ebbe G. Negenman. Deparment of
Technology Management, Eindhoven University of Technology, The
Netherlands.
SYNOPSE: A MODEL-BSED DECISION SUPORT SYSTEM FOR THE
EVALUATION OF FLIGHT SCHEDULES FOR CARGO AIRLINES. J.
Antes, L. Campen, U. Derings, C. Titze, G.D:Wolle. Winford, University of
Cologne, Germany.
A TABU SEARCH HEURISTIC FOR THE UNDIRECTED SELECTIVE
TRAVELING SALESMAN PROBLEM. Michael Gendreau, Gilbert Laporte,
Fréderic Sement. Center de Recherche sur les Transport. University of Montreal.
Montreal, Canada.
INTELLIGENT DYNAMIC CONTROL POLICIES FOR SERIAL
PRODUCTION LINES. Carlos D. Paternina A. Tapas K. Das. Industrial and
Management Systems Engineering Department. University of south Florida,
Tampa, FL.
A GENETIC ALGORITHM BASED PROCEDURE FOR MORE REALISTIC
JOB SHOP SCHEDULING PROBLEMS. M. A. B. Candido, S. K. Khator, R.
M. Barcia. Deparment or Informatics, Pontificial Catholic University of Parana,
Curitiba, Brazil.
SCHEDULING IN AN AUTOMATED FLOW SHOP TO MINIMIZE COST:
BACKWARD-META SCHEDULING METHOD. Ruengsak Kawtummachai,
Yoshinari Yanagawa, Kasumasa Ohashi. Engineering Mathematics, Faculty of
Engeniering. Okayama University, Japan.
DYNAMIC JOB SHOP SCHEDULING USING REINFORCEMENT
LEARNING AGENTS. M. Emin Aydin, Ercan Oztemel. Department of
Industrial Ingineering, Sakarya University. Adapazari, Turkey.
ASIGNACION Y SECUENCIACION DE TAREAS SOBRE MAQUINAS,
POR MEDIO DE HEURISTICAS DE ENFRIAMIENTO SIMULADO. Fidel
torres, Andres Troncoso, Pascal Blanc. Universidad de los Andes, Departamento
de Ingeniería Industrial. Santa Fe de Bogota, Colombia.
PINEDO Michael. SCHEDULING Theory, algorithms, and Systems, second
edition. Prentice Hall, 2002.
100
ASKIN Ronald G, STANDRIDGE Charles R. modeling and analisis of
manufacturing systems. 1993.
PINEDO Michael, CHAO Xiuli. operation scheduling with applications in
manufacturing and services. Irwin-McGrawHill, 1999.
NARDUCCI Francesco, Software genérico de programación de operaciones,
con base en algoritmos heurísticos. Proyecto de grado, titulo Ing. Industrial.
Universidad del Norte 2002.
SCRICH Cintya, ARMENTADO Vinicius, LAGUNA manuel. Tardiness
minimzation in a flexible job shop; A tabu search approach.
CHAMBERS Jhon B, BARNES J. Weley. Reactive search for flexible job shop
scheduling.
CHAMBERS Jhon B, BARNES J. Weley. Flexible job shop scheduling by tabu
search.
BONDORFER, Ralf, Martin Grotschel, Andreas Lobel. “Optimization of
transportation systems”.
BRUNNER, Daniel. (1998). “Towar increased use of simulation in
transportation”.
DE LA CRUZ, Jair J. and Carlos D. Paternina-Arboleda. An Ant Colony
System approach for heterogeneous vehicle routing problems with time
windows and multiple products. III Colombian congress and 1st international
Andean conference on Operational Research. Cartagena, Colombia, 2004.
DE LA CRUZ, Jair J. and Carlos D. Paternina-Arboleda. A Two-Pheromone
Trail ACS Approach for Heterogeneous VRPTW and Multiple Products. Under
review. European Journal of Operational Research.
DE LA CRUZ, Jair J., Adriana Mendoza, Astrid Del Castillo y Carlos D.
Paternina-Arboleda. Análisis comparativo de las aproximaciones heurísticas
Ant-Q, recocido simulado y búsqueda tabu en la solución del problema del
agente viajero. Revista Ingeniería & Desarrollo, (14) Universidad del Norte,
2004.
DE WEERDT, M. M.. (1999). “Towards algorithms for scheduling of transport
processes”.
101
DONOSO, Yezid. Multi-Objective Optimization Algorithm for Multicast
Routing with Traffic Engineering. Telecommunication Systems Journal. Kluwer
Publisher. 2004.
DONOSO, Yezid. Multi-Objective Optimization Algorithm for Multicast
Routing with Traffic Engineering, IEEE 3rd International Conference on
Networking ICN'04, Guadeloupe, French Caribbean, February 29 – March 4,
2004
GAYLE, Steve B (2003). “Looking at transportation planning with an
operations perspective”.
HOGHIEMSTRA, Jurjen S. and Maurice J. G. Teunisse. The use of simulation
in the planning of the dutch railway services. Proceedings of the 1998 Winter
Simulation Conference.
JONSON, Ellis, Renato Montero. “Transport dynamics, Inc.: Development of
planning system for the transportation industry”
PATERNINA-Arboleda Carlos D. y Tapas K. Das. Intelligent Dynamic Control
Policies for Serial Production Lines. IIE Transactions 33 (1), 2001.
PATERNINA-Arboleda Carlos D. y Tapas K. Das. A Multi-Agent
Reinforcement Learning Approach to Obtaining Dynamic Control Policies for
Stochastic Lot Scheduling Problem. In press, Simulation Modelling Practice and
Theory. 2005.
POMPEU Fabra, Helena, Jose P. Paixao, Rita Portugal. “Multiobjetive
Metaheuristic for the bus-driver scheduling problem”
POWELL, Warren B., Huseyin Topaloglu. “Stochastic programing in
transportation and logistic”.
RAO, K.V. Krishna, S. Muralidhar, S.L. Dhingra. “Public trasnport routing and
scheduling using genetic algorithms”.
REGO, Cesar, Catherine Roucairol. “Using Tabu search for solving a dynamic
multi-terminal truck dispatching problem”.
ROJAS S., Miguel, Carlos D. Paternina-Arboleda y Jairo R. Montoya-Torres.
Jobshop scheduling using hybrid meta-heuristic approaches. III Colombian
102
congress and 1st international Andean conference on Operational Research.
Cartagena, Colombia, 2004.
RUNDNICKI, Andrzej. “Investigation by computer simulation some aspect of
transportation service reliability in urban public transport”
SILVA, Gustavo P., Nicolaud D. F. Gualda, Raymond S. K. Kwan. “Bus
scheduling base don an arc generation _ network flow approach”.
XIONG Y., Schneider J.B. (1992). “Transportation network design using a
cumulative genetic algorithm and neural network”
T´KINDT Vincent., Billaut Jean Charles. “Multicriteria Scheduling – Theory,
Models and Algorithms” (2004)
G. P. Guinet and M. M. Solomon, “Scheduling hybrid ßowshops to minimize
maximum tardiness or maximum completion-times”, 1996.
J. N. D. Gupta, “Two stage hybrid ßowshop scheduling problem”, 1988.
J. N. D. Gupta and E. A. Tunc, “Scheduling a 2-stage hybrid ßowshop with
separable setup and removal times”, 1994.
M. I. Dessouky, B. Lageweg, J. K. Lenstra and S. L. van de Velde, “Scheduling
identical jobs on uniform parallel machines”, Statistica Neerlandica, 1990.
M. M. Dessouky, M. I. Dessouky and S. Verma, “Flowshop scheduling with
identical jobs and uniform parallel machines”, 1997.
Y. Lee and G. L. Vairaktarakis, “Minimizing makespan in hybrid ßowshops”,
1994.
www.inforg.uniovi.es/ia/Archivos/Apuntes%20y%20t/AlgoritmosGeneticos.pdf
http://w3.mor.itesm.mx/~logica/log2000_01/articulos_sat/GA_3-SAT.doc.
www.texelfactory.com/extras/Genetic_Algorithms_2.pdf
http://ttt.upv.es/ccarrasc/extdoc/Tema-3_4_algoritmos%20geneticos.pdf
http://pub.ufasta.edu.ar/ohcop/aGEsoullier.pdf
http://sci2s.ugr.es/docencia/bioinformatica/Bioinformatica-
Tema_10.pdf,BIoinformatica
http://www.ica.ele.puc-rio.br/publicacoes/download/cnf_0111.pdf
http://cs.uns.edu.ar/~grs/InteligenciaArtificial/Algoritmos%20GeneticosB&W.p
df, Inteligencia Artificial
103
http://www.alfredorahn.com/docs/AG_Clase_1.ppt, Alfredo Rahn
http://ants.dif.um.es/staff/juanbot/ml/files/20022003/geneticosI.pdf , Algoritmos
Geneticos, Juan Botia Blaya
www.inforg.uniovi.es/ia/Archivos/Apuntes%20y%20t/AlgoritmosGeneticos.pdf,
Los Algoritmos Geneticos
www.texelfactory.com/extras/Genetic_Algorithms_1.pdf, Javier Ventoso
http://lfc.uah.es/olmeda/CNeuronal/Tema4A.pdf, Computación Neuronal 459-
Algoritmos geneticos
http://geneura.ugr.es/~jmerelo/ie/ags.htm, Juan Merelo
http://torio.unileon.es/~dierfd/DOCT/genetic_UNEX/AlgGenetics-2.ppt
http://cipres.cec.uchile.cl/~em753/pdf/optimizacion.pdf , Pablo Estévez
Valencia
http://www.orcero.org/irbis/disertacion/node1.html, Varios
http://mit.ocw.universia.net/15.053/s02/pdf/s02-lec24.pdf
http://www.orcero.org/irbis/disertacion/node193.html
www.redcientifica.com/gaia/ce/agsp_c.htm
Crainic, T. and Toulouse, M., Parallel strategies for meta-heuristics., En: Glover,
F. y Kochenberger, G. (Eds.), Handbook of metaheuristics, Kluwer academic
publisher, 2003.
C. Coello. “An updated Survey of Evolutionary Multiobjective Optimization
Techniques, state of the art and future trends”. In Congress on Evolutionary
Computation. Piscataway, N. J. IEEE Service Center. 3–13. 1999.
Deb. “Evolutionary Algorithms for Multi-Criterion Optimization in Engineering
Design”. In Proceedings of Evolutionary Algorithms in Engineering and
Computer Science EUROGEN’99. 1999.
M. Dorigo y G. Di Caro. “The Ant Colony Optimization Meta-Heuristic”. In D.
Corne, M. Dorigo, and F. Glover (Eds.), New Ideas in Optimization, McGraw
Hill, London, UK, 11-32. 1999.
Sipper, D. y Bulfin, R.(1997). Production, Planning, Control and Integration.
Mc Graw Hill.