UNIVERSIDAD DE CONCEPCIÓN Facultad de Ingeniería Departamento de Ingeniería Industrial
Profesor Patrocinante Sr. Eduardo Salazar H.
APLICACIÓN DE UN ALGORITMO ACO AL PROBLEMA DE MINIMIZACIÓN DE MAKESPAN EN MÁQUINAS PARALELAS IDÉNTICAS CON TIEMPOS DE SETUP DEPENDIENTES DE LA SECUENCIA Pablo Arriagada Pizarro
Informe de Memoria de Título para optar al título de Ingeniero Civil Industrial
Abril, 2012
ii
Sumario El objetivo general de esta memoria de título es el desarrollo de una metaheurística basada en Ant Colony System que busque minimizar el makespan en el problema de máquinas paralelas idénticas con tiempo de preparación dependiente de la secuencia de trabajos. Este problema consiste básicamente en la configuración de procesan
trabajos, uno a la vez, con un tiempo de proceso
máquinas que simultáneamente y que al pasar de un trabajo a otro,
existe un tiempo de preparación de máquinas que depende exclusivamente de estos trabajos saliente y del entrante. El objetivo primario de la programación es minimizar el tiempo de finalización del último trabajo que se procesa, lo que a fin de cuentas se consigue balanceando los tiempos de finalización de las
máquinas. El problema es fuertemente NP-completo, de acuerdo a
la clasificación de Garey y Johnson (1979). Se describe el problema de programación de la producción, planteando sus características teóricas y sus aplicaciones prácticas, que cubre incluso más allá del ámbito productivo industrial, desde la configuración de rutas en vehículos de reparto a la exploración planetaria y satelital, entre muchos otros. Como el problema propiamente tal no tiene una resolución heurística simple, se presentan adaptaciones de problemas similares que intentan aproximarse a la (desconocida) solución óptima: dos nacidas a partir de la heurística Longest Processing Time (LPT), otra de acuerdo a la simulación Montecarlo y una más a partir de una secuenciación de la heurística del mejor vecino. Para contrastar los resultados que entregan estas heurísticas, se presenta una heurística de programación de trabajos que utiliza en su operación Ant Colony System (ACS), que forma parte de un grupo de metaheurísticas dentro de Ant Colony Optimization (ACO), heurísticas multipropósito que se originan e inspiran en el comportamiento de ciertas especies de hormigas que van creando el camino más conveniente para su colonia depositando feromonas que estimulan a los insectos, en una especial forma de comunicación denominada estigmergia, que es el intercambio de información modificando un lugar específico o su entorno inmediato y al que se accede sólo estando en ese lugar. La heurística de programación de la producción secuencia los trabajos inicialmente por medio de ACS, de manera que se utilice el menor tiempo de setup posible. Luego, la secuencia inicial es dividida para que los trabajos sean asignados en las máquinas que conforman el sistema. Esta asignación se divide internamente en dos variantes: una que asigna hasta el último trabajo que no sobrepase un límite determinado por el makespan inicial (asignación “antes”) y otra donde en cada máquina se asigna hasta el primer trabajo que sobrepase ese límite (asignación “después”). Los trabajos no secuenciados por alguna de las dos variantes se localizan en la máquina donde puedan terminar antes. Por último, la heurística propuesta intenta reducir la utilización de la máquina más utilizada, la que termina definiendo el makespan total. Entre los dos resultados obtenidos (producidos por las variantes antes y después),
iii
la heurística genera el makespan inferior. Este método heurístico es un híbrido entre configuraciones constructivas y procedimientos metaheurísticos adaptados completamente para este tipo de problemas. Los resultados fueron probados en 6 escenarios diferentes, con 20 instancias en cada uno y muestran que la heurística basada en Ant Colony System con revisión en su etapa final es consistentemente mejor que todos los otros métodos constructivos presentados, generando un makespan inferior en todos los experimentos y que en promedio supera entre un 5,5 y un 11% a la segunda mejor heurística (Mejor Vecino). Las diferencias son mayores cuando se está ante un escenario donde los tiempos de setup de los trabajos son comparables a los tiempos de proceso, con lo que la heurística propuesta maneja mejor la mayor variabilidad de las soluciones. Si bien comparativamente los tiempos que lleva ACS en ejecutarse son significativamente mayores que los de heurísticas constructivas (medio minuto vs. una fracción de segundo, en el peor caso), no son extremadamente grandes ni perjudican la toma de decisiones en ambientes de trabajo reales; es más, para problemas de esta clase de complejidad los tiempos de ejecución computacional de esta magnitud son especialmente bajos.
iv
Índice 1.
2.
3.
4.
Antecedentes Generales .......................................................................................................... 1 1.1.
Introducción ....................................................................................................................................... 1
1.2.
Revisión Bibliográfica ........................................................................................................................ 2
Programación de la Producción .............................................................................................. 5 2.1.
Aspectos Generales .......................................................................................................................... 5
2.2.
Ambientes de Máquinas .................................................................................................................... 6
2.3.
Restricciones ..................................................................................................................................... 7
2.4.
Medidas de Desempeño.................................................................................................................... 9
2.5.
Configuraciones Productivas ........................................................................................................... 11
2.5.1.
Por Proyectos ......................................................................................................................... 11
2.5.2.
Por Lotes ................................................................................................................................ 11
2.5.3.
Configuración Continua .......................................................................................................... 12
Minimización del Makespan en Máquinas Paralelas Idénticas ........................................... 13 3.1.
El Problema
3.2.
El Problema
3.3.
Formulación Matemática ................................................................................................................. 14
3.4.
Aplicaciones en el Mundo Real ....................................................................................................... 16
|
|
.............................................................................................................. 14
Heurísticas para el Problema de Máquinas Paralelas ......................................................... 20 4.1.
5.
................................................................................................................... 13
Heurísticas ...................................................................................................................................... 20
4.1.1.
Longest Processing Time (LPT) ............................................................................................. 20
4.1.2.
Adaptación a LPT ................................................................................................................... 23
4.1.3.
Montecarlo .............................................................................................................................. 24
4.1.4.
Mejor Vecino ........................................................................................................................... 25
Ant Colony Optimization ........................................................................................................ 30 5.1.
Origen en la Biología ....................................................................................................................... 30
5.2.
La Metaheurística ACO ................................................................................................................... 32
5.3.
Variantes de ACO ........................................................................................................................... 35
5.3.1.
Ant System (AS) ..................................................................................................................... 35
5.3.2.
Elitist Ant System (EAS) ......................................................................................................... 37
v
6.
7.
5.3.3.
Rank-Based Ant System (ASrank) ............................................................................................ 37
5.3.4.
MAX-MIN Ant System (MMAS) ............................................................................................... 38
5.3.5.
Ant Colony System (ACS) ...................................................................................................... 38
Método Propuesto ................................................................................................................... 41 |
Relación de
6.2.
Extensión de ACS con Revisión Final ............................................................................................. 42
con TSP ................................................................................................. 41
Evaluación y Análisis de Resultados .................................................................................... 48 7.1.
Información Preliminar..................................................................................................................... 48
7.2.
Escenarios de Evaluación ............................................................................................................... 49
7.3.
Definición de Parámetros ................................................................................................................ 51
7.3.1.
Montecarlo .............................................................................................................................. 51
7.3.2.
Extensión de ACS con Revisión Final .................................................................................... 52
7.4.
Resultados ...................................................................................................................................... 59
7.4.1.
Nivel de Setup Alto ................................................................................................................. 59
7.4.2.
Nivel de Setup Bajo ................................................................................................................ 62
7.5.
Análisis de Resultados .................................................................................................................... 65
7.5.1.
Influencia del Proceso de Revisión Final Mediante ACS ........................................................ 66
7.5.2.
Diferencias entre la Asignación “Antes” y “Después” .............................................................. 67
7.5.3.
Consistencia de Métodos Heurísticos..................................................................................... 69
7.6.
8.
|
6.1.
Validación Estadística ..................................................................................................................... 70
7.6.1.
Análisis de Varianza ............................................................................................................... 70
7.6.2.
Supuestos de ANOVA ............................................................................................................ 72
Conclusiones ........................................................................................................................... 75
Referencias ...................................................................................................................................... 78 Anexos .............................................................................................................................................. 85 A1.
Parámetros del Problema Ejemplo .................................................................................................. 86
A2.
Definición de Parámetros ACS ........................................................................................................ 87
A3.
Diferencias de Métodos Heurísticos ................................................................................................ 94
A4.
Diferencias Generadas por el Proceso de Revisión de ACS ......................................................... 100
A5.
Análisis de Varianza ...................................................................................................................... 102
A6.
Verificación de supuestos de ANOVA ........................................................................................... 108
1 Aplicación de un algoritmo ACO al problema
|
|
1. Antecedentes Generales 1.1. Introducción Debido al ritmo que llevan nuestras actividades, rápidamente se ha vuelto indispensable la organización y programación de las actividades que se realizarán, ya sea para poder compatibilizar distintas tareas durante una jornada laboral o para planificar las vacaciones, siempre se busca un objetivo común: aprovechar el tiempo, saber distribuirlo de la mejor manera. Tiempos de salida en el transporte público, la atención en un consultorio, los horarios de profesores en una institución educacional o la entrega de pizza a domicilio son sólo una pequeña muestra de la importancia de la programación de los trabajos. En las industrias, por lo tanto, esta situación no difiere de toda actividad que se quiere ejecutar y más cuando hay involucrada maquinaria que por lo general implica un desembolso de dinero importante. A cualquier empresa le gustaría utilizar sus equipos menos y poder producir más, y existe una multitud de casos donde se puede lograr, eliminando tiempos muertos perfectamente evitables si se redistribuyera la configuración de actividades. Tal es el caso de los tiempos de preparación de tareas, que por muchas décadas se tenían asumidos como parte inmodificable de los sistemas y poco a poco se ha entendido su relevancia, llegando a ocupar fácilmente desde el 20% de la capacidad de producción disponible (Allahverdi y Soroush, 2008). El interés de reducir estos tiempos se ha visto ayudado también por el explosivo aumento en la capacidad computacional para resolver problemas de optimización en lapsos que eran impensados diez años antes. Uno de los modelos más utilizados en la representación de la programación de actividades es la carta Gantt, llamadas así por su creador, Henry Laurence Gantt (1861-1919), ingeniero industrial y discípulo de Frederick W. Taylor, padre de la administración científica del trabajo. Básicamente, una carta Gantt representa la asignación de trabajos contra el tiempo, con recursos específicos en el eje vertical y una escala de tiempo en el eje horizontal. En varias páginas de esta investigación se utilizan para ejemplificar la asignación de trabajos. Como en cualquier actividad que involucra personas, el objetivo de aumentar la producción en tiempos cada vez menores debe siempre ir acompañado de beneficios que permitan mejorar las condiciones laborales (y por lo tanto, de vida) de cada trabajador involucrado, partiendo por asegurar su seguridad y la ergonomía de su estación de trabajo, hasta recibir la retribución justa que conlleva ser parte fundamental de la cadena productiva en una empresa.
2 Aplicación de un algoritmo ACO al problema
|
|
1.2. Revisión Bibliográfica Un problema ampliamente difundido en artículos científicos en programación de la producción es , consistente en un número
de máquinas paralelas idénticas, sin tiempos de
preparación entre trabajos y sujetos a minimización de makespan. El primer trabajo en este tema es realizado por McNauhgton (1959), donde el tiempo disponible para cada máquina estaba previamente definido y el algoritmo arbitrariamente toma un trabajo y lo procesa en la máquina disponible que tenga el menor número correlativo, hasta que todos los trabajos se asignen. Hace una contribución relevante a la programación, incorporando al secuenciamiento medidas de desempeño como el makespan, la tardanza total ponderada y el tiempo de flujo ponderado. Instancias pequeñas del problema pueden ser resueltas en un tiempo computacional razonable mediante algoritmos exactos, como branch-and-bound (van de Velde, 1993) y el método de planos de corte (Mokotoff, 2004), pero este problema, por ser NP-hard, toma tiempos computacionales exponenciales de resolución en instancias mayores, con lo que se recurre a heurísticas, como la bien conocida regla Longest Processing Time (LPT) de Graham (1969), que en una primera etapa ordena los trabajos en una lista de mayor a menor tiempo de procesamiento para después asignar. Más tarde, Coffman, Garey y Johnson (1978) proponen el algoritmo MULTIFIT que abarca la relación entre los problemas de bin packing y los de tiempo de finalización máxima, de manera que la heurística funciona con límites de tiempo que van cambiando de acuerdo a nuevas soluciones encontradas. Yue (1990), calculando cotas superiores de heurísticas, mostró que las heurísticas MULTIFIT no garantizan un mejor rendimiento que LPT en cualquier problema. Gupta y Ruiz-Torres (2001) propusieron un algoritmo LISFIT que combina el método de bin packing utilizado en la heurística MULTIFIT
con listas múltiples de trabajos. Los resultados
computacionales mostraron que la heurística superaba a los algoritmos LPT y MULTIFIT, comparando sus límites en el peor caso. Min y Cheng (1999) propusieron un algoritmo genético basado en el lenguaje de máquinas, diseñado especialmente para instancias grandes de programación. Indicaron que la calidad de la solución entregada es superior a procedimientos heurísticos basados en recocido simulado (Simulated Annealing, SA). Lee, Wu y Chen (2006) proponen un algoritmo SA para el problema y compararon sus resultados con el algoritmo LISFIT, superándolo en todas las pruebas (en tiempo y calidad de la solución) y mostrando mejor rendimiento aún en problemas calificados como difíciles por los mismos Gupta y Ruiz-Torres. Sevkli y Uysal (2009) utilizan por primera vez búsqueda en vecindad variable para el problema, mostrando mejores resultados que LPT y algoritmos genéticos. Una heurística y un método exacto para el problema se encuentran recopilados en Dell'Amico et al. (2008). La primera está basada en una búsqueda scatter, computacionalmente efectiva y capaz de llegar al óptimo en un alto porcentaje de instancias. El segundo, basado en búsqueda binaria y branch-and-price, llega al óptimo en las instancias restantes.
3 Aplicación de un algoritmo ACO al problema
|
|
A pesar de su relevancia, pasan quince años desde los primeros trabajos de programación de máquinas paralelas hasta que se consideran los tiempos de preparación en el análisis: Marsh y Montgomery (1973) propusieron aproximaciones heurísticas para el problema de minimización del costo total de setup en máquinas idénticas y no idénticas. Para este último caso, los tiempos de setup dependen tanto de la secuencia de trabajos como la máquina donde se procesa. Deane y White (1975) extendieron los resultados de Marsh y Montgomery para incluir balance de cargas de trabajo, desarrollando un algoritmo branch-and-bound para minimizar el costo de preparación. Geoffrion y Graves (1976) desarrollaron una formulación de asignación cuadrática para minimizar la suma de los costos de setup, producción y faltas por atrasos. La primera heurística en resolver el problema fue publicada en 1978 (Frederickson, Hecht y Kim), mediante dos algoritmos de aproximación que se derivan de la equivalencia entre el problema
|
|
y el del Vendedor Viajero (TSP), y hace uso de procedimientos heurísticos basados
en resoluciones para el TSP y el
-TSP (TSP múltiple). Dearing y Henderson (1984) publicaron un
modelo de programación lineal para la asignación de telares en la industria textil para la minimización de costo total de setup, considerando también restricciones de capacidad en el uso de los telares. Sus resultados los lograron mediante el redondeo de las soluciones obtenidas por la relajación lineal del modelo. Sumichrast y Baker (1987) proponen un método heurístico basado en la solución de una serie de subproblemas binarios que mejora los resultados de Dearing y Henderson, con resultados más cercanos al óptimo y menos carga computacional. Ambos trabajos consideran que un trabajo puede ser dividido en varias máquinas. Otros autores, como Flynn (1987), Hahn, Bragg y Shin (1989) y Boborowski y Kim (1994, 1997), investigaron el impacto de la variación de los tiempos de setup en la decisión de secuenciamiento y concluyen que su consideración influye significativamente en la programación de la producción, por lo tanto no recomiendan abordar el problema dejando los tiempos de preparación como parte del tiempo de proceso. Guinet (1993) muestra que el problema puede reducirse a uno de ruteo de vehículos y sugiere primero hacer una heurística de dos pasos. Además formula el problema linealmente con variables binarias y propuso una nueva heurística que consiste en resolver el problema dual del problema de asignación obtenido. Una recopilación de trabajos sobre programación de máquinas paralelas en base a tiempos de finalización, due dates, y tiempos de flujo como medidas de desempeño, se presentan en Cheng y Sin (1990). Lam y Xing (1997) revisaron nuevos desarrollos, asociados a los problemas de producción just-in-time, trabajos con preferencia y máquinas con capacidad. Algunas variaciones del problema, como en Kurz y Askin (2001) presentan una programación entera mixta para
|
|
y aplican cuatro heurísticas
basadas en trabajos anteriores (Coffman et al., 1978; Johnson y Papadimitriou, 1985; Reinelt, 1994; Papadimitriou y Steiglitz, 1998), además de hacer una revisión más acabada de heurísticas utilizadas.
4 Aplicación de un algoritmo ACO al problema
|
|
El uso de metaheurísticas para este problema comienza cuando França et al. (1996) abarcan el problema con una heurística de tres fases: la primera genera una solución inicial, que se mejora en una segunda etapa mediante una búsqueda tabú. La tercera etapa consiste en mejorar la secuencia de trabajos en la máquina más ocupada, la que determina el makespan. Este trabajo mejora varias heurísticas previas, incluyendo el “trabajo-padre” de Frederickson et al. Gendreau, Laporte y Morais (2001) idearon límites inferiores y una heurística de dividir-y-unir fácil de implementar que resulta ser más rápida que la heurística de França et al., y de calidad similar. Mendes et al. (2002) compararon tres metaheurísticas: dos basadas en búsqueda tabú (adaptada de 1996) y una memética, que combina un algoritmo genético con búsqueda local. Los resultados mostraron que mientras la memética es superior cuando los tiempos de setup eran pequeños en comparación a los tiempos de proceso, lo contrario sucede con tiempos de setup grandes y muchas máquinas. Para la minimización del tiempo de finalización ponderado con tiempos de liberación de trabajos distintos a cero, Nessah, Yalaoui y Chu (2005) tratan de minimizar la suma de tiempos de finalización presentando una condición necesaria y suficiente para obtener óptimos locales, además de un límite inferior. La heurística que generan se basa en la condición que exponen. Tahar et al. (2006) presentaron una heurística basada en programación lineal (con división de trabajos), cuyo rendimiento fue testeado en problemas con un límite inferior, entregando buenas soluciones en tiempos de ejecución cortos, mientras que Rocha et al. (2007) propusieron un algoritmo de búsqueda en vecindad variable y mostraron que su algoritmo supera a un algoritmo greedy de procedimiento de búsqueda adaptativa aleatoria, con muy buenas soluciones en instancias de 60 o más trabajos. Behnamian, Zandieh y Ghomi (2009) plantean una metaheurística híbrida para el problema, donde la solución inicial es generada por un método basado en Ant Colony Optimization (ACO), recocido simulado para su evolución y una búsqueda en vecindad variable (VNS) con búsqueda local para mejorarla. Esta combinación proporciona mejores resultados que los métodos de búsqueda variable y aleatoria anteriores. En cuanto a recopilaciones sobre el tema, Allahverdi, Jatinder, Gupta, y Tariq Aldowaisan (1999), publican un estado del arte de la programación de la producción con tiempos de setup. Allahverdi, Ng, Cheng y Kovalyov (2008) es una continuación del estudio anterior, comprende los trabajos publicados entre ambas revisiones. La publicación de Yang y Liao (1999) es otra revisión de secuenciamiento de trabajos con setup, mientras que Zhu y Wilhelm (2006) se concentran en seleccionar las investigaciones de programación con tiempos de preparación dependientes de la secuencia.
5 Aplicación de un algoritmo ACO al problema
|
|
2. Programación de la Producción 2.1. Aspectos Generales La programación de la producción es un proceso de toma de decisiones constantemente utilizado por las industrias productivas y de servicios. En términos simples consiste en la asignación de recursos a tareas que toman cierto tiempo en realizarse y cuya meta es optimizar uno (o más) objetivos. Estos recursos pueden traducirse generalmente como máquinas, pero también pueden ser equipos de personas, computadores y otros dispositivos con los que puede resolverse análogamente un problema de programación. En todos los problemas de programación de la producción considerados, el número de trabajos y el número de máquinas son finitos. El número de trabajos se denota por por
. Usualmente, el subíndice
y el número de máquinas
se refiere a un trabajo, mientras que el subíndice
indica una
máquina. Si un trabajo requiere de un número determinado de pasos u operaciones, el par indica la operación del trabajo en la máquina .
Tiempo de proceso
Representa el tiempo de procesamiento del trabajo
. Este subíndice se omite si el tiempo de proceso del trabajo donde se utiliza o si el trabajo
Tiempo de liberación
Due date
no depende de la máquina
sólo se procesa en una máquina definida.
Indica el tiempo en que el trabajo
equivalente al tiempo más temprano en que el trabajo
en la máquina
llega al sistema, lo que es
puede comenzar su proceso.
Representa el envío comprometido o el tiempo acordado con el cliente cuando
el trabajo esté realizado. La finalización de un trabajo después de su due date está permitido, pero se incurre en una falta. De no estar permitido, es un deadline, ̅ .
Peso
También llamada ponderación, es básicamente un factor de prioridad que denota la
importancia de un trabajo
en relación a los otros trabajos en el sistema. Por ejemplo, el peso
puede representar el costo real de mantener un trabajo en el sistema. Un problema de programación de la producción se describe por la notación por Graham et al. en 1979.
, introducida
describe el ambiente de las máquinas y contiene sólo una entrada.
detalla las características del proceso con sus restricciones y puede no tener ninguna, una, o múltiples entradas.
describe el objetivo a minimizar y por lo general contiene una sola entrada. A
continuación se describen estos campos, a partir de Pinedo (2008) y Baker (2009).
6 Aplicación de un algoritmo ACO al problema
|
|
2.2. Ambientes de Máquinas Los ambientes de máquinas posibles descritos en
Taller de una máquina
son:
es el caso más simple de todos y un caso especial de todos los
otros escenarios más complejos. Una máquina se encarga de procesar todos los trabajos.
Máquinas idénticas en paralelo la vez. El trabajo
es cuando existen
máquinas idénticas trabajando a
requiere una única operación y puede ser procesado en cualquiera de las
. Si sucede este
máquinas o en cualquiera que pertenezca a un subgrupo determinado último caso, la entrada
debe aparecer en el campo .
Máquinas en paralelo con diferentes velocidades
es cuando cada máquina influye en
los tiempos de proceso. La velocidad de cada máquina trabajo
utiliza en la máquina
es igual a
⁄
se denota por
. El tiempo
que el
(asumiendo que el trabajo se ejecuta
completamente en la máquina). A este ambiente también se le llama máquinas uniformes. Si es igual para todas las máquinas, estamos ante un sistema de máquinas paralelas idénticas.
Máquinas no relacionadas en paralelo configuración previa, donde la velocidad del trabajo trabajo. El tiempo
que el trabajo
es una generalización adicional de la depende de la máquina y del propio
utiliza en la máquina
es igual a
⁄
(asumiendo
nuevamente que el trabajo se ejecuta completamente en la máquina).
Flow shop cada una de las
es cuando existen
máquinas en serie, cada trabajo debe ser procesado en
máquinas y todos deben seguir la misma ruta de máquinas. Una vez que un
trabajo termina en una máquina pasa a una cola de espera (queue) y espera ser procesado en la máquina siguiente, usualmente bajo la priorización FIFO, que debe indicarse en el campo (en el caso de FIFO, la entrada es
Flexible flow shop
).
es una generalización del flow shop y de la configuración de
máquinas paralelas, donde en vez de
máquinas en serie hay
etapas en serie de máquinas
paralelas idénticas. En la literatura, es también llamado hybrid flow shop (flow shop híbrido) o multi-processor flow shop (flow shop con procesadores múltiples).
7 Aplicación de un algoritmo ACO al problema
Job shop
|
|
es el caso cuando cada trabajo tiene su ruta predeterminada en las
máquinas. Se hace una distinción entre job shops donde cada trabajo visita cada máquina a lo más una vez y en los cuales los trabajos pueden visitar cada máquina más de una vez. Para el último caso, el campo
Flexible job shop de
contiene la entrada
, indicando recirculación.
es una generalización del job shop y las máquinas paralelas. En vez
máquinas en serie, hay
centros de trabajo con un cierto número de máquinas paralelas
idénticas. Cada trabajo sigue su propia ruta en el taller y cada trabajo se procesa en cada centro de trabajo en una sola máquina y cualquier máquina dentro del centro puede hacerlo. También puede considerarse recirculación.
Open shop de las
es donde hay
máquinas y cada trabajo debe ser procesado en cada una
máquinas. Sin embargo, algunos de estos tiempos de proceso pueden ser cero. No
hay restricciones en cuanto a la ruta de cada trabajo, el programador determina la ruta para cada trabajo y diferentes trabajos pueden tener diferentes rutas.
2.3. Restricciones Las restricciones del proceso especificadas en el campo Las entradas posibles para
Tiempos de liberación
pueden ser una, más de una o ninguna.
son: Cuando aparece este símbolo, el trabajo
proceso antes su tiempo de liberación
no puede iniciar su
. Si no aparece, el trabajo puede iniciar su proceso en
cualquier momento.
Interrupciones
Implican que no es necesario mantener un trabajo en proceso hasta
su finalización. El programador puede interrumpir el proceso de un trabajo en cualquier punto y poner un nuevo trabajo en su reemplazo. Cuando el trabajo interrumpido se reanuda en la misma máquina o en otra, completa el tiempo que le restaba.
Restricciones de precedencia
Es cuando se requiere que uno o más trabajos deben
completarse antes de que otro trabajo pueda ejecutarse.
8 Aplicación de un algoritmo ACO al problema
|
|
Tiempos de setup dependientes de la secuencia determinado por la secuencia de trabajos cuando es el primero en la secuencia y
y
.
Representa el tiempo de preparación denota el tiempo de setup del trabajo
el tiempo de limpieza necesario después de
procesar el trabajo
(Ambos pueden ser cero). Si además este tiempo depende de la máquina,
se indica como
. Si no hay ninguna indicación del setup en el campo
, se asume que
estos tiempos son cero o son independientes de la secuencia, con lo que se incluyen en el tiempo de proceso.
Familias de trabajos
Cuando hay grupos de trabajos que pueden procesarse sin
existir tiempos de setup entre ellos. El tiempo de preparación entre una familia
o incluso no depender de ninguna familia
Proceso batch cantidad
Fallas
.
Cuando una máquina puede procesar simultáneamente una
de trabajos. Cuando
programación. Si
se
, pero también estos tiempos pueden depender sólo de la familia que se
representa por procesará
y
el problema se reduce a un problema convencional de
, no hay límite de trabajos simultáneos en una máquina. Se refiere a que una o más máquinas pueden no estar disponibles en
intervalos de tiempo determinados, por fallas y/o mantenciones.
Restricciones de elección de máquinas
Define qué máquinas son capaces de procesar
el trabajo .
Permutación
En un flow shop, implica que el orden en que entran los trabajos en la
primera máquina se mantiene en todo el sistema.
Bloqueo
Se da en flow shops cuando se llega al tope del buffer entre máquinas, o
cuando no hay buffer. La máquina es bloqueada hasta que la siguiente pueda ser utilizada.
No-wait
Es cuando en un flow shop un trabajo no puede esperar que lo procese una
máquina, por lo que debe retrasarse su proceso en la que lo antecede.
Recirculación
Cuando un trabajo puede visitar una máquina o un centro de trabajo
más de una vez. En job shops o flexible job shops.
9 Aplicación de un algoritmo ACO al problema
|
|
2.4. Medidas de Desempeño El campo
, que se refiere al objetivo a minimizar (medidas de desempeño del sistema), es
siempre una función de los tiempos de finalización de los trabajos, que dependen de la programación, evidentemente. El tiempo de finalización del trabajo trabajo
se va del sistema es
en la máquina
, que es igual a
se denota por
y el tiempo en que el
en sistemas donde un trabajo se procesa una
única vez. El objetivo también puede ser función de los due dates. El atraso de un trabajo
que es positivo cuando el trabajo
se define como:
finaliza tarde y negativo cuando se completa temprano,
comparando con el due date. La tardanza de un trabajo
{
se define como:
}
La diferencia entre el atraso y la tardanza está en el hecho que la tardanza nunca es negativa. Un trabajo tardío se define
{ El objetivo también puede ser en relación a los tiempos de liberación, así se define el tiempo de flujo:
que es el tiempo que el trabajo pasa en el sistema. Cuando los tiempos de liberación son cero,
.
Así, a partir de estas medidas de desempeño individuales en cada trabajo, se generan medidas de desempeño del sistema que son las que corresponden al campo .
Makespan
Es equivalente al tiempo de finalización del último trabajo en salir del
sistema. Un mínimo makespan por lo general implica una buena utilización de las máquinas.
10 Aplicación de un algoritmo ACO al problema
Atraso máximo
Tardanza máxima
Flujo máximo
|
|
Mide el mayor desfase de los trabajos en relación a los due dates.
Recoge la misma idea que el atraso máximo.
Indica el tiempo del trabajo que más permanece en el sistema.
También están las medidas de desempeño que surgen de la suma de las medidas de desempeño individuales, tales como:
Suma de tiempos de finalización: ∑
Atraso total:
Tardanza total:
Tiempo total de flujo:
Número de trabajos tardíos:
∑ ∑ ∑ ∑
En problemas que incluyan peso, estas expresiones se modifican para poder considerar la prioridad de los trabajos:
Tiempo total de finalización ponderado: ∑
Tardanza ponderada:
Tiempo de flujo ponderado:
Número ponderado de trabajos tardíos: ∑
∑ ∑
Todas estas funciones objetivo se llaman medidas de desempeño regulares. Se definen así todas las medidas de desempeño que su valor aumenta si algún valor de prontitud no es regular:
{
}
aumenta. Por ejemplo, la
11 Aplicación de un algoritmo ACO al problema
|
|
2.5. Configuraciones Productivas Además de la configuración de máquinas, una industria debe considerar el uso que le dará a estas para la posterior producción de bienes, lo que dependerá tanto de la cantidad y variedad de los productos, como
del tipo de demanda que deben cubrir. Los distintos tipos de proceso son
recogidos por Domínguez Machuca et al. (1995) a partir de la clasificación de Hayes y Wheelwright (1984) que es la que se usa habitualmente en los departamentos de operaciones. Los tipos de procesos están ordenados de modo que aumenta el volumen de producción, la automatización y homogeneización de los procesos, la repetividad de las operaciones, la inversión en capital y la estandarización del producto. A continuación se detallan estos tipos de procesos.
2.5.1. Por Proyectos Es la configuración que se utiliza para cuando se generan productos o servicios “únicos” y de cierta complejidad (aviones, barcos y obras públicas en general) que se obtienen a partir de inputs de gran tamaño, generalmente. Esto, junto a la especificidad de inputs y outputs, hace que comúnmente los primeros se trasladen al lugar donde se está creando el producto o servicio. Estas mismas características hacen que se requiera un nivel de coordinación de personas muy grande.
2.5.2. Por Lotes Lo que caracteriza a este tipo de proceso es que utiliza las mismas instalaciones para obtener múltiples productos, de manera que una vez que se obtiene un tipo de ellos, se ajustan las instalaciones y se procesa un lote de un producto distinto al anterior, repitiéndose la secuencia. Hay tres tipos de configuración por lotes, que dependen del tamaño, homogeneidad y variedad de los productos y cómo es el proceso en sí. Estos son: Configuración Job Shop: Producen lotes pequeños de una gran variedad de productos prácticamente no estandarizados, más bien, están cerca de ser hechos “a medida”, con lo que se usan equipos versátiles. Los costos variables son altos, debido a la poca automatización, pero por esto mismo, el costo fijo de inversión es bajo. Es importante notar que esta no es la misma definición que la dada en ambientes de máquinas. La configuración puede desagregarse en:
Configuración a medida o de talleres: En este caso, en el proceso hay un número bajo de operaciones poco especializadas, las que ejecuta uno o varios trabajadores. El lote suele ser de pocas unidades de un producto, que normalmente está diseñado a partir de los requerimientos del cliente, por lo que la variedad está sólo limitada por su imaginación y las posibilidades de la empresa. Un ejemplo es una mueblería a medida, donde cada operario debe dominar cada una de las tareas que están involucradas en el proceso.
12 Aplicación de un algoritmo ACO al problema
|
|
Configuración en batch: Aquí el proceso requiere más operaciones, las que son más especializadas, con lo que es más improbable que un operario las domine todas a un nivel alto, por lo que generalmente está sólo en un centro de trabajo. Los centros de trabajo tienen maquinaria más sofisticada y enfocada a operaciones específicas del proceso, con lo que la inversión es mayor, aunque sigue existiendo una automatización básica, lo que abre espacio a una buena flexibilidad. El lote (más grande que en el caso anterior) llega al centro de trabajo para sufrir una operación, y no es hasta que todo el lote se procesa que se traslada a otro centro de trabajo para su proceso, o en su defecto a un almacén de espera mientras el centro se utiliza. El producto tiene varias versiones que el cliente puede elegir, con lo que hay cierto grado de estandarización, aunque con una baja repetitividad de las operaciones. Un ejemplo de esta configuración es una fábrica normal de muebles, donde el cliente puede elegir características como la tapicería de las sillas, el barnizado o el tamaño de un armario.
Configuración en línea: Es básicamente cuando se fabrican grandes lotes de pocos productos diferentes, pero que son técnicamente homogéneos y usando las mismas instalaciones. Los distintos productos requieren una secuencia similar de operaciones, aunque más de alguno puede saltar alguna de estas. Por su naturaleza, las máquinas se disponen en línea, una después de la otra, las que luego de terminar la producción de un lote se ajustan para producir un lote distinto, y así sucesivamente. En este caso, las máquinas son mucho más especializadas, lo que conlleva una alta inversión y también una mayor automatización y homogeneidad que con un Job Shop, lo mismo pasa con la especialización de los operarios, que genera menores costos variables de producción, pero perdiendo flexibilidad. Los costos de inversión en esta configuración son mucho mayores que los de un Job Shop y aparecen también altos costos de preparación que, eso sí, producen productos de alta calidad. Un ejemplo de este proceso es la línea de montaje de un automóvil, donde, aunque varíen algunas características (motor, puertas, equipamiento), siempre es el mismo modelo.
2.5.3. Configuración Continua La producción pasa a ser continua cuando se eliminan los tiempos ociosos y de espera, de forma que siempre se estén ejecutando las mismas operaciones, en las mismas máquinas, para tener siempre el mismo producto, en una disposición en cadena o lineal. Tanto la automatización como la especialización y homogeneidad son altísimas, pero aunque las operaciones sean distintas, todas deben considerarse simultáneamente para que el sistema funcione. En estos procesos la producción no para en ningún momento, salvo cuando hay detenciones programadas. Un caso de producción continua es el de la celulosa, donde las detenciones programadas no ocurren con frecuencia.
13 Aplicación de un algoritmo ACO al problema
|
|
3. Minimización del Makespan en Máquinas Paralelas Idénticas Por lo general, la programación de trabajos requiere dos tipos de decisiones: 1. Decisiones de secuenciamiento 2. Decisiones de asignación de recursos. Cuando existe sólo un recurso, la decisión de asignación de recursos depende completamente de la secuencia. En cambio, la importancia de ambas decisiones se hace notar en configuraciones con más de una máquina, ya sean máquinas paralelas, flow shops o job shops, donde se amplía el número de posibilidades de operación que tienen los trabajos y a su vez complejiza la programación de la producción. La minimización del makespan es un objetivo de especial interés en un ambiente de máquinas paralelas, debido a que hacer que el proceso entero termine antes implica necesariamente balancear la carga de trabajo en cada máquina, repartiendo las tareas en forma equilibrada.
3.1. El Problema En el modelo estático de máquinas paralelas, la secuencia de trabajos en una máquina particular es irrelevante al tener las tareas ya asignadas, ya que no cambiará el tiempo de finalización de esa máquina. Aun así, el problema de minimización de makespan es un problema complejo, al intentar elegir qué trabajos operan en qué máquina, para obtener el máximo equilibrio en el uso de máquinas. Una cota inferior para
, se define así:
{∑
}
Si bien este valor no es el makespan mínimo para el problema, la cota inferior da una buena idea de lo que se aspira en minimizar el makespan y algunas restricciones que se encuentran en el problema
. El primer argumento indica la búsqueda del equilibrio en todas las máquinas,
intentando que terminen su proceso en tiempos lo más cercanos posibles, mientras que el segundo argumento muestra lo que puede suceder con algún tiempo de proceso
considerablemente
mayor al resto de los otros trabajos: si es mayor al promedio de tiempos de finalización de las máquinas, obligadamente ese tiempo será el mínimo makespan del sistema. Al no permitirse ni detenciones ni ningún tipo de trabajos parciales, buscar el equilibrio en la utilización de las máquinas se vuelve mucho más complejo, de hecho, el problema
es
14 Aplicación de un algoritmo ACO al problema 1
|
| 2
NP-completo y
es fuertemente NP-completo (Garey y Johnson, 1979). Sólo se puede
resolver en tiempo polinomial si todos los trabajos tienen la misma duración.
3.2. El Problema
|
|
En este problema, a diferencia del modelo anterior, sí cobran relevancia ambas decisiones de la programación de la producción, debido a que en una misma máquina dos secuencias con los mismos trabajos entregan resultados diferentes en cuanto al makespan; de hecho, en cada máquina, la cantidad de combinaciones de las distintas secuencias posibles entregará el mismo número de posibles tiempos de finalización. Algunos makespan parciales podrán repetirse, pero serán originados por distintos tiempos de preparación. Esto hace que se esté ante un problema más complejo que
, porque además de considerar en qué máquina asignar los trabajos,
la secuencia debe ser tal que genere los menores tiempos de preparación, en orden de producir el menor makespan. Entonces, como
|
|
es un problema fuertemente NP-completo,
también lo es (Rocha et al., 2007). El problema tratado tiene esta complejidad
también porque el modelo con una máquina equivale al problema del vendedor viajero, TSP, que es NP-completo (França et al., 1996)
3.3. Formulación Matemática El problema
|
|
puede ser expresado matemáticamente, con los siguientes parámetros
considerados (Gutiérrez y Mejía, 2006):
: Tiempo de proceso del trabajo . : Tiempo de preparación determinado por la secuencia de trabajos y : Tiempo de preparación para el trabajo cuando es el primero que se programa en la máquina. Y las variables de decisión:
{
{
1 2
Problema NP que puede resolverse, pero no en tiempo polinomial por algún algoritmo eficiente. Problema NP-completo que sigue siéndolo aunque sus parámetros se acoten polinomialmente.
15 Aplicación de un algoritmo ACO al problema
(
)
(
)
|
|
∑
∑
∑
∑
(1) Establece el tiempo de finalización de un trabajo, asegurando que el tiempo de finalización es al menos igual a la suma del tiempo de finalización del trabajo precedente, el tiempo de setup y su tiempo de proceso. (2) Es la aplicación del punto (1) para los trabajos asignados en la primera posición en cada máquina. (3) Si un trabajo es asignado a una máquina, entonces tiene definido sólo un predecesor. (4) Si un trabajo es asignado a una máquina, entonces tiene definido sólo un sucesor. (5) A lo más un trabajo es asignado en la primera posición de la secuencia de cada máquina. (6) Un trabajo es asignado sólo a una máquina. (7) Establece el makespan. (8) Establece no negatividad para los valores de tiempos de finalización. (9) Establece no negatividad para las variables de decisión.
16 Aplicación de un algoritmo ACO al problema
|
|
3.4. Aplicaciones en el Mundo Real El problema estudiado además de tener una relevancia teórica (al ser una generalización del problema de una máquina y un caso especial de flow shop), tiene importancia en la industria productiva: una gran variedad de rubros necesitan considerar tiempos de preparación al pasar de una tarea a otra. Algunas áreas, documentadas por Allahverdi y Soroush (2008) son:
Industria textil: Las operaciones de tejer y secar están sujetas a los tiempos de preparación, que dependen de los trabajos: los distintos tipos de telas hacen que tenga que cambiarse la cadena urdidora de la máquina.
Industria del plástico: El setup varía según el tipo y color del plástico a producir. Cuando el color de un ítem previamente procesado en la máquina no es el mismo que el que se procesa después, una cantidad de plástico se desperdicia. La secuencia de trabajos determina cuánto plástico se pierde.
Industria química: El tiempo necesario para limpiar un reactor antes de procesar un nuevo producto depende de qué fue lo último que se produjo en el reactor.
Imprentas: Se requiere un tiempo de setup para preparar la máquina (para limpiarla, por ejemplo), lo que depende del color de la tarea actual y la inmediatamente posterior.
Informática: En el desarrollo y ejecución de algunos software, una tarea necesita un tiempo de preparación para cargar un compilador diferente si el anterior no era el adecuado.
Producción de botellas: El setup depende de los tamaños y formas del envase.
Industria aeroespacial: En las líneas de producción de aspas para motores de aviones, un setup alto se requiere para pasar de una familia de aspas a otra.
Situaciones similares se dan en la industria del papel y la industria del vidrio. Además de todas las aplicaciones en procesos productivos que necesitan tiempos de preparación, el problema
|
|
es análogo al problema de múltiples vendedores viajeros,
-TSP
(como se detallará más adelante) y a una relajación del problema de ruteo de vehículos, VRP; de modo que el radio de aplicación real de se extiende más allá de la secuenciación en máquinas paralelas. Algunos ejemplos, recopilados por Bektas (2006), son:
17 Aplicación de un algoritmo ACO al problema
|
|
Prensa: Gorenstein (1970) trabaja un caso de la impresión de revistas. En este caso, existen cinco pares de cilindros entre los cuales los rollos de papel y ambos lados de una página se imprimen simultáneamente. Existen tres tipos de plantillas, de 4, 6 y 8 páginas, que se usan para imprimir las ediciones. El problema de secuenciación consiste en decidir qué plantilla se usará en qué corrida y la duración de cada corrida. El costo de cambiar estas plantillas es el que depende de la secuencia. En un contexto parecido, el problema puede ser usado para desarrollar programación de la producción para publicidad ya impresa en los diarios, como explican Carter y Ragsdale (2002). En este caso, los anunciantes deben insertar anuncios específicos dentro o con el diario, para distribuirlos a diferentes regiones geográficas. Para el contexto de la programación en máquinas, las regiones son los trabajos y las máquinas son las líneas de producción.
“Programación” de personal: Svestka y Huckfeldt (1973) crean una aplicación para la recolección de depósitos entre las distintas sucursales de un banco. Los depósitos necesitan llegar a la oficina central por un grupo de mensajeros, trabajo análogo al que hacen los llamados juniors. El objetivo es determinar las rutas de los mensajeros a un mínimo costo. Lenstra y Rinnooy Kan (1975) describen dos aplicaciones similares, la primera consiste en encontrar las rutas del personal técnico, que tiene que visitar cabinas telefónicas, lo que es similar a lo hace ahora el servicio técnico de las empresas de televisión, telefonía e internet. La segunda aplicación involucra diseñar las rutas de vehículos para visitar 200 casillas de correo, para que el número usado de vehículos sea el mínimo. Otra aplicación para la programación de equipos de personas está dada por Zhang, Gruver y Smith (1999), que investiga el problema de programar equipos de fotógrafos de un estudio a un grupo grande de escuelas primarias y secundarias.
Problemas de ruteo: El problema de programar buses es investigado por Angel et al. (1972) como una variación del
-TSP con algunas restricciones. El objetivo es obtener buses llenos
de tal forma que el número de rutas se minimice, la distancia total que recorre toda la flota se mantenga al mínimo, ningún bus esté sobrecargado y el tiempo requerido para viajar en cualquier ruta no exceda el máximo definido. De manera general, el problema es equivalente a asignar rutas de vehículos con capacidad, minimizando la ruta más larga.
Programación de entrevistas: Gilbert y Hofstra (1992) describen una variación multiperiodo del problema, para programar entrevistas entre representantes y vendedores en la industria del turismo. Cada representante representa a un vendedor que debe visitar un grupo específico de puestos de vendedores, en un set de
ciudades.
18 Aplicación de un algoritmo ACO al problema
|
|
Planificación de misiones: La planificación de misiones generalmente surge en el contexto de robots móviles autónomos, donde una variedad de aplicaciones incluye construcción, reconocimiento militar, automatización de bodegas, automatización de correos y exploración planetaria. Consiste en determinar el camino óptimo para cada robot para que complete los objetivos de la misión en el menor tiempo posible. El planificador utiliza una variación del TSP donde hay
robots,
-
objetivos que deben ser visitados por los robots, y una ciudad
base a la cual todos los robots deben volver. Dos aplicaciones de este problema han sido publicadas por Brummit y Stentz (1996, 1998), la segunda para ambientes no estructurados. La planificación de robots autónomos es modelada por Zhong et al. (2002) en el campo de robótica cooperativa. Similarmente, los problemas de ruteo surgidos en la planificación de aplicaciones de vehículos aéreos no tripulados son investigados por Ryan et al. (1998) pueden ser modelados como un
-TSP con ventanas de tiempo.
Laminación en caliente: En la industria del hierro y acero, las órdenes de trabajo deben programarse en el taller de laminado de modo que el costo (setup) total de transición en la secuencia se minimice. Una aplicación reciente que modela este problema se encuentra en un complejo de hierro y acero en China, por Tang et al. (2000).
Vigilancia satelital: Una aplicación reciente y muy interesante es investigada por Saleh y Chelouah (2004). Un sistema global de navegación satelital (GNSS) es un sistema de satélites basado en el espacio que provee cobertura a todos los lugares del mundo y que es trascendental en aplicaciones de alerta temprana y manejo de desastres, monitoreo del medioambiente y agricultura, etc. El objetivo es determinar las posiciones geográficas de puntos desconocidos en y sobre la Tierra usando satélites. Estos puntos, en los cuales se sitúan receptores, son coordinados por una serie de sesiones de observación. Cuando hay receptores o períodos de trabajo múltiples, el problema de encontrar el mejor orden de sesiones.
Los casos prácticos mencionados pueden ser directamente modelados desde
|
|
(o un
-TSP), con algunas extensiones menores de ser necesarias. Sin embargo, el problema es importante también debido a que es un subproblema de otros que son más generales. Por ejemplo, el balancear las cargas de trabajo entre los vendedores, discutido por Okonjo-Adigwe (1988), que agregó límites inferior y superior a los tiempos de viaje y el peso de cada vendedor. Otro ejemplo es el del problema del guardia nocturno, investigado por Calvo y Cordone (2003), que consiste en asignar tareas a un grupo de guardias que realizan servicios de inspección de rutina en un número definido de lugares. Se agregan las restricciones de capacidad y espacios de tiempo.
19 Aplicación de un algoritmo ACO al problema
|
|
También surge como subproblema en la programación de grúas en la planificación de operación de barcos. Kim y Park (2004) investigan el problema, utilizando
-TSP para encontrar límites
inferiores en un algoritmo branch-and-bound. Una aplicación interesante está en el problema de coordinar el movimiento de múltiples objetos, como lo plantean Basu, Elnagar y Al-Hajj (2000). El problema surge en el ensamblaje de circuitos electrónicos, administración de memoria de sistemas distribuidos y la coordinación de robots móviles en un espacio estructurado, como una bodega. Se define en una red rectangular que se divide en cuadrados, que pueden contener un objeto o estar en blanco. Entonces el movimiento óptimo de objetos en una red con múltiples espacios en blanco puede encontrarse usando un modelo
-TSP.
Por último, es importante considerar que el problema de máquinas paralelas idénticas puede utilizarse para optimizar partes de otros problemas de programación de la producción, como son flow shops flexibles y job shop flexibles, que incluyen en cada etapa un set de máquinas paralelas idénticas (ver Figura 3.1, los círculos son las máquinas de cada etapa), con lo que igual pueden optimizarse estos procesos sin recurrir a métodos de mayor escala cuando no se necesitan.
Figura 3.1 Flexible Flow Shop
20 Aplicación de un algoritmo ACO al problema
|
|
4. Heurísticas para el Problema de Máquinas Paralelas 4.1. Heurísticas Las heurísticas son criterios, métodos o principios para decidir cuál de una variedad de cursos de acción alternativos promete ser el más efectivo en orden de lograr un objetivo. Representan el compromiso entre dos requerimientos: la necesidad de hacer estos criterios simples y, al mismo tiempo, el deseo de ver que discriminen correctamente entre elecciones buenas y malas. Los algoritmos son la heurística plasmada, definida paso a paso, que cumplen una misión similar a la de una receta de cocina: seguir instrucciones para lograr el objetivo propuesto, o al menos acercársele. Acercarse, porque en algunos casos resulta muy complejo llegar a la solución óptima de un problema de optimización combinatoria, muchos de estos problemas requieren la evaluación de un inmenso número de posibilidades para determinar una solución exacta, lo que lleva a necesitar tiempos extremadamente largos, incluso décadas. Las heurísticas juegan un rol efectivo en estos problemas, indicando una forma de reducir el número de evaluaciones y obtener soluciones dentro de restricciones de tiempo razonables. El problema de máquinas paralelas idénticas con tiempos de setup dependientes de la secuencia, al ser fuertemente NP-completo, es un problema que requiere heurísticas de aproximación para tener soluciones que se acercan a la ideal. Además de los tiempos exponenciales que requiere un algoritmo exacto, no se ha desarrollado ninguno para el problema, lo que refuerza más aún la idea de profundizar la investigación en heurísticas efectivas de resolución. Aunque no hay ninguna heurística definida explícitamente para el modelo, hay un número grande de heurísticas diseñadas: se han adaptado algunas del problema
(considerando la
existencia de tiempos de preparación) o por otro lado, se ha adaptado el problema a estas heurísticas (integrando los tiempos de preparación a los tiempos de proceso). En este trabajo se consideran ambas aproximaciones, además de algoritmos usados en TSP y otros problemas de optimización.
4.1.1. Longest Processing Time (LPT) Desarrollada por Graham (1969), esta regla asigna en descendentemente por sus tiempos de proceso, a las
los
primeros trabajos, ordenados
máquinas. Luego, los trabajos restantes
se programan en la máquina que esté libre antes que las otras. La heurística intenta programar los trabajos que requieren menos tiempos de proceso al final de la secuencia, donde puedan usarse para balancear la carga en las máquinas.
21 Aplicación de un algoritmo ACO al problema
|
|
Una modificación de la heurística, que considera los tiempos de setup, se encuentra en Cortés (2009): 1. Generar la secuencia de acuerdo a la regla LPT . 2. Asignar los
primeros trabajos a las
primeras máquinas.
3. Siguiendo la secuencia generada, fijar el trabajo siguiente en la máquina que termine antes de procesarlo considerando los tiempos de setup. La diferencia con la heurística LPT original es sutil: ambas buscan fijar los trabajos en la máquina que lo haga finalizar antes, pero mientras para
|
finaliza antes, para
|
sólo hay que considerar la máquina que
hay que considerar eso, pero originado por el tiempo de setup
entre los trabajos: si es grande, puede evitar que un trabajo
sea asignado en una iteración.
A modo de ejemplo, a continuación se muestra la resolución de un problema con 15 trabajos y 3 máquinas. Los tiempos de proceso se distribuyen uniformemente en preparación en
y los tiempos de
(Anexo 1).
Al ordenar los 15 trabajos de acuerdo a LPT, se obtiene la secuencia dada por la Tabla 4.1: 15
2
13
12
10
6
11
3
5
9
8
14
7
4
1
99
88
82
81
70
64
54
39
35
35
30
23
20
17
11
Tabla 4.1 Secuencia de trabajos de acuerdo a LPT
El segundo paso consiste en asignar los primeras
primeros trabajos (en este caso, 15, 2 y 13) a las
máquinas, como lo muestra la Figura 4.1.
M3
13
M2
2
M1
15 0
20
40
60
80 100 120 140 160 180 200 220 240 260 280 300 320 340 Figura 4.1 Paso 2 de algoritmo LPT
La zona achurada corresponde a los tiempos de setup, y específicamente en la figura anterior, a los tiempos de setup iniciales de cada máquina, dependientes del primer trabajo.
22 Aplicación de un algoritmo ACO al problema
|
|
La asignación posterior sigue el orden de la secuencia LPT, en la máquina que permita que el trabajo finalice antes. Para el trabajo que corresponde inmediatamente a los tres primeros (el 6), la decisión se toma de la forma mostrada en la Figura 4.2
M3
13
M2
12
2
M1
12 15
0
20
40
60
12 80 100 120 140 160 180 200 220 240 260 280 300 320 340 Figura 4.2 Paso 3 de algoritmo LPT
, pero como se da
En este caso, el menor tiempo de finalización del trabajo 12 se da en
tanto en la máquina 2 como en la 3, se elige la máquina 2 simplemente por un criterio de desempate (menor número de máquina). Finalmente, al seguir este criterio de asignación, la programación de trabajos por medio de la extensión de LPT está distribuida como muestra la Figura 4.3.
M3
13
M2
2
M1
15 0
20
40
60
10
3
14
12
11
8
6
5
9
4 1 7
80 100 120 140 160 180 200 220 240 260 280 300 320 340
Figura 4.3 Resultado de programación con extensión de LPT
La aplicación de esta heurística para este problema en específico entrega el makespan determinado por la primera máquina y da como resultado:
23 Aplicación de un algoritmo ACO al problema
|
|
4.1.2. Adaptación a LPT La extensión de LPT explicada anteriormente sigue sin considerar la importancia de los tiempos de setup en el ordenamiento inicial, los trabajos sólo se ordenan de acuerdo a su duración. Es por eso que en esta heurística, presentada en Medina (2010), los tiempos de proceso se modifican y se componen del tiempo de proceso y además del tiempo de preparación, de la forma señalada a continuación:
̅
̅ es el valor promedio de todos los tiempos de setup que podría tener el trabajo . ̅
∑
Para este ejemplo, al ordenar estos nuevos tiempos de proceso de acuerdo a LPT, se tiene: 15
2
13
12
10
6
11
3
5
9
8
14
7
4
1
113,2 106,3 94,9 93,7 88,1 83,5 67,9 57,7 52,9 48,7 46,9 38,5 37,5 34,1 28,3 Tabla 4.2 Secuencia de trabajos de acuerdo a la adaptación a LPT
De la misma manera que la extensión de LPT se asignan los trabajos. A partir de ese algoritmo, la programación de trabajos resulta ser como lo muestra la Figura 4.4
M3
13
M2
2
M1
15 0
20
40
60
10
3
14
12
11
8
6
5
9
4 1 7
80 100 120 140 160 180 200 220 240 260 280 300 320 340
Figura 4.4 Resultado de programación con adaptación a LPT
Casualmente es la misma secuencia y asignación entregada por la extensión de LPT, con el tiempo de finalización:
24 Aplicación de un algoritmo ACO al problema
|
|
4.1.3. Montecarlo 3
Montecarlo es un algoritmo probabilístico desarrollado a mediados de los años 40 por von 4
Neumann, Ulam y Metropolis mientras trabajaban en el Proyecto Manhattan . Su nombre es a partir del Casino de Montecarlo, por su relación con el azar y por ser donde el tío de Ulam gastaba su dinero. Su esencia es usar distribuciones de números aleatorios que representen un proceso en específico para calcular muestras que se aproximen a un comportamiento real. Se utiliza sobre todo cuando no se tiene un algoritmo determinístico para el problema en cuestión. Salazar (2010) define el algoritmo de Montecarlo para el secuenciamiento de la siguiente manera: 1. Determinar de forma aleatoria
secuencias, denotadas por
2. Evaluar cada secuencia respecto a la medida de desempeño considerada. 3. Denotar por
el valor resultante de para la secuencia
, con valor
4. La mejor secuencia
Para este caso el
.
de medida de desempeño es tal que
a minimizar es el makespan,
, y la asignación es la misma de LPT.
Para ejemplificar el funcionamiento de esta aplicación de Montecarlo, se usa el mismo problema 5
presentado con los algoritmos LPT. En el software SPS_PS_Setup (v2012), creado a partir de rutinas adaptadas de SPS_Optimizer (Salazar, 2010), se generan aleatoriamente secuencias que se asignan de la misma manera que las heurísticas modificadas de LPT. Como es una generación aleatoria, los resultados dependen de cada ejecución; en este caso, los resultados están dados por la programación de máquinas de la Figura 4.5
M3
3
1
M2
8
10
15
M1
6 0
20
40
11 12
60
2 9 7
13 4
14
5
80 100 120 140 160 180 200 220 240 260 280 300 320 340
Figura 4.5 Resultado de una corrida de la heurística de Montecarlo, N=100
El makespan para esta configuración lo determina la máquina 3, y es:
3
Algoritmo que utiliza la aleatoriedad como parte de su lógica. Proyecto dirigido por EE.UU que tuvo como fin el desarrollo de la primera bomba atómica. 5 Desarrollado por el profesor Eduardo Salazar H. (
[email protected]) 4
25 Aplicación de un algoritmo ACO al problema
|
|
4.1.4. Mejor Vecino La heurística del mejor vecino se origina en la resolución del problema del vendedor viajero como una solución inicial a ser mejorada por otros métodos de optimización. Es una heurística conocida como greedy, golosa, por elegir la opción más conveniente en cada iteración. Para el problema de programación de la producción de una máquina, consiste en generar
secuencias de acuerdo a
SST (shortest setup time, ordenar los trabajos por tiempos de setup, ascendentemente), cada una de estas secuencias comenzando por cada uno de los
trabajos. La secuencia elegida es la que
minimice la función objetivo. El algoritmo de la heurística del mejor vecino para el secuenciamiento de trabajos en una máquina se define a continuación. 1. Asignar cada trabajo como primer trabajo de la secuencia. 2. Realizar secuenciamiento SST (prioriza el trabajo que genera menor tiempo de preparación) con los trabajos restantes. 3. Calcular la suma de los tiempos de preparación. 4. Seleccionar la secuencia con menor suma de tiempos de preparación. Para el problema que concierne a este trabajo, la heurística del mejor vecino puede utilizarse como punto de partida para la posterior asignación en cada una de las
máquinas. Cortés (2009)
propone un algoritmo doble de resolución, que internamente tiene dos variantes de asignación: antes y después de un límite
definido tanto por el makespan inicial como por el número de
máquinas. El algoritmo se describe de la siguiente manera:
MVA 1. Realizar la secuencia como la heurística del mejor vecino. 2. Obtener el makespan
de la secuencia, como si se trabajara con una sola máquina.
3. Dividir el makespan obtenido por
(número de máquinas). Hacer este valor igual a .
4. Asignar la mayor cantidad de trabajos a la primera máquina (manteniendo la secuencia), hasta que el makespan parcial de la máquina no sea mayor a . Repetir el mismo procedimiento para cada máquina. 5. Si existen trabajos que no han sido programados, elegir el primer trabajo restante y asignarlo en la máquina en donde genere menor makespan parcial. Repetir el mismo procedimiento para cada trabajo restante.
MVD 1. Realizar la secuencia como la heurística del mejor vecino. 2. Obtener el makespan de la secuencia como si se trabajara con una sola máquina.
26 Aplicación de un algoritmo ACO al problema
|
3. Dividir el makespan obtenido por
| (número de máquinas). Hacer este valor igual a .
4. Asignar la mayor cantidad de trabajos a la primera máquina (manteniendo la secuencia), siendo el último trabajo asignado a la máquina el primer trabajo que sobrepase el valor
.
Repetir el procedimiento para cada máquina. 5. Si existen trabajos que no han sido programados, elegir el primer trabajo restante y asignarlo en la máquina en donde genere menor makespan parcial. Repetir el mismo procedimiento para cada trabajo restante.
Usando el mismo ejemplo de prueba, se elige la secuencia que utiliza menor tiempo de setup entre las
18 6 12 22 24 15 15 27 5 21 12 11 27 15 13
generadas por la heurística del mejor vecino (Figura 4.6).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 1 1 2 4 3 2 3 1 1 2 1 1 3 1
5 13 12 10 13 15 8 9 10 12 1 11 1 1 11
4 1 1 1 1 1 3 1 1 1 2 2 2 2 2
13 1 11 12 1 11 9 10 12 11 5 1 5 5 1
6 2 2 1 2 2 1 1 1 2 4 2 7 4 2
12 5 1 11 8 1 10 12 11 1 13 5 12 13 5
1 7 2 2 3 2 1 1 2 2 6 4 1 6 4
11 12 5 1 9 5 12 11 1 5 12 13 11 12 13
9 1 4 2 1 4 1 2 2 4 3 8 9 1 6
14 11 13 5 10 13 11 1 5 13 15 6 14 11 12
4 9 8 4 1 6 2 2 4 8 7 3 4 14 9
9 14 6 13 12 12 1 5 13 6 9 15 9 7 4
1 4 3 8 1 9 2 4 8 3 1 7 1 2 2
10 9 15 6 11 4 5 13 6 15 10 9 10 8 10
1 1 7 3 9 2 4 8 3 7 9 1 1 3 9
15 10 9 15 14 10 13 6 15 9 6 10 15 9 6
20 1 1 7 5 16 8 3 14 3 16 16 20 1 16
7 15 10 9 15 2 6 15 14 7 2 2 7 10 2
2 20 16 3 20 1 3 14 8 2 1 1 2 1 1
8 7 2 7 7 14 15 14 4 8 14 14 8 15 14
Figura 4.6 Heurística del mejor vecino
La secuencia generada tiene un makespan
dado por:
∑
Al dividir este resultado por
, se obtiene:
∑
8 2 1 2 3 4 14 8 4 7 8 8 8 22 4
3 8 14 8 4 9 14 4 2 14 4 4 3 6 9
19 8 8 7 4 3 8 4 6 8 6 6 19 16 3
4 3 4 14 2 7 4 2 3 4 8 8 4 2 7
4 19 6 21 6 2 4 6 14 4 8 8 4 6 2
2 4 8 2 3 8 2 3 7 2 3 3 2 3 8
26 26 28 6 20 8 6 14 2 6 14 14 26 19 8
6 6 7 3 6 3 3 7 8 3 7 7 6 4 3
Σ 125 108 100 91 104 78 74 98 75 79 99 92 132 115 82
27 Aplicación de un algoritmo ACO al problema
|
|
Al aplicar la heurística con asignación antes, puede verse que la asignación de trabajos en la máquina 1 hasta la tarea 12 entrega un makespan parcial de 258 y al agregar el trabajo siguiente de la secuencia (11) el makespan pasa a ser 313, con lo que debe dejarse el trabajo 11 asignado en la siguiente máquina, para cumplir que para cada división de la secuencua el makespan sea menor a
(274), según indica el algoritmo. (Figura 4.7)
M3 M2 M1
7 0
20
8 40
9 60
10
12
11
80 100 120 140 160 180 200 220 240 260 280 300 320 340 Figura 4.7 Asignación “antes”
Luego, después de asignar el trabajo 11 y todos los restantes posibles antes del valor
, la
configuración queda como muestra la Figura 4.8.
M3
15
M2
11
M1
7 0
20
14 1
8 40
5 9
60
4
2
13 10
6 12
80 100 120 140 160 180 200 220 240 260 280 300 320 340
Figura 4.8 Asignación completa del paso 4 del algortimo “antes”
En este caso, sólo queda por asignar el trabajo 3, con lo que se aplica lo especificado en el paso 5 del algoritmo: asignarlo donde la máquina pueda finalizar su proceso antes. Como lo muestra la Figura 4.9, es por esto que termina asignándose a la máquina 1.
M3
15
M2
11
M1
7 0
20
1 8
40
14 5 9
60
4
2
13 10
3 6
12
3 3
80 100 120 140 160 180 200 220 240 260 280 300 320 340 Figura 4.9 Paso 5 del algoritmo
28 Aplicación de un algoritmo ACO al problema
|
|
Por lo tanto, de acuerdo a la heurística del mejor vecino con asignación “antes”, la configuración final de trabajos queda presentada en la Figura 4.10.
M3
15
M2
11
M1
7 0
20
14 1
8 40
5 9
60
4
2
13 10
6 12
3
80 100 120 140 160 180 200 220 240 260 280 300 320 340
Figura 4.10 Asignación final del algoritmo del mejor vecino con asignación “antes”
Con un makespan
A partir de los datos ya obtenidos al principio de la heurística anterior, la asignación “después” de en la primera máquina es la que se muestra en la Figura 4.11
M3 M2 M1
7 0
20
8 40
9 60
10
12
11
80 100 120 140 160 180 200 220 240 260 280 300 320 340 Figura 4.11 Asignación “después”
A diferencia de la asignación antes de , en este caso el makespan parcial al terminar el trabajo 12 permite programar una nueva tarea que sobrepase este límite
. Como ahora el
makespan es 313, ya no se pueden asignar nuevos trabajos y se pasa a la siguiente máquina. Una vez asignados los trabajos por este método, la distribución de trabajos está en la Figura 4.12
29 Aplicación de un algoritmo ACO al problema
M3
14
M2
1
M1
7 0
20
4
|
2
5
3
13
8 40
|
9 60
6
15
10
12
11
80 100 120 140 160 180 200 220 240 260 280 300 320 340
Figura 4.12 Asignación final del algoritmo del mejor vecino con asignación “después”
Esta heurística, al ir asignando trabajos más allá del límite , llega a la última máquina con una especie de buffer que prevendrá que se tengan que reasignar trabajos, lo que tiene pros y contras, dependiendo del caso: a favor, que se evite perder la secuencia generada inicialmente sin enfrentar un escenario más incierto de programación, pero en contra que pueda entregar resultados muy desbalanceados. El makespan después de la ejecución de este algoritmo es Y por lo tanto, la extensión de la heurística del mejor vecino en este ejemplo arroja el makespan:
{
}
Con la programación determinada por la heurística del mejor vecino, con asignación antes de (Figura 4.10). La diferencia entre las asignaciones antes y después de
para este ejemplo está dada sobre todo
por la división de la secuencia inicial: su asignación en las
máquinas genera un escenario
excesivamente desbalanceado (y por lo tanto, peor) para el caso donde se asigna después, en comparación a la variante antes de
. Esto no necesariamente significa que ese sea siempre el
comportamiento de la heurística, para poder llegar a alguna conclusión de ese tipo es lógico que deben hacerse más pruebas. En el caso del ejemplo, es claro que la configuración desbalanceada está originada por los tiempos de proceso de varios de los trabajos asignados a las máquinas 1 y 2, considerablemente más altos que los de la máquina 3, pero desbalanceos de esta forma pueden ser originados por tiempos de setup grandes en otros casos.
30 Aplicación de un algoritmo ACO al problema
|
|
5. Ant Colony Optimization La inteligencia de enjambre es un enfoque relativamente nuevo para la resolución de problemas que se inspira en el comportamiento social de insectos y otros animales. En particular, las hormigas han inspirado variados métodos y técnicas, una de las más estudiadas es la técnica de optimización conocida como Ant Colony Optimization (ACO). ACO se inspira en el comportamiento de ciertas especies de hormigas cuando buscan su alimento. Estas hormigas depositan feromonas en el suelo para marcar los caminos que deberían seguir los otros miembros de la colonia. Ant Colony Optimization explota un mecanismo similar para resolver problemas de optimización. Desde los años noventa, cuando el primer algoritmo de ACO fue publicado, la técnica atrajo la atención de más investigadores y está disponible un número relativamente grande de aplicaciones exitosas. Por otro lado, un volumen importante de resultados teóricos se ha masificado, lo que entrega una muy útil guía para investigadores en aplicaciones adicionales de ACO.
5.1. Origen en la Biología En los años cuarenta y cincuenta, el entomólogo Pierre-Paul Grassé observó que algunas especies de termitas (Bellicositermes natalensis y Cubitermes) reaccionan a lo que llamó estímulos significantes. Observó que los efectos de estas reacciones pueden actuar como nuevos estímulos significantes tanto para el insecto que lo produjo como para los otros insectos en la colonia. Grassé usó el término estigmergia para describir esta particular forma de comunicación donde los “trabajadores son estimulados por el desempeño logrado”. Las dos características principales que distinguen a la estigmergia de otras formas de comunicación son las siguientes:
Es una forma de comunicación indirecta y sin símbolos en la que media el ambiente: los insectos intercambian información modificando su entorno.
La información es local: Sólo pueden acceder a ella los insectos que visitan el lugar donde se liberó (o su entorno inmediato).
Variados ejemplos de estigmergia pueden encontrarse en colonias de hormigas: en muchas especies, las hormigas caminan desde y hacia una fuente de comida depositada en el suelo depositando feromonas. Otras hormigas perciben la presencia de feromona y tienden a seguir caminos donde su concentración es mayor. A través de este mecanismo las hormigas son capaces de transportar comida al hormiguero en una forma extraordinariamente efectiva.
31 Aplicación de un algoritmo ACO al problema
|
|
Deneubourg et al. (1990) estudiaron extensivamente esta depositación de feromonas y el consiguiente comportamiento de las hormigas. En un experimento conocido como “del puente doble”, el hormiguero de una colonia de hormigas argentinas (Linepithema humile) fue conectado a una fuente de alimento por dos puentes de igual longitud (Figura 5.1a). En esa configuración, las hormigas comenzaron a explorar los alrededores del hormiguero y eventualmente llegaron a la comida. A lo largo de su camino entre el hormiguero y su fuente de alimentos, las hormigas anrgentinas depositan feromona. Inicialmente, cada hormiga elige al azar uno de los dos puentes, sin embargo, debido a fluctuaciones aleatorias, después de un tiempo uno de los dos puentes presenta una concentración mayor de feromonas y por lo tanto atrae más hormigas. Este puente se vuelve más atractivo, con el resultado que después de un tiempo toda la colonia converge a usar el mismo puente. Los investigadores realizaron el experimento en reiteradas oportunidades y verificaron que cada puente es utilizado el 50% de las veces (Figura 5.2a). Este comportamiento se basa en la autocatálisis, que es el aprovechamiento de retroalimentación positiva; de esta manera, las hormigas buscan el camino más corto entre la fuente de alimentos y el hormiguero. Goss et al. (1989) consideraron una variante del experimento del puente doble en el cual un puente es significativamente más largo que el otro (Figura 5.1b). En este caso, las fluctuaciones aleatorias en la elección inicial de un puente están muy reducidas y un segundo mecanismo juega un rol importante: las hormigas que eligen al azar el puente corto son las primeras en llegar al hormiguero, con lo que este puente recibe antes feromonas que el más largo (Figura 5.2b).
Figura 5.1 Esquema del experimento del puente doble (Dorigo y Stützle, 2004)
32 Aplicación de un algoritmo ACO al problema
|
|
Figura 5.2 Resultados del experimento del puente doble (Dorigo y Stützle, 2004)
Goss et al. (1989) desarrollaron un modelo del comportamiento de estas hormigas, asumiendo que en un momento del tiempo hay una probabilidad
hormigas que utilizaron el primer camino y
de cruzar el primer puente y una
el segundo, hay
de cruzar el segundo, dadas por:
Este modelo fue la principal fuente de inspiración para el desarrollo de la optimización de colonia de hormigas: en ACO, un número predeterminado de hormigas artificiales construye soluciones de un problema de optimización e intercambia información sobre la calidad de estas soluciones por medio de un sistema de comunicación que recuerda al que utilizan hormigas reales.
5.2. La Metaheurística ACO ACO se ha formalizado como una metaheurística para problemas de optimización combinatoria por Marco Dorigo y otros colaboradores. Una metaheurística es un set de conceptos algorítmicos que pueden ser usados para definir métodos heurísticos aplicables a un amplio grupo de problemas diferentes. Es decir, una metaheurística es una estructura algorítmica de propósito general que puede aplicarse a diferentes problemas de optimización con pocas modificaciones. ACO no es la única metaheurística existente, de hecho hay una gran cantidad de procedimientos metaheurísticos creados los últimos 50 años, entre los que se cuentan búsqueda tabú, computación evolutiva, recocido simulado o búsqueda iterativa local, por nombrar unos pocos.
33 Aplicación de un algoritmo ACO al problema
|
|
Para aplicar ACO a un problema de optimización se necesita un modelo adecuado:
que consiste en:
Un espacio de búsqueda
definido sobre un set finito de variables de decisión discretas
;
Un set de restricciones
Una función objetivo
La variable genérica
;y a ser minimizada (o maximizada:
).
. Una solución factible
toma valores en
asignación completa de valores a variables que satisfacen todas las restricciones en solución
es una
. Una
es llamada un óptimo global si y sólo si
Este modelo es usado para definir el modelo de feromonas de ACO. Un valor de feromona está asociado con cada componente de la solución posible, esto es, con cada posible asignación de un valor a una variable. Formalmente, el valor de feromona solución
, que consiste en la asignación
posibles se denota por
está asociado con el componente de la
. El set de todos los componentes de solución
.
En ACO, una hormiga artificial construye una solución recorriendo el grafo de construcción, un grafo completo
, donde
es un set de vértices y
obtenerse desde el set de componentes de solución
un set de aristas. Este grafo puede de dos formas: representando los
componentes como vértices o aristas. Para ir creando esta solución, las hormigas artificiales se mueven de vértice en vértice (sin repetirse) recorriendo las aristas del grafo y adicionalmente dejando una cierta cantidad de feromona en los componentes: en los vértices o en las aristas, según se haya definido. La cantidad de feromona que se deposita,
, puede depender de la
calidad de la solución encontrada y esta información es usada por las hormigas subsecuentes como una guía hacia regiones prometedoras del espacio de búsqueda. La metaheurística ACO se describe en la Figura 5.3. Después de su inicialización, itera sobre tres fases: en cada iteración, un número de soluciones se construyen por las hormigas; estas soluciones son mejoradas mediante una búsqueda local (opcional) y finalmente la feromona se actualiza.
34 Aplicación de un algoritmo ACO al problema
|
|
Definir parámetros, inicializar rastros de feromona Mientras ¬(condición) Hacer ConstruirSolucionesdeHormigas AplicarBúsquedaLocal (opcional) ActualizarFeromonas Fin Mientras Figura 5.3 Descripción de la metaheurística ACO (Dorigo y Stützle, 2004)
ConstruirSolucionesdeHormigas: Un set de
hormigas artificiales construye soluciones
desde elementos de un set finito de componentes de soluciones disponibles
{
}
. Una construcción de solución comienza desde una solución parcial vacía
. En cada paso, la solución parcial
solución factible desde el set pueden agregarse a la solución parcial
es extendida agregando un componente de
, que es definido como el set de componentes que sin violar ninguna de las restricciones en
. El
proceso de construir soluciones puede considerarse como un paseo por el grafo de construcción
.
La elección de un componente de solucion de
es guiada por un mecanismo estocástico,
que está influenciado por la feromona asociada a cada uno de los elementos de
. Esta
elección varía en los distintos algoritmos ACO, pero todos ellos fueron inspirados en el modelo de comportamiento dado en la ecuación de Goss et al.
AplicarBúsquedaLocal: Una vez que las soluciones se construyeron y antes de actualizar las feromonas, es común mejorar las soluciones obtenidas por las hormigas mediante una búsqueda local. Esta fase, que depende específicamente del problema, es opcional, aunque está incorporada en los algoritmos ACO modernos.
ActualizarFeromonas: Su objetivo es aumentar los valores de feromona que están asociados con soluciones buenas o prometedoras y disminuir las asociadas a soluciones malas. Usualmente esto se logra:
Disminuyendo todos los valores de feromonas a través de evaporación.
Aumentando los niveles de feromonas asociados con un grupo elegido de buenas soluciones.
35 Aplicación de un algoritmo ACO al problema
|
|
5.3. Variantes de ACO Para una major comprensión de cada heurística, estas son explicadas por medio el problema del vendedor viajero, TSP, porque aunque si bien ACO puede aplicarse a una gran variedad de problemas de optimización, con TSP la relación con las rutas que recorren las hormigas es mucho más directa. De hecho, las primeras implementaciones de Ant Colony Optimization fueron para este problema. En TSP, un set de ciudades es dado, la distancia entre ellas es conocida y el objetivo es encontrar la ruta más corta que permita visitar todas las ciudades una sola vez. Formalmente, el objetivo es 6
encontrar un camino hamiltoniano de largo mínimo en un grafo completo.
5.3.1. Ant System (AS) Desarrollado por Dorigo, Maniezzo y Colorni (1991), es el primer algoritmo ACO propuesto en la literatura. Su característica principal es que en cada iteración los valores de feromona se actualizan por todas las
hormigas que construyeron una solución. Las feromonas
, asociadas a la arista
que une los vértices y se actualizan así:
∑
es la tasa de evaporación de feromona, feromona que deposita la hormiga
el número de hormigas y
la cantidad de
, que se define en forma diferente dependiendo de la versión
de Ant System que se usa. Originalmente, el trabajo de Dorigo et al. (1991) considera tres diferentes versiones de AS: antdensity, ant-quantity y ant-cycle. En ant-density la actualización de feromona es inmediatamente después de que la hormiga se desplaza de un vértice a otro y su valor está dado por una cantidad fija
, de la siguiente manera:
{ En ant-quantity la actualización de feromona también es inmediatamente después de que una hormiga recorra un arco, pero a diferencia de ant-density, la actualización considera la distancia que hay entre un vértice y otro: el valor asignado al arco, como se presenta a continuación.
6
Es un grafo no dirigido que visita cada vértice sólo una vez.
36 Aplicación de un algoritmo ACO al problema
|
|
{
De esa manera, se asigna menos feromona a los arcos más extensos. Ant-cycle se diferencia de las otras dos versiones en que la actualización de feromona se hace sólo después que todas las hormigas construyan sus rutas en una función que depende de la calidad de la ruta completa generada. La cantidad de feromona depositada en este caso está definida de la siguiente forma:
{
Donde
es una constante y
es el largo del recorrido hecho por la hormiga
. Como se puede
ver, entre más corta la ruta dada por la hormiga, más feromonas se depositarán, lo que va de acuerdo con el objetivo de minimización. Cuando una hormiga
ha construido una solución parcial
y está en el vértice , elige llegar al
vértice por un procedimiento aleatorio, con una probabilidad
{∑
Donde
es el conjunto de componentes factibles: aristas
no visitada por la hormiga información heurística
Donde
.
y
donde es una ciudad (vértice)
controlan la importancia relativa de las feromonas versus la
, dada por
es la distancia entre dos vértices.
Aunque originalmente AS se componía de tres variaciones, en estos días se considera que al referirse a Ant System se está refiriendo en realidad a ant-cycle, debido a que las otras dos definiciones fueron abandonadas por su desempeño inferior.
37 Aplicación de un algoritmo ACO al problema
|
|
5.3.2. Elitist Ant System (EAS) Es la primera mejora de AS, que se introdujo por Dorigo (1992). Modifica las feromonas entregando más a los arcos pertenecientes a la mejor ruta desde el inicio del algoritmo, Esto se logra agregando una cantidad ⁄ ,y
, donde
(best so far tour).
es un parámetro que define el peso dado a
es su largo. La actualización de feromona entonces, es así:
∑
{
5.3.3. Rank-Based Ant System (ASrank) Esta es otra mejora sobre AS, planteada por Bullnheimer et al. (1999). En este caso, cada hormiga deposita feromona que va descendiendo de acuerdo a su ranking; también se le da más feromonas a los arcos de la mejor ruta, como en EAS. Antes de actualizar las feromonas, las hormigas son ordenadas de acuerdo al largo de su ruta, en orden ascendente; luego cada hormiga deposita feromonas ponderada por su ranking
. En cada iteración sólo las
hormigas mejor
rankeadas y la que ha producido el mejor recorrido (en la iteración o desde el inicio) son las que depositan feromonas. La hormiga con mejor ruta desde el inicio tiene la actualización mayor, con peso
⁄
y la -ésima hormiga de la iteración contribuye a la actualización de feromonas con el valor multiplicado por un peso dado por
. Entonces, se actualiza así:
∑
Los resultados de Bullnheimer et al. muestran que su algoritmo tiene mejores resultados que AS y EAS.
38 Aplicación de un algoritmo ACO al problema
|
|
5.3.4. MAX-MIN Ant System (MMAS) Realizado por Stützle y Hoos (1996, 2000) es una mejora de Ant System. Sus elementos característicos son que sólo la mejor hormiga actualiza los rastros de feromona y que su valor está limitado. La actualización de feromonas opera de la forma:
[ y
Donde
]
son los límites superior e inferior de feromona, respectivamente. El operador
se define como:
{
Y el valor de
es
{
es el largo de ruta de la mejor hormiga, que puede ser tanto la mejor de la iteración o la mejor desde el inicio del algoritmo, o combinadas, dependiendo de la programación. Todas las heurísticas descritas son modificaciones mayores o menores de Ant System. A continuación se describe una heurística, que aunque inspirada fuertemente en AS, introduce nuevas funcionalidades ausentes en la heurística original.
5.3.5. Ant Colony System (ACS) ACS es desarrollado por Dorigo y Gambardella (1997) y se diferencia de Ant System en tres puntos:
Aprovecha la experiencia de búsqueda acumulada por las hormigas mucho más que AS, a través del uso de una regla de acción más agresiva.
La evaporación y el depósito de feromona toma lugar sólo en los arcos del mejor tour desde el inicio del algoritmo.
Cada vez que una hormiga utiliza el arco
para desplazarse de la ciudad (vértice) a la
, remueve algo de feromonas del arco para aumentar la exploración de caminos alternativos.
39 Aplicación de un algoritmo ACO al problema
Cuando una hormiga
|
|
se desplaza de
a , lo hace de acuerdo a la regla proporcional
pseudoaleatoria, dada por
{
{
Donde
}
es una variable aleatoria distribuida uniformemente en
parámetro, y
es un
es una variable aleatoria seleccionada de acuerdo a la distribución de
probabilidades dada por la ecuación de Ant System, con
:
{∑
Lo que que quiere decir que, con una probabilidad
, la hormiga hace el mejor movimiento
posible, de acuerdo a los rastros de feromona aprendidos y la información heurística (aprovecha el conocimiento aprendido), mientras que con probabilidad influenciada de los arcos. La definición de
realiza una exploración
permite controlar el grado de exploración y la decisión
de concentrarse en la búsqueda alrededor de la mejor solución obtenida hasta el momento, o la de la exploración de otras rutas. En Ant Colony System sólo una hormiga (la de la mejor ruta hasta el momento) puede depositar feromonas en cada iteración. Esta es la llamada actualización global y se define como:
La actualización de feromonas a sólo una hormiga tiene especial relevancia: reduce la complejidad computacional de cada iteración de resolviendo. El factor
a
, siendo
el tamaño de la instancia que se está
sigue representando evaporación, con la diferencia que ahora se evaporan
tanto la feromona existente
como la feromona depositada
.
Además de esta actualización de feromona global, en ACS las hormigas también tienen un método de actualización local, que aplican inmediatamente después de cruzar un arco
:
40 Aplicación de un algoritmo ACO al problema
|
|
es el valor inicial de feromona. El efecto de esta regla de optimización local es que cada vez que
, su rastro de feromona
una hormiga utiliza un arco
se reduce, con lo que la arista se
vuelve menos atractiva para las siguientes hormigas, lo que genera un aumento de la exploración 7
de arcos que no han sido visitados y se evita el estancamiento . ACS está basado en Ant-Q, un algoritmo anterior que propusieron Dorigo y Gambardella (1995),
; Ant-Q lo definía como
que se diferencia de ACS en la definición de
8
partir de una definición similar en el algoritmo Q-learning . Si se deja
, a como un valor pequeño
resulta un algoritmo más simple, lo que sumado a que los resultados de los algoritmos no diferían demasiado, Ant-Q fue dejado de lado. MMAS y ACS comparten el hecho que ocupan límites de feromonas: uno explícitamente y el otro
, porque en ambas
implícitamente: en ACS los rastros de feromona nunca serán menores que ecuaciones de feromonas se agrega un valor mayor o igual a
, y este es el valor inicial. Por una
⁄
razón similar, los rastros de feromona nunca pueden ser mayores que
⁄
implícitamente:
. Por lo tanto,
(Dorigo y Stützle, 2004).
A partir de un significativo número de instancias, en la literatura se recomienda configurar los parámetros de ACO en TSP como se muestra en la Tabla 5.1. Algoritmo AS EAS ASrank MMAS ACS
1 1 1 1 -
2a5 2a5 2a5 2a5 2a5
0,5 0,5 0,1 0,02 0,1
⁄ ⁄ ⁄ ⁄ ⁄
10
Tabla 5.1 Configuración de parámetros para algoritmos ACO (Dorigo y Stützle, 2004)
representa el número de vértices a recorrer y la feromona inicial puede inicializarse con cualquier solución inicial, no estrictamente la del mejor vecino. Además, algunos parámetros adicionales se requieren en las extensiones de AS. EAS: ASrank: El número de hormigas que depositan feromonas MMAS:
⁄
y
√
⁄
.
√
.
es el número
promedio de opciones en cada iteración. ACS: 7
y
Que las hormigas converjan a generar el mismo camino, que puede ser una mala solución. Técnica de aprendizaje por refuerzo que indica qué acción debe ejecutarse dependiendo del estado en que se encuentre el agente. El aprendizaje por refuerzo es un esquema de prueba y error donde un agente computacional aprende a realizar una acción al recibir realimentación evaluativa del medio. 8
41 Aplicación de un algoritmo ACO al problema
|
|
6. Método Propuesto |
6.1. Relación de
|
con TSP
Varios problemas de la programación de la producción comparten similitudes con algunas instancias del problema del vendedor viajero, siendo el caso más directo el de |
|
:
La secuencia de ciudades a recorrer es análoga a la secuencia de trabajos a programar en una máquina.
Las rutas están determinadas por la distancia entre las ciudades, de la misma forma que la secuencia de trabajos depende de los tiempos de setup.
El objetivo a minimizar en TSP es la distancia recorrida por todas las ciudades, lo mismo que minimizar los tiempos de preparación, ante tiempos de proceso invariables.
Por lo general, en problemas de programación de la producción se trabaja con tienpos de setup
, con lo que la asociación es con el problema aTSP, problema
que no son simétricos del vendedor viajero asimétrico
.
Para el caso con máquinas paralelas idénticas, la analogía se transforma en
-TSP con un
objetivo minmax, que es el problema de múltiples vendedores viajeros ( ), con el objetivo de minimizar el largo de la ruta más extensa, con lo que se equilibran las distancias a recorrer entre los vendedores. Lo mismo que sucede con
|
|
: el objetivo es minimizar el tiempo de
finalización del proceso, lo que se define por la máquina que ocupa más tiempo en el sistema. Entre las múltiples heurísticas de resolución de TSP y sus variantes, han tomado mucha fuerza en los últimos quince años el uso de metaheurísticas, por sus nuevos enfoques al enfrentarse a problemas de optimización, su efectividad y adaptabilidad. Las metaheurísticas ACO han mostrado resultados prometedores en algunos casos y que superan métodos previos, en muchos otros. Por ejemplo, para TSP, dos de las heurísticas más desarrolladas y efectivas de ACO son MAX-MIN Ant System y Ant Colony System, que según los estudios de Dorigo (2004) exhiben comportamientos distintos: MMAS inicialmente entrega soluciones pobres y aunque demora, finalmente entrega las mejores soluciones; en cambio, ACS es el algoritmo ACO más agresivo y entrega las mejores soluciones en un lapso corto y muy cercanas a las que entrega MMAS en tiempos largos, como lo muestra la Figura 6.1. Por tener un mejor balance entre ambas opciones, se opta por usar ACS en la heurística para
|
|
42 Aplicación de un algoritmo ACO al problema
|
|
Figura 6.1 Desviación del valor óptimo vs. tiempo computacional de ACO en 2 problemas TSP (Dorigo y Stützle, 2004)
Heurísticas ACO se han utilizado en la resolución de diversos problemas de programación de la producción y otros, por su relación con el problema TSP. Salazar y Ruiz (2009) presentan un modelo que utiliza ACS para el problema de recolección de residuos domiciliarios por contenedores, que reduce las rutas que deben tomar los camiones recolectores. Behnamian et al. (2009) utilizan MMAS para generar una solución inicial en ejecutan ACS en una adaptación del problema
|
| |
|
, Salazar y Pavón (2011) , que es el problema de flow
shop de permutación con tiempos de preparación dependientes de la secuencia y minimización de makespan, mientras que Salazar y Sánchez (2012) evalúan tres variantes distintas de MMAS en el problema de programación de una máquina con tiempos de setup dependientes de la secuencia,
|
|
.
El algoritmo diseñado para la programación de la producción reemplaza la heurística del mejor vecino presente en Cortés (2009) por ACS y agrega una fase de optimización local en la etapa final de ambas variantes internas (antes/después), que funciona por medio de ACS también.
6.2. Extensión de ACS con Revisión Final El algoritmo, al igual que en la extensión del método del mejor vecino, considera dos variantes internas para la asignación de los trabajos luego de ser secuenciados por ACS: una asignación antes del límite
y otra después. Los trabajos pendientes son localizados en la máquina que
pueda terminar su proceso antes. La última fase de optimización local de las máquinas reordena mediante ACS la máquina más ocupada, que es la que está determinando el makespan del sistema: si se disminuye su valor y una nueva máquina es la más ocupada, se realiza el mismo proceso a este recurso. Este proceso de revisión final nace para amortiguar el efecto que tienen los tiempos de setup iniciales y los generados por la localización de trabajos pendientes.
43 Aplicación de un algoritmo ACO al problema
|
|
ACSA 1. Secuenciar los trabajos de acuerdo a la heurística Ant Colony System. 2. Obtener el makespan
de la secuencia, considerando una configuración de una máquina.
3. Obtener , dividiendo el makespan obtenido por el número de máquinas
.
4. Manteniendo la secuencia inicial, asignar la mayor cantidad de trabajos a la primera máquina, hasta que el tiempo de finalización parcial de la máquina no sobrepase el valor . Repetir para cada máquina. 5. Si todos los trabajos están programados, continuar al paso 6. Si no es así, asignarlos donde se genere un menor makespan parcial. 6. Calcular el makespan. 7. Seleccionar la máquina cuya secuencia genere el tiempo de finalización más grande. 8. Re-secuenciar los trabajos de la máquina seleccionada de acuerdo a la heurística Ant Colony System 9. Si el makespan no se reduce, finalizar. Si el makespan disminuye y la máquina resecuenciada sigue siendo la más ocupada, actualizar y finalizar. Si la máquina ya no es la más ocupada, volver al paso 7.
ACSD 1. Secuenciar los trabajos de acuerdo a la heurística Ant Colony System. 2. Obtener el makespan
de la secuencia, considerando una configuración de una máquina.
3. Obtener , dividiendo el makespan obtenido por el número de máquinas
.
4. Manteniendo la secuencia inicial, asignar la mayor cantidad de trabajos a la primera máquina, de modo que el último trabajo en la máquina será a su vez el primero que sobrepase . Repetir para cada máquina. 5. Si todos los trabajos están programados, continuar al paso 6. Si no es así, asignarlos donde se genere un menor makespan parcial. 6. Calcular el makespan. 7. Seleccionar la máquina cuya secuencia genere el tiempo de finalización más grande. 8. Re-secuenciar los trabajos de la máquina seleccionada de acuerdo a la heurística Ant Colony System 9. Si el makespan no se reduce, finalizar. Si el makespan disminuye y la máquina resecuenciada sigue siendo la más ocupada, actualizar y finalizar. Si la máquina ya no es la más ocupada, volver al paso 7. El makespan generado por el procedimiento heurístico es el menor entre las dos variantes:
44 Aplicación de un algoritmo ACO al problema
|
|
Aplicando el algoritmo para el problema-ejemplo de
y
y usando los parámetros
recomendados por la literatura en ACS para resolver TSP (Dorigo y Stützle, 2004), se obtiene la siguiente secuencia por medio del software SPS_PS_Setup: 2 14 4 10 12 11 1
5 13 6 15 9
7
8
3
88 23 17 70 81 54 11 35 82 64 99 35 20 30 39 Tabla 6.1 Secuencia inicial generada por ACS
Con
Que es completamente distinta a la secuencia inicial de LPT, lógicamente, y también diferente a la generada por la heurística del mejor vecino, sin dejar de considerar eso sí la existencia de “subrutas” que coinciden en ambas secuencias. El makespan
que produce la secuencia total es:
∑
Con lo que el parámetro
∑
resulta ser:
̅ La asignación de trabajos antes de este límite
M3
13
M2
12
M1
2 0
20
40
6 11 14
60
se presenta en la Figura 6.2.
1 4
5 10
80 100 120 140 160 180 200 220 240 260 280 300 320 340 Figura 6.2 Asignación de ACS, antes de L
45 Aplicación de un algoritmo ACO al problema
|
|
En este caso faltan 5 trabajos por asignar, se aplica el mismo procedimiento de los otros algoritmos, programando donde la máquina termine de funcionar antes. De esta manera, la configuración queda tal como muestra la Figura 6.3.
M3
13
M2
12
M1
2 0
20
40
6 11 14
60
15 1
4
5
9
3
10
7
8
80 100 120 140 160 180 200 220 240 260 280 300 320 340
Figura 6.3 Programación de heurística ACSA, hasta paso 5
.
El makespan lo define la máquina 2, y es
En este punto, la heurística revisa si esta máquina 2 puede finalizar su operación antes, reordenando su secuencia con este objetivo, mediante ACS. Resulta que hay una secuencia de estos trabajos que termina antes, como lo muestra la Figura 6.4:
M3
13
M2
3
12
M1
2 0
20
6
40
11 14
60
15
4
1 10
5
9 7
8
80 100 120 140 160 180 200 220 240 260 280 300 320 340 Figura 6.4 Revisión de ACSA en máquina 2
El makespan parcial de la máquina 2 pasa a ser 282 y como la máquina 1 es ahora la más ocupada, el makespan del sistema es
.
Como es una nueva máquina la más ocupada, el algoritmo nuevamente revisa si ACS puede determinar un reordenamiento que entregue un makespan menor, situación que se da nuevamente (Figura 6.5).
46 Aplicación de un algoritmo ACO al problema
M3
|
|
13
M2
6
3
12
M1
11
2 0
20
40
14 60
15
4
1
7
5
9
8
10
80 100 120 140 160 180 200 220 240 260 280 300 320 340 Figura 6.5 Revisión de ACSA en máquina 1
El nuevo makespan parcial de la máquina 1 es 279, pero como M3 es ahora la máquina más
.
ocupada, el makespan del sistema cambia a
Una vez más, al cambiar la máquina que determina el makespan del sistema, se revisa si algún reordenamiento puede seguir reduciéndolo. Esta vez no es posible, con lo que la secuencia final de ACSA es la misma obtenida en la iteración anterior y, por lo tanto, el makespan es
. , los trabajos quedan asignados de esta
Ahora, en cuanto a la asignación después del límite manera, a partir de la secuencia ACS inicial (Figura 6.6)
M3
15
M2
11
M1
1 2
0
20
40
9 5
8
13 14
60
7
4
3 6
10
12
80 100 120 140 160 180 200 220 240 260 280 300 320 340 Figura 6.6 Asignación de ACS, después de L
En este ejemplo todos los trabajos ya han sido asignados a partir de la secuencia inicial que produjo ACS, por lo que también es la programación hasta el paso 5 del algoritmo ACSD. El makespan lo define la máquina 1, y es
.
Posteriormente, se revisa la posibilidad de que el makespan de la máquina 1 pueda disminuir; este no es el caso, por lo que la asignación que entrega ACSD es la mostrada en la Figura 6.5 y su makespan es
.
47 Aplicación de un algoritmo ACO al problema
|
|
Finalmente, el makespan que entrega la heurística ACS con revisión es el menor entre las variantes ACSA y ACSD:
{
}
Makespan cuya programación corresponde a la que generó la sección ACSA de la heurística, representado en la Figura 6.5. Los resultados que entregaron las cinco heurísticas para el problema ejemplo se presentan en la Tabla 6.2. Heurística
LPT 336
xLPT 336
MC-100 311
MV 309
ACS(S) 297
ACS(C) 283
Tabla 6.2 Makespan del problema ejemplo en distintas heurísticas
Al menos para este problema ejemplo se puede observar que la secuenciación inicial mediante ACS reduce el makespan del problema de máquinas paralelas, en comparación con su método “hermano” (extensión del mejor vecino) y que la optimización llevada a cabo por ACS en la etapa de revisión del algoritmo propuesto lo reduce y en una mayor proporción, incluso. Esta última etapa resulta ser muy exitosa debido al balanceo de cargas entre las máquinas; de hecho, la diferencia entre la primera máquina en terminar y la última no supera los 5 segundos. Por otro lado, Montecarlo muestra el potencial de generar makespan similares a los de la extensión del mejor vecino. Por último, las heurísticas basadas en Longest Processing Time exhiben un desempeño inferior al de los otros procedimientos y que no se diferencia al menos en este ejemplo. Evidentemente, esta es sólo una comparación ilustrativa. Una comparación mucho más acabada de cada uno de los métodos heurísticos se presenta en el Capítulo 7, con instancias para problemas de complejidad superior.
48 Aplicación de un algoritmo ACO al problema
|
|
7. Evaluación y Análisis de Resultados 7.1. Información Preliminar Para la evaluación de la efectividad del método heurístico propuesto y las demás heurísticas expuestas, es necesario definir los parámetros involucrados en la programación del problema
|
|
, de manera que presenten variabilidad y prueben las heurísticas en distintos
escenarios. Estos parámetros básicos son:
Número de trabajos, .
Número de máquinas,
Tiempos de proceso de los trabajos,
Tiempos de setup dependientes de la secuencia de trabajos,
. .
Ya que el problema en sí no es cubierto extensamente, en la literatura asociada es común generar problemas artificiales. La cantidad de trabajos y máquinas en estos trabajos aunque no es la misma, tiende a coincidir: Kurz et al. (2001) usan utilizan
y
y
, Behnamian et al. (2009)
, respectivamente, França et al. (1996)
y
; mientras que Gendreau et al. (2001) experimentan con un número más amplio de valores,
y
. En Mendes et al. (2002), al igual que França et al. eligen una
proporcionalidad entre trabajos y máquinas:
y
al. (2007) mantienen fijo el número de máquinas en 6 y
. Por último, Rocha et
varía entre 10 y 100.
En cuanto a los tiempos del sistema existe más divergencia: Kurz y Behnamian con sus colaboradores establecen los tiempos de acuerdo a aplicaciones del mundo real, el primer trabajo plantea dos escenarios, donde los tiempos de setup son en promedio iguales a los de proceso y otro donde los tiempos de proceso multiplican por 10 los de setup. El segundo trabajo considera que los tiempos de setup son aproximadamente entre el 20 y 40% de los tiempos que demoran las tareas en ejecutarse, con lo que plantea que
, además de
. Los otros autores estudiados asignan los tiempos aleatoriamente sin ninguna referencia real, pero manteniendo lógicas similares a los autores anteriores: França et al. equilibran ambos
tiempos,
en
valores
más
bajos,
comparando
con
las
otras
referencias:
. Gendreau et al. diferencian los promedios de tiempos de setup y proceso, con
, mientras que Mendes et al. dejan los mismos escenarios
de Kurz et al: uno donde los tiempos de setup y proceso son en promedio iguales, y otro donde son el 10% de los tiempos de trabajo. Rocha et al. están más cerca de la consideración de Behnamian y sus colaboradores, considerando los setup aproximadamente un 40% de los tiempos de proceso.
49 Aplicación de un algoritmo ACO al problema
|
|
7.2. Escenarios de Evaluación Es en base a esta información, y con el objetivo de acercar el planteamiento teórico a las aplicaciones prácticas, que las heurísticas se estudiaron de acuerdo a tres escenarios en lo que a y
respecta:
Lo que hace que progresivamente aumente la complejidad del problema, manteniendo una relación de aproximadamente 10 trabajos en cada máquina, mismo criterio utilizado en Cortés (2009) y Medina (2010). En cuanto a los tiempos involucrados en
|
|
, para ver la influencia de los tiempos de
preparación en la resolución, se ha resuelto plantear dos escenarios:
Un nivel alto y otro bajo, para contrastar con los tiempos de proceso, distribuidos uniformemente:
Los tiempos de setup que están asociados al primer trabajo a procesarse en una máquina son considerados y están definidos tal como los otros tiempos de setup, en un nivel alto y bajo:
A continuación se definen todos los escenarios: Setup Alto
U[1,100]
U[1,100]
Bajo
U[1,30]
U[1,100]
3 5 10 3 5 10
30 50 100 30 50 100
Tabla 7.1 Escenarios considerados para la comparación de las heurísticas
En la notación de los resultados expuestos LPT representa la heurística extensión de LPT para trabajos con setup, xLPT su adaptación, con tiempo de setup promedio considerado; MC es la heurística Montecarlo, MV la del Mejor Vecino y ACS es la heurística Ant Colony System con Revisión.
50 Aplicación de un algoritmo ACO al problema
|
|
Cada vez que se compare porcentualmente los resultados de una heurística
con otra , es por
medio de la razón:
De esta manera, combinadas todas las posibilidades descritas, las heurísticas se resolvieron en 6 escenarios distintos, en las que se ejecutaron 20 repeticiones para poder apreciar de mejor manera el comportamiento de las opciones de resolución. Para el caso de la heurística basada en Montecarlo, se definió el
a utilizar mediante una prueba preliminar en el problema de
máquinas, entre
, eligiendo la que entregue la mejor
solución en un tiempo razonable. Los resultados de las heurísticas LPT, Montecarlo y del Mejor Vecino se registran mediante la ejecución de una sola repetición por instancia, a diferencia de la heurística ACS con Revisión, donde se consideran 10 repeticiones. Esto es porque la heurística ACS es un procedimiento pseudoaleatorio que considera una sola solución inicial, sujeta por tanto a variaciones entre una ejecución y otra. En el otro procedimiento aleatorio (Montecarlo) no se hace lo mismo, sólo por el hecho que
define internamente un número de repeticiones donde se elige la mejor.
Las 120 distintas consideradas se generan en el software Microsoft Excel mediante la función ALEATORIO() y luego se ejecutan en SPS_PS_Setup, diseñado para resolver cada instancia del problema y cuya interfaz se muestra en la Figura 7.1. El software se ejecuta en un computador con procesador Intel Core i5-460M de 2.53 GHz y 4 GB de memoria RAM con el Sistema Operativo Windows 7 Home Premium. Sistema de Programacion de Maquinas Paralelas con Setup Prof. Eduardo Salazar H. DII-Universidad de Concepcion / Chile Ingrese Archivo…: ejemplo.txt Heuristicas Maquinas Paralelas 1 LPT_Setup 2 LPT_xSetup 3 MV_A 4 MV_D 5 Montecarlo 6 ACS_PS Ingrese Heuristica: _ Figura 7.1 Interfaz de software SPS_PS_Setup
51 Aplicación de un algoritmo ACO al problema
|
|
7.3. Definición de Parámetros 7.3.1. Montecarlo Para definir el ,
usado en la heurística Montecarlo, se ejecutaron 20 instancias en el problema con y tiempos de setup en nivel alto, uno de los problemas de mayor complejidad
entre los 6 expuestos anteriormente, debido a su tamaño. Los valores de
analizados fueron 10,
100, 1.000, 10.000, 100.000 y 1.000.000. Como la primera ejecución de
demoró
más de 10 minutos, se decidió excluir del análisis. Los makespan generados son los que se exponen en la Tabla 7.2 Instancia
MC10
MC100
MC1000
MC10000
MC100000 MC1000000
1
758
742
711
706
695
689
2
819
791
776
760
747
733
3
796
749
739
718
711
699
4
751
715
711
704
693
682
5
770
746
718
702
690
692
6
741
716
706
696
681
669
7
726
705
696
674
670
657
8
833
793
795
775
767
758
9
818
784
770
750
744
732
10
782
752
736
739
722
701
11
728
717
690
700
687
659
12
720
704
675
664
661
648
13
774
747
745
739
721
707
14
795
746
737
720
718
715
15
726
739
710
706
692
684
16
761
741
721
706
705
684
17
758
708
709
687
684
680
18
756
743
724
714
703
685
19
757
735
726
717
700
699
20
761
735
710
714
699
691
Tabla 7.2 Makespan para MC100A
En promedio, y como es de esperar, los tiempos de finalización van mejorando a medida que el valor de
aumenta, disminución expresada de esta forma.
→
→
→
→
→
Si bien parece que una disminución del makespan de 1 o 2% puede ser baja, se traduce en alrededor de 10 segundos, lo que en el largo plazo ayuda a disponer antes de los productos y máquinas, además de tener un menor uso de estas últimas.
52
|
Aplicación de un algoritmo ACO al problema
|
En cuanto al tiempo de ejecución de las heurísticas, varía en promedio desde una fracción de segundo a más de un minuto, como puede verse en la Tabla 7.3: M10
M100
M1000
M10000
M100000
M1000000
0,00
0,01
0,07
0,71
7,08
70,78
Tabla 7.3 Tiempos de ejecución promedio para MC100A
Los tiempos de ejecución pasan de ser en promedio menores a 0,01 segundos para los casos de a irse multiplicando por 10 a medida que
se multiplica por 10 también, hasta llegar a
ser un poco más de un minuto en el caso de
. Si bien es un valor considerablemente
mayor a los que toma la ejecución de las otras cinco instancias, sigue siendo un tiempo que no es grande y permite analizar un millón de alternativas sin la necesidad de ir haciendo repeticiones. El tiempo es la misma razón por la que no se considera Montecarlo con un
, ya no es
práctico mejorar resultados en un 1% esperando 10 minutos más. De esta manera, se considera
y los makespan registrados quedan para la
comparación con las otras heurísticas en este escenario.
7.3.2. Extensión de ACS con Revisión Final Dorigo y Stützle, en el libro básico de la metaheurística (Ant Colony Optimization, 2004), recomiendan que para asegurar un buen desempeño en la aplicación de Ant Colony System para TSP los parámetros involucrados deben definirse de la manera presentada a continuación:
Parámetros determinados a partir de la experiencia en la resolución de ese problema de optimización. Para el caso de
|
|
, se compararon las secuencias iniciales de
trabajos
generadas por ACS, para ver la influencia directa de las primeras tres variables expuestas. Los valores de cada parámetro se definieron por medio de combinaciones alrededor de estos números recomendados. Específicamente, las combinaciones son a partir de los siguientes números:
53
|
Aplicación de un algoritmo ACO al problema
|
Para comenzar la comparación, se ejecutan las 27 combinaciones de parámetros en 10 instancias diferentes del problema más complejo entre los escenarios de evaluación planteados, en el que está definido definir el
y tiempos de setup en un nivel alto, que es el mismo problema usado para
en Montecarlo. Los resultados de esta comparación se encuentran en el Anexo 2 y se
resumen en la Figura 7.2.
5900 5700 5500 5300 5100 2.5.85 2.10.90 2.15.95 3.5.85 3.10.90 3.15.95 5.5.85 5.10.90 5.15.95 2.5.90 2.5.95 2.10.85 2.10.95 2.15.85 2.15.90 3.5.90 3.5.95 3.10.85 3.10.95 3.15.85 3.15.90 5.5.90 5.5.95 5.10.85 5.10.95 5.15.85 5.15.90
4900
1
2
3
4
5
6
7
8
9
10
Figura 7.2 Comparación de combinaciones de parámetros para ACS
Al ser complicado verificar sólo con este gráfico si alguna combinación es mejor que otra, es pertinente hacer un análisis más detallado. Un ranking de los promedios de makespan que generan las distintas configuraciones se muestra parcialmente en la Tabla 7.4 y completamente en el Anexo 2. Parámetros
Promedio
Desv. Est.
2.15.90
5359,9
286,4
2.10.85
5369,4
282,4
2.10.95
5369,8
288,5
2.5.85
5370,5
289,4
2.15.85
5374,4
289,2
3.5.85
5378,8
288,0
2.10.90
5379,3
280,9
3.15.85
5379,3
281,7
2.5.90
5379,7
279,0
3.10.85
5380,2
277,5
Tabla 7.4 Ranking de los primeras 10 combinaciones de parámetros, según makespan
Por otro lado, es necesario verificar cuan robusta es la generación de makespan de una combinación de parámetros, debido a que el promedio oculta esa información. Una forma de
54
|
Aplicación de un algoritmo ACO al problema
|
observarlo es registrar cuantas veces una combinación es la mejor o está entre las mejores (o las peores). La Tabla 7.5 muestra las cinco mejores, según su lugar promedio en cada una de las 10 instancias del problema y refleja en qué porcentaje una combinación se ubica entre las tres primeras. Instancia
2.15.90 2.5.85 2.10.85 2.10.95 2.15.85
1
2
1
7
3
4
2
2
8
4
1
5
3
1
9
4
2
7
4
3
3
1
5
9
5
3
4
7
4
1
6
1
2
4
5
3
7
3
6
12
4
12
8
2
3
5
8
12
9
2
9
1
10
11
10
3
8
8
13
4
% en “podio”
100%
40%
20%
30%
20%
Tabla 7.5 Posiciones de las mejores cinco combinaciones
La
heurística
ACS
que
combina
y
es
la
que
muestra
consistentemente el mejor comportamiento entre las 27 alternativas: es dos veces el valor mínimo, cuatro veces el segundo valor y cuatro veces el tercero; no sale de esas posiciones. En cambio, todas las otras opciones tienen un comportamiento más errático, llegando a ser la primera en una instancia y la 13° en otra, además que no llegan a estar entre los tres mejores resultados ni el 50% de las instancias, lo que nunca es deseable. En la otra vereda, las cinco combinaciones que muestran el comportamiento más pobre son las que muestra la Tabla 7.6: Instancia
3.5.95 5.15.95 5.10.95 5.5.95 5.5.90
1
15
24
20
27
22
2
15
19
27
26
25
3
21
20
24
24
27
4
27
25
22
26
22
5
27
24
9
25
26
6
26
19
24
18
20
7
23
26
27
21
24
8
13
26
27
19
19
9
22
18
27
22
26
10
23
20
14
21
27
% en “podio”
30%
30%
40%
40%
50%
Tabla 7.6 Posiciones de las peores cinco combinaciones
55 Aplicación de un algoritmo ACO al problema
|
|
Si se agrupan las combinaciones de acuerdo a los distintos niveles que tienen los parámetros, se aprecia claramente que el valor de
influye directamente en el desempeño de la heurística para
minimizar el makespan de la secuencia de trabajos inicial: mientras más bajo es
, se llega a
mejores soluciones de makespan; de hecho, las cinco mejores combinaciones del set de 27 son con
y siete de las ocho peores son con
. No es difícil explicar el porqué:
es el 9
parámetro que determina la importancia relativa que se le da a la información heurística , con lo que si es mayor, en cada iteración el algoritmo tenderá a comportarse más cercano a un algoritmo
.
greedy en cada iteración, siempre y cuando
Por otro lado, para este problema los valores de
y
no ejercen una influencia tal que
determinen por sí mismos el desempeño de la heurística, sí combinados con
: se encuentran
configuraciones buenas (pero no las mejores) en niveles bajos, medios y altos de valores de
y
con
.
Para determinar finalmente qué parámetros se utilizaron en la experimentación de la heurística ACS con Revisión, se eligió el set de cinco mejores combinaciones para testearlos en cinco problemas distintos a los que se utilizaron en la prueba preliminar, repitiendo cinco veces. De esta manera, pudo verificarse con mayor seguridad el desempeño de una y otra opción, así como cuándo la búsqueda de la solución se estabiliza dentro de los 5000 ciclos de prueba, importante para eliminar tiempo de ejecución computacional innecesario. Para ejemplificar el comportamiento, se muestran los resultados de una instancia del problema (Tabla 7.7). 1
2
3
4
5
Promedio Desv. Est.
2.15.90 4881 4869 4882 4893 4889
4882,8
9,18
2.5.85
4883 4915 4885 4911 4888
4896,4
15,32
2.10.85 4880 4888 4891 4896 4872
4885,4
9,48
2.10.95 4887 4907 4886 4925 4910
4903,0
16,54
2.15.85 4900 4893 4905 4882 4890
4894,0
8,92
Tabla 7.7 Makespan obtenidos con las cinco combinaciones de parámetros
Las cinco combinaciones seleccionadas no se comportan establemente, entregando distintos resultados, esto es porque ACS es un procedimiento pseudoaleatorio dirigido, con lo que la mejor solución en ese espacio factible tan grande puede ser desplazada por una solución que sigue siendo buena, debido a las bondades de la exploración de las hormigas. De hecho, las soluciones 9
Para ACO, información proporcionada al principio de la ejecución de la heurística. En el caso de TSP, son las distancias entre las ciudades y en el de | | , los tiempos de setup. Se opone a la información de feromona, que va cambiando a medida que se desarrolla la heurística ACO.
56 Aplicación de un algoritmo ACO al problema
|
|
por lo general están separadas entre 10 y 20 segundos. Pese al comportamiento descrito, puede observarse una tendencia: la heurística ACS que combina
y
nuevamente es la que en promedio genera menores makespan, seguida muy de cerca por la de parámetros
, aunque la última tiene una desviación ligeramente
y
mayor. La Figura 7.3 permite verificar gráficamente estas características en una de las instancias. 4940 4920 4900 4880 4860 4840 2.15.90
2.5.85
2.10.85 1
2
3
4
2.10.95
2.15.85
5
Figura 7.3 Makespan obtenidos con las cinco combinaciones de parámetros
Estas observaciones no sólo se rescatan de la instancia ejemplificada, sino que con pocas diferencias se presentan en las otras cuatro: en todas ellas la heurística con parámetros y
es la que en promedio entrega el menor makespan, además que en 4 de las
5 instancias es el mejor valor entre todos y donde no lo es, es el segundo mejor. La información de las cinco instancias se presenta en el Anexo 2. Es por todas estas razones que se resuelve trabajar la heurística ACS para el problema
|
|
con los parámetros:
Ahora, para fijar el número de iteraciones que tendrá como máximo la heurística para buscar una solución, se utilizan las mismas instancias y repeticiones resueltas por esta combinación de parámetros, pero ahora considerando cada iteración donde el makespan de la secuencia inicial fue mejorando. La información de dos instancias se resume en la Figura 7.4.
57
|
Aplicación de un algoritmo ACO al problema
|
5690 5640 5590 5540 0
500
1000
1500
2000
2500
2
3
2000
2500
2
3
1
3000 4
3500
4000
4500
5000
4000
4500
5000
5
5600 5550 5500 5450 5400 0
500
1000
1500 1
3000 4
3500 5
Figura 7.4 Comportamiento de ACS en 5000 ciclos para dos instancias distintas
En estos casos, una repetición es la mejor cerca del ciclo 5000, tres repeticiones encuentran su mejor solución alrededor del ciclo 4000, dos cerca de 3000, dos alrededor de 2000 y otras dos cerca del ciclo 1000, lo que muestra que es bien variable la convergencia de una solución, porque tiene un factor aleatorio considerable. Es por esto que es mejor observar cuántas veces se llega a mejorar la solución en cierto ciclo y cuánto se mejora. Ciclo
Dism. Makespan Frecuencia Frecuencia relativa
0-10
4172,84
25
100%
11-500
79,2
25
100%
501-1000
9,75
24
96%
1001-1500
7,41
22
88%
1501-2000
5,05
21
84%
2001-2500
3,16
19
76%
2501-3000
5
18
72%
3001-3500
4,07
15
60%
3501-4000
1,92
12
48%
4001-4500
5,6
10
40%
4501-5000
5,67
6
24%
Tabla 7.8 Ciclos de mejora de solución y disminución de makespan
58 Aplicación de un algoritmo ACO al problema
|
|
Es claro que la mejora más importante se da en los primeros 2000 ciclos, y por sobre todo los primeros 10, donde disminuye de forma radical una solución generada aleatoriamente. Este comportamiento es característico de ACS y fue una de las razones de su elección sobre otras heurísticas ACO. La cantidad de repeticiones donde la heurística llega a mejorar va disminuyendo a medida que los ciclos aumentan, llegando a ser un 24% entre los ciclos 4500 y 5000, prácticamente la mitad que en el ciclo inmediatamente anterior. Esta situación “real” se refleja en la Tabla 7.9, donde se asigna un valor 0 en todos los intervalos donde ya no se mejore la solución obtenida (entre el mejor encontrado y el último evaluado, 5000). Ciclo
Disminución Makespan
0-10
4172,84
11-500
79,2
501-1000
9,36
1001-1500
6,52
1501-2000
4,24
2001-2500
2,4
2501-3000
3,6
3001-3500
2,44
3501-4000
0,92
4001-4500
2,24
4501-5000
1,36
Tabla 7.9 Disminución “real” de makespan en cada tramo de ciclos
Como en más de la mitad de las instancias el makespan disminuye hasta el ciclo 3500, se eligió ese número como el tope de iteraciones para la generación de la secuencia inicial por medio de ACS. Si bien puede seguir mejorándose ese makespan, se incurre un tiempo innecesario de resolución para mejorar tiempos que se redistribuirán en las
máquinas y serán de magnitudes
muy similares a los que se reducen en la etapa de optimización del algoritmo, la última etapa de ACS con Revisión. De esta manera, al utilizar 3500 ciclos de límite en vez de 5000 para minimizar los tiempos de setup en una secuencia de trabajos, se reduce considerablemente el tiempo de ejecución computacional, un 30% aproximadamente para el caso en que se hicieron las pruebas (
,
y tiempos de setup en nivel alto): de un poco más de 50 segundos a alrededor de 35 segundos. Con estos parámetros definidos, la heurística ACS con Revisión se ejecutará 10 veces para una misma instancia, de modo que la que genere menor makespan se comparará a cada una de las otras cinco heurísticas.
59 Aplicación de un algoritmo ACO al problema
|
|
7.4. Resultados 7.4.1. Nivel de Setup Alto Primero se compara la heurística propuesta sin optimización final con los otros cuatro procedimientos. n=30
n=50
n=100
LPT xLPT MC MV ACS(S)
LPT xLPT MC MV ACS(S)
LPT xLPT MC MV ACS(S)
1
921
964
737 661
647
814
890
706 643
603
794
772
689 642
637
2
948
905
754 720
647
774
728
669 630
573
800
788
733 695
622
3
923
902
725 686
636
871
869
738 681
661
754
757
699 648
633
4
887
880
682 662
602
778
795
664 588
571
747
709
682 633
624
5
958
975
703 663
627
949
847
714 637
629
725
767
692 642
620
6
982
1032 810 767
701
815
859
684 620
586
733
743
669 601
592
7
845
893
692 579
591
827
847
699 652
621
718
699
657 609
578
8
841
899
609 548
530
901
864
729 645
658
805
846
758 682
653
9
850
950
672 676
566
809
796
713 611
637
801
775
732 659
641
10
970
919
686 602
610
854
800
734 655
615
752
773
701 663
632
11
820
869
724 672
653
855
837
710 597
626
745
730
659 618
576
12
987
1013 760 664
609
868
901
755 660
659
678
726
648 567
595
13
814
874
600 564
535
850
836
728 645
630
768
788
707 647
655
14
827
862
720 629
638
826
819
701 608
614
745
744
715 654
601
15
772
872
609 526
531
790
823
655 566
563
757
733
684 615
579
16 1014
914
777 749
699
678
659
609 543
525
763
746
684 605
606
17
858
905
672 603
585
806
862
702 632
629
730
749
680 606
615
18
792
825
672 644
580
873
811
708 641
629
746
767
685 628
586
19 1065
992
716 697
689
867
869
762 686
646
732
755
699 636
597
20
845
637 561 538 781 806 660 597 587 786 773 691 645 Tabla 7.10 Resultados de makespan para el nivel de setup alto
597
886
El menor makespan de cada instancia está subrayado y con negrita y muestra que el efecto que tiene el cambio de Mejor Vecino a ACS en la secuenciación inicial es disminuir el makespan en el 85% de las instancias para
y en el 80% del resto de los casos (
y
). Los
tiempos que demoró la ejecución computacional se muestran a continuación. LPT xLPT
MC
MV
ACS
n=30 0,00 0,00 15,43 0,00 4,96 n=50 0,00 0,00 26,07 0,00 10,83 n=100 0,00 0,00 70,78 0,02 37,19 Tabla 7.11 Tiempo promedio de ejecución para nivel alto de setup
Tiempos que varían entre una fracción de segundo para LPT y Mejor Vecino en todos los casos y tiempos menores a un minuto en heurísticas aleatorias, salvo Montecarlo para
.
60
|
Aplicación de un algoritmo ACO al problema
|
El desempeño de los procedimientos heurísticos para el problema con
y
puede
diferenciarse con mayor claridad en la Figura 7.5.
1080 980 880 780 680 580 480 0
1
2
3
4
5
6
7
LPT
8
9
xLPT
10 11 12 13 14 15 16 17 18 19 20 21 MV
Figura 7.5 Resultados para el problema con
MC ,
ACS(S) y nivel de setup alto
Se observa que los makespan generados se agrupan en 2: un grupo de tiempos de finalización altos (LPT y xLPT) y otro distanciado del primero, donde está Mejor Vecino, Montecarlo y ACS, siendo esta última la que tiene en promedio menores valores. Esto es establecido numéricamente al calcular las diferencias promedio entre las heurísticas: a la mejor heurística, ACS, sigue la heurística del Mejor Vecino, teniendo tiempos de finalización 5,38% más altos, luego sigue Montecarlo con 14,41% y mucho más lejos las dos variaciones de LPT, con 47,37% para LPT y 50,48% en la adaptación de LPT con tiempos de setup promedio, que en términos prácticos representan diferencias de 33, 87, 287 y 304 segundos, respectivamente, en tiempos alrededor de 600 segundos. Estas diferencias se detallan en el Anexo 3. 1000 900 800 700 600 500 0
1
2
3
4
5 LPT
6
7
8 xLPT
9
10 11 12 13 14 15 16 17 18 19 20 21 MV
Figura 7.6 Resultados para el problema con
MC ,
ACS(S) y nivel de setup alto
61 Aplicación de un algoritmo ACO al problema
A diferencia del escenario con
|
|
, para
la heurística del Mejor Vecino se diferencia en
un mayor grado de Montecarlo, debido a que el problema se vuelve más complejo, y por lo tanto el espacio de soluciones factibles es más grande, con lo que es más improbable encontrar buenas soluciones buscando con un procedimiento aleatorio. De todas maneras, la mejor heurística sigue siendo ACS con Revisión y en promedio, el makespan generado por el procedimiento del Mejor Vecino es un 2,31% mayor, lo sigue Montecarlo con un 14,56% y luego LPT y xLPT con valores muy similares: 35,27% y 34,77% sobre ACS, respectivamente. En promedio, estos porcentajes sobre ACS implican una diferencia de 14 segundos en relación a Mejor Vecino, 89 con Montecarlo y alrededor de 215 segundos (casi cuatro minutos) en comparación a las heurísticas LPT, que reflejan un porcentaje alto del tiempo total en el sistema (610 segundos de promedio, para ACS).
840 790 740 690 640 590 540 0
1
2
3
4
5
6 LPT
7
8 xLPT
9
10 11 12 13 14 15 16 17 18 19 20 21 MV
Figura 7.6 Resultados para el problema con
En el caso con
MC
ACS(S)
,
y nivel de setup alto
sigue presentándose la distancia entre Montecarlo y la heurística del Mejor
Vecino con ACS a medida que el tamaño del problema crece. Un problema crecientemente más complejo sigue sin afectar mayormente a la heurística ACS, aunque el desempeño de las otras se acerca: ACS es seguido una vez más por la heurística MV, con makespan 3,77% mayores, Montecarlo con 13,34% y LPT junto a xLPT con diferencias de 23,29% y 23,76%, que implican tiempos de 23, 81, 142 y 145 segundos en tiempos de sistema que son en promedio desde 610 segundos. La evolución de todas estas diferencias para los casos estudiados se representa en la Tabla 7.12. LPT
xLPT
MC
MV
n=30 50,48% 47,37% 14,41% 5,38% n=50 35,27% 34,77% 14,56% 2,31% n=100 23,29% 23,76% 13,34% 3,77% Tabla 7.12 Diferencias de makespan en nivel de setup alto
62 Aplicación de un algoritmo ACO al problema
|
|
7.4.2. Nivel de Setup Bajo Los makespan generados por todas las instancias en un nivel de setup bajo comparado con los tiempos de proceso se presentan en la Tabla 7.13. n=30
n=50
LPT xLPT MC MV ACS(S)
n=100
LPT xLPT MC MV ACS(S)
LPT xLPT MC MV ACS(S)
1
673
639
623 612
581
734
732
695 682
641
601
601
593 583
547
2
669
654
610 614
576
613
617
590 565
553
626
638
622 594
585
3
640
615
597 587
546
680
672
653 626
611
642
643
641 628
603
4
563
548
489 465
454
665
664
628 612
576
623
634
617 582
580
5
607
592
538 528
496
653
645
620 626
569
563
571
557 545
542
6
625
608
557 530
518
664
669
632 605
588
614
605
608 601
568
7
571
596
522 520
484
622
646
596 591
570
652
659
657 645
613
8
550
578
497 492
467
590
585
565 537
531
568
575
570 566
529
9
616
645
572 568
524
660
666
628 607
587
609
606
591 593
573
10 645
644
578 572
549
600
589
550 559
536
565
554
557 532
516
11 654
656
607 575
564
599
591
567 565
528
624
632
630 620
605
12 523
519
482 479
440
664
666
637 629
590
646
632
622 616
586
13 712
724
655 650
626
643
650
606 602
581
551
559
558 543
521
14 678
662
607 589
593
651
656
614 576
570
620
623
607 603
568
15 686
712
644 618
595
627
634
598 568
556
585
589
577 555
530
16 627
640
575 541
545
630
631
609 568
555
602
603
595 590
559
17 692
701
636 619
601
633
635
607 612
574
667
662
664 653
629
18 628
632
581 564
545
678
672
674 662
646
591
590
589 567
566
19 567
589
510 503
480
555
542
529 523
522
541
550
546 549
517
20 731
729
685 666
657
623
624
598 598
570
604
598
600 592
569
Tabla 7.13 Resultados de makespan para el nivel de setup bajo
El desempeño de ACS es indiscutiblemente superior una vez más: en las 120 instancias el tiempo de finalización que entrega es el menor entre los cinco procedimientos heurísticos, salvo en 2 ocasiones (
). Los tiempos de ejecución computacional que se presentan en la Tabla 7.14
son prácticamente iguales a los que se dan en un escenario con nivel alto de setup, por lo que se puede inferir que la complejidad computacional entre ambas configuraciones es la misma. LPT xLPT
MC
MV
ACS
n=30 0,00 0,00 15,45 0,00 4,78 n=50 0,00 0,00 26,06 0,00 10,69 n=100 0,00 0,00 70,54 0,01 36,92 Tabla 7.14 Tiempo promedio de ejecución para nivel bajo de setup
63 Aplicación de un algoritmo ACO al problema
|
|
750 700 650 600 550 500 450 400 0
1
2
3
4
5
6
7
LPT
8
9
xLPT
10 11 12 13 14 15 16 17 18 19 20 21 MV
Figura 7.7 Resultados para el problema con
MC ,
ACS(S) y nivel de setup bajo
En el caso menos complejo del escenario de setup bajo, los makespan de Montecarlo y Mejor Vecino exhiben un comportamiento muy similar, mucho más que lo que sucede con tiempos de setup alto. ACS se comporta mejor que ambas heurísticas, aunque a menor distancia que en los casos anteriores. Las dos variantes de LPT continúan con un desempeño equivalente, pero alejado de los otros tres procedimientos. Los tiempos de finalización de la Extensión del Mejor Vecino para |
|
son en promedio un 4,29% mayores que los de ACS, seguidos de cerca por los que
genera Montecarlo, con 6,79% y más alejados LPT con xLPT (17,00% y 17,29%, respectivamente). En promedio, ACS entrega makespan de 542 segundos y las diferencias con los otros procedimientos (23, 36, 91 y 92 segundos) reflejan que la optimización es considerable. 735 685 635 585 535 485 0
1
2
3
4
5
6 LPT
7
8 xLPT
9
10 11 12 13 14 15 16 17 18 19 20 21 MV
Figura 7.8 Resultados para el problema con
MC ,
ACS(S) y nivel de setup bajo
Cuando el problema es asignar 50 trabajos en 5 máquinas, la heurística ACS se separa un poco más de la heurística del Mejor Vecino, comparando con el caso de
. Esta última tiene tiempos
de finalización 3,98% más altos. Montecarlo lo sigue bien de cerca: los makespan que entrega son
64 Aplicación de un algoritmo ACO al problema
|
|
6,45% más altos que ACS. Para confirmar el comportamiento similar de las dos variantes de LPT, ambas tienen makespan 11,62% mayores que el procedimiento propuesto en este trabajo. En promedio, ACS tiene un makespan de 577, con lo que diferencias de 23, 37 y 67 segundos son una mejora significativa para las operaciones.
650 600 550 500 0
1
2
3
4
5
6 LPT
7
8 xLPT
9
10 11 12 13 14 15 16 17 18 19 20 21 MV
Figura 7.9 Resultados para el problema con
MC
ACS(S)
,
y nivel de setup bajo
El caso más complejo en el escenario de setup bajo muestra una similitud mucho mayor entre las heurísticas constructivas LPT, Mejor Vecino y Montecarlo. De hecho, los resultados de MV son un 4,01% mayores a los de ACS, los de Montecarlo son un 6,17% mayores, los de LPT 6,99% y los de xLPT 7,27%, que se ven reflejados en diferencias de 23, 35, 39 y 41 segundos, respectivamente, en un escenario donde ACS entrega un makespan de 565 segundos. En resumen, las diferencias relativas entre ACS y las otras heurísticas ejecutadas se presentan en la Tabla 7.15. LPT
xLPT
MC
MV
n=30 17,00% 17,29% 6,79% 4,29% n=50 11,62% 11,62% 6,45% 3,98% n=100 7,27% 6,99% 6,17% 4,01% Tabla 7.15 Diferencias de makespan en nivel de setup alto
65 Aplicación de un algoritmo ACO al problema
|
|
7.5. Análisis de Resultados Si bien el desempeño de las heurísticas está ordenado de la misma manera tanto en un nivel alto como en un nivel bajo de setup, las diferencias observadas son un tanto distintas en uno y otro caso, como lo señala la Tabla 7.16.
Nivel de Setup Alto LPT
xLPT
MC
Nivel de Setup Bajo MV
n=30 50,48% 47,37% 14,41% 5,38% n=50 35,27% 34,77% 14,56% 2,31% n=100 23,29% 23,76% 13,34% 3,77%
LPT
xLPT
MC
MV
17,00% 17,29% 6,79% 4,29% 11,62% 11,62% 6,45% 3,98% 7,27%
6,99%
6,17% 4,01%
Tabla 7.16 Diferencias de makespan en relación a ACS
Una de las características que distinguen a ambos escenarios y que puede explicar las diferencias es que un proceso con tiempos de setup altos hace mucho más importante la decisión de ordenar trabajos: en un secuenciamiento que no es tan bueno claramente un tiempo de setup grande afectará la configuración del sistema mucho más que tiempos pequeños de preparación, por esto mismo en el primer caso se está frente a una variabilidad mucho mayor en los tiempos de finalización, que se hace notar en heurísticas que no manejan de la mejor manera la minimización de tiempos entre trabajos (LPT, xLPT y en menor medida Montecarlo). Los procedimientos del Mejor Vecino y ACS siguen un camino distinto a los otros tres algoritmos, porque precisamente buscan minimizar los setup en la etapa inicial, con resultados distintos generados por la diferencia que hay entre los dos procedimientos: la secuenciación inicial en ACS busca una solución que se aproxima a la mejor que se pueda encontrar en el espacio de soluciones, mientras que en muchos casos la Extensión del Mejor Vecino no lo logra por su naturaleza greedy: en las últimas asignaciones de trabajos ya no van quedando necesariamente tiempos de setup bajos, sólo los de trabajos que no se han elegido. En la heurística propuesta también se plantea un proceso de optimización en la última etapa cuyo objetivo es reducir la variabilidad que se da en cada una de las
máquinas y que es creada por
los tiempos involucrados en el proceso, aprovechando las ventajas que ya son evidentes en Ant Colony System. Su desempeño es analizado a continuación para poder definir el grado de relevancia que tiene su implementación.
66 Aplicación de un algoritmo ACO al problema
|
|
7.5.1. Influencia del Proceso de Revisión Final Mediante ACS En la Tabla 7.17 se presenta una comparación entre la heurística planteada con y sin el procedimiento de optimización final mediante ACS para todos los escenarios de análisis ya descritos. Nivel de Setup Alto
Nivel de Setup Bajo
n=30
n=50
n=100
n=30
n=50
n=100
ACS(S) ACS(C)
ACS(S) ACS(C)
ACS(S) ACS(C)
ACS(S) ACS(C)
ACS(S) ACS(C)
ACS(S) ACS(C)
1
647
597
603
589
637
594
581
569
641
641
547
547
2
647
647
573
549
622
622
576
575
553
535
585
585
3
636
594
661
623
633
592
546
543
611
601
603
596
4
602
564
571
527
624
577
454
444
576
573
580
569
5
627
596
629
602
620
583
496
496
569
569
542
530
6
701
701
586
557
592
576
518
518
588
586
568
565
7
591
556
621
570
578
566
484
484
570
553
613
612
8
530
530
658
621
653
644
467
460
531
518
529
528
9
566
553
637
585
641
612
524
524
587
578
573
552
10
610
569
615
612
632
601
549
536
536
515
516
516
11
653
593
626
515
576
555
564
561
528
528
605
591
12
609
594
659
619
595
540
440
438
590
577
586
586
13
535
480
630
617
655
612
626
608
581
562
521
508
14
638
589
614
558
601
585
593
567
570
564
568
565
15
531
497
563
535
579
576
595
593
556
556
530
528
16
699
657
525
498
606
595
545
530
555
547
559
551
17
585
563
629
574
615
585
601
592
574
554
629
618
18
580
569
629
595
586
584
545
545
646
619
566
545
19
689
603
646
639
597
597
480
469
522
485
517
513
20
538
538
587
560
597
584
657
637
570
554
569
549
Tabla 7.17 Comparación entre ACS con revisión y ACS sin revisión
Para el escenario de setup alto, el procedimiento de revisión mejora la solución inicial en la mayoría de las instancias ejecutadas: en el 80% para
, el 90% para
y el 100% para
. Cuando los tiempos de setup son bajos comparados a los de proceso, la situación es ligeramente distinta: la revisión mejora la solución inicial en el 75% de las instancias para en el 80% de las instancias para
y
y
. Esto se explica porque la revisión por medio de
ACS intenta amortiguar la variabilidad que se produce al dividir la solución inicial en
partes,
donde aparecen los tiempos de setup que anteceden el primer trabajo de las máquinas y que no estaban considerados en la secuencia inicial. Además, amortigua posibles tiempos de setup grandes generados por los trabajos que no se asignaban antes/después de . Esa amortiguación será mayor mientras más variabilidad haya, lo que se da cuando hay nivel de setup alto.
67
|
Aplicación de un algoritmo ACO al problema
|
La influencia de la etapa final de revisión entonces puede inferirse a partir de la información ya expuesta, pero se plasma en la comparación entre la diferencia porcentual que tiene ACS sin revisión sobre ACS con revisión en la Tabla 7.18.
Heurística
Nivel de Setup Alto
Nivel de Setup Bajo
n=30
n=30
n=50 n=100
ACS sin revisión 5,45% 6,36% 3,93%
n=50 n=100
1,39% 2,19% 1,37%
Tabla 7.18 Diferencia porcentual entre ACS con revisión y ACS sin revisión
Si bien parecen diferencias menores, la inclusión del proceso de revisión produce disminuciones de makespan que no son despreciables: el 6,36% de diferencia que se da en el caso de
,
y nivel de setup alto, representa 36 segundos en procesos que de otra manera demorarían 613 segundos en promedio. El detalle de las diferencias que involucra la presencia de revisión se encuentra en el Anexo 4.
7.5.2. Diferencias entre la Asignación “Antes” y “Después” Tanto la heurística del Mejor Vecino como ACS con Revisión internamente se dividen en dos: en una heurística donde los trabajos se asignan hasta el límite calculado
y otra donde la asignación
es hasta el primer trabajo que sobrepase ese valor. La idea de esta programación es elegir la configuración que balancea mejor las máquinas, ante variabilidades de cada uno de los dos métodos. Sin embargo, es necesario saber en qué proporción se van eligiendo las soluciones para entender su funcionamiento y también para tomar decisiones de diseño de algoritmo, en casos como cuando sólo una alternativa entregue siempre los makespan menores. La Tabla 7.19 acumula las instancias de la Extensión de la heurística del Mejor Vecino donde el tiempo de finalización menor es generado por la variante antes y/o después. Mejor Vecino Nivel de setup alto
Nivel de setup bajo
n=30 n=50 n=100 Total n=30 n=50 n=100 Total Total
Antes 10 6 5 21 13 12 12 37 58
Después 10 14 15 39 6 8 7 21 60
Empate 0 0 0 0 1 0 1 2 2
Tabla 7.19 Distribución de mejores soluciones en Mejor Vecino
Para esta heurística, en los casos de setup alto la asignación después de
va aumentando su
efectividad a medida que el tamaño del problema crece y cuando el setup es bajo hay una
68 Aplicación de un algoritmo ACO al problema
|
|
estabilidad independiente de la complejidad, pero que favorece a la asignación antes de . En el caso de la heurística ACS propuesta existen algunas diferencias frente a MV, como se muestra en la Tabla 7.20. ACS sin revisión Nivel de setup alto
Nivel de setup bajo
n=30 n=50 n=100 Total n=30 n=50 n=100 Total Total
Antes 6 3 2 11 8 11 9 28 39
Después 12 17 18 47 12 9 11 32 79
Empate 2 0 0 2 0 0 0 0 2
Tabla 7.20 Distribución de mejores soluciones en ACS sin Revisión
La asignación después de
es claramente la que entrega mejores resultados en el escenario de
setup alto, llega a ser la mejor más del 80% de las instancias, lo que no se replica cuando los tiempos de preparación son bajos en relación a los tiempos de proceso; en este caso se aprecia que entre ambas se reparten los menores makespan. La Tabla 7.21 muestra cómo es la distribución de makespan mínimos después de la revisión en la máquina más ocupada. ACS con revisión Nivel de setup alto
Nivel de setup bajo
n=30 n=50 n=100 Total n=30 n=50 n=100 Total Total
Antes 3 4 1 8 8 11 10 29 37
Después 15 16 19 50 12 9 10 31 81
Empate 2 0 0 2 0 0 0 0 2
Tabla 7.21 Distribución de mejores soluciones en ACS con Revisión
Son varios los valores que cambian, pero en general se mantiene sin grandes cambios la tendencia: si la variante antes (después) es la mejor antes de hacer cualquier revisión, es probable que lo siga siendo luego de ser optimizada. De esta manera, en el diseño del algoritmo no puede dejarse de lado ninguna de las dos opciones consideradas, debido a que una u otra puede producir la mejor solución, sobre todo a partir de factores aleatorios como el tiempo de proceso de un trabajo: si es muy grande en comparación a los otros en el sistema, existe la posibilidad alta que termine desbalanceando una máquina y favoreciendo la otra alternativa que pudo manejar mejor ese problema.
69 Aplicación de un algoritmo ACO al problema
|
|
7.5.3. Consistencia de Métodos Heurísticos Si sólo se analizan valores y diferencias promedio de makespan, es posible perder una parte importante de información del comportamiento de las heurísticas en cada instancia. Por ejemplo, un procedimiento aunque tenga una mejor diferencia promedio frente a otro, puede que en varias oportunidades sea sobrepasado, debido a inconsistencias en su funcionamiento entre instancias (aleatoriedad, por ejemplo). La Tabla 7.22 indica en qué porcentaje de las 20 instancias una heurística se ubica en primer, segundo, tercer, cuarto o quinto lugar en el escenario de tiempos de setup en nivel alto. La Tabla 7.23 refleja lo mismo, pero para un nivel bajo de setup. m=3, n=30
m=5, n=50
m=10, n=100
LPT
xLPT
MV
MC
ACS
LPT
xLPT
MV
MC
ACS
LPT
xLPT
MV
MC
ACS
1°
0%
0%
20%
0%
80%
0%
0%
20%
0%
80%
0%
0%
20%
0%
80%
2°
0%
0%
75%
5%
20%
0%
0%
80%
0%
20%
0%
0%
80%
0%
20%
3°
0%
0%
5%
95%
0%
0%
0%
0%
100%
0%
0%
0%
0%
100%
0%
4°
65%
35%
0%
0%
0%
45%
55%
0%
0%
0%
50%
50%
0%
0%
0%
5°
35%
65%
0%
0%
0%
55%
45%
0%
0%
0%
50%
50%
0%
0%
0%
Tabla 7.22 Porcentajes de posiciones de las heurísticas (Nivel alto) m=3, n=30
m=5, n=50
m=10, n=100
LPT
xLPT
MV
MC
ACS
LPT
xLPT
MV
MC
ACS
LPT
xLPT
MV
MC
ACS
1°
0%
0%
10%
0%
90%
0%
0%
0%
0%
100%
0%
0%
0%
0%
100%
2°
0%
0%
85%
5%
10%
0%
0%
85%
20%
0%
5%
0%
90%
5%
0%
3°
0%
0%
5%
95%
0%
0%
5%
15%
75%
0%
20%
20%
5%
55%
0%
4°
50%
50%
0%
0%
0%
55%
40%
0%
5%
0%
40%
20%
5%
40%
0%
5°
50%
50%
0%
0%
0%
45%
55%
0%
0%
0%
35%
60%
0%
0%
0%
Tabla 7.23 Porcentajes de posiciones de las heurísticas (Nivel bajo)
ACS genera los mejores resultados la gran mayoría de las instancias ejecutadas (90%, en promedio). La Extensión de la heurística del Mejor Vecino en promedio es la que sigue a ACS en desempeño, pero en algunas ocasiones (que siguen siendo minoría) es superada por Montecarlo, que aprovecha la menor variabilidad que provocan tiempos de setup bajos. Montecarlo es en general la heurística que presenta el tercer mejor desempeño, aunque en una menor proporción en el problema de
,
y nivel bajo de setup, donde LPT y xLPT aprovechan la menor
variabilidad de las soluciones y que el problema sea más complejo, con lo que Montecarlo tiene menos probabilidades de obtener soluciones buenas. Las dos variantes de Longest Processing Time se disputan el cuarto lugar: su rendimiento es prácticamente igual y en los 120 problemas LPT tiene 61 veces mejor solución que xLPT (59). Es importante acotar que la etapa de revisión hace que la heurística propuesta sea la mejor en el 100% de los casos.
70 Aplicación de un algoritmo ACO al problema
|
|
7.6. Validación Estadística 7.6.1. Análisis de Varianza Además de comparar el comportamiento promedio de las heurísticas, es necesario verificar si los resultados tienen una diferencia estadísticamente significativa, de manera de asegurar que una heurística es consistentemente mejor que otra y que sus resultados no fueron producto de mero azar. El análisis de varianza, también conocido como ANOVA, se utiliza para contrastar la hipótesis de igualdad de medias poblacionales, eligiendo entre las dos hipótesis:
Donde
representa la media de la población de la cual se ha tomado una muestra. El rechazar la
hipótesis nula
indica simplemente que no se puede asegurar que las distintas muestras
tengan la misma media. El análisis de la varianza descompone la variabilidad de los datos observados en dos componentes: una componente entre grupos, que en este caso cuantifica las diferencias entre el makespan generado por las distintas heurísticas, y una componente dentro de grupos, que cuantifica las diferencias dentro de cada heurística. Si se estima la variabilidad entre grupos y es significativamente mayor que la variabilidad dentro de grupos, es evidente que las medias de los grupos no son similares. Fuente Suma de Cuadrados Entre grupos 1,8402E6 Intra grupos 379705, Total (Corr.) 2,21991E6
Gl Cuadrado Medio Razón-F Valor-P 4 460050, 115,10 0,0000 95 3996,9 99
Tabla 7.24 Ejemplo de tabla ANOVA
Tanto la razón-F como el valor-P pueden entregar los resultados del análisis de varianza, pero suele utilizarse este último, por ser más directo. Cuando un valor-P es menor a 0,05 (con 5% de 10
nivel de significancia ), la hipótesis nula se rechaza. En el caso del ejemplo se están comparando los cinco métodos heurísticos en tiempos de setup de nivel alto, con
. Como 0,0000 < 0,05,
existe una diferencia significativa entre las medias. Si el valor-P es pequeño, las muestras deben ser examinadas para determinar qué medias son significativamente diferentes unas de otras. Un método para hacer esta comparación son las pruebas de múltiples rangos por medio de los intervalos HSD de Tukey (Honestly Significant Difference), que compara todos los pares de muestras mediante la diferencia de sus medias e 10
Error de tipo I, probabilidad de rechazar
cuando en realidad es verdadera.
71 Aplicación de un algoritmo ACO al problema
|
|
identifica cuando una de ellas es mayor al error estándar esperado. La tabla especifica claramente cuáles muestras tienen una media significativamente diferente. Método: 95,0 porcentaje Tukey HSD
ACS MV MC LPT xLPT
Casos 20 20 20 20 20
Media Grupos Homogéneos 579,5 X 643,65 X 697,85 X 898,0 X 914,5 X
Contraste Sig. Diferencia +/- Límites LPT - xLPT -16,5 55,5938 LPT - MV * 254,35 55,5938 LPT - MC * 200,15 55,5938 LPT - ACS * 318,5 55,5938 xLPT - MV * 270,85 55,5938 xLPT - MC * 216,65 55,5938 xLPT - ACS * 335,0 55,5938 MV - MC -54,2 55,5938 MV - ACS * 64,15 55,5938 MC - ACS * 118,35 55,5938 * indica una diferencia significativa. Tabla 7.25 Test de Rangos Múltiples
La sección inferior muestra cada par de medias. La columna Diferencia muestra la media simple del primer grupo menos la del segundo. La columna +/- Límites muestra un intervalo de confianza para la diferencia. Cualquier par de medias para el que el valor absoluto de la diferencia exceda el límite presenta diferencia estadísticamente significativa al nivel de confianza seleccionado y es representado por un * en la columna Sig. Cuando existen valores atípicos, deben utilizarse procedimientos no paramétricos como una alternativa a los análisis estándar de la varianza seleccionando test como el de Kruskal-Wallis, que compara las medianas de las muestras en vez de las medias:
LPT xLPT MV MC ACS
Tamaño de Muestra Rango Promedio 20 78,725 20 82,125 20 31,025 20 44,575 20 16,05 Estadístico = 80,7532 Valor-P = 0 Tabla 7.26 Prueba de Kruskal-Wallis
72 Aplicación de un algoritmo ACO al problema
|
|
Nuevamente es el valor-P el que debe observarse: si es menor que 0,05, la hipótesis nula se rechaza, y si es mayor se acepta que las medianas son todas iguales. Los resultados de ANOVA muestran que existe una diferencia estadísticamente significativa entre las medias de los makespan generados por las heurísticas, con un valor-P que fue siempre menor del orden de 0,0000. La prueba de Kruskal-Wallis también entrega valores-P muy cercanos a cero, lo que lleva a concluir que las medianas de los tiempos de finalización no son iguales. Por último, el test de rangos múltiples evalúa las diferencias estadísticas entre cada par de heurísticas y arroja las siguientes conclusiones:
No hay diferencia estadística significativa entre los makespan generados por LPT y xLPT.
No existe diferencia estadística significativa entre Montecarlo y la Extensión del Mejor Vecino en ninguna de las instancias de tiempos de setup en nivel bajo. Tampoco en el caso de
,
y tiempos de setup en nivel alto, cuando en promedio MV tiene mejor desempeño que Montecarlo.
Los resultados de makespan que genera ACS con Revisión tienen una diferencia estadísticamente significativa con todos los otros procedimientos heurísticos, salvo en el caso de
,
y tiempos de setup en nivel bajo, donde no la hay con Montecarlo y el Mejor
Vecino, aunque de todas maneras siempre tenga los menores valores, que es lo que realmente importa. El detalle de estos resultados y las pruebas de hipótesis asociadas se encuentran en el Anexo 5.
7.6.2. Supuestos de ANOVA Para que los resultados de la validación estadística representen realmente el comportamiento de la muestra, según Dean y Voss (2009) y Kutner (2004) deben cumplirse obligatoriamente tres condiciones básicas en relación a los residuos
Independencia.
Normalidad.
Homocedasticidad.
11
de cada muestra:
Si se realiza un análisis bajo estos supuestos cuando las variables de error son dependientes, los verdaderos niveles de significancia en las pruebas de hipótesis pueden ser mucho más altos que los planteados y los verdaderos niveles de confianza mucho menores. La forma más simple de observar la independencia de los residuos es graficando los residuos estandarizados en el orden en que las observaciones correspondientes se recolectaron y en una disposición que permita ver la
11
Diferencia entre una observación y la media de la muestra.
73 Aplicación de un algoritmo ACO al problema
|
|
diferencia con el valor 0, ya sea en forma diagonal u horizontal. Si se cumple el supuesto de independencia, los residuos deberían estar dispersos alrededor de cero sin ningún patrón distinguible. De todas maneras, para no estar sujeto al arbitrio de lo que se aprecia en un gráfico, se busca probar las siguientes hipótesis para descartar correlación
12
en las instancias generadas:
La prueba más común para la independencia es la prueba chi-cuadrada, que compara las frecuencias esperadas y observadas calculando:
∑∑
Donde
representa el número de filas y
el número de columnas del conjunto de datos. Asociada
a la prueba hay un valor-P que si es menor a 0,05 (cuando el nivel de confianza es del 5%) permite rechazar la hipótesis nula. Este valor-P se calcula comparando la estadística de prueba a una chicuadrada con
grados de libertad.
Tal como con la independencia de los residuos, la normalidad puede verificarse mediante un gráfico, que contrasta los residuos estandarizados contra los percentiles de la distribución estándar, de manera que si los puntos muestran una tendencia diagonal, se está ante normalidad. Pero como es preferible contar con un resultado concreto, pueden utilizarse las pruebas de bondad de ajuste, que en el caso que concierne a esta verificación, las hipótesis son:
Otraa prueba chi-cuadrada (que funciona de manera similar a la prueba de independencia) divide el rango de la muestra en
intervalos y hace la comparación entre
y
, de la forma
∑
es el número de datos observados en el intervalo intervalo. El valor
y
el número esperado de datos en el
es comparado con una distribución chi-cuadrada con
, con
dependiendo de la distribución comparada. Si el valor-P que resulta de esta prueba es mayor a 0,05, se rechaza la hipótesis nula.
12
Grado de dependencia entre muestras.
74 Aplicación de un algoritmo ACO al problema
|
|
Por último, la homocedasticidad se puede verificar mediante el planteamiento de estas dos hipótesis:
Prueba Valor-P Levene's 1,81737 0,131841 Tabla 7.27 Verificación de varianza
La prueba de Levene entrega, aparte de su estadístico, un valor-P que si es menor que 0,05 indica una diferencia estadísticamente significativa entre las varianzas de las muestras. Un valor mayor a 0,05 no permite rechazar
. Además se indica cuáles son las varianzas comparadas, como se
muestra en la Tabla 7.26. Comparación ResLPT / ResxLPT ResLPT / ResMV ResLPT / ResMC ResLPT / ResACS ResxLPT / ResMV ResxLPT / ResMC ResxLPT / ResACS ResMV / ResMC ResMV / ResACS ResMC / ResACS
Sigma1 80,8768 80,8768 80,8768 80,8768 56,3116 56,3116 56,3116 66,4936 66,4936 56,7332
Sigma2 56,3116 66,4936 56,7332 51,3066 66,4936 56,7332 51,3066 56,7332 51,3066 51,3066
F-Ratio 2,06277 1,47941 2,03223 2,48485 0,717194 0,985192 1,20462 1,37368 1,67963 1,22272
P-Valor 0,1233 0,4010 0,1310 0,0541 0,4756 0,9744 0,6890 0,4956 0,2673 0,6656
Tabla 7.28 Comparación de desviaciones de residuos.
Los supuestos estadísticos de ANOVA se cumplen en cada una de las heurísticas aplicadas en los 6 escenarios diferentes, información disponible en el Anexo 6.
75 Aplicación de un algoritmo ACO al problema
|
|
8. Conclusiones El problema
|
|
a pesar de no ser abordado extensamente en la literatura (como
) tiene una multitud de aplicaciones en áreas de la industria tan diversas como la producción de plásticos, imprentas, producción de vidrio e industrias textiles, además es análogo a problemas que tampoco se exploran con frecuencia, como el más larga entre
-TSP donde se minimiza la ruta
viajeros, aplicado por ejemplo a ruteo de buses, programación de repartidores,
servicio técnico e incluso aplicaciones satelitales y de exploración militar y planetaria. El problema tiene una alta complejidad, con lo que es posible ir mejorando las soluciones con nuevos métodos y mejorar los procesos de muchas áreas de la vida productiva. La heurística consistente en una extensión del método del Mejor Vecino entrega mejores resultados que las heurísticas basadas en LPT y el algoritmo aleatorio de Montecarlo, pero tiene las limitaciones que se dedica a mejorar el procedimiento ACS propuesto: la secuencia inicial que genera al ser mediante un algoritmo greedy no permite una exploración acabada de posibles soluciones. En este caso sólo se revisan
opciones, correspondientes a los
trabajos que
comienzan una secuencia y a medida que avanzan las asignaciones de la secuencia ya no se elige necesariamente un tiempo de setup bajo entre trabajos, sino que sólo las opciones que no se han elegido antes. Luego, en la etapa final del algoritmo, las asignaciones antes/después de
y de los
trabajos no asignados no logran corregir variabilidades que nacen tanto del tiempo inicial de setup en cada máquina como de la partición en
secuencias, que con alta probabilidad no será lo
idealmente balanceado. Las modificaciones incluidas en la heurística ACS con Revisión demuestran numéricamente que tanto la optimización inicial por ACS como la revisión final en la máquina más ocupada disminuyen los tiempos de makespan: la exploración inicial permite encontrar una solución que está entre las mejores en el espacio de soluciones factibles y la etapa de revisión permite optimizar sub-secuencias que para la solución inicial de
trabajos no eran la
mejor opción, sin dejar de considerar la variabilidad ya mencionada. El procedimiento ACS sin revisión es mejor que el Mejor Vecino alrededor del 90% de los casos y con revisión en el 100%, con tiempos de finalización promedio que son mejorados un 6,4% en promedio. El desempeño de la heurística basada en ACS es en promedio superior al de los cuatro métodos ya mencionados y su diferencia se amplía cuando los tiempos de setup son comparables a los tiempos de proceso, debido a la mayor influencia que tienen en el secuenciamiento tiempos de preparación grandes. Esto es porque la variabilidad de las soluciones es más grande y una solución que no es lo suficientemente buena puede desbalancear la carga de una o más máquinas o por otro lado puede generar un sistema balanceado pero con tiempos de finalización que pueden seguir siendo optimizados.
76 Aplicación de un algoritmo ACO al problema
|
|
La asignación de trabajos antes y después del parámetro
que utilizan tanto ACS como la
extensión del Mejor Vecino no pueden calificarse como uno mejor que el otro: hay casos donde la asignación “después” entrega muchas más soluciones para la heurística que la variante después (niveles de setup alto), mientras que en otros casos el comportamiento es repartido (niveles bajos de setup), lo que es definido sobre todo por factores aleatorios, como un trabajo con tiempo de proceso muy alto que desbalancee la configuración de una asignación y favoreciendo otra. Ningún rediseño que considere este tipo de asignaciones debería dejar de lado una u otra variante. Algunas de las razones que originan las diferencias de desempeño entre las heurísticas estudiadas tienen que ver con que algunas son adaptaciones imperfectas de procedimientos aplicados exitosamente en otros algoritmos. Es el caso de LPT, que tiene buenos resultados en el problema
, pero que no maneja de la mejor forma la presencia de tiempos de preparación entre trabajos: empieza ordenando los trabajos según su tiempo de proceso y luego limita la decisión de minimizar el setup a
opciones en cada iteración, lo que de por sí limita cualquier búsqueda de
solución. La adaptación consistente en considerar un promedio de los tiempos de setup posibles para cada trabajo es inefectiva por esta limitación de la decisión y porque ese promedio introducido no permite aprovechar combinaciones de trabajos que minimicen una secuencia. Aun así, estas dos variantes de Longest Processing Time logran acercarse a los métodos con mejor desempeño en el problema más grande analizado y con los tiempos de setup más bajos, ya que en ese caso trabajan con una variabilidad de tiempos menor a la del caso de un nivel de setup alto y alcanzan a ejecutar mejor su estrategia de asignar los trabajos con menores tiempos de proceso al final para balancear el sistema. El trabajo mostró también la relevancia que puede tener un método heurístico pseudoaleatorio que va usando la información disponible (y modificándola en el camino) versus un procedimiento que ocupa sólo la aleatoriedad, sin dirigirla, como Montecarlo, que sólo genera y genera soluciones en forma aleatoria y elige la mejor. Esta diferencia se plasma en el hecho que ACS con Revisión chequea entre 3500 soluciones posibles exploradas por 10 hormigas para entregar una solución que llega a ser más de un 20% mejor que un algoritmo que revisó 1.000.000 de alternativas y que terminó necesitando más del doble de tiempo en su ejecución computacional. La definición de los parámetros necesarios en un procedimiento metaheurístico demuestra ser tan importante como la misma elección del método, es el caso de la determinación de los parámetros y
y sobre todo con el factor : para el caso tratado en este trabajo, si se escoge un valor alto
dentro de lo que es recomendado en la literatura, las soluciones encontradas no son las mejores y se llega en pocas iteraciones al estancamiento de la búsqueda. Es necesario entonces hacer las pruebas suficientes para afinar el funcionamiento y tener la mejor puesta a punto del sistema. Si bien uno de los parámetros escogidos es ligeramente distinto al que recomienda la literatura para
77 Aplicación de un algoritmo ACO al problema
|
|
TSP, su comportamiento en las pruebas fue el más consistente, lo que puede explicarse por dos motivos: la naturaleza del problema que se está tratando (sin dejar de lado su complejidad), y por otro lado que los autores de la metaheurística los testearon en márgenes más amplios, para poder abordar buena parte de los niveles posibles que se pueden combinar. Los resultados que genera la heurística ACS con Revisión son un indicativo fuerte del potencial que tiene la aplicación de metaheurísticas en la resolución de distintos problemas de optimización, potencial que se ha visto facilitado por todos los avances exponenciales que ha tenido la tecnología las últimas décadas. Lo más interesante de todo es que a pesar de todas las ventajas que entrega el progreso extensivo de la tecnología, la ciencia (y por tanto el hombre) se vuelve hacia la naturaleza que siempre ha estado, para inspirarse y aprovechar los recursos que ha creado. Casos como algoritmos evolutivos, algoritmos genéticos, algoritmos de abejas o el mismo Ant Colony Optimization lo comprueban. A partir de esta propuesta de heurística híbrida entre métodos constructivos y metaheurísticas pueden desarrollarse trabajos futuros que aprovechen aún más las ventajas de la optimización proporcionada por Ant Colony System, integrando funciones de intercambio de tareas entre las máquinas, de inserción de un trabajo en otra máquina, o la remoción de un proceso crítico para después asignarlo en otro recurso, por ejemplificar algunas. Funciones como esas permiten explorar más a fondo aún el espacio de soluciones del problema
|
|
y posiblemente
llegar a encontrar mejores soluciones a las que no tiene acceso ACS con Revisión. Además, la extensión de un procedimiento heurístico como este no necesariamente puede ser sólo con nuevas funciones o la misma metaheurística ACO, puede considerar aplicaciones generalmente utilizadas en problemas de optimización combinatorial complejos, como procedimientos de búsqueda local, que exploran soluciones de forma iterativa en las vecindades de las soluciones y que pueden lograr una convergencia más rápida del procedimiento. Otro tipo de metaheurísticas, como búsqueda tabú pueden ayudar a este mismo objetivo, ignorando en algunas iteraciones soluciones que no son lo suficientemente buenas, o puede aprovecharse el uso de algoritmos genéticos en algunas funciones, como la de intercambio, por la directa relación que puede tener con su idea de cromosomas y el uso de crossovers. La idea general es no limitarse a un procedimiento y buscar como objetivo optimizar las soluciones, para que el impacto real que pueda tener sea el máximo posible.
78 Aplicación de un algoritmo ACO al problema
|
|
Referencias Allahverdi, A., Gupta, J. N., & Aldowaisan, T. (1999). A review of scheduling research involving setup considerations. Omega, 27(2), 219-239. Allahverdi, A., Ng, C. T., Cheng, T. C., & Kovalyov, M. Y. (2008). A survey of scheduling problems with setup times or costs. European Journal of Operational Research, 187(3), 985-1032. Allahverdi, A., & Soroush, H. M. (2008). The significance of reducing setup times/setup costs. European Journal of Operational Research, 187(3), 978-984. Angel, R. D., Caudle, W. L., Noonan, R., & Whinston, A. (1972). Computer-Assisted School Bus Scheduling. Management Science, 18(6), B279-B288. Baker, K. R., & Trietsch, D. (2009). Principles of sequencing and scheduling. John Wiley and Sons. Basu, A., Elnagar, A., & Al-Hajj, R. (2000). Efficient coordinated motion. Mathematical and Computer Modelling, 31(2–3), 39 - 53. Bektas, T. (2006). The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega, 34(3), 209-219. Behnamian, J., Zandieh, M., Fatemi Ghomi S.M.T. (2009), Parallel-machine scheduling problems with sequence-dependent setup times using an ACO, SA and VNS hybrid algorithm. Expert Systems with Applications: An International Journal, v.36 n.6, p.9637-9644. Brummit, B., & Stentz, A. (Tony). (1996). Dynamic Mission Planning for Multiple Mobile Robots. Proceedings of the IEEE International Conference on Robotics and Automation. Brummit, B., & Stentz, A. (Tony). (1998). GRAMMPS: A Generalized Mission Planner for Multiple Mobile Robots. Proceedings of the IEEE International Conference on Robotics and Automation. Bullnheimer, B., Hartl, R. F., & Strauß, C. (1997). A new rank based version of the Ant System. A computational study. Adaptive Information Systems and Modelling in Economics and Management Science Calvo, W. R., & Cordone, R. (2003). A heuristic approach to the overnight security service problem. Computers & Operations Research, 30(9), 1269-1287. Carter, A. E., & Ragsdale, C. T. (2002). Scheduling pre-printed newspaper advertising inserts using genetic algorithms. Omega, 30(6), 415-421.
79 Aplicación de un algoritmo ACO al problema
|
|
Cortés, P. (2009). Análisis de heurísticas para el problema de máquinas paralelas idénticas, con setup y minimización del makespan. Memoria de título. Departamento de Ingeniería Industrial, Universidad de Concepción. Cheng, T. C. E., & Sin, C. C. S. (1990), A state of the art review of parallel machine scheduling research. European Journal of Operational Research, 47, 271–292 Coffman EG, Garey MR, Johnson DS. (1978), An application of bin-packing to multi-processor scheduling. SIAM Journal of Computing Vol. 7, pp.1-17. Dean, A. M., & Voss, D. (1999). Design and Analysis of Experiments. Springer. Deane RH, White ER. (1975), Balancing workloads and minimizing setup costs in the parallel processing shop. Operations Research Q; 26:45-53. Dearing, P. M., Henderson, R. A. (1984), Assigning looms in a textile weaving operation with changeover limitations. Production and Inventory Management 25, 23-31. Dell'Amico, M., lori, M., Martello, S., and Monaci, M. (2008), Heuristic and Exact Algorithms for the Identical Parallel Machine Scheduling Problem. INFORMS Journal on Computing, Vol. 20, No.3, pp.333-344. Deneubourg, J.-L., Aron, S., Goss, S., & Pasteels, J. M. (1990). The self-organizing exploratory pattern of the argentine ant. Journal of Insect Behavior, 3(2), 159-168. Domínguez Machuca, J., Álvarez, M.J., García, S., Domínguez Machuca, M. A., Ruíz, A. (1995). Dirección de Operaciones: Aspectos Estratégicos en la Producción y los Servicios. McGraw-Hill, Primera Edición Dorigo, M., Birattari, M., & Stutzle, T. (2006). Ant Colony Optimization: Artificial Ants as a Computational Intelligence Technique. IEEE Computational Intelligence Magazine, 1(4), 28-39. Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1), 53-66. Dorigo, M., Maniezzo, V., Colorni, A. (1991). Positive Feedback as a Search Strategy. Technical Report 91-016, Dipartimento di Elettronica Politecnico di Milano. Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 26(1), 29-41. Dorigo, M, & Stützle, T. (2004). Ant Colony Optimization. Bradford Books, MIT Press. Primera Edición.
80 Aplicación de un algoritmo ACO al problema
|
|
Flynn, B. B. (1987). The effects of setup time on output capacity in cellular manufacturing. International Journal of Production Research, 25, 1761–1772. França, P.M., Gendreau, M., Laporte, G., Muller, F.M. (1996). A tabu search heuristic for the multiprocessor scheduling problem with sequence dependent setup times. International Journal of Production Economics, 43(2/3), 79–89. Frederickson, G., Hecht, M. S., & Kim, C. E. (1978). Approximation algorithm for some routing problems. SIAM Journal on Computing, 7, 178–193. Gambardella, L. M., Dorigo, M. (1995). Ant-Q: A Reinforcement Learning approach to the traveling salesman problem. Proceedings of ML-95, Twelfth International Conference on Machine Learning, Morgan Kaufmann, 1995, 252–260 Gambardella, L. M., & Dorigo, M. (1996). Solving symmetric and asymmetric TSPs by ant colonies. Proceedings of IEEE International Conference on Evolutionary Computation, 1996 (pp. 622-627). Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NPCompleteness. A Series of Books in the Mathematical Sciences. Freeman. Gendreau, M., Laporte, G., Morais, E.M. (2001). A divide and merge heuristic for the multiprocessor scheduling problem with sequence dependent setup times. European Journal of Operational Research, 133(1), 183–189. Gilbert, K. C., & Hofstra, R. B. (1992). A New Multiperiod Multiple Traveling Salesman Problem with Heuristic and Application to a Scheduling Problem. Decision Sciences, 23(1), 250. Geoffrion AM, Graves GW. (1976). Scheduling parallel production lines with changeover costs: Practical application of a quadratic assignment/LP approach. Operations Research; 24:595-610. Gorenstein, S. (1970). Printing Press Scheduling for Multi-Edition Periodicals. Management Science, 16(6), B373-B383. Goss, S., Aron, S., Deneubourg, J., & Pasteels, J. (1989). Self-organized shortcuts in the Argentine ant. Naturwissenschaften, 76(12), 579-581. Graham, R. L. (1969). Bounds on multiprocessor timing anomalies. SIAM Journal of Applied Mathematics, Vol.17, pp.416-429. Guinet, A. (1993). Scheduling sequence-dependent jobs on identical parallel machines to minimize completion criteria. International Journal of Production Research, 31, 1579–1594.
81 Aplicación de un algoritmo ACO al problema
|
|
Gupta J.N.D., Ruiz-Torres AJ. (2001). A LISTFIT heuristic for minimizing makespan on identical parallel machines. Prod Plan Control, Vol 12, pp.28-36. Gutiérrez, E. & Mejía, G. (2006). Evaluación de algoritmos genéticos para el problema de máquinas en paralelo con tiempos de alistamiento dependientes de la secuencia y restricciones en las fechas de entrega. Grupo de Investigación en Producción y Logística (PYLO), Universidad de los Andes, Colombia. Hahn, C. K., Bragg, D. J., & Shin, D. W. (1989). Impact of the setup variable on capacity and inventory decisions. Academic Management Review, 13, 91–103. Johnson, D.S. and Papadimitriou, C.H. (1985). Computational complexity, in The Traveling Salesman Problem. Lawler, E.L., Lenstra, J.K., Rinnooy, A.H.G. and Shmoys D.B., (eds.), Wiley, Chichester, UK, pp. 37–85. Kim, K. H., & Park, Y.-M. (2004). A crane scheduling method for port container terminals. European Journal of Operational Research, 156(3), 752 - 768. Kurz, M., Askin, R. (2001). Heuristic scheduling of parallel machines with sequence dependent setup times. International Journal of Production Research 39, 3747–3769. Kutner, M. H., Nachtsheim, C. J., Neter, J., & Li, W. (2004). Applied Linear Statistical Models (5th ed.). McGraw-Hill/Irwin. Lam, K., & Xing, W. (1997), New trends in parallel machine scheduling. International Journal Operations Management, 17, 326–338. Lee W.C., Wu C.C., Chen P. (2006). A simulated annealing approach to makespan minimization on identical parallel machines. International Journal Advanced Manufacturing Technology, Vol.31, pp.328-334. Lenstra, J. K., & Kan, A. H. G. R. (1975). Some Simple Applications of the Travelling Salesman Problem. Operational Research Quarterly (1970-1977), 26(4), 717-733. Marsh JD, Montgomery DC. (1973). Optimal procedures for scheduling jobs with sequencedependent changeover times on parallel processors. AIIE Technical Papers, p. 279-286. McNaughton, R. (1959). Scheduling with deadlines and loss functions. Management Science 6, 112.
82 Aplicación de un algoritmo ACO al problema
|
|
Medina, J.C. (2010). Estudio comparativo de heurísticas constructivas y un algoritmo genético para el problema de máquinas paralelas idénticas con setup y minimización de makespan. Tesis de postgrado. Departamento de Ingeniería Industrial, Universidad de Concepción. Mendes, A.S., Müller, F.M., França, P.M., Moscato, P. (2002). Comparing meta-heuristic approaches for parallel machine scheduling problems. Production Planning y Control, 13(2), 143– 154. Min, L., Cheng, W. (1999). A genetic algorithm for minimizing the makespan in the case of scheduling identical parallel machines. Artificial Intelligence in Engineering Vol.I3, pp.399-403. Mokotoff, E. (2004). An exact algorithm for the identical parallel machine scheduling problem. European Journal of Operational Research, Vol.152, pp.758-769. Nessah, F., Yalaoui, F., & Chu, C. (2005). New heuristics for identical parallel machine scheduling with sequence-dependent setup times and dates. Proceedings of the international conference on industrial engineering and systems management (pp. 32–41). Marrakech, Morocco, May 16–19. Okonjo-Adigwe C. (1988). An effective method of balancing the workload amongst salesmen. Omega, 16(2), 159-163. Papadimitriou, C.H. and Steiglitz, K. (1998). Combinatorial Optimization: Algorithms and Complexity. Mineola, New York, NY. Pinedo, M. (2008). Scheduling: Theory, Algorithms, and Systems. Springer, Tercera Edición. Reinelt, G. (1994). The Traveling Salesman: Combinatorial Solutions for TSP Applications. Springer-Verlag, Berlin. Rocha, M., Gómez Ravetti, M., Mateus, G. R., Pardalos, P. M. (2007). Solving parallel machines scheduling problems with sequence-dependent setup times using variable neighborhood search. IMA Journal of Management Mathematics, 18, 101–115. Ryan, J. L., Bailey, T. G., Moore, J. T., & Carlton, W. B. (1998). Reactive Tabu Search in unmanned aerial reconnaissance simulations. Simulation Conference Proceedings, 1998. Winter (Vol. 1, pp. 873-879 vol.1). Salazar, E., & Ruiz, N. (2009). Modelo ACO para la recolección de residuos por contenedores. Ingeniare. Revista chilena de ingeniería, 17(2), 236-243. doi:10.4067/S0718-33052009000200012 Salazar, E. (2010). Planificación y Programación de la Producción. Apuntes de clases. Departamento de Ingeniería Industrial, Universidad de Concepción.
83 Aplicación de un algoritmo ACO al problema
|
|
Salazar, E. (2010). Programación de Sistemas de Producción con SPS_Optimizer. Revista ICHIO, 1(2), 33-46. Salazar, E., & Pavón, N. (2011). Aplicación de un algoritmo ACO al problema de taller de flujo de permutación con tiempos de preparación dependientes de la secuencia y minimización de makespan. Ingeniare. Revista chilena de ingeniería, 19(2), 253-264. Salazar, E., Sánchez, O. (Aceptada para publicación) Estrategia MMAS para minimización del makespan en la programación de una máquina con setup. Revista Ingeniería Industrial, Universidad del Biobío. Saleh, H. A., & Chelouah, R. (2004). The design of the global navigation satellite system surveying networks using genetic algorithms. Engineering Applications of Artificial Intelligence, 17(1), 111122. Sevkli, M., Uysal, H. (2009). A Modified Variable Neighborhood Search for Minimizing the Makespan on Identical Parallel Machines. International Conference on Computers y Industrial Engineering, 2009. CIE 2009. Stützle, T., & Hoos, H. H. (2000). MAX–MIN Ant System. Future Generation Computer Systems, 16(8), 889-914. Sumichrast, R., Baker, J. R. (1987). Scheduling parallel processors: an integer linear programming based heuristic for minimizing setup time. International Journal of Production Research 25, (5), 761 - 771. Svestka, J. A., & Huckfeldt, V. E. (1973). Computational Experience with an M-Salesman Traveling Salesman Algorithm. Management Science, 19(7), 790-799. Tahar, D. N., Yalaoui, F., Chu, C., Amodeo, L. (2006). A linear programming approach for identical parallel machine scheduling with job splitting and sequence-dependent setup times. International Journal of Production Economics, 99, 63–73. Tang, L., Liu, J., Rong, A., & Yang, Z. (2000). A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron & Steel Complex. European Journal of Operational Research, 124(2), 267-282. Van de Velde, S. L. (1993), Duality-based algorithms for scheduling unrelated parallel machines. ORSA Journal on Computing, Vol. 5, pp.192-205. Yang, W.-H. (1999). Survey of scheduling research involving setup times. International Journal of Systems Science, 30(2), 143-155.
84 Aplicación de un algoritmo ACO al problema
|
|
Yue, M. (1990). On the exact upper bound for the MULTIFIT processor algorithm. Annals of Operations Research, Vol. 24, pp.233-259. Zhang, T., Gruver, W. A., & Smith, M. H. (1999). Team scheduling by genetic search. Intelligent Processing and Manufacturing of Materials, 1999. Proceedings of the Second International Conference on (Vol. 2, pp. 839-844 vol.2). Zhong, Y., Liang, J., Gu, G., Zhang, R., & Yang, H. (2002). An implementation of evolutionary computation for path planning of cooperative mobile robots. Proceedings of the 4th World Congress on Intelligent Control and Automation, 2002 (Vol. 3, pp. 1798- 1802 vol.3). Zhu, X., & Wilhelm, W. E. (2006). Scheduling and lot sizing with sequence-dependent setup: A literature review. IIE Transactions, 38(11), 987-1007.
ANEXOS
86 Aplicación de un algoritmo ACO al problema
|
|
A1. Parámetros del Problema Ejemplo
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 11 88 39 17 35 64 20 30 35 70 54 81 82 23 99
18
6
12 22 24 15 15 27
5
21
-
7
16 16
25
26
29
-
6
16 12 26 14 10 11
26
-
19 29 20 14 26 18
27
19 21 26
4
21
-
2
28 17
18 26
9
5
1
16
21
7
28
27
7
4
27
8
7
4
14
28
8
13
22
3
26 25
23 29 20 28
-
2
3
12
3
16
24
7
20
-
3
7
28
18
9
7
25
21
-
1
24
20
5
22
13
-
17
1
5
24
1
25
-
10
24
9
29
27
1
-
11
26
3
24 28 18 18 23
2
3
19 16 17 18 14
9
22 30 22
17 17 24 19 23 14 18 14 26 25 19 12 29
21 29
16
1
29
18
16 22 16 18
18
1
24
9
3
14
26
3
1
4 21
9
22 24 27
9
8 26
16 27 29
-
26 20 12
13
23 30 18
-
2
15
2
7
8
27
9
6
16 24 26
11
6
27 26 26 15
7
2
12
13
10
6
-
28
14
8
4
21
9
18
13
-
5
12 28 26 23 16 22 20 24
7
13
1
23
21
14
-
8
8
23 22 17
22 28 20
87 Aplicación de un algoritmo ACO al problema
|
|
A2. Definición de Parámetros ACS Prueba Preliminar Las configuraciones se describen como:
2.5.85 2.10.90 2.15.95 3.5.85 3.10.90 3.15.95 5.5.85 5.10.90 5.15.95 1
5255
5292
5273
5271
5267
5278
5299
5297
5299
2
5623
5627
5644
5632
5622
5635
5651
5661
5649
3
5414
5417
5418
5413
5420
5460
5432
5447
5436
4
5135
5148
5169
5154
5168
5165
5156
5165
5176
5
5248
5273
5249
5263
5265
5269
5244
5287
5300
6
5010
5051
5045
5027
5040
5084
5048
5100
5067
7
5006
4993
5024
4993
5029
5030
5005
5015
5054
8
5861
5872
5894
5867
5876
5887
5897
5896
5917
9 5666 10 5487
5631
5671
5657
5648
5674
5681
5699
5685
5489
5491
5511
5486
5501
5503
5509
5506
2.5.90 2.5.95 2.10.85 2.10.95 2.15.85 2.15.90 3.5.90 3.5.95 3.10.85 1
5262
5274
5267
5257
5259
5256
5275
5281
5286
2
5632
5623
5617
5602
5620
5610
5621
5633
5630
3
5422
5412
5407
5402
5413
5395
5404
5439
5411
4
5155
5134
5133
5142
5150
5135
5147
5187
5157
5
5261
5259
5252
5248
5239
5246
5272
5309
5282
6
5045
5075
5016
5017
5014
4997
5050
5097
5039
7
5023
5048
5020
5000
5020
4996
5014
5040
5015
8
5866
5888
5866
5869
5879
5860
5906
5883
5849
9
5643
5671
5629
5668
5671
5630
5665
5691
5672
10 5488
5465
5487
5493
5479
5474
5480
5511
5461
3.10.95 3.15.85 3.15.90 5.5.90 5.5.95 5.10.85 5.10.95 5.15.85 5.15.90 1
5285
5271
5266
5295
5321
5286
5288
5300
5281
2
5652
5616
5631
5669
5671
5650
5675
5640
5660
3
5425
5425
5420
5475
5465
5472
5465
5419
5432
4
5174
5153
5156
5175
5184
5175
5175
5147
5151
5
5271
5259
5265
5306
5304
5279
5257
5254
5294
6
5049
5042
5036
5072
5064
5059
5088
5090
5079
7
5018
5008
5028
5046
5038
5038
5062
5030
5036
8
5869
5864
5884
5895
5895
5906
5924
5888
5895
9
5685
5659
5685
5703
5691
5679
5724
5686
5702
10
5512
5496
5483
5521
5508
5517
5496
5499
5497
88 Aplicación de un algoritmo ACO al problema
|
|
Promedios de Makespan 2.15.90 2.10.85 2.10.95 2.5.85 2.15.85 3.5.85 2.10.90 3.15.85 2.5.90 5359,9 5369,4 5369,8 5370,5 5374,4 5378,8 5379,3 5379,3 5379,7
3.10.85 3.10.90 3.5.90 2.5.95 3.15.90 2.15.95 5.5.85 3.10.95 5.15.85 5380,2 5382,1 5383,4 5384,9 5385,4
5387,8 5391,6
5394
5395,3
3.15.95 5.15.90 5.10.85 3.5.95 5.10.90 5.15.95 5.5.95 5.10.95 5.5.90 5398,3 5402,7 5406,1 5407,1 5407,6
5408,9 5414,1 5415,4 5415,7
Posiciones de las 27 Heurísticas en las 10 Instancias 2.5.85 2.10.90 2.15.95 3.5.85 3.10.90 3.15.95 5.5.85 5.10.90 5.15.95 1
1
21
11
9
7
14
24
23
24
2
8
10
18
13
7
16
21
24
19
3
9
10
11
7
13
23
18
22
20
4
3
8
20
12
19
17
14
17
25
5
4
19
6
13
14
16
2
22
24
6
2
16
11
6
9
23
13
27
19
7
6
1
15
1
17
18
5
9
26
8
3
10
18
7
11
15
23
22
26
9
9
3
11
6
5
15
17
24
18
10
8
11
12
23
7
18
19
22
20
2.5.90 2.5.95 2.10.85 2.10.95 2.15.85 2.15.90 3.5.90 3.5.95 3.10.85 1
5
12
7
3
4
2
13
15
18
2
13
8
4
1
5
2
6
15
11
3
15
6
4
2
7
1
3
21
5
4
13
2
1
5
9
3
6
27
16
5
12
10
7
4
1
3
18
27
21
6
11
21
4
5
3
1
15
26
8
7
14
25
12
4
12
3
8
23
9
8
5
16
5
8
12
2
24
13
1
9
4
11
1
10
11
2
8
22
14
10
10
2
8
13
4
3
5
23
1
89 Aplicación de un algoritmo ACO al problema
|
|
3.10.95 3.15.85 3.15.90 5.5.90 5.5.95 5.10.85 5.10.95 5.15.85 5.15.90 1
17
9
6
22
27
18
20
26
15
2
22
3
12
25
26
20
27
17
23
3
16
16
13
27
24
26
24
12
18
4
21
11
14
22
26
22
22
6
10
5
17
10
14
26
25
20
9
8
23
6
14
10
7
20
18
17
24
25
22
7
11
7
16
24
21
21
27
18
20
8
8
4
14
19
19
24
27
16
19
9
18
7
18
26
22
16
27
21
25
10
25
14
6
27
21
26
14
17
16
Promedio y Desviación Estándar de las Posiciones 2.15.90 2.5.85 2.10.85 2.10.95 2.15.85 3.15.85 3.5.85 2.5.90 3.10.85 Promedio
2,2
5,3
Desviación est. 0,7888 3,0569
5,3
5,5
6,8
3,335
3,7491
7,306
9,1
9,7
10,2
10,4
4,0675 5,9824 4,077 6,8993
3.5.90 2.10.90 3.10.90 2.5.95 3.15.90 2.15.95 5.5.85 5.15.85 3.10.95 Promedio
10,6
10,9
10,9
11,3
Desviación est. 6,7032 6,3675 4,7246 7,5873
12 3,171
13,3
15,6
16,6
4,3218 7,306 6,5693
3.15.95 5.15.90 5.10.85 5.10.90 3.5.95 5.15.95 5.10.95 5.5.95 Promedio
17,5
Desviación est.
3,171
19,1
21
21,2
21,2
4,5326 3,5277 4,5326 5,1812
22,1 3,178
22,1
22,9
16,9 5,087
5.5.90 23,8
6,1905 3,1429 2,8983
90
|
Aplicación de un algoritmo ACO al problema
|
Makespan de las cinco mejores combinaciones (cinco instancias) Parámetros
1
2
3
4
5
Promedio Desv. Est. 5035,6
3,97492138
2.5.85
5037 5029 5035 5038 5039 5065 5020 5042 5036 5037
5040
16,2326831
2.10.85
5055 5032 5036 5045 5050
5043,6
9,55510335
2.10.95
5069 5035 5057 5036 5053
5050
14,4913767
2.15.85
5051 5031 5047 5055 5029
5042,6
11,8659176
2.15.90
Parámetros
1
2
3
4
5
Promedio Desv. Est.
2.15.90
4881 4869 4882 4893 4889
4882,8
9,1760558
2.5.85
4883 4915 4885 4911 4888
4896,4
15,323185
2.10.85
4880 4888 4891 4896 4872
4885,4
9,47628619
2.10.95
4887 4907 4886 4925 4910
4903
16,5378354
2.15.85
4900 4893 4905 4882 4890
4894
8,91627725
Parámetros
1
2
3
4
5
Promedio Desv. Est.
2.15.90
5553 5547 5555 5558 5549
5552,4
4,44971909
2.5.85
5562 5551 5553 5564 5561
5558,2
5,80517011
2.10.85
5572 5549 5574 5560 5574
5565,8
11,0544109
2.10.95
5585 5577 5548 5559 5568 5547 5552 5551 5557 5560
5567,4
14,5705182
5553,4
5,12835256
2.15.85
Parámetros
1
2
3
4
5
Promedio Desv. Est.
2.15.90
5410 5433 5429 5401 5419
5418,4
13,2211951
2.5.85
5417 5438 5406 5433 5443
5427,4
15,4369686
2.10.85
5438 5421 5451 5415 5411
5427,2
16,8285472
2.10.95
5442 5418 5425 5441 5420
5429,2
11,5195486
2.15.85
5422 5421 5424 5419 5434
5424
5,87367006
Parámetros
1
2
3
4
5
Promedio Desv. Est.
2.15.90
5179 5199 5205 5206 5191
5196
11,2249722
2.5.85
5196 5189 5197 5216 5210
5201,6
11,058933
2.10.85
5189 5200 5201 5209 5218
5203,4
10,8305125
2.10.95
5224 5195 5199 5205 5240
5212,6
18,928814
2.15.85
5210 5191 5207 5204 5196
5201,6
7,8930349
91 Aplicación de un algoritmo ACO al problema
|
|
Posiciones de los makespan en las cinco instancias Parámetros 1 2 3
4
5 Promedio Desv. Est. 9,2
5,06951674
2.5.85
11 2 6 13 14 24 1 15 8 11
11,8
8,5264295
2.10.85
21 5 8 16 18
13,6
6,80441033
2.10.95
25 6 23 8 20
16,4
8,79204186
2.15.85
19 4 17 21 2
12,6
8,90505474
2.15.90
Parámetros 1
2
3
1
4
5 Promedio Desv. Est.
2.15.90
4
5 16 13
7,8
6,37965516
2.5.85
7 24 8 23 11
14,6
8,2643814
2.10.85
3 11 15 18 2
9,8
7,12039325
2.10.95
10 21 9 25 22
17,4
7,36885337
2.15.85
19 16 20 5 14
14,8
5,9749477
Parámetros
1
2
2.15.90
9
1 11 13 4
2.5.85
18 6
3
4
5 Promedio
Desv. Est.
7,6
4,97995984
9 19 17
13,8
5,89067059
2.10.85
21 4 22 15 22
16,8
7,72657751
2.10.95
25 24 3 14 20
17,2
9,03880523
2.15.85
1
8
6 12 15
8,4
5,41294744
Parámetros 1
2
3
4
5 Promedio Desv. Est. 1
9
7,31436942
13,8
9,39148551
13
9,246621
23 7 15 22 10
15,4
7,09224929
13 11 14 8 19
13
4,0620192
2.15.90
3 17 16 8
2.5.85
6 20 2 17 24
2.10.85
20 11 25 5
2.10.95 2.15.85
Parámetros 1
2
3
4
4
5 Promedio
Desv. Est.
2.15.90
1 10 15 17 4
9,4
6,87749955
2.5.85
7
12
8,63133825
2
9 22 20
2.10.85
2 12 13 19 23
13,8
7,98122798
2.10.95
24 6 10 15 25
16
8,39642781
2.15.85
20 4 18 14 7
12,6
6,91375441
92
|
Aplicación de un algoritmo ACO al problema
|
Convergencia de la heuristica ACS Instancia 1 5175 5125 5075 5025 0
500
1000
1500 1
2000
2500
2
3
2000
2500
2
3
2000
2500
2
3
3000 4
3500
4000
4500
5000
4000
4500
5000
4000
4500
5000
5
Instancia 2 5020 4970 4920 4870 0
500
1000
1500 1
3000 4
3500 5
Instancia 3 5690 5640 5590 5540 0
500
1000
1500 1
3000 4
3500 5
93
|
Aplicación de un algoritmo ACO al problema
|
Instancia 4 5600 5550 5500 5450 5400 0
500
1000
1500 1
2000
2500
2
3
2000
2500
2
3
3000 4
3500
4000
4500
5000
4000
4500
5000
5
Instancia 5
5370 5320 5270 5220 5170 0
500
1000
1500 1
3000 4
3500 5
94 Aplicación de un algoritmo ACO al problema
|
|
A3. Diferencias de Métodos Heurísticos Comparados con ACS sin el proceso de revisión.
Nivel de Setup Alto m = 3, n = 30 Makespan
Diferencia porcentual
LPT xLPT MC MV ACS(S)
LPT
xLPT
MC
Diferencia en segundos MV
LPT
xLPT
MC
MV
1
921
964
737 661
647
42,35% 49,00% 13,91%
2,16%
274
317
90
14
2
948
905
754 720
647
46,52% 39,88% 16,54% 11,28%
301
258
107
73
3
923
902
725 686
636
45,13% 41,82% 13,99%
7,86%
287
266
89
50
4
887
880
682 662
602
47,34% 46,18% 13,29%
9,97%
285
278
80
60
5
958
975
703 663
627
52,79% 55,50% 12,12%
5,74%
331
348
76
36
6
982
1032 810 767
701
40,09% 47,22% 15,55%
9,42%
281
331
109
66
7
845
893
692 579
591
42,98% 51,10% 17,09% -2,03%
254
302
101
-12
8
841
899
609 548
530
58,68% 69,62% 14,91%
3,40%
311
369
79
18
9
850
950
672 676
566
50,18% 67,84% 18,73% 19,43%
284
384
106
110
10
970
919
686 602
610
59,02% 50,66% 12,46% -1,31%
360
309
76
-8
11
820
869
724 672
653
25,57% 33,08% 10,87%
2,91%
167
216
71
19
12
987
1013 760 664
609
62,07% 66,34% 24,79%
9,03%
378
404
151
55
13
814
874
600 564
535
52,15% 63,36% 12,15%
5,42%
279
339
65
29
14
827
862
720 629
638
29,62% 35,11% 12,85% -1,41%
189
224
82
-9
15
772
872
609 526
531
45,39% 64,22% 14,69% -0,94%
241
341
78
-5
16 1014
914
777 749
699
45,06% 30,76% 11,16%
7,15%
315
215
78
50
17
858
905
672 603
585
46,67% 54,70% 14,87%
3,08%
273
320
87
18
18
792
825
672 644
580
36,55% 42,24% 15,86% 11,03%
212
245
92
64
19 1065
992
716 697
689
54,57% 43,98%
3,92%
1,16%
376
303
27
8
20
845
637 561
538
64,68% 57,06% 18,40%
4,28%
348
307
99
23
47,37% 50,48% 14,41%
5,38%
886
Promedio diferencias
287,3 303,8 87,15 32,95
95 Aplicación de un algoritmo ACO al problema
|
|
m = 5, n = 50 Makespan
Diferencia porcentual
LPT xLPT MC MV ACS(S)
LPT
xLPT
MC
Diferencia en segundos MV
LPT
xLPT MC
MV
1
814
890
706 643
603
34,99% 47,60% 17,08% 6,63%
211
287
103
40
2
774
728
669 630
573
35,08% 27,05% 16,75% 9,95%
201
155
96
57
3
871
869
738 681
661
31,77% 31,47% 11,65% 3,03%
210
208
77
20
4
778
795
664 588
571
36,25% 39,23% 16,29% 2,98%
207
224
93
17
5
949
847
714 637
629
50,87% 34,66% 13,51% 1,27%
320
218
85
8
6
815
859
684 620
586
39,08% 46,59% 16,72% 5,80%
229
273
98
34
7
827
847
699 652
621
33,17% 36,39% 12,56% 4,99%
206
226
78
31
8
901
864
729 645
658
36,93% 31,31% 10,79% -1,98%
243
206
71
-13
9
-26
809
796
713 611
637
27,00% 24,96% 11,93% -4,08%
172
159
76
10 854
800
734 655
615
38,86% 30,08% 19,35% 6,50%
239
185
119
40
11 855
837
710 597
626
36,58% 33,71% 13,42% -4,63%
229
211
84
-29
12 868
901
755 660
659
31,71% 36,72% 14,57% 0,15%
209
242
96
1
13 850
836
728 645
630
34,92% 32,70% 15,56% 2,38%
220
206
98
15
14 826
819
701 608
614
34,53% 33,39% 14,17% -0,98%
212
205
87
-6
15 790
823
655 566
563
40,32% 46,18% 16,34% 0,53%
227
260
92
3
16 678
659
609 543
525
29,14% 25,52% 16,00% 3,43%
153
134
84
18
17 806
862
702 632
629
28,14% 37,04% 11,61% 0,48%
177
233
73
3
18 873
811
708 641
629
38,79% 28,93% 12,56% 1,91%
244
182
79
12
19 867
869
762 686
646
34,21% 34,52% 17,96% 6,19%
221
223
116
40
20 781
806
660 597
587
33,05% 37,31% 12,44% 1,70%
194
219
73
10
Promedio diferencias
35,27% 34,77% 14,56% 2,31%
216,2 212,8 88,9 13,75
96 Aplicación de un algoritmo ACO al problema
|
|
m = 10, n = 100 Makespan
Diferencia porcentual
LPT xLPT MC MV ACS(S)
LPT
xLPT
Diferencia en segundos
MC
MV
LPT
xLPT
MC
MV
8,16%
1
794
772
689 642
637
24,65% 21,19%
0,78%
157
135
52
5
2
800
788
733 695
622
28,62% 26,69% 17,85% 11,74%
178
166
111
73
3
754
757
699 648
633
19,12% 19,59% 10,43%
2,37%
121
124
66
15
4
747
709
682 633
624
19,71% 13,62%
9,29%
1,44%
123
85
58
9
5
725
767
692 642
620
16,94% 23,71% 11,61%
3,55%
105
147
72
22
6
733
743
669 601
592
23,82% 25,51% 13,01%
1,52%
141
151
77
9
7
718
699
657 609
578
24,22% 20,93% 13,67%
5,36%
140
121
79
31
8
805
846
758 682
653
23,28% 29,56% 16,08%
4,44%
152
193
105
29
9
801
775
732 659
641
24,96% 20,90% 14,20%
2,81%
160
134
91
18
10 752
773
701 663
632
18,99% 22,31% 10,92%
4,91%
120
141
69
31
11 745
730
659 618
576
29,34% 26,74% 14,41%
7,29%
169
154
83
42
12 678
726
648 567
595
13,95% 22,02%
8,91%
-4,71%
83
131
53
-28
13 768
788
707 647
655
17,25% 20,31%
7,94%
-1,22%
113
133
52
-8
14 745
744
715 654
601
23,96% 23,79% 18,97%
8,82%
144
143
114
53
15 757
733
684 615
579
30,74% 26,60% 18,13%
6,22%
178
154
105
36
16 763
746
684 605
606
25,91% 23,10% 12,87% -0,17%
157
140
78
-1
17 730
749
680 606
615
18,70% 21,79% 10,57% -1,46%
115
134
65
-9
18 746
767
685 628
586
27,30% 30,89% 16,89%
7,17%
160
181
99
42
19 732
755
699 636
597
22,61% 26,47% 17,09%
6,53%
135
158
102
39
20 786
773
691 645
597
31,66% 29,48% 15,75%
8,04%
189
176
94
48
23,29% 23,76% 13,34%
3,77%
142 145,05 81,25 22,8
Promedio diferencias
97 Aplicación de un algoritmo ACO al problema
|
|
Nivel de Setup Bajo m = 3, n = 30 Makespan
Diferencia porcentual
LPT xLPT MC MV ACS(S)
LPT
xLPT
1
673
639
623 612
581
15,83%
9,98%
7,23% 5,34%
92
58
42
31
2
669
654
610 614
576
16,15% 13,54% 5,90% 6,60%
93
78
34
38
3
640
615
597 587
546
17,22% 12,64% 9,34% 7,51%
94
69
51
41
4
563
548
489 465
454
24,01% 20,70% 7,71% 2,42%
109
94
35
11
5
607
592
538 528
496
22,38% 19,35% 8,47% 6,45%
111
96
42
32
6
625
608
557 530
518
20,66% 17,37% 7,53% 2,32%
107
90
39
12
7
571
596
522 520
484
17,98% 23,14% 7,85% 7,44%
87
112
38
36
8
550
578
497 492
467
17,77% 23,77% 6,42% 5,35%
83
111
30
25
9
616
645
572 568
524
17,56% 23,09% 9,16% 8,40%
92
121
48
44
10 645
644
578 572
549
17,49% 17,30% 5,28% 4,19%
96
95
29
23
11 654
656
607 575
564
15,96% 16,31% 7,62% 1,95%
90
92
43
11
12 523
519
482 479
440
18,86% 17,95% 9,55% 8,86%
83
79
42
39
13 712
724
655 650
626
13,74% 15,65% 4,63% 3,83%
86
98
29
24
14 678
662
607 589
593
14,33% 11,64% 2,36% -0,67%
85
69
14
-4
15 686
712
644 618
595
15,29% 19,66% 8,24% 3,87%
91
117
49
23
16 627
640
575 541
545
15,05% 17,43% 5,50% -0,73%
82
95
30
-4
17 692
701
636 619
601
15,14% 16,64% 5,82% 3,00%
91
100
35
18
18 628
632
581 564
545
15,23% 15,96% 6,61% 3,49%
83
87
36
19
19 567
589
510 503
480
18,13% 22,71% 6,25% 4,79%
87
109
30
23
20 731
729
685 666
657
11,26% 10,96% 4,26% 1,37%
74
72
28
9
17,00% 17,29% 6,79% 4,29%
90,8
92,1
Promedio diferencias
MC
Diferencia en segundos MV
LPT xLPT MC
MV
36,2 22,55
98 Aplicación de un algoritmo ACO al problema
|
|
m = 5, n = 50 Makespan
Diferencia porcentual
Diferencia en segundos
LPT
xLPT
MC
MV
ACS(S)
LPT
xLPT
MC
MV
LPT
xLPT
MC
MV
1
734
732
695
682
641
14,51%
14,20%
8,42%
6,40%
93
91
54
41
2
613
617
590
565
553
10,85%
11,57%
6,69%
2,17%
60
64
37
12
3
680
672
653
626
611
11,29%
9,98%
6,87%
2,45%
69
61
42
15
4
665
664
628
612
576
15,45%
15,28%
9,03%
6,25%
89
88
52
36
5
653
645
620
626
569
14,76%
13,36%
8,96%
10,02%
84
76
51
57
6
664
669
632
605
588
12,93%
13,78%
7,48%
2,89%
76
81
44
17
7
622
646
596
591
570
9,12%
13,33%
4,56%
3,68%
52
76
26
21
8
590
585
565
537
531
11,11%
10,17%
6,40%
1,13%
59
54
34
6
9
660
666
628
607
587
12,44%
13,46%
6,98%
3,41%
73
79
41
20
10
600
589
550
559
536
11,94%
9,89%
2,61%
4,29%
64
53
14
23
11
599
591
567
565
528
13,45%
11,93%
7,39%
7,01%
71
63
39
37
12
664
666
637
629
590
12,54%
12,88%
7,97%
6,61%
74
76
47
39
13
643
650
606
602
581
10,67%
11,88%
4,30%
3,61%
62
69
25
21
14
651
656
614
576
570
14,21%
15,09%
7,72%
1,05%
81
86
44
6
15
627
634
598
568
556
12,77%
14,03%
7,55%
2,16%
71
78
42
12
16
630
631
609
568
555
13,51%
13,69%
9,73%
2,34%
75
76
54
13
17
633
635
607
612
574
10,28%
10,63%
5,75%
6,62%
59
61
33
38
18
678
672
674
662
646
4,95%
4,02%
4,33%
2,48%
32
26
28
16
19
555
542
529
523
522
6,32%
3,83%
1,34%
0,19%
33
20
7
1
20
623
624
598
598
570
9,30%
9,47%
4,91%
4,91%
53
54
28
28
11,62%
11,62%
6,45%
3,98%
66,5
66,6
37,1
22,95
Promedio diferencias
99 Aplicación de un algoritmo ACO al problema
|
|
m = 10, n = 100 Makespan
Diferencia porcentual
LPT xLPT MC MV ACS(S)
LPT
xLPT
MC
Diferencia en segundos MV
LPT xLPT
MC
MV
1
601
601
593 583
547
9,87%
9,87%
8,41% 6,58%
54
54
46
36
2
626
638
622 594
585
7,01%
9,06%
6,32% 1,54%
41
53
37
9
3
642
643
641 628
603
6,47%
6,63%
6,30% 4,15%
39
40
38
25
4
623
634
617 582
580
7,41%
9,31%
6,38% 0,34%
43
54
37
2
5
563
571
557 545
542
3,87%
5,35%
2,77% 0,55%
21
29
15
3
6
614
605
608 601
568
8,10%
6,51%
7,04% 5,81%
46
37
40
33
7
652
659
657 645
613
6,36%
7,50%
7,18% 5,22%
39
46
44
32
8
568
575
570 566
529
7,37%
8,70%
7,75% 6,99%
39
46
41
37
9
609
606
591 593
573
6,28%
5,76%
3,14% 3,49%
36
33
18
20
10 565
554
557 532
516
9,50%
7,36%
7,95% 3,10%
49
38
41
16
11 624
632
630 620
605
3,14%
4,46%
4,13% 2,48%
19
27
25
15
12 646
632
622 616
586
10,24%
7,85%
6,14% 5,12%
60
46
36
30
13 551
559
558 543
521
5,76%
7,29%
7,10% 4,22%
30
38
37
22
14 620
623
607 603
568
9,15%
9,68%
6,87% 6,16%
52
55
39
35
15 585
589
577 555
530
10,38% 11,13% 8,87% 4,72%
55
59
47
25
16 602
603
595 590
559
7,69%
7,87%
6,44% 5,55%
43
44
36
31
17 667
662
664 653
629
6,04%
5,25%
5,56% 3,82%
38
33
35
24
18 591
590
589 567
566
4,42%
4,24%
4,06% 0,18%
25
24
23
1
19 541
550
546 549
517
4,64%
6,38%
5,61% 6,19%
24
33
29
32
20 604
598
600 592
569
6,15%
5,10%
5,45% 4,04%
35
29
31
23
6,99%
7,27%
6,17% 4,01%
39,4
40,9
Promedio diferencias
34,75 22,55
100 Aplicación de un algoritmo ACO al problema
|
|
A4. Diferencias Generadas por el Proceso de Revisión de ACS Nivel de Setup Alto n=30 ACS sin ACS con
Dif. %
n=50 Dif.
ACS sin 603
ACS con 589
Dif. %
n=100 Dif. 14
ACS sin 637
ACS con 594
7,24%
622
Dif. %
Dif.
1
647
597
2
647
647
0,00%
0
573
549
4,37%
24
622
0,00%
0
3
636
594
7,07%
42
661
623
6,10%
38
633
592
6,93%
41
4
602
564
6,74%
38
571
527
8,35%
44
624
577
8,15%
47
5
627
596
5,20%
31
629
602
4,49%
27
620
583
6,35%
37
6
701
701
0,00%
0
586
557
5,21%
29
592
576
2,78%
16
7
591
556
6,29%
35
621
570
8,95%
51
578
566
2,12%
12
8
530
530
0,00%
0
658
621
5,96%
37
653
644
1,40%
9
9
2,35%
13
637
585
8,89%
52
641
612
4,74%
29
8,38%
50
2,38%
43
566
553
10
610
569
7,21%
41
615
612
0,49%
3
632
601
5,16%
31
11
653
593
10,12%
60
626
515
21,55%
111
576
555
3,78%
21
12
609
594
2,53%
15
659
619
6,46%
40
595
540
10,19%
55
13
11,46%
55
630
617
2,11%
13
655
612
7,03%
43
535
480
14
638
589
8,32%
49
614
558
10,04%
56
601
585
2,74%
16
15
531
497
6,84%
34
563
535
5,23%
28
579
576
0,52%
3
16
699
657
6,39%
42
525
498
5,42%
27
606
595
1,85%
11
17
3,91%
22
629
574
9,58%
55
615
585
5,13%
30
585
563
18
580
569
1,93%
11
629
595
5,71%
34
586
584
0,34%
2
19
689
603
14,26%
86
646
639
1,10%
7
597
597
0,00%
0
20
538
538
0,00%
0
587
560
4,82%
27
597
584
2,23%
13
5,45%
31,2
6,36%
35,85
3,93%
22,95
Promedio diferencias
101 Aplicación de un algoritmo ACO al problema
|
|
Nivel de Setup Bajo
n=30
n=50
Dif.
581
569
2,11%
12
2
576
575
0,17%
1
553
535
3,36%
18
585
585
0,00%
0
3
546
543
0,55%
3
611
601
1,66%
10
603
596
1,17%
7
4
454
444
2,25%
10
576
573
0,52%
3
580
569
1,93%
11
5
496
496
0,00%
0
569
569
0,00%
0
542
530
2,26%
12
6
518
518
0,00%
0
588
586
0,34%
2
568
565
0,53%
3
7
484
484
0,00%
0
570
553
3,07%
17
613
612
0,16%
1
8
467
460
1,52%
7
531
518
2,51%
13
529
528
0,19%
1
9
524
524
0,00%
0
587
578
1,56%
9
573
552
3,80%
21
10
549
536
2,43%
13
536
515
4,08%
21
516
516
0,00%
0
11
564
561
0,53%
3
528
528
0,00%
0
605
591
2,37%
14
12
440
438
0,46%
2
590
577
2,25%
13
586
586
0,00%
0
13
626
608
2,96%
18
581
562
3,38%
19
521
508
2,56%
13
14
593
567
4,59%
26
570
564
1,06%
6
568
565
0,53%
3
15
595
593
0,34%
2
556
556
0,00%
0
530
528
0,38%
2
16
545
530
2,83%
15
555
547
1,46%
8
559
551
1,45%
8
17
601
592
1,52%
9
574
554
3,61%
20
629
618
1,78%
11
18
545
545
0,00%
0
646
619
4,36%
27
566
545
3,85%
21
19
480
469
2,35%
11
522
485
7,63%
37
517
513
0,78%
4
20
657
637
3,14%
20
570
554
2,89%
16
569
549
3,64%
20
1,39%
7,6
1,37%
7,6
Promedio diferencias
0,00%
n=100
1
ACS sin ACS con Dif. % Dif.
ACS con 641
Dif.
ACS sin 641
Dif. %
0
ACS sin 547
ACS con 547
0,00%
0
2,19% 11,95
Dif. %
102
|
Aplicación de un algoritmo ACO al problema
|
A5. Análisis de Varianza Nivel de Setup Alto m = 3, n = 30 Tabla ANOVA Fuente Entre grupos Intra grupos Total (Corr.)
Suma de Cuadrados 1,8402E6 379705, 2,21991E6
Gl Cuadrado Medio Razón-F Valor-P 4 460050, 115,10 0,0000 95 3996,9 99
Pruebas de Múltiples Rangos Método: 95,0 porcentaje Tukey HSD
ACS MV MC LPT xLPT
Casos 20 20 20 20 20
Media Grupos Homogéneos 579,5 X 643,65 X 697,85 X 898,0 X 914,5 X
Contraste Sig. Diferencia +/- Límites LPT - xLPT -16,5 55,5938 LPT - MV * 254,35 55,5938 LPT - MC * 200,15 55,5938 LPT - ACS * 318,5 55,5938 xLPT - MV * 270,85 55,5938 xLPT - MC * 216,65 55,5938 xLPT - ACS * 335,0 55,5938 MV - MC -54,2 55,5938 MV - ACS * 64,15 55,5938 MC - ACS * 118,35 55,5938 * indica una diferencia significativa.
Prueba de Kruskal-Wallis Tamaño de Muestra Rango Promedio LPT 20 78,725 xLPT 20 82,125 MV 20 31,025 MC 20 44,575 ACS 20 16,05 Estadístico = 80,7532 Valor-P = 0
103
|
Aplicación de un algoritmo ACO al problema
|
m = 5, n = 50 Tabla ANOVA Fuente Entre grupos Intra grupos Total (Corr.)
Suma de Cuadrados 1,0448E6 201446, 1,24625E6
Gl Cuadrado Medio Razón-F Valor-P 4 261201, 123,18 0,0000 95 2120,49 99
Pruebas de Múltiples Rangos Método: 95,0 porcentaje Tukey HSD
ACS MV MC xLPT LPT
Casos 20 20 20 20 20
Media Grupos Homogéneos 577,25 X 626,85 X 702,0 X 825,9 X 829,3 X
Contraste Sig. Diferencia +/- Límites LPT - xLPT 3,4 40,4932 LPT - MV * 202,45 40,4932 LPT - MC * 127,3 40,4932 LPT - ACS * 252,05 40,4932 xLPT - MV * 199,05 40,4932 xLPT - MC * 123,9 40,4932 xLPT - ACS * 248,65 40,4932 MV - MC * -75,15 40,4932 MV - ACS * 49,6 40,4932 MC - ACS * 124,75 40,4932 * indica una diferencia significativa.
Prueba de Kruskal-Wallis Tamaño de Muestra Rango Promedio LPT 20 79,6 xLPT 20 79,225 MV 20 28,55 MC 20 50,875 ACS 20 14,25 Estadístico = 82,411 Valor-P = 0
104
|
Aplicación de un algoritmo ACO al problema
|
m = 10, n = 100 Tabla ANOVA Fuente Entre grupos Intra grupos Total (Corr.)
Suma de Cuadrados 434894, 79987,9 514882,
Gl Cuadrado Medio Razón-F Valor-P 4 108724, 129,13 0,0000 95 841,978 99
Pruebas de Múltiples Rangos Método: 95,0 porcentaje Tukey HSD
ACS MV MC LPT xLPT
Casos 20 20 20 20 20
Media Grupos Homogéneos 589,0 X 634,75 X 693,2 X 753,95 X 757,0 X
Contraste Sig. Diferencia +/- Límites LPT - xLPT -3,05 25,5161 LPT - MV * 119,2 25,5161 LPT - MC * 60,75 25,5161 LPT - ACS * 164,95 25,5161 xLPT - MV * 122,25 25,5161 xLPT - MC * 63,8 25,5161 xLPT - ACS * 168,0 25,5161 MV - MC * -58,45 25,5161 MV - ACS * 45,75 25,5161 MC - ACS * 104,2 25,5161 * indica una diferencia significativa.
Prueba de Kruskal-Wallis Tamaño de Muestra Rango Promedio LPT 20 78,15 xLPT 20 79,725 MV 20 29,7 MC 20 52,3 ACS 20 12,625 Estadístico = 82,9203 Valor-P = 0
105
|
Aplicación de un algoritmo ACO al problema
|
Nivel de Setup Bajo m = 3, n = 30 Tabla ANOVA Fuente Entre grupos Intra grupos Total (Corr.)
Suma de Cuadrados 152957, 304219, 457176,
Gl Cuadrado Medio Razón-F Valor-P 4 38239,4 11,94 0,0000 95 3202,3 99
Pruebas de Múltiples Rangos Método: 95,0 porcentaje Tukey HSD
ACS MV MC LPT xLPT
Casos 20 20 20 20 20
Media 534,45 564,6 578,25 632,85 634,15
Grupos Homogéneos X X X X X
Contraste Sig. Diferencia +/- Límites LPT - xLPT -1,3 49,7618 LPT - MV * 68,25 49,7618 LPT - MC * 54,6 49,7618 LPT - ACS * 98,4 49,7618 xLPT - MV * 69,55 49,7618 xLPT - MC * 55,9 49,7618 xLPT - ACS * 99,7 49,7618 MV - MC -13,65 49,7618 MV - ACS 30,15 49,7618 MC - ACS 43,8 49,7618 * indica una diferencia significativa.
Prueba de Kruskal-Wallis Tamaño de Muestra Rango Promedio LPT 20 69,125 xLPT 20 69,825 MV 20 39,975 MC 20 45,925 ACS 20 27,65 Estadístico = 32,6576 Valor-P = 0,00000140367
106
|
Aplicación de un algoritmo ACO al problema
|
m = 5, n = 50 Tabla ANOVA Fuente Entre grupos Intra grupos Total (Corr.)
Suma de Cuadrados 86740,7 145473, 232214,
Gl Cuadrado Medio Razón-F Valor-P 4 21685,2 14,16 0,0000 95 1531,29 99
Pruebas de Múltiples Rangos Método: 95,0 porcentaje Tukey HSD
ACS MV MC LPT xLPT
Casos 20 20 20 20 20
Media 560,75 595,65 609,8 639,2 639,3
Grupos Homogéneos X X XX X X
Contraste Sig. Diferencia +/- Límites LPT - xLPT -0,1 34,4107 LPT - MV * 43,55 34,4107 LPT - MC 29,4 34,4107 LPT - ACS * 78,45 34,4107 xLPT - MV * 43,65 34,4107 xLPT - MC 29,5 34,4107 xLPT - ACS * 78,55 34,4107 MV - MC -14,15 34,4107 MV - ACS * 34,9 34,4107 MC - ACS * 49,05 34,4107 * indica una diferencia significativa.
Prueba de Kruskal-Wallis Tamaño de Muestra Rango Promedio LPT 20 68,65 xLPT 20 69,425 MV 20 41,85 MC 20 50,675 ACS 20 21,9 Estadístico = 37,559 Valor-P = 1,38158E-7
107
|
Aplicación de un algoritmo ACO al problema
|
m = 10, n = 100 Tabla ANOVA Fuente Entre grupos Intra grupos Total (Corr.)
Suma de Cuadrados 32379,9 108007, 140387,
Gl Cuadrado Medio Razón-F Valor-P 4 8094,98 7,12 0,0000 95 1136,92 99
Pruebas de Múltiples Rangos Método: 95,0 porcentaje Tukey HSD
ACS MV MC LPT xLPT
Casos 20 20 20 20 20
Media Grupos Homogéneos 557,7 X 587,85 X 600,05 X 604,7 X 606,2 X
Contraste Sig. Diferencia +/- Límites LPT - xLPT -1,5 29,6503 LPT - MV 16,85 29,6503 LPT - MC 4,65 29,6503 LPT - ACS * 47,0 29,6503 xLPT - MV 18,35 29,6503 xLPT - MC 6,15 29,6503 xLPT - ACS * 48,5 29,6503 MV - MC -12,2 29,6503 MV - ACS * 30,15 29,6503 MC - ACS * 42,35 29,6503 * indica una diferencia significativa.
Prueba de Kruskal-Wallis Tamaño de Muestra Rango Promedio LPT 20 60,95 xLPT 20 62,05 MV 20 46,95 MC 20 56,85 ACS 20 25,7 Estadístico = 21,6407 Valor-P = 0,000236274
108 Aplicación de un algoritmo ACO al problema
|
|
A6. Verificación de supuestos de ANOVA Nivel de Setup Alto m = 3, n = 30 Prueba Chi-Cuadrado de Independencia Prueba Estadístico Gl Valor-P Chi-Cuadrada 88,739 76 0,6693
Pruebas Chi-Cuadrado de Normalidad Heurística LPT xLPT MV MC ACS
Estadístico 4,7 9,9 6,0 13,8 13,8
Valor-P 0,910297 0,44931 0,815263 0,182311 0,182311
Verificación de Varianza Prueba Valor-P Levene's 1,81737 0,131841
Comparación ResLPT / ResxLPT ResLPT / ResMV ResLPT / ResMC ResLPT / ResACS ResxLPT / ResMV ResxLPT / ResMC ResxLPT / ResACS ResMV / ResMC ResMV / ResACS ResMC / ResACS
Sigma1 80,8768 80,8768 80,8768 80,8768 56,3116 56,3116 56,3116 66,4936 66,4936 56,7332
Sigma2 56,3116 66,4936 56,7332 51,3066 66,4936 56,7332 51,3066 56,7332 51,3066 51,3066
F-Ratio 2,06277 1,47941 2,03223 2,48485 0,717194 0,985192 1,20462 1,37368 1,67963 1,22272
P-Valor 0,1233 0,4010 0,1310 0,0541 0,4756 0,9744 0,6890 0,4956 0,2673 0,6656
m = 5, n = 50 Prueba Chi-Cuadrado de Independencia Prueba Estadístico Gl Valor-P Chi-Cuadrada 57,818 76 0,9402
109 Aplicación de un algoritmo ACO al problema
|
|
Pruebas Chi-Cuadrado de Normalidad Heurística LPT xLPT MV MC ACS
Estadístico 8,6 7,3 7,3 9,9 4,7
Valor-P 0,570438 0,696852 0,696852 0,44931 0,910297
Verificación de Varianza Prueba Valor-P Levene's 0,949777 0,438888 Comparación ResLPT / ResxLPT ResLPT / ResMV ResLPT / ResMC ResLPT / ResACS ResxLPT / ResMV ResxLPT / ResMC ResxLPT / ResACS ResMV / ResMC ResMV / ResACS ResMC / ResACS
Sigma1 56,9414 56,9414 56,9414 56,9414 55,755 55,755 55,755 36,1958 36,1958 36,995
Sigma2 55,755 36,1958 36,995 39,6576 36,1958 36,995 39,6576 36,995 39,6576 39,6576
F-Ratio 1,04301 2,4748 2,36903 2,0616 2,37275 2,27134 1,97658 0,957258 0,833035 0,87023
P-Valor 0,9278 0,0552 0,0676 0,1236 0,0671 0,0817 0,1465 0,9251 0,6946 0,7650
m = 10, n = 100 Prueba Chi-Cuadrado de Independencia Prueba Estadístico Gl Valor-P Chi-Cuadrada 19,458 76 1,0000
Pruebas Chi-Cuadrado de Normalidad Heurística LPT xLPT MV MC ACS
Estadístico 11,2 17,7 7,3 16,4 17,7
Valor-P 0,34215 0,0602401 0,696852 0,0887402 0,0602401
Verificación de Varianza Prueba Valor-P Levene's 0,580127 0,677752
110 Aplicación de un algoritmo ACO al problema
|
Comparación ResLPT / ResxLPT ResLPT / ResMV ResLPT / ResMC ResLPT / ResACS ResxLPT / ResMV ResxLPT / ResMC ResxLPT / ResACS ResMV / ResMC ResMV / ResACS ResMC / ResACS
F-Ratio 0,996782 1,15013 1,42016 1,92669 1,15385 1,42475 1,93291 1,23478 1,67519 1,35667
Sigma1 32,0599 32,0599 32,0599 32,0599 32,1116 32,1116 32,1116 29,8943 29,8943 26,9026
Sigma2 32,1116 29,8943 26,9026 23,097 29,8943 26,9026 23,097 26,9026 23,097 23,097
| P-Valor 0,9945 0,7636 0,4517 0,1620 0,7583 0,4476 0,1600 0,6504 0,2697 0,5126
Nivel de Setup Bajo m = 3, n = 30 Prueba Chi-Cuadrado de Independencia Prueba Estadístico Gl Valor-P Chi-Cuadrada 15,951 76 1,0000
Pruebas Chi-Cuadrado de Normalidad Heurística LPT xLPT MV MC ACS
Estadístico 6,0 11,2 9,9 6,0 6,0
Valor-P 0,815263 0,34215 0,44931 0,815263 0,815263
Verificación de Varianza Prueba Valor-P Levene's 0,036171 0,997459 Comparación ResLPT / ResxLPT ResLPT / ResMV ResLPT / ResMC ResLPT / ResACS ResxLPT / ResMV ResxLPT / ResMC ResxLPT / ResACS ResMV / ResMC ResMV / ResACS ResMC / ResACS
Sigma1 56,6004 56,6004 56,6004 56,6004 56,0444 56,0444 56,0444 56,541 56,541 57,9209
Sigma2 56,0444 56,541 57,9209 55,814 56,541 57,9209 55,814 57,9209 55,814 55,814
F-Ratio 1,01994 1,0021 0,954924 1,02838 0,982512 0,936255 1,00827 0,95292 1,02622 1,07692
P-Valor 0,9661 0,9964 0,9210 0,9520 0,9697 0,8873 0,9859 0,9174 0,9556 0,8734
111 Aplicación de un algoritmo ACO al problema
|
|
m = 5, n = 50
Prueba Chi-Cuadrado de Independencia Prueba Estadístico Gl Valor-P Chi-Cuadrada 9,487 76 1,0000
Pruebas Chi-Cuadrado de Normalidad Heurística LPT xLPT MV MC ACS
Estadístico 8,6 13,8 9,9 12,5 8,6
Valor-P 0,570438 0,182311 0,44931 0,252985 0,570438
Verificación de Varianza Prueba Valor-P Levene's 0,0938543 0,984191 Comparación ResLPT / ResxLPT ResLPT / ResMV ResLPT / ResMC ResLPT / ResACS ResxLPT / ResMV ResxLPT / ResMC ResxLPT / ResACS ResMV / ResMC ResMV / ResACS ResMC / ResACS
Sigma1 39,0743 39,0743 39,0743 39,0743 41,1967 41,1967 41,1967 39,3945 39,3945 39,7963
Sigma2 41,1967 39,3945 39,7963 36,0115 39,3945 39,7963 36,0115 39,7963 36,0115 36,0115
F-Ratio 0,899616 0,983811 0,964043 1,17733 1,09359 1,07162 1,30871 0,979906 1,19671 1,22125
P-Valor 0,8200 0,9720 0,9372 0,7256 0,8474 0,8817 0,5634 0,9652 0,6995 0,6675
112 Aplicación de un algoritmo ACO al problema
|
|
m = 10, n = 100 Prueba Chi-Cuadrado de Independencia Prueba Estadístico Gl Valor-P Chi-Cuadrada 5,438 76 1,0000
Pruebas Chi-Cuadrado de Normalidad Heurística LPT xLPT MV MC ACS
Estadístico 8,6 9,9 7,3 7,3 8,6
Valor-P 0,570438 0,44931 0,696852 0,696852 0,570438
Verificación de Varianza Prueba Valor-P Levene's 0,0148062 0,999561 Comparación ResLPT / ResxLPT ResLPT / ResMV ResLPT / ResMC ResLPT / ResACS ResxLPT / ResMV ResxLPT / ResMC ResxLPT / ResACS ResMV / ResMC ResMV / ResACS ResMC / ResACS
Sigma1 34,7292 34,7292 34,7292 34,7292 33,7492 33,7492 33,7492 33,9989 33,9989 33,5441
Sigma2 33,7492 33,9989 33,5441 32,5319 33,9989 33,5441 32,5319 33,5441 32,5319 32,5319
F-Ratio 1,05892 1,04342 1,0719 1,13964 0,985368 1,01227 1,07624 1,0273 1,09222 1,0632
P-Valor 0,9020 0,9272 0,8813 0,7787 0,9747 0,9791 0,8744 0,9538 0,8495 0,8951
UNIVERSIDAD DE CONCEPCIÓN – FACULTAD DE INGENIERÍA RESUMEN DE MEMORIA DE TÍTULO Departamento de Ingeniería
Industrial
Título
Aplicación de un algoritmo ACO al problema de minimización
de
makespan
en
máquinas
paralelas idénticas con tiempos de setup dependientes de la secuencia Nombre Memorista Modalidad
Pablo Arriagada Pizarro Investigación
Profesor Patrocinante
Concepto
Sr. Eduardo Salazar Hornig
Calificación
Ingeniero Supervisor
Fecha
Abril, 2012
-
Institución -
Comisión (Nombre y Firma) Sr. Alejandro Concha
Sra. Lorena Pradenas
Resumen Este trabajo aplica un procedimiento heurístico al problema
|
|
, que es el problema de
programación de la producción sobre la minimización de makespan en máquinas paralelas idénticas, con tiempos de preparación dependientes de la secuencia de trabajos, un problema que se encuentra bastante en las industrias, pero que no tiene la misma consideración teórica que (sin tiempos de setup). La heurística aprovecha la metaheurística Ant Colony System por su aplicación exitosa en el Problema del Vendedor Viajero y similares. El algoritmo consiste en generar una secuencia inicial de trabajos por medio de ACS, para luego distribuirlos en las máquinas disponibles para producir; con dos variantes dentro de la misma heurística: uno que va asignando los trabajos antes de un límite calculado a partir de los parámetros de la instancia y otro que lo asigna después. Finalmente, por medio de ACS la máquina más ocupada pasa a ser revisada para evaluar si puede disminuir su tiempo de finalización, y, por lo tanto, el de todo el sistema. El makespan que entrega la heurística es el menor entre las dos variantes descritas. El desempeño de este procedimiento se compara con el de otras cuatro alternativas: LPT, LPT con tiempos de setup promedio, Mejor Vecino y Montecarlo. Los resultados de makespan generados por la heurística ACS con revisión muestran ser consistentemente menores que los otros cuatro métodos descritos, diferencia que es mayor en escenarios balanceados, donde los tiempos de setup son comparables a los tiempos de proceso.
