Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas

Trabajo Fin de Máster Máster Organización Industrial y Gestión de Empresas Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas Autor: Fernando Guerrero Ortega Tutor: Víctor Fernández-Viagas Escudero Dpto. Organización Industrial y Gestión de Empresas Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2019 Trabajo Fin de Máster Máster Organización Industrial y Gestión de Empresas Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas Autor: Fernando Guerrero Ortega Tutor: Víctor Fernández-Viagas Escudero Profesor Ayudante Doctor Dpto. Organización Industrial y Gestión de Empresas Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2019 Trabajo Fin de Máster: Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas Autor: Fernando Guerrero Ortega Tutor: Víctor Fernández-Viagas Escudero El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2019 El Secretario del Tribunal Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas Agradecimientos A todo el personal docente, en todos los niveles, que me ha enseñado a aprender y no sólo a estudiar. A los profesores que desde el primer momento consiguieron que encontrara todo el interés en una especialidad respecto a la que era bastante escéptico cuando la escogí. Al tutor de este trabajo, D. Víctor Fernández-Viagas Escudero, quien además de orientarme de forma ejemplar de nuevo, se adaptó a mis cambiantes circunstancias durante todo el tiempo que duró su elaboración. A ARUS, por permitirme vivir una experiencia irrepetible en un contexto que todos sus miembros sabemos que será imposible de encontrar en nuestras vidas profesionales. A todos los que mantienen sus principios y siguen escribiendo “sólo” con tilde. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas vii Í NDÍCE ÍNDICE DE FIGURAS ................................................................................................................................ x ÍNDICE DE TABLAS ............................................................................................................................... viii 1. INTRODUCCIÓN ............................................................................................................................... 12 2. DESCRIPCIÓN DEL PROBLEMA .......................................................................................................... 16 3.ESTADO DEL ARTE ............................................................................................................................. 19 3.1.Problema Fm|prmu, nwt|∑Cj .......................................................................................................... 19 3.2. Problemas similares ........................................................................................................................ 20 4. HEURÍSTICA REFERENCIA ................................................................................................................. 21 4.1. Algoritmo generador de la secuencia inicial (ISA) ........................................................................... 21 4.2. Heurística para encontrar mejoras a la secuencia inicial (CFI) ........................................................ 24 5. TÉCNICAS DE BÚSQUEDA LOCAL ...................................................................................................... 27 5.1. Intercambio de trabajos .................................................................................................................. 27 5.2. Inserción completa de trabajos ....................................................................................................... 31 5.3. Inserción hacia delante de trabajos ................................................................................................ 33 5.4. Técnica de búsqueda local basada en la NEH ................................................................................. 35 6. HEURÍSTICAS PROPUESTAS .............................................................................................................. 37 6.1. Heurística CML-I .............................................................................................................................. 37 6.2. Heurística CML-II ............................................................................................................................. 37 6.3. Heurística CML-III ............................................................................................................................ 37 6.4. Heurística CML-IV ............................................................................................................................ 38 6.5. Heurística CML-V ............................................................................................................................. 38 7. METAHEURÍSTICAS PROPUESTAS ..................................................................................................... 39 7.1. Algoritmo de generación de secuencia iniciales alternativas (ISA-GRASP) ..................................... 39 7.2. Metaheurística MH-I ....................................................................................................................... 40 7.3. Metaheurística MH-II ...................................................................................................................... 41 7.4. Metaheurística MH-III ..................................................................................................................... 42 8. EVALUACIÓN COMPUTACIONAL ...................................................................................................... 44 8.1. Heurística referencia. ISA y CFI ....................................................................................................... 44 8.2. Técnicas de búsqueda local ............................................................................................................. 50 8.3. Heurísticas propuestas .................................................................................................................... 51 8.4. Metaheurísticas propuestas............................................................................................................ 53 8.5. Parametrización de la metaheurística MH-III.................................................................................. 56 8.6. Comparación general de algoritmos ............................................................................................... 60 9. CONCLUSIONES ................................................................................................................................ 64 REFERENCIAS ....................................................................................................................................... 65 ANEXOS ............................................................................................................................................... 69 Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas viii Í NDÍ CE DE TABLAS Tabla 1.1. Tiempos de proceso para un problema genérico con cuatro trabajos y tres máquinas. Tabla 4.1. Tiempos de proceso para un problema genérico con cuatro trabajos y tres máquinas. Tabla 4.2. Cálculo de los tiempos ociosos y del índice para cada uno de los trabajos, y selección del primer trabajo de la secuencia inicial. Tabla 4.3. Cálculo de los tiempos ociosos y del índice para cada uno de los trabajos restantes, y selección del segundo trabajo de la secuencia inicial. Tabla 4.4. Cálculo de los tiempos ociosos y del índice para cada uno de los trabajos restantes en cada iteración, y obtención de la secuencia inicial. Tabla 7.1. Cálculo de los tiempos ociosos y del índice para cada uno de los trabajos, y selección del primer trabajo de una secuencia inicial con aleatoriedad. Tabla 8.1. Tamaño de los problemas que componen las instancias de Taillard. Tabla 8.2. TCT de las secuencias generadas por el algoritmo ISA en las 120 instancias. Tabla 8.3. TCT y RPD de las secuencias generadas por el algoritmo CFI en las 120 instancias. Tabla 8.4. ARPD y tiempo computacional medio de la heurística CFI agrupado por instancias. Tabla 8.5. RPD y tiempo computacional empleado por la heurística CFI en las 120 instancias. Tabla 8.6. ARPD y tiempo computacional medio de la heurística CFI interrumpido agrupado por instancias. Tabla 8.7. ARPD y tiempo computacional medio de las diez técnicas de búsqueda local consideradas. Tabla 8.8. ARPD y tiempo computacional medio de las heurísticas propuestas CML-I y CML-II. Tabla 8.9. ARPD y tiempo computacional medio de las heurísticas propuestas CML-III y CML-IV. Tabla 8.10. ARPD y tiempo computacional medio de la heurística propuesta CML-V. Tabla 8.11. ARPD y tiempo computacional medio de la metaheurística propuesta MH-I para x=5, x=10, x=50, x=100. Tabla 8.12. ARPD y tiempo computacional medio de la metaheurística propuesta MH-II para x=5 y x=10. Tabla 8.13. ARPD y tiempo computacional medio de la metaheurística propuesta MH-III para cuatro combinaciones de parámetros distintas. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas ix Tabla 8.14. Valores propuestos para los parámetros del problema: x, z; así como el valor de y en cada caso. Tabla 8.15. ARPD de la metaheurística propuesta MH-III para los 34 casos planteados según x, z. Tabla 8.16. Tiempo computacional medio empleado por la metaheurística propuesta MH-III para los 34 casos planteados según x, z. Tabla 8.17. ARPD y tiempo computacional de los algoritmos propuestos que aparecen en la Figura 8.5. Tabla 8.18. ARPD y tiempo computacional empleado por la heurística referencia y MH-III (x=20, y=5) agrupado por instancias. Tabla 8.19. TCT de las secuencias obtenidas mediante ISA+CFI y MH-III (x=20, y=5) en las 120 instancias, y mejora porcentual de MH-III respecto a la heurística referencia. Tabla A.1. Extracto de las dos muestras a las que se realiza el análisis estadístico. Tabla A.2. Tabla de la distribución t de Student. Tabla B.1. ARPD y tiempo computacional medio, agrupados por instancias, de las técnicas de búsqueda local de intercambio de trabajos. Tabla B.2. ARPD y tiempo computacional medio, agrupados por instancias, de las técnicas de búsqueda local de inserción completa de trabajos. Tabla B.3. ARPD y tiempo computacional medio, agrupados por instancias, de las técnicas de búsqueda local de inserción hacia delante de trabajos. Tabla B.4. ARPD y tiempo computacional medio, agrupados por instancias, de la técnica de búsqueda local NEHLOC. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 16 2. DESCRÍPCÍO N DEL PROBLEMA Como se ha dicho anteriormente, el permutation flow shop problema (PFSP) es objeto de análisis en gran cantidad de estudios debido a que es un entorno de producción muy común cuando se fabrica en serie. En muchos de ellos además se considera la restricción no-wait, que impide a las unidades producidas esperar entre las distintas etapas del proceso de fabricación. Si bien el uso de talleres de tipo flow shop es algo bastante común en procesos de fabricación, la gran mayoría de estos problemas son NP-hard (Garey, Johnson, Sethi; 1976), llegando a ser muy complicado alcanzar soluciones cercanas al óptimo para casos con un número de trabajos y/o máquinas lo suficientemente altos, por lo que se usan heurísticas con el fin de intentar llegar a una solución no muy alejada de la óptima de manera relativamente sencilla. El objetivo que se intenta minimizar en el problema tratado en este proyecto es el tiempo total de finalización, que es la suma del tiempo que permanece en el taller cada una de las unidades que en él se fabrican. Este valor también es comúnmente denominado tiempo total de flujo, pero dichos conceptos sólo representan lo mismo cuando la disponibilidad de los trabajos es completa desde el instante inicial, es decir, cuando éstos no tienen fechas de llegada, como ocurre en el problema estudiado en este proyecto. Minimizar dicho valor es equivalente a reducir el tiempo medio que pasan los trabajos en las distintas etapas del proceso de fabricación (Shyu, Lin, Yin; 2004), por lo que un buen resultado significaría que los clientes tendrían antes sus productos terminados, algo que no ocurre necesariamente cuando el objetivo es el makespan, el tiempo de finalización del último trabajo, que es el que más habitualmente se estudia en esta clase de problemas. Adicionalmente, se consideran las restricciones comunes del entorno flow shop, es decir, que una máquina no puede procesar más de un trabajo simultáneamente, y que un trabajo no puede estar asignado a más de una máquina al mismo tiempo. El propósito de este proyecto es encontrar nuevos métodos de resolución del problema presentado que puedan aportar mejores resultados que los obtenidos con los existentes en la actualidad. Para describir el modelo del problema, usaremos la notación introducida por Graham et al. (1979), que consiste en describir los tres conceptos previamente mencionados en tres campos, 𝛼|𝛽|𝛾, representando cada uno de ellos:  𝛼: el entorno del proceso de fabricación, es decir, la disposición de las máquinas y cuáles se deben usar para producir los trabajos.  𝛽: las distintas restricciones que se aplican al problema.  𝛾: el objetivo que determina qué soluciones son más beneficiosas. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 17 Usando dicha notación, el problema a estudiar en este proyecto se expresa como 𝐹𝑚|𝑝𝑟𝑚𝑢,𝑛𝑤𝑡|∑𝐶𝑗. Para expresar las ecuaciones que modelan el problema, se toma como referencia el artículo publicado por Stafford Jr, Tseng y Gupta (2005), en el que se recogen varios modelos para problemas de taller de flujo, siendo uno de ellos el del problema 𝐹𝑚|𝑝𝑟𝑚𝑢|𝐶𝑚𝑎𝑥 . Basándose en ese modelo, basta con cambiar el objetivo a minimizar y eliminar la holgura de una de las ecuaciones para impedir que haya esperas entre máquinas, y se obtiene el que caracteriza al problema a analizar. A continuación, se plantean y describen los datos y variables que en él aparecen en la Figura 2.1, en la que se representa el modelo del problema, y se explica el papel de cada una de las restricciones que lo forman, así como el cálculo de la función objetivo.  𝑝𝑖𝑗 : Tiempo que tarda en procesarse el trabajo j en la máquina i  𝐶𝑖𝑗 : Tiempo de finalización del trabajo j en la máquina i  𝑋𝑗𝑘 : Variable binaria que vale 1 si el trabajo j se procesa antes que el k (no necesariamente inmediatamente antes)  𝐴 : Término lo suficientemente grande como para considerar despreciables el resto de sumandos de su lado de la inecuación  𝑀 : Conjunto de todas las máquinas que componen el taller  𝑁 : Conjunto de todos los trabajos que se deben procesar  𝑚 : Número de máquinas que componen el taller  𝑛 : Número de trabajos que deben ser procesados 𝑀𝐼𝑁 ∑ 𝐶𝑚𝑗 𝑛 𝑗=1 (0) s. a: 𝐶1𝑗 ≥ 𝑝1𝑗 ∀𝑗∈ 𝑁 (1) 𝐶𝑖𝑗 − 𝐶𝑖𝑘 + 𝐴 ·𝑋𝑗𝑘 ≥ 𝑝𝑖𝑗 ∀𝑖 ∈𝑀, ∀𝑗∈ 𝑁, ∀𝑘 ∈𝑁, 𝑗 <𝑘 (2) 𝐶𝑖𝑗 − 𝐶𝑖𝑘 + 𝐴 (𝑋𝑗𝑘 − 1)≤ − 𝑝𝑖𝑘 ∀𝑖 ∈𝑀, ∀𝑗 ∈𝑁, ∀𝑘 ∈𝑁, 𝑗 <𝑘 (3) 𝐶𝑖𝑗 − 𝐶𝑖−1,𝑗 = 𝑝𝑖𝑗 ∀𝑖 ∈𝑀−{1}, ∀𝑗∈𝑁 (4) Figura 2.1. Modelo del problema Fm|prmu, nwt|∑Cj. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 18 La función objetivo (0) hace que no sólo se intente que último trabajo se termine lo antes posible, sino que se minimice la suma de los instantes de finalización de cada uno de ellos, que obviamente coincide con el tiempo en el que salen de la última máquina de la línea. Este valor se denomina Tiempo Total de Finalización, más conocido por sus siglas en inglés, TCT (Total Completion Time). La ecuación (1) establece el límite inferior del tiempo de finalización de cada uno de los trabajos en la primera máquina, que debe ser al menos igual al tiempo de proceso del trabajo correspondiente en la primera máquina, es decir, evita que haya trabajos que comiencen a procesarse antes del instante inicial. Las ecuaciones (2) y (3) son muy similares a la (1), pero para las máquinas a partir de la segunda, por lo que en este caso el “instante inicial” viene marcado por el instante de finalización en la máquina en cuestión del trabajo que se procese con anterioridad. La ecuación (4) es la que asegura que la restricción no-wait se cumpla, es decir, que cada uno de los trabajos sea procesado en cada una de las máquinas sin interrupción alguna. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 19 3. ESTADO DEL ARTE Se ha llevado a cabo una revisión de artículos publicados sobre entornos de producción en talleres de flujo regular (flow shop) en los que se imponen restricciones sobre las esperas de los trabajos entre máquinas, y se han analizado los artículos encontrados que tratan tanto el problema que estudia este trabajo como otros con restricciones u objetivos similares con el propósito de observar y analizar los métodos ya propuestos para resolver dichos problemas. 3.1. Problema Fm|prmu, nwt|∑Cj Como se comentó en el capítulo anterior, minimizar el tiempo total de finalización no es el objetivo más habitual en este tipo de situaciones. Sin embargo, han sido numerosos los autores que han estudiado este problema. Los algoritmos aproximados para resolver el problema del que trata este trabajo se pueden dividir en heurísticas constructivas y metaheurísticas (Lin, Ying; 2016). Dentro de las heurísticas constructivas, Rajendran y Chaudhuri (1990) propusieron dos heurísticas basadas en la inserción de trabajos, que eran más efectivas que otras existentes en su momento. Aldowaisan y Allahverdi (2004) presentaron seis heurísticas usando diferentes métodos de búsqueda, entre las cuales destacaba la PH1(p), que mejoraba la propuesta por Rajendran y Chaudhuri (1990), o el algoritmo genético propuesto por Chen, Neppaili y Alkaber (1996). Framinan, Nagano y Moccellin (2010) propusieron la heurística constructiva FNM, con la que se obtenían mejores resultados que con las anteriores. Basándose en el procedimiento de Laha y Chakraborty (2009), Gao, Pan, Suganthan y Li (2013) propusieron dos heurísticas constructivas: una de ellas desarrollada a partir de la heurística de desviación típica de Gao, Pan, Li (2011), y otra a partir de la heurística de Bertolissi (2000). Ésta última demostró aportar mejores resultados que la heurística de inserción de trabajos NEH (Nawaz et al., 1983). Más recientemente, se han propuesto artículos que presentan procedimientos para resolver el problema 𝐹𝑚|𝑛𝑤𝑡|∑𝐶𝑗, como un algoritmo híbrido de optimización por enjambre de partículas (Akhshabi, Tavakkoli-Modhaddam, Rahnamay-Roodposhti; 2014), o el de Laha y Sapkal (2014), quienes presentaron una heurística LS con la que se obtienen mejores resultados que con las heurísticas PH1(p) y FNM. Por último, la heurística propuesta por Ye, Li, Abedini, Nault (2017), denominada CFI, aporta mejores resultados que con las heurísticas PH1(p), FNM y LS, empleando además un menor tiempo computacional. Esta heurística consiste en una serie de mejoras sobre una secuencia inicial generada mediante un algoritmo cuyo uso está bastante extendido, como se observa en los artículos publicados por Liu y Reeves (2001), Fernandez-Viagas y Framinan (2015), Fernandez-Viagas, Dios y Framinan (2016) o Framinan y Perez-Gonzalez (2017). Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 20 En lo referente a las metaheurísticas, hay muchos estudios que han tratado este problema, como los que presentaron Akhshabi, Tavakkoli-Modhaddam y Rahnamay-Roodposhti (2014) o Zhu y Li (2015). Qi et al. (2016) propusieron un algoritmo de búsqueda local rápida, y los resultados experimentales demuestran que dicho algoritmo es más efectivo que otros propuestos previamente, como el IHA o el DHS. Sin embargo, el tiempo computacional requerido para obtener una solución próxima a la óptima es considerablemente mayor que con las heurísticas constructivas. Esto hace que no sea habitual usar metaheurísticas para la programación de operaciones. 3.2. Problemas similares En cuanto a estudios sobre problemas similares, la minimización del makespan en el problema flow shop no-wait ha sido ampliamente estudiada. Algunas metaheurísticas usualmente empleadas para su resolución fueron analizadas por Bewoor, Prakash y Sapkal (2017), como la búsqueda tabú, el algoritmo genético o la optimización por enjambre de partículas. Lin y Ying (2016) presentan otra metaheurística, consistente en tres fases: una heurística constructiva MNEH para lograr una secuencia de trabajos inicial, un algoritmo LHK que mejora dicha secuencia, y un modelo matemático BIP que hace que ésta se aproxime a la óptima. Asimismo, se han propuesto numerosos algoritmos y heurísticas para resolver el problema con el makespan como objetivo, como el Discrete Water Wave (Zhao, Liu, Zhang, Ma, Zhang; 2018) o el ACO-LS (Riyanto, Santosa; 2015). Se han estudiado otros objetivos para este tipo de problemas además del makespan y el TCT, como el que tratan Ruiz y Allahverdi (2009), que consiste en una combinación del propio makespan con el retraso del trabajo que se termina de procesar más tarde respecto a su fecha de entrega. En otros estudios se ha tratado el mismo problema pero con unas restricciones distintas, como permitir un tiempo máximo de espera entre máquinas (Ye, Zhao, Li, Lei; 2017) o considerar fechas de entrega para los trabajos (Samarghandi, Behroozi; 2017). Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 21 4. HEURÍ STÍCA REFERENCÍA En esta sección, se detalla la heurística con la que se obtienen mejores resultados de entre todas las analizadas en el capítulo anterior, que es la propuesta por Ye, Li, Abedini y Nault (2017), denominada CFI. Básicamente, esta heurística consiste en una primera parte donde se genera una secuencia inicial y una segunda en la que se aplican técnicas de inserción e intercambio de trabajos con el fin de mejorar dicha secuencia. Ambas etapas se detallan a continuación, adjuntándose además su aplicación a un problema de tamaño reducido. 4.1. Algoritmo generador de la secuencia inicial (ISA) En este algoritmo, llamado ISA por sus siglas en inglés, Initial Sequence Algorithm, y cuyo pseudocódigo se adjunta en la Figura 4.1, se ordenan los trabajos basándose en el tiempo ocioso que habría en las máquinas, intentando que sea lo menor posible, especialmente entre el procesado de los primeros trabajos secuenciados. Para ello, se define un índice para cada uno de los trabajos, denominado 𝑖𝑛𝑑, que depende de:  𝐶𝐼: Tiempo ocioso actual, el que tiene lugar antes de procesar el trabajo en cuestión, sumado para todas las máquinas.  𝐹𝐼: Tiempo ocioso futuro, entre dicho trabajo y el posterior, sumado para todas las máquinas. Sin embargo, como no se puede conocer cuál es el trabajo posterior, se construye artificialmente uno cuyos tiempos de proceso se obtienen a partir de la media de los tiempos en cada una de las máquinas de los trabajos aún no secuenciados. Entrada: datos del problema (𝑚,𝑛,𝑝𝑖𝑗) Salida: secuencia inicial de trabajos (𝑠𝑒𝑐𝐼𝑁𝐼) Se define 𝑈: conjunto de trabajos aún no secuenciados, inicialmente {1,2,…,𝑛} 𝐹𝑜𝑟 𝑘 =1 𝑡𝑜 (𝑛 − 1) 𝐹𝑜𝑟 ∀ 𝑗∈ 𝑈 Insertar el trabajo 𝑗 en la posición 𝑘 de 𝑠𝑒𝑐𝐼𝑁𝐼, y el trabajo artificial en la 𝑘+1 𝑖𝑛𝑑𝑗=(𝑛−𝑘)∗𝐶𝐼+𝐹𝐼 Insertar el trabajo con menor 𝑖𝑛𝑑𝑗en la posición 𝑘 de 𝑠𝑒𝑐𝐼𝑁𝐼, y extraerlo de 𝑈 Insertar el único trabajo restante en el conjunto 𝑈 en la posición 𝑛 de 𝑠𝑒𝑐𝐼𝑁𝐼 Figura 4.1. Pseudocódigo del algoritmo ISA. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 22 Con el fin de hacer más entendible este algoritmo, se detalla a continuación cómo se aplica a un problema sencillo de 4 trabajos y 3 máquinas, con los tiempos de proceso indicados en la Tabla 4.1. Tabla 4.1. Tiempos de proceso para un problema genérico con cuatro trabajos y tres máquinas. En primer lugar, el trabajo 1 se coloca en la primera posición de la secuencia. Posteriormente, se calcula la media de los tiempos de proceso del resto de trabajos para cada una de las máquinas (APT: AverageProcessing Times), y esos son los tiempos de proceso del trabajo artificial, que se situaría tras el trabajo 1, obteniendo la situación representada en la Figura 4.2. 𝐴𝑃𝑇234 (𝑚á𝑞𝑢𝑖𝑛𝑎 1)= (8 + 5 + 1) 3=4,67 ⁄ 𝐴𝑃𝑇234 (𝑚á𝑞𝑢𝑖𝑛𝑎 2)= (9 + 9 + 3) 3=7 ⁄ 𝐴𝑃𝑇234 (𝑚á𝑞𝑢𝑖𝑛𝑎 3)= (6 + 2 + 8) 3=5,33 ⁄ Nótese que al trabajo artificial también se le impide permanecer en espera entre dos máquinas, como a cualquier otro trabajo real. Figura 4.2. Diagrama de Gantt obtenido al secuenciar el trabajo 1 en primer lugar, y posteriormente el trabajo artificial. En este caso, los tiempos ociosos actuales y futuros para el trabajo 1 se calculan como sigue: 𝐶𝐼1=(0−0)+(2−0)+(7−0)=9 𝐹𝐼1=(2,33−2)+(7−7)+(14−13)= 1,33 𝑖𝑛𝑑1=(4−1)∗9+1,33=28,33 Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 23 Este proceso se repite con cada uno de los trabajos, obteniendo los resultados mostrados en la Tabla 4.2. Como al secuenciar el trabajo 4 es cuando se obtiene un menor valor del índice, es dicho trabajo el que ocupa la primera posición de la secuencia inicial. Tabla 4.2. Cálculo de los tiempos ociosos y del índice para cada uno de los trabajos, y selección del primer trabajo de la secuencia inicial. En la segunda iteración, se sitúan todos los trabajos restantes en la segunda posición de la secuencia, pues el trabajo 4 está ya fijado en la primera. Por ejemplo, al asignar el trabajo 1 a la segunda posición y secuenciar tras él el trabajo artificial (construido esta vez a partir de los tiempos de proceso de los trabajos 2 y 3), se obtiene el Diagrama de Gantt representado en la Figura 4.3. Figura 4.3. Diagrama de Gantt obtenido, una vez se ha fijado el trabajo 4 al inicio de la secuencia, al secuenciar el trabajo 1 en segundo lugar, y posteriormente el trabajo artificial. 𝐶𝐼1=(5−1)+(7−4)+(12−12)=7 𝐹𝐼1=(7−7)+(13,5−12)+(22,5−18)=6 𝑖𝑛𝑑1=(4−2)∗7+6=20 De igual forma, se calculan los índices para el resto de trabajos en la Tabla 4.3, hallando el segundo trabajo de la secuencia inicial. El algoritmo sigue aplicándose hasta que ya sólo quede un trabajo por ser secuenciado, que evidentemente se coloca en la última posición de la secuencia, como se puede observar en la Tabla 4.4, que resume el proceso completo. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 24 Tabla 4.3. Cálculo de los tiempos ociosos y del índice para cada uno de los trabajos restantes, y selección del segundo trabajo de la secuencia inicial. Tabla 4.4. Cálculo de los tiempos ociosos y del índice para cada uno de los trabajos restantes en cada iteración, y obtención de la secuencia inicial. 4.2. Heurística para encontrar mejoras a la secuencia inicial (CFI) En esta segunda etapa, partiendo de la secuencia inicial obtenida en la anterior, se obtienen nuevas secuencias mediante un proceso iterativo de inserción e intercambio de trabajos, cuyos pasos se describen en la Figura 4.4. 1. Fijar la variable 𝑟 =1. Se define 𝑠𝑒𝑐𝐵𝐸𝑆𝑇 como la secuencia de 𝑛 trabajos con la que se consigue un mejor resultado. Inicialmente, 𝑠𝑒𝑐𝐵𝐸𝑆𝑇 es la secuencia obtenida mediante ISA. 2. Seleccionar los dos primeros trabajos de 𝑠𝑒𝑐𝐵𝐸𝑆𝑇, y elegir la secuencia parcial con menor TCT. 3. En primer lugar, insertar el siguiente trabajo de 𝑠𝑒𝑐𝐵𝐸𝑆𝑇 en cada una de las posibles posiciones, obteniendo nuevas y más largas secuencias parciales, y elegir la mejor de ellas. Posteriormente, intercambiar dos a dos los trabajos de ésta última para generar otras secuencias, y sustituir la anterior por la mejor de ellas en caso de encontrarse alguna que dé un mejor resultado. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 25 4. Repetir el paso 3 hasta que todos los trabajos estén secuenciados, y nombrar a la secuencia resultante de tamaño 𝑛 𝑠𝑒𝑐𝑃. 5. Desde 𝑗 =1 hasta (𝑛 − 1), insertar el trabajo𝑗de 𝑠𝑒𝑐𝑃 en las (𝑛−𝑗) posibles posiciones posteriores en la secuencia. Si alguna de las secuencias halladas en este paso (o la propia 𝑠𝑒𝑐𝑃) mejora a 𝑠𝑒𝑐𝐵𝐸𝑆𝑇, actualizar ésta última por la mejor de ellas. 6. Aumentar en 1 el valor de𝑟. Si 𝑟 ≤6, volver al paso 2. 7. Definir 𝑠𝑒𝑐𝐶𝐹𝐼 = 𝑠𝑒𝑐𝐵𝐸𝑆𝑇, la secuencia finalmente obtenida tras aplicar el algoritmo. Figura 4.4. Pasos de la heurística CFI. Se adjunta, al igual que para el algoritmo de generación de la secuencia inicial, la aplicación de esta heurística al mismo ejemplo de 4 trabajos y 3 máquinas. En primer lugar, cada iteración parte de la mejor ecuación hallada hasta el momento, denominada 𝑠𝑒𝑐𝐵𝐸𝑆𝑇, que en la primera es la obtenida mediante el algoritmo ISA, como muestra la Figura 4.5. Figura 4.5. Paso 1 de la heurística CFI. La Figura 4.6 representa el segundo paso de la heurística, en el que se forman las dos secuencias posibles de dos trabajos que se pueden construir con los dos primeros trabajos de la secuencia inicial, quedándonos con la mejor. Figura 4.6. Paso 2 de la heurística CFI. Posteriormente, el paso 3 para el trabajo situado en tercer lugar en la secuencia inicial consiste en insertarlo en las tres posibles posiciones de la secuencia parcial que se obtuvo en el paso anterior. A la mejor de esas tres secuencias se le intercambian dos a dos todos sus trabajos, buscando una nueva secuencia que la mejore, como se observa en la Figura 4.7. Figura 4.7. Paso 3 de la heurística CFI para el tercer trabajo. A continuación, en la Figura 4.8 se repite el proceso anterior, pero esta vez con el cuarto trabajo de la secuencia inicial. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 32 5.2.2. Inserción completa de trabajos – FIRST (insF) En este caso, se van obteniendo nuevas secuencias de igual forma a partir de la que se tiene como referencia, pero se deja de buscar en el momento en el que una de ellas ya sea mejor que la que se tenía, pasando directamente a la siguiente iteración. Como se observa en la Figura 5.6, cuando se halla la secuencia [1, 3, 2, 4], que mejora a la referencia inicial, se da por finalizada la primera iteración y se reinicia el proceso de generación de nuevas secuencias, por lo que en esta técnica no tienen por qué generarse esas doce secuencias en cada una de las iteraciones. Figura 5.6. Aplicación de la técnica Inserción de trabajos (FIRST) al problema de la Tabla 4.1. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 33 5.2.3. Inserción completa de trabajos – FIRST BEST (insFB) A diferencia de lo que sucedía con los intercambios de trabajos, no se genera la misma cantidad de secuencias por iteración que en caso BEST, pues en éste se hallan 𝑛2 nuevas soluciones en cada una de ellas, como puede apreciarse en el problema de la Figura 5.7. Figura 5.7. Aplicación de la técnica Inserción de trabajos (FIRST BEST) al problema de la Tabla 4.1. 5.3. Inserción hacia delante de trabajos En este tipo de búsqueda, se encuentran nuevas secuencias a partir de la inserción de cada trabajo sólo en las posiciones posteriores de la secuencia. Según cómo se actúe al hallar soluciones mejores a las que se tenían previamente, se subdividen estas técnicas en otras tres. 5.3.1. Inserción hacia delante de trabajos – BEST (insforB) Partiendo de la secuencia referencia, cada uno de los trabajos se inserta en todas las posiciones posteriores de la secuencia respetando el orden del resto de trabajos. El trabajo en la posición 𝑗 puede insertarse en (𝑛−𝑗) posiciones distintas, generando otras tantas secuencias. En total, en cada iteración se generan (𝑛−1)+(𝑛−2)+⋯+1 nuevas secuencias. La Figura 5.8 muestra un problema en el que, al haber cuatro trabajos, se generan seis secuencias en cada iteración, y en el que la secuencia resultado de la primera ya no se mejora en la segunda, por lo que ésa es la secuencia resultado de aplicar esta técnica. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 34 Figura 5.8. Aplicación de la técnica Inserción hacia delante de trabajos (BEST) al problema de la Tabla 4.1 5.3.2. Inserción hacia delante de trabajos – FIRST (insforF) En este caso, se van obteniendo nuevas secuencias de igual forma a partir de la que se tiene como referencia, pero se deja de buscar en el momento de que una de ellas ya sea mejor que la que se tenía, pasando directamente a la siguiente iteración. Como se observa en la Figura 5.9, cuando se halla la secuencia [1, 3, 2, 4], que mejora a la referencia inicial, se da por finalizada la primera iteración y se reinicia el proceso de generación de nuevas secuencias, por lo que en esta técnica no tienen por qué generarse esas seis secuencias en cada una de las iteraciones. Figura 5.9. Aplicación de la técnica Inserción hacia delante de trabajos (FIRST) al problema de la Tabla 4.1 Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 35 5.3.3. Inserción hacia delante de trabajos – FIRST BEST (insforFB) En este caso, el número de secuencias nuevas que se generan en cada iteración no es fijo, pues depende de la posición que ocupen los trabajos que aún no han sido insertados en el resto de posiciones cada vez que se encuentre una nueva secuencia referencia. El mínimo de secuencias nuevas que se generan en cada iteración es seis, pero si se hallan soluciones mejores a la que se tenía hasta ese instante, puede ocurrir que se obtengan más de seis secuencias, como sucede en la primera iteración del ejemplo mostrado en la Figura 5.10. Figura 5.10. Aplicación de la técnica Inserción hacia delante de trabajos (FIRST BEST) al problema de la Tabla 4.1. 5.4. Técnica de búsqueda local basada en la NEH (NEHLOC) Se trata de un procedimiento basado en una heurística constructiva habitual en la programación de operaciones como la NEH. En ella, partiendo de una secuencia inicial, se insertan uno a uno sus trabajos en todas las posibles posiciones de una nueva secuencia, quedándose con la mejor secuencia parcial obtenida en cada momento, hasta haber insertado todos los trabajos y obtenido una nueva secuencia final. Los pasos para aplicar la técnica de inserción de trabajos NEH estándar se explican en la Figura 5.11, mostrándose además una aplicación de la misma en el ejemplo representado en la Figura 5.12. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 36 1. Se consideran los dos primeros trabajos de la secuencia inicial (𝑠𝑒𝑐𝐼𝑁𝐼), de tamaño 𝑛, y la mejor de las dos secuencias parciales que pueden formar dichos trabajos se convierte en la secuencia resultado provisional (𝑠𝑒𝑐𝑅𝐸𝑆). 2. Se crea la variable 𝑖, que inicialmente toma el valor 3. 3. Se toma el siguiente trabajo de 𝑠𝑒𝑐𝐼𝑁𝐼 (el que está en la posición 𝑖), y se inserta en todas las posibles posiciones de 𝑠𝑒𝑐𝑅𝐸𝑆, obteniendo 𝑖 secuencias parciales de tamaño 𝑖. La mejor de todas ellas es la nueva 𝑠𝑒𝑐𝑅𝐸𝑆. 4. Si 𝑖 <𝑛 , se aumenta en 1 unidad el valor de 𝑖 y se vuelve el paso 3. Figura 5.11. Pasos de la heurística NEH. Figura 5.12. Aplicación de la técnica de inserción de trabajos NEH al problema de la Tabla 4.1. Dependiendo del problema y de la secuencia inicial desde la que se parta, pudiera suceder que la secuencia final fuese peor que la inicial, algo que nunca ocurre con las nueve técnicas anteriores. Esto sucede porque la NEH se trata de una heurística constructiva, así que para asegurarse de que este procedimiento propuesto sea siempre un método de mejora, se compara la secuencia inicial con la obtenida finalmente, y se mantiene la primera en caso de que la segunda no la mejore. Al añadirle esta modificación a la técnica NEH, se denomina NEHLOC al procedimiento descrito en este párrafo. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 37 6. HE URÍ STÍCAS PROPUESTAS Partiendo del algoritmo de generación de secuencia inicial (ISA) descrito en el punto 4, se combinan algunas de las técnicas de mejora local explicadas en el capítulo anterior. Según cuáles de ellas se apliquen y en qué orden se haga, se plantean distintas heurísticas, cuya evaluación se trata en el capítulo 8. Las dos primeras combinan las técnicas insFB y NEHLOC en los dos posibles órdenes, mientras que las dos siguientes aplican en primer lugar la NEHLOC y posteriormente las insFB y swapFB, también en los dos órdenes posibles. Se presenta también una quinta heurística en la que dichas técnicas se aplican en múltiples ocasiones. 6.1. Heurística CML-I Esta primera heurística planteada consiste en, partiendo de la secuencia inicial, realizar una combinación de dos de las técnicas de búsqueda local explicadas en el capítulo anterior. 1. Se obtiene la secuencia 𝜋𝑖𝑛𝑖 mediante el algoritmo de secuencia inicial (ISA). 2. Se aplica la técnica insFB a 𝜋𝑖𝑛𝑖, obteniendo la secuencia 𝜋𝐼. 3. Se aplica la técnica NEHLOC a 𝜋𝐼, obteniendo la secuencia 𝜋𝑓𝑖𝑛. Figura 6.1. Pasos de la heurística CML-I. 6.2. Heurística CML-II En esta heurística se invierte respeto a la CML-I el orden de las dos técnicas de búsqueda local aplicadas tras la obtención de la secuencia inicial. 1. Se obtiene la secuencia 𝜋𝑖𝑛𝑖 mediante el algoritmo de secuencia inicial (ISA). 2. Se aplica la técnica NEHLOC a 𝜋𝑖𝑛𝑖, obteniendo la secuencia 𝜋𝐼. 3. Se aplica la técnica insFB a 𝜋𝐼, obteniendo la secuencia 𝜋𝑓𝑖𝑛. Figura 6.2. Pasos de la heurística CML-II. 6.3. Heurística CML-III Esta heurística incluye una nueva técnica de búsqueda local en comparación a las dos anteriores, como es la swapFB, que se aplica en último lugar. Es idéntica a la CML-I, salvo por precisamente ese último paso. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 38 1. Se obtiene la secuencia 𝜋𝑖𝑛𝑖 mediante el algoritmo de secuencia inicial (ISA). 2. Se aplica la técnica NEHLOC a 𝜋𝑖𝑛𝑖, obteniendo la secuencia 𝜋𝐼. 3. Se aplica la técnica insFB a 𝜋𝐼, obteniendo la secuencia 𝜋𝐼𝐼. 4. Se aplica la técnica swapFB a 𝜋𝐼𝐼, obteniendo la secuencia 𝜋𝑓𝑖𝑛. Figura 6.3. Pasos de la heurística CML-III. 6.4. Heurística CML-IV Esta heurística invierte respeto a la CML-III el orden de los pasos 3 y 4, es decir, de las dos técnicas de búsqueda local aplicadas tras la obtención de la secuencia inicial y la aplicación de la NEHLOC. 1. Se obtiene la secuencia 𝜋𝑖𝑛𝑖 mediante el algoritmo de secuencia inicial (ISA). 2. Se aplica la técnica NEHLOC a 𝜋𝑖𝑛𝑖, obteniendo la secuencia 𝜋𝐼. 3. Se aplica la técnica swapFB a 𝜋𝐼, obteniendo la secuencia 𝜋𝐼𝐼. 4. Se aplica la técnica insFB a 𝜋𝐼𝐼, obteniendo la secuencia 𝜋𝑓𝑖𝑛. Figura 6.4. Pasos de la heurística CML-IV. 6.5. Heurística CML-V Esta heurística, siendo similar a la CML-III, contempla en varios puntos del proceso distintas alternativas, según qué técnica vaya logrando mejores resultados. 1. Se obtiene la secuencia 𝜋𝑖𝑛𝑖 mediante el algoritmo de secuencia inicial (ISA). 2. Se aplica a 𝜋𝑖𝑛𝑖 la técnica NEHLOC, obteniendo 𝜋𝐼, y a ésta se le aplica la insFB, obteniendo la secuencia 𝜋𝐼𝐼. 3. Se aplica la técnica insFB a 𝜋𝑖𝑛𝑖, obteniendo la secuencia 𝜋𝐼𝐼𝐼. 4. Se comparan las secuencias 𝜋𝐼𝐼 y 𝜋𝐼𝐼𝐼, conservando solamente la mejor, renombrada como 𝜋𝐼𝑉. 5. Se repiten los pasos 2,3 y 4, siendo en este caso 𝜋𝐼𝑉 la nueva secuencia inicial. 6. Se aplica la técnica swapFB a 𝜋𝐼𝑉, obteniendo 𝜋𝑓𝑖𝑛. Figura 6.5. Pasos de la heurística CLM-V. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 39 7. METAHEURÍ STÍCAS PROPUESTAS Las heurísticas presentadas en el capítulo anterior pretendían encontrar buenas soluciones utilizando tiempos computacionales pequeños, con el fin de obtener soluciones rápidas que además pudieran usarse como soluciones iniciales de metaheurísticas más complejas. Sin embargo, no dejan de ser algoritmos deterministas que siempre emplean el mismo tiempo y llegan a idénticos resultados. Con el fin de ampliar las posibilidades de búsquedas de óptimos locales, se plantea un nuevo algoritmo de generación de secuencias iniciales, basado en explicado en el capítulo 4 pero que incluye cierta aleatoriedad. Esto, además, hace que las metaheurísticas que se plantean en este capítulo puedan llegar a mejores resultados si se ejecutan durante más tiempo, a diferencia de lo que ocurría con todas las propuestas hasta este punto. 7.1. Algoritmo de generación de secuencia iniciales alternativas (ISA-GRASP) Dada la complejidad del problema, se presenta un procedimiento de búsqueda GRASP (Greedy Randomized Adaptative Search Procedure) para resolverlo. Este tipo de procedimientos fueron propuestos por primera vez por Feo y Resende (1989), y desde entonces se han aplicado frecuentemente en problemas de optimización. Festa y Resende (2001) realizaron una revisión de los distintos usos de estos algoritmos. El algoritmo ISA-GRASP es similar al ISA original ya explicado en el capítulo 4, con la diferencia de que en lugar de seleccionar el trabajo con menor valor del índice en cada iteración, escoge aleatoriamente uno de los dos elementos con menor índice. Es decir, se adapta parte del algoritmo ISA para integrarlo en una GRASP. Entrada: datos del problema (𝑚,𝑛,𝑝𝑖𝑗) Salida: secuencia inicial de trabajos (𝑠𝑒𝑐𝐼𝑁𝐼) Se define 𝑈: conjunto de trabajos aún no secuenciados, inicialmente {1,2,…,𝑛} 𝐹𝑜𝑟 𝑘 =1 𝑡𝑜 (𝑛 − 1) 𝐹𝑜𝑟 ∀ 𝑗∈ 𝑈 Insertar el trabajo 𝑗 en la posición 𝑘 de 𝑠𝑒𝑐𝐼𝑁𝐼, y el trabajo artificial en la 𝑘+1 𝑖𝑛𝑑𝑗=(𝑛−𝑘)∗𝐶𝐼+𝐹𝐼 Identificar los dos trabajos con menor 𝑖𝑛𝑑𝑗, y seleccionar uno de ellos aleatoriamente Insertar el trabajo seleccionado en la posición 𝑘 de 𝑠𝑒𝑐𝐼𝑁𝐼, y extraerlo de 𝑈 Insertar el único trabajo restante en el conjunto 𝑈 en la posición 𝑛 de 𝑠𝑒𝑐𝐼𝑁𝐼 Figura 7.1. Pseudocódigo del algoritmo ISA-GRASP. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 40 Al aplicar el algoritmo ISA en el problema ejemplo con los tiempos de proceso que se muestran en la Tabla 4.1, cuando se quería hallar el primer elemento de la secuencia inicial se calculaba el índice correspondiente a cada uno de ellos a partir de sus tiempos ociosos actuales y futuros, y se seleccionaba el trabajo 4 por ser el de menor índice, como demuestra la Tabla 4.2 o la Tabla 7.1. Tabla 7.1. Cálculo de los tiempos ociosos y del índice para cada uno de los trabajos, y selección del primer trabajo de una secuencia inicial con aleatoriedad. Sin embargo, el ISA-GRASP escoge aleatoriamente entre los dos trabajos con menor índice, es decir, entre 4 y 1. A priori no hay evidencia que asegure que este algoritmo vaya a lograr mejores resultados que el ISA, pero sí va a permitir obtener secuencias iniciales distintas en cada aplicación, algo en lo que se basan las metaheurísticas propuestas a continuación. Las metaheurísticas propuestas en este capítulo se basan en la repetición de una serie de pasos, partiendo en cada iteración de una secuencia inicial diferente, lo que teóricamente permite llegar a múltiples óptimos locales, pudiendo elegir el mejor de todos ellos. No obstante, todas ellas tienen unos primeros pasos en los que se trabaja con la secuencia inicial original obtenida mediante el algoritmo ISA, para así asegurar rápidamente una referencia a la cual intentar mejorar. 7.2. Metaheurística MH-I En esta primera metaheurística, a cada secuencia inicial generada mediante el algoritmo ISA-GRASP se le aplica la técnica NEHLOC. Y tras alcanzar el criterio de parada definido, a la mejor secuencia obtenida hasta el momento se le aplican otras dos técnicas de búsquedas local más: insFB y swapFB. 1. Se obtiene la secuencia 𝜋0 mediante el algoritmo de secuencia inicial (ISA). 2. Se aplica la técnica NEHLOC a 𝜋0, obteniendo la secuencia 𝜋𝐼. 3. Se aplica la técnica insFB a 𝜋𝐼, obteniendo la secuencia 𝜋𝐼𝐼. 4. Se define una secuencia referencia 𝜋𝑟𝑒𝑓, por ahora igual a 𝜋𝐼𝐼. 5. Si 𝜋𝐼𝐼 no mejora a 𝜋𝐼, se salta directamente al paso 9. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 41 6. Se aplica la técnica NEHLOC a 𝜋𝐼𝐼, obteniendo la secuencia 𝜋𝐼𝐼𝐼, que pasa a ser 𝜋𝑟𝑒𝑓. 7. Si 𝜋𝐼𝐼𝐼 no mejora a 𝜋𝐼𝐼, se salta directamente al paso 9. 8. Se aplica la técnica insFB a 𝜋𝐼𝐼𝐼, obteniendo la secuencia 𝜋𝐼𝑉, que pasa a ser 𝜋𝑟𝑒𝑓. 9. Se aplica la técnica swapFB a 𝜋𝑟𝑒𝑓, obteniendo la secuencia 𝜋𝐿𝐵. 10. Determinar el valor de la variable 𝑥, que determina el criterio de parada. 11. Fijar la variable𝑖 =1. 12. Se genera una secuencia inicial usando el algoritmo ISA-GRASP,𝜋𝑖𝑛𝑖−𝑖. 13. Se aplica a 𝜋𝑖𝑛𝑖−𝑖 la técnica NEHLOC, obteniendo la secuencia 𝜋𝑛𝑒ℎ−𝑖. 14. Aumentar en 1 el valor de 𝑖. Si 𝑖 ≤𝑥, volver al paso 12. 15. Se conserva sólo la mejor secuencia de todas las 𝑥 secuencias obtenidas en el paso 13, descartándose las restantes. La secuencia obtenida se renombra como 𝜋𝑛𝑒ℎ 16. Se aplica la técnica insFB a la secuencia 𝜋𝑛𝑒ℎ, obteniendo la secuencia 𝜋𝑖𝑛𝑠. 17. Se aplica la técnica swapFB a la secuencia 𝜋𝑖𝑛𝑠, obteniendo la secuencia 𝜋𝑠𝑤𝑎𝑝. 18. Se comparan las secuencias 𝜋𝑠𝑤𝑎𝑝 y 𝜋𝐿𝐵, siendo la mejor de ellas𝜋𝑓𝑖𝑛. Figura 7.2. Pasos de la metaheurística MH-I. El criterio de parada escogido es el número de iteraciones realizadas, es decir, el parámetro 𝑥 representa la cantidad de secuencias iniciales generadas mediante el algoritmo ISA-GRASP. Es posible usar algún otro, como el tiempo computacional empleado, pero por simplicidad se decide usar el número de iteraciones. 7.3. Metaheurística MH-II La diferencia con respecto a la anterior es que en ésta la técnica insFB es aplicada en cada una de las iteraciones, antes de descartar ninguna secuencia. Finalmente, a la mejor de todas las secuencias que se han obtenido se le aplica la swapFB, de igual forma que en MH-I. 1. Se obtiene la secuencia 𝜋0 mediante el algoritmo de secuencia inicial (ISA). 2. Se aplica la técnica NEHLOC a 𝜋0, obteniendo la secuencia 𝜋𝐼. 3. Se aplica la técnica insFB a 𝜋𝐼, obteniendo la secuencia 𝜋𝐼𝐼. 4. Se define una secuencia referencia 𝜋𝑟𝑒𝑓, por ahora igual a 𝜋𝐼𝐼. 5. Si 𝜋𝐼𝐼 no mejora a 𝜋𝐼, se salta directamente al paso 9. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 48 Tabla 8.5. RPD y tiempo computacional empleado por la heurística CFI en las 120 instancias. Como se podría esperar, en las instancias de mayor tamaño se requiere un tiempo computacional superior, sufriendo éste un crecimiento exponencial proporcional al número de trabajos a procesar. Por otra parte, el número de máquinas tiene una influencia mucho menor, como se aprecia, por ejemplo, en los resultados de las instancias 91-100 (de 200 trabajos y 10 máquinas) y 101-110 (de 200 trabajos y 20 máquinas). Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 49 Sobre la mejora relativa con respecto a la secuencia ISA, se observa una clara relación con el número de máquinas en el taller, pues en instancias donde hay más máquinas no se mejora tanto la secuencia inicial como cuando éste es menor, sucediendo esto para instancias con distintas cantidades de trabajos a procesar. Por tanto, se demuestra que el algoritmo ISA original aporta mejores soluciones cuando el número de máquinas en el taller es mayor. A continuación, en la Tabla 8.6 se muestran los resultados obtenidos con la heurística CFI interrumpido, un proceso con el que, como ya se explicó al final del capítulo 4, se logran exactamente los mismos valores del TCT pero empleando un menor tiempo computacional que con CFI, pues se da por finalizado cuando se encuentra el óptimo local. Tabla 8.6. ARPD y tiempo computacional medio de la heurística CFI interrumpido agrupado por instancias. Evidentemente, la mejora media del TCT respecto al de la secuencia inicial se mantiene en el 2.07 %, pero el tiempo computacional empleado se reduce hasta la cuarta parte de lo que era con la heurística CFI original. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 50 8.2. Técnicas de búsqueda local Con el fin de presentar los datos de forma clara, se adjunta directamente la Tabla 8.7, en la que se observa la mejora relativa y el tiempo computacional medio para las 120 instancias al aplicar a la secuencia inicial cada una de las diez técnicas de búsqueda local explicadas en el capítulo 5. En el anexo B se pueden consultar los resultados de cada técnica por separado para los distintos tamaños de problema. Tabla 8.7. ARPD y tiempo computacional medio de las diez técnicas de búsqueda local consideradas. Con la tabla anterior, queda demostrado que los diferentes criterios de actuación al encontrar una secuencia vecina mejor (BEST, FIRST, FIRST BEST) no influyen en el valor de la función objetivo de la secuencia final, pero sí en el tiempo que se tarda en hallarla, siendo las FIRST BEST claramente las más rápidas en todos los casos. Por otra parte, las técnicas de inserción completa de trabajos parecen ser las que mayores mejoras consiguen. Es por ello que siempre se incluye la técnica insFB en los algoritmos presentados a partir del capítulo 6. También se considera la swapFB al tratarse de una técnica de búsqueda diferente que puede hallar otros óptimos locales sin ralentizar excesivamente el proceso. Por su parte, la NEHLOC demuestra ser una heurística extremadamente rápida y que también logra grandes mejoras, por lo que es el tercero de los diez métodos de búsquedas locales que se usan para construir los algoritmos propuestos, no usándose ninguno de los siete restantes. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 51 8.3. Heurísticas propuestas En primer lugar, se comparan los resultados obtenidos con las dos primeras heurísticas propuestas, que obviamente emplean el mismo tiempo computacional, pues se componen de las mismas técnicas, sólo que aplicadas en distinto orden. Tabla 8.8. ARPD y tiempo computacional medio de las heurísticas propuestas CML-I y CML-II. Se observa en la Tabla 8.8 que para la mayoría de tamaños de problema, y por tanto también en término medio, la segunda heurística consigue resultados claramente mejores que la primera, por lo que se demuestra que la técnica NEHLOC debe aplicarse antes que la insFB, información que se tiene en cuenta al construir los algoritmos posteriores. Sabiendo que la NEHLOC ha de aplicarse en primer lugar, en la Tabla 8.9 se estudia en qué orden es mejor aplicar las otras dos técnicas consideradas: insFB y swapFB. De nuevo, el tiempo computacional empleado por ambas heurísticas es idéntico, y se demuestra que es ligeramente más favorable aplicar la insFB antes que la swapFB, de ahí que en todos los algoritmos posteriores la swapFB sea la última técnica que se aplique. La quinta heurística propuesta necesita más tiempo para ejecutarse en comparación a las anteriores porque aplica en dos ocasiones la técnica NEHLOC, cuatro veces la insFB y una la swapFB. Aunque atendiendo a la Tabla 8.10, los resultados mejoran con respecto a las anteriores. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 52 Tabla 8.9. ARPD y tiempo computacional medio de las heurísticas propuestas CML-III y CML-IV. Tabla 8.10. ARPD y tiempo computacional medio de la heurística propuesta CML-V. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 53 8.4. Metaheurísticas propuestas Se muestran en la Tabla 8.11 los resultados obtenidos por el algoritmo MH-I realizando 5, 10, 50 y 100 iteraciones. Tabla 8.11. ARPD y tiempo computacional medio de la metaheurística propuesta MH-I para x=5, x=10, x=50, x=100. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 54 Como se podía deducir, aplicar un mayor número de iteraciones hace que el tiempo computacional empleado crezca. Y también se logran mejores resultados, algo que realmente no tiene por qué ser siempre así, ya que éstos dependen de las secuencias iniciales generadas en cada caso. La principal debilidad de esta heurística es que descarta muchas secuencias que podrían aportar buenos resultados una vez se les aplica las técnicas insFB y swapFB, pero que no sobreviven al paso 15 del proceso (Figura 7.2), ya que tras él sólo se conserva una secuencia, de la cual no hay ninguna certeza de que vaya a mejorar considerablemente tras los pasos 16 y 17. La heurística MH-II no descarta tantas secuencias de forma prematura, y teóricamente asegura una secuencia final al menos igual de buena que la obtenida con MH-I a igual número de iteraciones (algo que realmente no tiene por qué cumplirse siempre debido a la aleatoriedad existente al generar las secuencias iniciales). Sin embargo, emplea un tiempo considerablemente mayor, pues la técnica insFB se aplica tantas veces como secuencias iniciales se generen, mientras que en la MH-I apenas se aplicaba en una ocasión. Tabla 8.12. ARPD y tiempo computacional medio de la metaheurística propuesta MH-II para x=5 y x=10. El algoritmo MH-III, al consistir en un híbrido entre los dos anteriores, consigue resultados no tan buenos como los de MH-II a igualdad de secuencias iniciales distintas generadas, pero en un tiempo claramente menor. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 55 Tabla 8.13. ARPD y tiempo computacional medio de la metaheurística propuesta MH-III para cuatro combinaciones de parámetros distintas. Observando las Tablas 8.12 y 8.13, se aprecia lo importante del hecho de que en la MHIII sólo se intente profundizar en las iteraciones que son más prometedoras tras los primeros pasos, pues lo que ralentiza tanto a la MH-II es que se aplican las técnicas insFB y swapFB 𝑥 veces cada una, mientras que en la MH-III sólo en 𝑦 ocasiones. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 56 8.5. Parametrización de la metaheurística propuesta MH-III Al ser un algoritmo doblemente parametrizable, se plantean numerosas combinaciones de los dos parámetros: 𝑥, 𝑧. No obstante, se da el caso de que distintas combinaciones resulten en el mismo problema, ya que, como se observa en la Tabla 8.14, cualquier valor de 𝑧 menor de 20 cuando 𝑥 =5 hace que sólo se cuente con la mejor de las cinco secuencias obtenidas para la parte final del algoritmo. Por ello, a pesar de plantear hasta 42 posibles combinaciones, realmente sólo se tienen 34 distintas. Tabla 8.14. Valores propuestos para los parámetros del problema: x, z; así como el valor de y en cada caso. En las Tablas 8.15 y 8.16 se observa el ARPD y tiempo computacional empleado por la metaheurística MH-III para cada uno de los 34 casos planteados. Tabla 8.15. ARPD de la metaheurística propuesta MH-III para los 34 casos planteados según x, z. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 57 Tabla 8.16. Tiempo computacional medio empleado por la metaheurística propuesta MH-III para los 34 casos planteados según x, z. Como ya se comentó en el capítulo 7 al definir el algoritmo, se demuestra que aumentar el valor de los parámetros (generar más secuencias iniciales distintas y/o guardar una mayor cantidad de ellas de cara a la parte final del algoritmo) incrementa notablemente el tiempo computacional que emplea la metaheurística, aunque también logra mejorar los resultados obtenidos. Esta relación se plasma en la Figura 8.2, en la que se representan los resultados de los 34 problemas planteados. Figura 8.2. Representación gráfica del ARPD y tiempo computacional de la metaheurística propuesta MH-III para los 34 problemas planteados. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 64 9. CONCLUSÍONES Tratar de encontrar buenas soluciones para problemas de taller de flujo regular es algo habitualmente analizado, pues la adecuada secuenciación de los trabajos tratados en dichos escenarios es de vital importancia competitiva y económica para las empresas que gestionan esta clase de situaciones. En este caso concreto, en el que el problema particular que se estudia es un permutation flow shop problem (PFSP) al que se le aplica la restricción no-wait y en el que se intenta minimizar el tiempo total de finalización (TCT), se realiza una revisión previa de otros artículos que tratan dicho problema, con el fin de identificar los procesos y métodos de resolución referentes hasta el momento. Una vez identificada la heurística referencia, se ejecuta para 120 instancias estandarizadas habituales a la hora de comparar distintos procesos, guardándose los resultados obtenidos con ellas así como el tiempo empleado en hallarlos. Con esta información, ya se está en disposición de probar los algoritmos propuestos y poder compararlos. Esta heurística referencia consiste en una rápida generación de una secuencia inicial de trabajos, paso del que parten todos los algoritmos propuestos, pues se demuestra que es un muy buen punto de partida; y posteriormente en un proceso iterativo de mejora de dicha secuencia inicial, que si bien consigue mejorarla generalmente, emplea demasiado tiempo, y es eso lo que se trata de evitar con los algoritmos propuestos. En primer lugar, se plantean técnicas básicas de búsqueda local, cuyos resultados permiten decidir con cuáles de ellas se plantean los algoritmos posteriores. Las heurísticas, que simplemente combinan algunas de las técnicas anteriores, ya se acercan bastante a los resultados de la heurística referencia, empleando un tiempo mucho menor. Por último, se plantean unas metaheurísticas basadas en procedimientos GRASP, que además son parametrizables, por lo que permiten decidir en cada situación si centrarse en lograr el mejor resultado posible o simplemente en lograr uno bueno en poco tiempo. Basándose en las conclusiones extraídas al analizar los resultados de todos los algoritmos planteados previamente, se propone el algoritmo MH-III, con el que se mejora un 0,43% los resultados obtenidos por la heurística referencia empleando el mismo tiempo que ella. Mediante un análisis estadístico, se demuestra que dicha diferencia es significativa, probando así que realmente se encuentran mejores secuencias usando la metaheurística propuesta en este documento. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 65 REFERENCÍAS Framinan, J. M., Leisten, R., Ruiz, R. (2014) “Manufacturing Scheduling Systems. An integrated view on Models, Methods and Tools”. Editorial Springer. Ruiz, R. and Stüztle, T. (2007) “A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem”. European Journal of Operational Research. Pinedo, M. (2012) “Scheduling.Theory, Algorithms, and Systems”. Editorial Springer. Shyu, S. J., Lin, B. M., Yin, P.-Y. (2004) “Application of ant colony optimization for no-wait flowshop scheduling problems to minimize the total completion time”. Computers & Industrial Engineering. Garey, M. R., Johnson, D. S., Sethi, R. (1976) “The complexity of flowshop and jobshop scheduling”. Mathematics of operations research, 1(2), 117-119 Graham, R. L., Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G. (1979) “Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey”. Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium. Editorial Elseiver. Stafford Jr, E. F., Tseng, F. T., Gupta, J. N. D. (2005) “Comparative evaluation of MILP flowshop models”. Journal of the Operational Research Society, 56, 88-101. Lin, S.-W., Ying, K.-C. (2016) “Optimization of makespan for no-wait flowshop scheduling programs using different metaheuristics”. Omega, 64, 115 - 125. Rajendran, C., Chaudhuri, D. (1990) “Heuristics algorithms for continuous flow-shop problem”. Naval Research Logistics (NRL), 37(5), 695 - 705. Aldowaisan, T., Allahverdi, A. (2004) “New heuristics for m-machine no-wait flowshop to minimize total completion time”. Omega, 32(5), 345 - 352. Chen, C.-L., Neppalli, R. V., Aljaber, N. (1996) “Genetic algorithms applied to the continuous flow shop problem”. Computers & Industrial Engineering, 30(4), 919 - 929. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 66 Framinan, J. M., Nagano, M. S., Moccellin, J. V. (2010) “An efficient heuristic for total flowtime minimization in no-wait flowshops”. The International Journal of Advanced Manufacturing Technology, 46 (9 - 12), 1049 – 1057. Laha, D., Chakraborty, U. K. (2009) “A constructive heuristic for minimizing makespan in nowait flow shop scheduling”. The International Journal of Advanced Manufacturing Technology, 41 (1 - 2), 97 – 109. Gao, K., Pan, Q., Suganthan, P, Li, J. (2013) “Effective heuristics for the no-wait flow shop scheduling problem with total flow time minimization”. The International Journal of Advanced Manufacturing Technology, 66 (9 - 12), 1563 – 1572. Gao, K., Pan, Q., Li, J. (2011) “Discrete harmony search algorithm for the no-wait flow shop scheduling problem with total flow time criterion”. The International Journal of Advanced Manufacturing Technology, 56 (5 - 8), 683 – 692. Bertolissi, E. (2000) “Heuristic algorithm for scheduling in the no-wait flow-shop”. Journal of Materials Processing Technology, 107(1), 459 – 465. Nawaz, M., Enscore, E. E., Ham, I. (1983) “A heuristic algorithm for the m.machine, n-job flow-shop sequencing problem”. Omega, 11(1), 91 – 95. Akhshabi, M., Tavakkoli-Moghaddam, R., Rahnamay-Roodposhti, F. (2014) “A hybrid particle swarm optimization algorithm for a no-wait flow shop scheduling problem with the total flow time”. The International Journal of Advanced Manufacturing Technology, 70(5 – 8), 1181 – 1188. Laha, D., Sapkal, S. U. (2014) “An improved heuristic to minimize total flow time for scheduling in the m-machine no-wait flow shop”. Computers & Industrial Engineering, 67, 36 – 43. Ye, H., Li, W., Abedini, A., Nault, B. (2017) “An effective and efficient heuristic for no-wait flow shop production to minimize total completion time”. Computers & Industrial Engineering, 108, 57 – 69. Liu, J., Reeves, C. R. (2001) “Constructive and composite heuristic solutions to the P||∑𝐶𝑖 scheduling problem”. European Journal of Operational Research, 132, 439 – 452. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 67 Fernandez-Viagas, V., Framinan, J. M. (2015) “A new set of high-performing heuristics to minimise flowtime in permutation flowshops”. Computers and Operations Research, 53, 68 – 80. Fernandez-Viagas, V., Dios, M., Framinan, J. M. (2016) “Efficient constructive and composite heuristics for the Permutation Flowshop to minimise total earliness and tardiness”. Computers and Operations Research, 75, 38 – 48. Framinan, J. M., Perez-Gonzalez, P. (2017) “The 2-stage assembly flowshop scheduling problem with total completion time: Efficient constructive heuristic and metaheuristic”. Computers and Operations Research, 88, 237 – 246. Zhu, X., Li, X. (2015) “Iterative search method for total flowtime minimization no-wait flowshop problem”. International Journal of Machine Learning and Cybernetics, 6(5), 747 – 761. Qi, X., Wang, H., Zhu, H., Zhang, J., Chen, F., Yang, J. (2016) “Fast local neighborhood search algorithm for the no-wait flow shop scheduling with total flow time minimization”. International Journal of Production Research, 54(16), 4957 – 4972. Bewoor, L. A., Prakash, V. C., Sapkal, S. U. (2017) “Comparative analysis of metaheuristics approaches for makespan minimization for no wait flow shop scheduling problem”. International Journal of Electrical and Computer Engineering. Lin, S.-W., Ying, K.-C. (2016) “Optimization of makespan for no-wait flowshop scheduling problems using efficient matheuristics”. Omega, 64, 115 – 125. Zhao, F., Liu, H., Zhang, Y., Ma, W., Zhang, C. (2018) “A discrete Water Wave Optimization algorithm for no-wait flow shop scheduling problem”. Expert Systems with Applications. Riyanto, O. A. W., Santosa, B. (2015) “ACO-LS algorithm for solving no-wait flow shop scheduling problem”. Communications in Computer and Information Science. Ruiz, R., Allahverdi, A. (2009) “New heuristics for no-wait flow shops with a linear combination of makespan and maximum lateness”. International Journal of Production Research. Ye, S., Zhao, N., Li, K., Lei, C. (2017) “Efficient heuristics for solving non-permutation flowshop scheduling problems with maximal and minimal time lags”. Computers & Industrial Engineering. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 68 Samarghandi, H., Behroozi, M. (2017) “On the exact solution of the no-wait flow shop problem with due date constraints”. Computers and Operations Research. Feo, T. A., Resende, M. G. C. (1989) “A probabilistic heuristic for a computationally difficult set covering problem”. Operations Research Letters, vol. 8, no. 2, pp. 67-71. Festa, P., Resende, M. G. C. (2001) “GRASP: An Annotated Bibliography”. Kluwer Academic Publishers, pp. 325-367, Boston, Mass, USA. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 69 ANEXOS A. Análisis estadístico. Contraste de hipótesis. Atendiendo a las Tablas 8.18 y 8.19, se aprecia que generalmente se obtienen mejores resultados aplicando la metaheurística MH-III que con la heurística referencia CFI, pues en 90 de las 120 instancias el TCT de la solución hallada con la primera es menor, siendo éste, en término medio, un 0,43 % inferior. No obstante, con el fin de poder asegurar con una cierta confianza que realmente se logran mejores soluciones con la metaheurística MH-III, se realiza un análisis estadístico usando el software SPSS. Dicho análisis consiste en una prueba t de Student para muestras relacionadas, que en este caso consisten en los 120 valores del indicador RPD para cada una de las instancias de Taillard, tanto para la heurística CFI como para la MH-III. Se puede observar que los valores de la variable RPD_CFI en la Tabla A.1 son los que aparecían en las Tablas 8.3 y 8.5. Tabla A.1. Extracto de las dos muestras a las que se realiza el análisis estadístico. Los resultados del análisis permiten aceptar o rechazar las hipótesis planteadas a continuación: Hipótesis nula (𝐻0): La metaheurística MH-III no logra encontrar soluciones con un TCT menor que las que se obtenían usando la heurística referencia CFI. Hipótesis alternativa (𝐻1): Siguiendo la metaheurística MH-III se obtienen secuencias mejores que las halladas usando la heurística referencia CFI. 𝐻0∶ 𝜇𝑅𝑃𝐷_𝑀𝐻𝐼𝐼𝐼 ≥ 𝜇𝑅𝑃𝐷_𝐶𝐹𝐼 𝐻1∶ 𝜇𝑅𝑃𝐷_𝑀𝐻𝐼𝐼𝐼 < 𝜇𝑅𝑃𝐷_𝐶𝐹𝐼 Cabe recordar que, según cómo se definió el RPD, un valor más negativo implica una secuencia final con menor TCT, y por tanto, mejor. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 70 Por cómo se ha definido, se trata de un t-Test unilateral, ya que sólo se busca confirmar que con la metaheurística MH-III se obtienen resultados mejores que con CFI. De ahí que, como se aprecia en la Figura A.1, se define un porcentaje del intervalo de confianza del 97,5 % aunque se busque un nivel de confianza del 95 %. Figura A.1. Configuración del t-Test para muestras relacionadas efectuado. Tras llevar a cabo el análisis, se obtienen los resultados presentados en la Figura A.2. Figura A.2. Resultados del t-Test para muestras relacionadas efectuado. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 71 La primera tabla muestra, como ya se observaba en la Tabla 8.18, que la media del RPD para el MH-III es sensiblemente superior (en valor absoluto) a la de la heurística referencia. En la segunda se confirma que ambas variables están muy relacionadas, cuya interpretación es que, como ambos algoritmos parten de la misma secuencia inicial (la que determina el algoritmo ISA), si dicha secuencia no es excesivamente buena, ambos la van a mejorar holgadamente, aunque no terminen llegando a la misma secuencia final. La tercera tabla es la que confirma que sí hay una diferencia sustancial entre las mejoras logradas por ambos indicadores, y la que permite afirmar con un 95% de confianza que el algoritmo MH-III encuentra soluciones con un menor TCT que la heurística CFI. El valor de la t de 6,333 (claramente mayor que el presente en la Tabla A.2 para los casos con 120 grados de libertad y α en torno al 2,5 %), así como la no inclusión del cero en el intervalo de confianza de la diferencia entre los RPD, confirma el rechazo de la hipótesis nula, y por tanto la aceptación de la alternativa. Tabla A.2. Tabla de la distribución t de Student. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 72 B. Resultados detallados de las técnicas de búsqueda local En la Tabla 8.7 se indicaba el ARPD y el tiempo computacional empleado medio de cada una de las diez técnicas de búsqueda local para las 120 heurísticas. A continuación se adjuntan los resultados obtenidos por cada una de ellas para cada uno de los grupos de instancias de Taillard, dependiendo del tamaño de las mismas. Tabla B.1. ARPD y tiempo computacional medio, agrupados por instancias, de las técnicas de búsqueda local de intercambio de trabajos. Tabla B.2. ARPD y tiempo computacional medio, agrupados por instancias, de las técnicas de búsqueda local de inserción completa de trabajos. Algoritmos aproximados para minimizar el tiempo total de finalización en talleres de flujo sin esperas 73 Tabla B.3. ARPD y tiempo computacional medio, agrupados por instancias, de las técnicas de búsqueda local de inserción hacia delante de trabajos. Tabla B.4. ARPD y tiempo computacional medio, agrupados por instancias, de la técnica de búsqueda local NEHLOC.