Programación de operaciones en flujo uniforme con fechas de comienzo

Equation Chapter 1 Section 1 Trabajo'Fin'de'Grado' Grado en Ingeniería de las Tecnologías Industriales ' Programación de operaciones en flujo uniforme con fechas de comienzo Autor: Guillermo Díaz – Toledo Álvarez Tutor: José Manuel Framiñán Torres Dpto. de Organización Industrial y Gestión de Empresas Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2018 ' ' ii' iii' Trabajo Fin de Grado Grado en Ingeniería de las Tecnologías Industriales Programación de operaciones en flujo uniforme con fechas de comienzo Autor: Guillermo Díaz – Toledo Álvarez Tutor: José Manuel Framiñán Torres Catedrático de Universidad Dpto. de Organización Industrial y Gestión de Empresas Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2018 ' ' iv' v' Trabajo Fin de Grado: Programación de operaciones en flujo uniforme con fechas de comienzo Autor: Guillermo Díaz – Toledo Álvarez Tutor: José Manuel Framiñán Torres El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2018 El Secretario del Tribunal ' ' vi' vii' RESUMEN En este Trabajo de Fin de Grado se aborda el problema de la programación de trabajos en flujo uniforme con fechas de comienzo, también conocido como flowshop scheduling with release dates. Se realizará una revisión de los conceptos fundamentales y de los distintos métodos aproximados para resolver estos problemas. Por último, se adaptarán y evaluarán los distintos métodos, analizando la influencia de los parámetros, la calidad de las soluciones obtenidas y los tiempos de ejecución. ' ' viii' ix' ABSTRACT This work aims to solve the flowshop scheduling problem with release dates. Firstly, a review of the main concepts and approximate methods to solve these problems will be conducted. Finally, the methods will be adapted and evaluated, analysing the influence of the parameters, the solutions’ quality and the runtimes. ' ' xvi' Figura 8. Esquema de las fases de destrucción y construcción. [Fuente: Pan Q-K, Tasgetiren M, Liang Y-C. A discrete differential evolution algorithm for the permutation flowshop scheduling problem. Comput Ind Eng 2008;55(4):795–816.] 19 Figura 9. Referenced insertion scheme. [Fuente: Pan Q-K, Tasgetiren M, Liang Y-C. A discrete differential evolution algorithm for the permutation flowshop scheduling problem. Comput Ind Eng 2008;55(4):795–816.] 20 Figura 10. Diagrama del algoritmo IGRIS. [Fuente: Pan Q-K, Tasgetiren M, Liang Y-C. A discrete differential evolution algorithm for the permutation flowshop scheduling problem. Comput Ind Eng 2008;55(4):795–816.] 21 Figura 11. Pseudocódigo de NEH al aplicar TBFF. [Fuente: Fernandez-Viagas, V. & Framinan, J.M., 2014. On insertion tie-breaking rules in heuristics for the permutation flowshop scheduling problem. Computers & Operations Research, 45, pp.60–67.] 23 Figura 12. Diagrama del algoritmo MGS. [Fuente: Ren, T. et al., 2015. A Local Search Algorithm for the Flow Shop Scheduling Problem with Release Dates. Discrete Dynamics in Nature and Society, 2015, pp.1–8.] 25 Figura 13. ARPD de cada método en función de las características de los problemas. 36 Figura 14. RPD del método DSJF en función de las características de los problemas. 37 Figura 15. RPD del método IGRIS(TBFF) en función de las características de los problemas. 38 Figura 16. RPD del método iMGS en función de las características de los problemas. 38 Figura 17. RPD del método NEH en función de las características de los problemas. 39 Figura 18. RPD del método NEH(TBFF) en función de las características de los problemas. 39 Figura 19. Diferencia de rendimiento máxima, mínima y media entre NEH y NEH(TBFF) en función de las características de los problemas. 41 Figura 20. Diferencia de rendimiento media entre NEH y NEH(TBFF) y porcentaje de problemas en los que cada método es superior. 42 Figura 21. Diferencia de rendimiento media y diferencia entre el porcentaje de problemas en los que cada método es superior. 43 xvii' Figura 22. Efecto de Rt. 44 Figura 23. Efecto de Rt en el método DSJF. 45 Figura 24. Efecto de Rt en el método IGRIS(TBFF). 46 Figura 25. Efecto de Rt en el método iMGS. 46 Figura 26. Efecto de Rt en el método NEH. 47 Figura 27. Efecto de Rt en el método NEH(TBFF). 48 Figura 28. Rendimiento de los métodos NEH y NEH(TBFF) en función de los valores de Rt. 49 Figura 29. Diferencias de rendimiento máximas, mínimas y medias de los métodos NEH y NEH(TBFF) en función de los valores de Rt. 49 Figura 30. Diferencia de rendimiento media y diferencia entre el porcentaje de problemas en los que cada método es superior para Rt = 0,5. 50 Figura 31. Diferencia de rendimiento media y diferencia entre el porcentaje de problemas en los que cada método es superior para Rt = 1. 51 Figura 32. Diferencia de rendimiento media y diferencia entre el porcentaje de problemas en los que cada método es superior para Rt = 5. 52 Figura 33. ARPD de cada método en función del número de trabajos y máquinas. 53 Figura 34. Efecto del número de trabajos y máquinas en el método DSJF. 54 Figura 35. Efecto del número de trabajos y máquinas en el método IGRIS(TBFF). 54 Figura 36. Efecto del número de trabajos y máquinas en el método iMGS. 55 Figura 37. Efecto del número de trabajos y máquinas en el método NEH. 55 Figura 38. Efecto del número de trabajos y máquinas en el método NEH(TBFF). 56 1 1 INTRODUCCIÓN Y OBJETIVOS DEL TRABAJO La correcta programación de las operaciones supone, especialmente en el sector industrial, unas considerables reducciones de los plazos de entrega al igual que notables incrementos en la productividad y eficiencia de las empresas, que pueden ser necesarias para la supervivencia empresarial en un entorno de alta competitividad. Algunos ejemplos serían la producción de vehículos, el ensamblaje de productos tecnológicos u otros problemas no industriales como la gestión de las puertas de embarque en los aeropuertos, obras civiles o las mercancías de un puerto. Uno de los problemas de programación de la producción más conocidos es la programación de trabajos en flujo uniforme, ya que es la configuración más extendida en la industria y en la mayoría de los casos en los que no se da, es esta una aproximación razonable. Dentro de este tipo de problemas es habitual que cada uno de los trabajos tenga una fecha de comienzo, a partir de la cual este está disponible para ser realizado, en muchos casos esto es debido a la necesidad de recibir las piezas necesarias de un proveedor. 1.1 Objetivos Mediante la realización de este trabajo se persigue la identificación de los algoritmos más eficientes para la minimización del tiempo necesario para completar una serie de trabajos en flujo uniforme con fechas de comienzo distintas del instante inicial. Para ello, se adaptaron uno de los mejores algoritmos para el caso en el que las fechas de comienzo son todas el instante cero, propuesto por Víctor Fernández - Viagas y José Manuel Framiñán (Fernández – Viagas, Framiñán, 2014), y el algoritmo en el que este está basado, propuesto por Muhammad Nawaz, E. Emory Enscore Jr. y Inyong Ham (Nawaz, Enscore, Ham, 1983). Los resultados de estos se compararon con los de las recientes contribuciones de Danyu Bai y Lixin Tang (Bai, Tang, 2009) y Tao Ren, Meiting Guo, Lin Lin y Yunhui Miao (Ren et al., 2015). 2 Introducción y objetivos del trabajo Los métodos a comparar se implementaron en el lenguaje de programación C++, como se indica en la Sección 4.1. Posteriormente, Capítulo 5, se analizarán los resultados obtenidos, utilizando las herramientas del programa Microsoft Excel, comparando la eficiencia de los métodos antes mencionados. Para ello se compararán los tiempos de ejecución y las calidades de las soluciones obtenidas por cada uno de ellos en función de los distintos parámetros del problema. 1.2 Justificación El ahorro de tiempo, y por tanto de costes, que aporta una adecuada programación de las operaciones hace que el estudio de este tipo de problemas sea de gran interés. El hecho de que muchos de estos problemas, y en concreto el que ocupa este trabajo (programación de trabajos en flujo uniforme con fechas de comienzo), sean denominados NP-hard y que por tanto, como se explicara en la Sección 2.3, la ingente cantidad de tiempo y recursos necesarios para la resolución exacta del problema hace que sea necesario desarrollar algoritmos que permitan encontrar resultados suficientemente próximos a la solución óptima del problema en un tiempo adecuado para el uso que se vaya a dar a ese resultado. Figura 1. Relación entre el tiempo necesario para resolver un problema y el tamaño de este en función de su complejidad. [Fuente: Cmglee. commons.wikimedia.org] 3 Programación de operaciones en flujo uniforme con fechas de comienzo 1.3 Estructura Tratando de cumplir con estos objetivos, el trabajo se ha estructurado en los 6 capítulos que se describen a continuación: En el primer capítulo, el presente, se introduce el problema a estudiar, y se justifica su utilidad. Por último, se explica la estructura y los objetivos que se persiguen con la realización de este Trabajo de Fin de Grado. El segundo capítulo presenta y describe el problema sobre el que versa el trabajo y se comentan sus particularidades y las razones por las que es interesante estudiarlo. Previamente, se introducirán los conceptos básicos y se realizará una breve reseña histórica de la disciplina de Programación de la Producción. El capítulo 3 se dedica a presentar y explicar los principios en que se basan los distintos algoritmos/heurísticas a comparar, describiendo los pasos que siguen estos y las modificaciones realizadas a los mismos. También se indicarán las distintas ventajas e inconvenientes que presentan cada uno de ellos. En el capítulo 4 se explica el software utilizado para la realización de los experimentos y el posterior procesado de los resultados. A continuación, se presentarán el conjunto de problemas con el que se probarán y compararán los algoritmos, se asignará y justificará el valor de los parámetros y se describirán los indicadores con los que se compararán los distintos algoritmos. Mediante el quinto capítulo se procede a mostrar y analizar los resultados. Se comparan los resultados obtenidos por los distintos algoritmos al igual que los distintos tiempos de ejecución de cada uno de ellos, analizando la influencia de los parámetros en la calidad de las soluciones obtenidas por cada uno de los métodos. Por último, en el sexto capítulo, se muestran las conclusiones más significativas que se han obtenido tras la realización de este trabajo. 5 2 DESCRIPCIÓN DEL PROBLEMA En este apartado, como se ha comentado en la Sección 1.3, se describirá el problema sobre el que versa este trabajo y previamente se introducirán algunos conceptos importantes que sirven como base de este problema, y por tanto son convenientes para su comprensión. 2.1 Programación de la Producción La programación de la producción, universalmente conocida como scheduling o en castellano secuenciación o programación de operaciones, se puede definir como el proceso de asignar en el tiempo los recursos disponibles con el objetivo de realizar un trabajo en el menor tiempo posible, al mínimo coste y con la mínima utilización de los recursos disponibles (Framiñan, Leisten, Ruíz, 2014). Figura 2. Diagrama de Gantt que muestra la secuencia de un proceso de tipo Flowshop. [Fuente: Ruiz, R., 2015] 6 Descripción del problema Una de las primeras herramientas desarrolladas con el fin de programar y supervisar el desarrollo de trabajos es el diagrama de Gantt, que debe su nombre al ingeniero mecánico y consultor estratégico Henry Laurence Gantt quien en la década de 1910 modificó y popularizó el uso de este tipo de diagramas. Pero fue durante la Segunda Guerra Mundial cuando se produjeron los primeros avances significativos en el campo de la gestión de operaciones, tras el final de la guerra y con la posterior llegada de los primeros ordenadores modernos muchos de los científicos que trabajaron en este campo durante la misma continuaron desarrollando las herramientas y teorías que forman la base sobre la que se sustenta la Investigación Operativa, y concretamente la programación de operaciones, en la actualidad. El aumento del tamaño y la complejidad de los problemas obligó a desarrollar métodos aproximados, que como se verá en las Secciones 2.2 y 2.3 son la forma mas eficiente de resolver determinados problemas. 2.2 Algoritmos “Algoritmo: Conjunto ordenado y finito de operaciones que permite hallar la solución de un problema.” (Diccionario de la lengua española, Real Academia Española) Se trata de una secuencia finita de operaciones bien definidas y ordenadas, con el fin de obtener una solución a un problema. Los algoritmos se pueden clasificar según la precisión de sus soluciones en: • Exactos: Proporcionan la solución óptima o exacta del problema. • Aproximados: Estos se caracterizan por una aproximación intuitiva al problema, que permite encontrar una solución en un menor tiempo, aunque renunciando a la exactitud, a encontrar todas las soluciones o a encontrar una solución óptima o más cercana a esta. Son de gran utilidad dado que la complejidad computacional de muchos problemas hace inviable el uso de algoritmos exactos para resolverlos, por lo que se usan este tipo de algoritmos para obtener soluciones útiles con unos recursos razonables. 7 Programación de operaciones en flujo uniforme con fechas de comienzo También es posible clasificarlos según la aleatoriedad de sus soluciones: • Deterministas: Para unas entradas dadas el algoritmo siempre devolverá la misma solución. • No deterministas o aleatorios: Se caracterizan por que pueden obtener distintas soluciones para un mismo problema. Esto se debe a la introducción de algún factor de aleatoriedad, como puede ser el caso de que la solución dependa de un número generado al azar. Se usa habitualmente cuando la solución es aproximada. 2.3 Complejidad de los algoritmos La forma mas habitual de clasificar los algoritmos según su complejidad es mediante el tiempo necesario para resolverlos en una máquina de Turing. La máquina de Turing es un dispositivo hipotético, definida por el matemático inglés Alan Turing en 1936, que ha resultado de gran utilidad para el desarrollo teórico de la teoría de la complejidad computacional. Según este criterio las clases de algoritmos de más interés son: • Clase P: A esta categoría pertenecen todos los problemas que pueden ser un resueltos en tiempo polinomial por una máquina de Turing determinista. • Clase NP: Esta categoría está formada por todos aquellos problemas que pueden ser resueltos en tiempo polinomial por una máquina de Turing no determinista, o lo que es lo mismo, todos los problemas cuya solución se puede verificar en tiempo polinomial por una máquina de Turing determinista. • Clase NP-hard: Grosso modo pertenecen a esta categoría los problemas con una complejidad mayor o igual que los de la clase NP. • Clase NP-completo: Esta categoría la forman los problemas que siendo de clase NP lo son también de la clase NP-hard. 15 3 DESCRIPCIÓN DE LOS ALGORITMOS En este capítulo se expondrán los distintos algoritmos que se van a comparar en la resolución del problema expuesto en el Capítulo 2. Para ello, en los siguientes apartados se realizará una descripción de los pasos que realizan estos algoritmos para obtener las soluciones de los problemas, se señalarán las características por las que estos destacan y se describirá sucintamente los conceptos en los que están basados. Por último se adaptarán las ecuaciones de la aceleración de Taillard a los problemas con fechas de comienzo. 3.1 NEH Esta heurística, diseñada en 1982 por Muhammad Nawaz, E. Emory Enscore Jr. y Inyong Ham (Nawaz, Enscore, Ham, 1983), a los que debe su nombre, es la base de los que a día de hoy se consideran los mejores algoritmos para la resolución de los problemas de programación de la producción en flujo uniforme con el objetivo de minimizar el makespan (Fm | prmu | Cmax). La complejidad de esta heurística es O(n3m), ya que la complejidad de evaluar el makespan de una determinada secuencia es O(nm) y por tanto la de evaluar cada una de las posiciones que puede ocupar un trabajo en esa secuencia es O(n2m). Como se explicará posteriormente, en la Sección 3.2, aplicando la aceleración de Taillard la complejidad de evaluar cada una de las posiciones que puede ocupar un trabajo en una secuencia se reduce a O(nm), reduciendo por tanto la complejidad total de la heurística a O(n2m). La idea en la que se basa la efectividad de esta heurística es que los trabajos con un mayor tiempo total de procesado deberán realizarse antes que aquellos con menores tiempos totales de procesado. Con el fin de aprovechar esta idea el algoritmo ha de seguir los siguientes pasos: • Primero: Calcular el tiempo total de procesado de cada uno de los trabajos, siendo este /)=# ∑ 12,) 4 256 . • Segundo: Ordenar los trabajos en orden descendente según su tiempo total de procesado. • Tercero: Seleccionar los dos trabajos con mayor tiempo total de procesado y calcular la secuencia óptima para estos dos trabajos según su makespan, la posición relativa de estos trabajos se mantendrá fija. Asignar a i el valor 3, 7 = 3 . 16 Descripción de los algoritmos ' • Cuarto: Seleccionar el trabajo que ocupa la j-ésima posición de la lista obtenida en el segundo paso y calcular la secuencia óptima de insertar este trabajo en la secuencia parcial obtenida en el paso anterior, sin alterar el orden relativo de los trabajos que ya forman parte de la secuencia parcial. • Quinto: Mientras que i sea menor que n calcular i como 7 = 7 +1 y volver al cuarto paso. El hecho de que esta heurística sea una de las mejores para la resolución del problema sin fechas de comienzo (Fm | prmu | Cmax) permite asumir que los resultados de adaptar esta heurística al problema con fechas de comienzo (Fm | rj; prmu | Cmax) han de ser favorables. 3.2 Taillard Como se ha mencionado anteriormente, Sección 3.1, una de las causas de la eficiencia de los algoritmos basados en la heurística NEH es el uso de la aceleración de Taillard, desarrollada por Éric D. Taillard en 1990 (Taillard, 1990). Esta se basa en aprovechar el hecho de que al insertar un trabajo en una secuencia parcial se ha de calcular el makespan que se obtiene en cada una de las distintas combinaciones, por lo tanto, facilita el cálculo de este usando unas variables comunes a todas las posiciones de inserción en esa secuencia parcial. Las ecuaciones que se utilizan para calcular estas variables auxiliares y finalmente el makespan al insertar el késimo trabajo son las siguientes: • eij (Earliest completion time): ;<,) = 0,;2,< = 0 ;2,) =>?@ A ;2,)#B#6,;2#B#6,) C +#12,) (i = 1, ..., m) (j = 1, ..., k - 1) 17 Programación de operaciones en flujo uniforme con fechas de comienzo Figura 4. Earliest completion time del trabajo 2 en esta secuencia parcial. [Fuente: Taillard E., 1990] • qij (Tail): D2,E = 0,;4#F#6,) = 0 D2,) =>?@ A D2#F#6,),D2,)#F#6 C +#12,) (i = m, ..., 1) (j = k - 1, ..., 1) Figura 5. Tail del trabajo 3 en esta secuencia parcial. [Fuente: Taillard E., 1990] • fij (Completion time): G<,2 = 0 G2,) =>?@ A G2#B#6,),;2,)#B#6 C +#12,E (i = 1, ..., m) (j = 1, ..., k) 18 Descripción de los algoritmos Figura 6. Completion time del trabajo 3 y makespan de esta secuencia. [Fuente: Taillard E., 1990] • Cmax(j) (Makespan): (4HI# ( K ) =#max 2(G2,) +#D2,)) (i = 1, ..., m) (j = 1, ..., k) Para las pruebas que se han realizado con el fin de comparar los distintos algoritmos se han usado un conjunto de problemas, también desarrollados por Éric Taillard (Taillard, 1993), que destacan por ser unos de los mas usados en las pruebas de algoritmos para la resolución de este tipo de problemas. Posteriormente a estos se les han añadido fechas de comienzo, como se explicará en el siguiente capítulo, Capítulo 4. 3.3 IGRIS Este algoritmo, desarrollado en 2008 por Quan-Ke Pan, Mehmet Fatih Tasgetiren y Yun- Chia Liang (Pan, Tasgetiren, Liang, 2008), destaca por ser uno de los más eficientes en la resolución de problemas de programación de la producción en flujo uniforme con el objetivo de minimizar el makespan (Fm | prmu | Cmax). Este método está basado en IG_RSLS, desarrollado por Rubén Ruiz y Thomas Stützle (Ruiz, Stützle, 2007), al que se mejoró la fase de búsqueda local mediante el uso de referenced insertion scheme, técnica que se explicará posteriormente. Ambos a su vez usan como base un algoritmo iterated greedy, voraz iterativo, que empieza generando una solución inicial, mediante la heurística NEH mencionada anteriormente, para después realizar una búsqueda local y a continuación iniciar un bucle en el que pasa por una fase de destrucción, en la que se eliminan d trabajos de la solución obtenida, una fase de construcción, en la que los d trabajos previamente retirados vuelven a ser insertados en la 19 Programación de operaciones en flujo uniforme con fechas de comienzo secuencia, y otra fase de búsqueda local para por último aplicar un criterio de aceptación. Como criterio de finalización de este bucle se usa un límite de tiempo proporcional al número de máquinas y trabajos del problema, P#∙ R 4 S T #∙#1U , siendo ts un parámetro del algoritmo. A continuación, Figura 7, se muestra un esquema general del algoritmo. Figura 7. Esquema algoritmo iterated greedy. [Fuente: Pan Q-K, Tasgetiren M, Liang Y-C., 2008] Parte clave de estos algoritmos son las fases de destrucción y construcción. En la fase de destrucción d trabajos aleatoriamente seleccionados se retiran de la solución ! . En la siguiente fase, construcción, cada uno de estos trabajos se reinserta en la secuencia obtenida mediante el procedimiento de la heurística NEH. Figura 8. Esquema de las fases de destrucción y construcción. [Fuente: Pan Q-K, Tasgetiren M, Liang Y-C., 2008] El procedimiento referenced insertion scheme consiste en encontrar para cada uno de los trabajos que forman una secuencia su posición óptima dentro de esta secuencia y si esta es distinta de la posición que anteriormente ocupaban reiniciar el procedimiento con la nueva 20 Descripción de los algoritmos secuencia. El proceso finaliza una vez se han comprobado, con éxito, todos los trabajos. A continuación, Figura 9, se muestra un diagrama de este procedimiento. Figura 9. Referenced insertion scheme. [Fuente: Pan Q-K, Tasgetiren M, Liang Y-C., 2008] Con el fin de evitar un estancamiento de las soluciones este algoritmo incluye un criterio de aceptación del tipo recocido simulado, para el cual se define la siguiente temperatura, donde V es un parámetro: / =# ∑ ∑ WX,Y Z X[\ ] Y[\ ^#∙#4#∙#6< #∙V . En el siguiente diagrama, Figura 10, se muestra el funcionamiento del algoritmo IGRIS. 21 Programación de operaciones en flujo uniforme con fechas de comienzo Figura 10. Diagrama del algoritmo IGRIS. [Fuente: Pan Q-K, Tasgetiren M, Liang Y-C., 2008] El hecho de que esta heurística, al igual que NEH, sea una de las mejores para la resolución del problema sin fechas de comienzo (Fm | prmu | Cmax) permite asumir que los resultados de adaptar esta heurística al problema con fechas de comienzo (Fm | rj; prmu | Cmax) han de ser favorables. 22 Descripción de los algoritmos 3.4 TBFF Los procedimientos anteriormente expuestos provocan un gran número de empates entre secuencias, al insertar un trabajo en una secuencia se obtienen varias posiciones con idéntico makespan, y es sabido que la forma de romper estos empates influye significativamente en el rendimiento de estos algoritmos. También existen mecanismos para los casos de empate en el orden inicial de los trabajos, pero estos no son objeto de estudio en este trabajo. Aunque en la literatura existen diversos mecanismos de tie-breaking, como los propuestos por Xingye Dong, Houkuan Huang y Ping Chen (Dong, Huang, Chen, 2008) basado en equilibrar la carga de trabajo de las distintas máquinas y Pawel Jan Kalczynski y Jerzy Kamburowski (Kalczynski, Kamburowski, 2008) y (Kalczynski, Kamburowski, 20011), el propuesto por Víctor Fernández – Viagas y José M. Framiñan (Fernández – Viagas, Framiñán, 2014) (TBFF) es el que obtiene los mejores resultados. Entre estos mecanismos no se ha considerado el propuesto por Imma Ribas, Ramón Companys y Xavier Tort – Martorell (Ribas, Companys, Tort – Martorell, 2010) debido a que su complejidad computacional es O(n2m) o O(nm2), en función de si se aplica la aceleración de Taillard o no, frente a la de los anteriores mecanismos que es O(nm). El mecanismo TBFF basa su funcionamiento en la reducción de los idle time, los cuales, aunque pueden definirse de las siguientes formas: considerando los tiempos anteriores al primer trabajo y posteriores al último, descontando ambos o descontando solo los posteriores al último trabajo, se opta por aplicar la última de estas definiciones. Por lo tanto, los tiempos ociosos de la i-ésima máquina se calcularán como #712=#(2,^ −# ∑ _2,) ^ )56 # y el tiempo ocioso total como 71 =# ∑ 712 4 256 # . De esta forma el incremento del tiempo ocioso total que provoca insertar un nuevo trabajo en una secuencia se calcula como ∆2,)#= A ;2,)F6#−#_2,)F6 C −#;2,)# , siendo por tanto 71 =# ∑ ∑ ∆2,)# ^B6 )5< 4 256 . Para que el cálculo del tiempo ocioso total no incremente la complejidad del algoritmo este se calcula usando una estimación #71a ( b ) =# ∑A c2,dB6 +#ℎ2,d +#∆′2,dB6 +#∆′2,d C 4 256 # , siendo gi, l - 1 la suma de los tiempos ociosos provocados en la máquina i por los trabajos anteriores a la posición l – 1, hi, l es análogamente la suma de los tiempos ociosos provocados en la máquina i por los trabajos posteriores a la posición l y ∆′2,dB6 y ∆′2,d son los tiempos ociosos producidos al insertar el nuevo trabajo en la posición l. Estas variables se calculan de la siguiente forma, siendo r el trabajo a insertar en la secuencia: c2,dB6 =# ∑ ∆2,)#=# ∑gA ;2,) #−#_2,) C −#;2,)B#6 h dB6 )56 dBS )5< ℎ2,d =# ∑ ∆2,)#=# ∑gA ;2,)F6#−#_2,)F6 C −#;2,) h EBS )5d EBS )5d ∆′2,dB6 = A G2,d −#12,i C −#;2,dB6 23 Programación de operaciones en flujo uniforme con fechas de comienzo ∆′2,d =>?@ j G′2B6,d −#G2,d,0 k G′<,d = 0 , G′2,d =>?@ j G2,d, G′2B6,d k +#_2,d , i = 1, ..., m Siendo por tanto 71a ( b ) = ( +71aa ( b ) =# ∑A c2,dB6 +#ℎ2,d +#∆′2,dB6 C 4 256 + ∑A G2,d −#;2,d +#_2,d −#12,i +#∆′2,d C 4 256 Quedando, ya que ∑ 12,i# 4 256 es constante, la estimación del tiempo ocioso total como 71aa ( b ) =# ∑A G2,d −#;2,d +#_2,d +#>?@ j G′2B6,d −#G2,d,0 kC 4 256 A continuación, Figura 11, se muestra el pseudocódigo de este mecanismo aplicado al NEH. Figura 11. Pseudocódigo de NEH al aplicar TBFF. [Fuente: Fernandez-Viagas, V. & Framinan, J.M., 2014] 30 Aplicación de los métodos mostrar los resultados obtenidos por cada uno de los algoritmos a comparar y las conclusiones obtenidas en la realización de este Trabajo de Fin de Grado. 4.2 Generación de los problemas El rendimiento de los distintos algoritmos se ha comparado usando la batería de 120 problemas, anteriormente mencionada en la Sección 3.2, propuesta por Taillard (Taillard, 1993) y disponibles en la siguiente página web: http://mistic.heigvd.ch/taillard/problemes.dir/ordonnancement.dir/ordonnancement.html. Esta la conforman 12 grupos de 10 problemas con los siguientes números de trabajos y máquinas respectivamente: 20 y 5, 20 y 10, 20 y 20, 50 y 5, 50 y 10, 50 y 20, 100 y 5, 100 y 10, 100 y 20, 200 y 10, 200 y 20 y 500 y 20. Los tiempos de proceso para cada uno de los trabajos de esta batería de problemas han sido generados según una distribución uniforme en el intervalo [1, 99]. Dado que esta batería de problemas fue diseñada para problemas sin fecha de comienzo, se han generado 3 subproblemas para cada uno de los problemas anteriores. Estos subproblemas comparten los mismos tiempos de proceso que el problema del que parten, pero sus fechas de comienzo tienen características distintas. Estas fechas de comienzo se han generado, igual que las utilizadas por Danyu Bai y Lixin Tang (Bai, Tang, 2008), según una distribución uniforme en el intervalo [1, yz#∙P ], siendo Rt un parámetro que regula la dispersión de las fechas de comienzo y que toma los valores de 0.5, 1 y 5 para cada uno de los 3 subproblemas que se generan a partir de cada problema. A cada uno de estos problemas se les denotará, según sus características, como: taNUMn,m,Rt, siendo NUM un número de 3 cifras asignado originalmente por Taillard. 4.3 Parámetros de los algoritmos El funcionamiento del algoritmo IGRIS(TBFF) estará caracterizado por sus parámetros, d, V y ts. Rubén Ruiz y Thomas Stützle (Ruiz, Stützle, 2007), anteriormente mencionados en la Sección 3.3, realizaron un análisis factorial completo de los parámetros d y V en el que determinaron que sus valores óptimos al combinarlos son d = 4 y V = 0.4, por lo que estos fueron los valores escogidos, aunque en este análisis concluyeron que también existen otras combinaciones de valores con resultados estadísticamente similares. El parámetro que determina el tiempo de parada, ts, se fijó en 60 milisegundos, también el mismo que el propuesto por Ruiz y Stützle (Ruiz, 31 Programación de operaciones en flujo uniforme con fechas de comienzo Stützle, 2007), pese a esto, los resultados no son comparables debido al uso de ordenadores con distintas características. Como se ha mencionado anteriormente otro de los parámetros que influyen de manera determinante en el funcionamiento de los algoritmos con tiempos de finalización son las características de los ordenadores en los que se realizan las pruebas. Estas, aunque no afectan a la calidad de las soluciones obtenidas por el resto de los algoritmos, también influyen de manera determinante en los tiempos ejecución necesarios para obtener esas soluciones, de modo que, sí afectan finalmente al rendimiento de los algoritmos, si se considera este como una relación entre la calidad de las soluciones y el tiempo de ejecución necesario para obtener estas soluciones. Los resultados que posteriormente se mostraran han sido obtenidos con un ordenador con las siguientes características: • Ordenador: MacBook Pro (15 pulgadas, mediados de 2012). • Sistema operativo: macOS Sierra. • Procesador: Intel Core i7-3615QM, 2.3 GHz. • Memoria RAM: 8 GB 1600 MHz DDR3. 4.4 Indicadores A la hora de determinar el rendimiento de cada uno de los algoritmos se valorarán sus tiempos de ejecución y la calidad de sus soluciones, para determinar esta última se usará el Average Relative Percentage Deviation (ARPD). El ARPD de cada algoritmo para cada grupo de problemas se calculará como la media de sus Relative Percentage Deviation (RPD), calculándose estos como y{| = R }~dB•ÄUz}~d •ÄUz}~d T #∙100 , donde Sol hace referencia al valor de la solución cuya calidad se desea medir y BestSol al valor de la mejor solución encontrada por el conjunto de métodos a comparar, expuestos en el Capítulo 3. Con respecto al tiempo de ejecución, estos se han medido en segundos y se han calculado las medias de cada algoritmo para cada grupo de problemas. Con el fin mejorar de la precisión de este análisis y debido a que el algoritmo IGRIS(TBFF) no es determinista este se ha ejecutado 5 veces para cada uno de los problemas, de modo que la calidad de sus soluciones para los distintos problemas se ha determinado como la ARPD de las 5 soluciones obtenidas para cada uno de los problemas. 33 5 RESULTADOS En este capítulo se presentarán los resultados obtenidos y por último estos se analizarán, con el objetivo de determinar si algún método es globalmente superior a los demás o destaca para problemas con unas determinadas características o en los que se buscan tiempos de ejecución extremadamente reducidos, para un determinado tamaño del problema. 5.1 Resultados Cada uno de los 360 problemas, previamente explicados, se ha resuelto según los distintos métodos expuestos en el Capítulo 3, es decir NEH, DSJF, iMGS, NEH(TBFF) y IGRIS(TBFF). Con el fin de permitir una mejor visualización de los resultados, y dado que el interés de este análisis no es sobre un problema concreto sino sobre las características de estos, los resultados se han agregado por grupos de problemas, formados por problemas con las mismas características (número de trabajos, número de máquinas y dispersión de las fechas de comienzo). En las tablas que se muestran a continuación se presentan los resultados obtenidos, ARPD (Tabla 1) y tiempos de ejecución (Tabla 2). 34 Resultados n m Rt NEH DSJF iMGS NEH(TBFF) IGRIS(TBFF) 20 5 0,5 3,416 18,892 9,223 2,558 0,008 20 5 1 3,072 19,113 8,949 2,026 0,010 20 5 5 2,931 16,446 7,678 3,196 0,000 20 10 0,5 4,488 25,199 10,745 4,437 0,009 20 10 1 4,731 24,752 10,350 5,019 0,014 20 10 5 4,694 23,616 10,294 4,990 0,006 20 20 0,5 3,896 21,763 7,184 3,132 0,019 20 20 1 4,282 22,482 8,039 3,822 0,039 20 20 5 4,570 20,942 6,933 4,804 0,031 50 5 0,5 1,115 15,200 5,281 0,707 0,000 50 5 1 1,017 15,543 4,177 1,545 0,007 50 5 5 1,359 14,221 4,423 1,423 0,010 50 10 0,5 5,045 25,993 10,006 4,650 0,149 50 10 1 5,377 25,972 9,094 4,946 0,117 50 10 5 5,594 24,813 9,289 5,530 0,103 50 20 0,5 6,148 25,132 10,547 6,067 0,306 50 20 1 5,805 24,153 10,296 6,274 0,325 50 20 5 5,795 23,420 10,479 5,877 0,221 100 5 0,5 0,537 10,051 2,708 0,435 0,026 100 5 1 0,626 9,729 3,247 0,462 0,006 100 5 5 1,677 9,251 3,471 1,284 0,007 100 10 0,5 2,157 18,281 6,134 1,921 0,061 100 10 1 1,986 18,187 5,527 1,853 0,113 100 10 5 2,630 17,199 4,979 2,736 0,145 100 20 0,5 4,922 24,379 8,344 4,010 0,248 100 20 1 4,472 23,390 7,700 4,523 0,177 100 20 5 5,211 22,615 8,463 4,775 0,272 200 10 0,5 1,171 13,710 3,911 1,009 0,103 200 10 1 1,394 13,414 3,277 0,927 0,106 200 10 5 1,540 13,067 3,490 1,393 0,058 200 20 0,5 3,302 19,522 5,784 2,871 0,169 200 20 1 3,269 19,778 5,386 3,239 0,170 200 20 5 3,772 18,847 6,302 3,185 0,206 500 20 0,5 1,669 14,532 3,014 1,295 0,095 500 20 1 1,837 14,372 2,997 1,400 0,118 500 20 5 1,904 13,937 3,663 1,451 0,106 Promedio 3,261 18,942 6,705 3,049 0,099 Tabla 1. ARPD de cada método en función de las características del problema. 35 Programación de operaciones en flujo uniforme con fechas de comienzo n m Rt NEH DSJF iMGS NEH(TBFF) IGRIS(TBFF) 20 5 0,5 0,0 0,0 0,0 0,0 3,0 20 5 1 0,0 0,0 0,0 0,0 3,0 20 5 5 0,0 0,0 0,0 0,0 3,0 20 10 0,5 0,0 0,0 0,0 0,0 6,0 20 10 1 0,0 0,0 0,0 0,0 6,0 20 10 5 0,0 0,0 0,0 0,0 6,0 20 20 0,5 0,0 0,0 0,0 0,0 12,0 20 20 1 0,0 0,0 0,0 0,0 12,0 20 20 5 0,0 0,0 0,0 0,0 12,0 50 5 0,5 0,0 0,0 0,0 0,0 7,5 50 5 1 0,0 0,0 0,0 0,0 7,5 50 5 5 0,0 0,0 0,0 0,0 7,5 50 10 0,5 0,0 0,0 0,0 0,0 15,0 50 10 1 0,0 0,0 0,0 0,0 15,0 50 10 5 0,0 0,0 0,0 0,0 15,0 50 20 0,5 0,0 0,0 0,0 0,0 30,0 50 20 1 0,0 0,0 0,0 0,0 30,0 50 20 5 0,0 0,0 0,0 0,0 30,0 100 5 0,5 0,0 0,0 0,0 0,0 15,0 100 5 1 0,0 0,0 0,0 0,0 15,0 100 5 5 0,0 0,0 0,0 0,0 15,0 100 10 0,5 0,0 0,0 0,0 0,0 30,0 100 10 1 0,0 0,0 0,0 0,0 30,0 100 10 5 0,0 0,0 0,0 0,0 30,0 100 20 0,5 0,0 0,0 0,1 0,0 60,0 100 20 1 0,0 0,0 0,5 0,0 60,0 100 20 5 0,0 0,0 0,3 0,0 60,0 200 10 0,5 0,0 0,0 0,4 0,0 60,0 200 10 1 0,0 0,0 0,6 0,0 60,0 200 10 5 0,0 0,0 0,1 0,0 60,0 200 20 0,5 0,0 0,0 2,1 0,0 120,0 200 20 1 0,0 0,0 1,2 0,0 120,0 200 20 5 0,0 0,0 0,4 0,0 120,0 500 20 0,5 0,0 0,0 18,8 0,1 300,0 500 20 1 0,0 0,0 10,6 0,1 300,0 500 20 5 0,0 0,0 2,5 0,1 300,0 Tabla 2. Tiempo medio de ejecución, en segundos, de cada método en función de las características del problema. 36 Resultados 5.2 Análisis de los resultados A lo largo de esta sección se realizará un análisis de los resultados obtenidos, atendiendo a la influencia de los distintos factores en estos. En la Figura 13, que se muestra a continuación, se presentan los resultados obtenidos para cada uno de los algoritmos en función de los parámetros característicos de los problemas, n, m y Rt. Figura 13. ARPD de cada método en función de las características de los problemas. Como se puede apreciar en esta gráfica, Figura 13, el método IGRIS(TBFF) obtiene unos resultados claramente superiores a los del resto de algoritmos. Esta gráfica también muestra que el método con el que se obtienen los peores resultados es el método DSJF, seguido por el método iMGS. Aunque en esta gráfica, Figura 13, se puede apreciar una ligera superioridad de la calidad de las soluciones obtenidas mediante el método NEH frente a la calidad de las 37 Programación de operaciones en flujo uniforme con fechas de comienzo soluciones obtenidas mediante el método NEH(TBFF), esta diferencia no es tan amplia como la que separa los restantes métodos. Por ello se prestará especial atención a ambos métodos, profundizando en el análisis de la calidad de sus soluciones. En la Tabla 1 y en la Figura 13 se han usado como indicadores de la calidad de las soluciones proporcionadas por los distintos métodos el ARPD, por lo que, debido a la naturaleza de este, la dispersión de los resultados obtenidos queda oculta. Para evitar esto, a continuación, Figuras 14-18, se muestran los RPD máximos, mínimos y medios (ARPD) de cada uno de los algoritmos en función de los parámetros característicos de los problemas, n, m y Rt. Figura 14. RPD del método DSJF en función de las características de los problemas. 38 Resultados Figura 15. RPD del método IGRIS(TBFF) en función de las características de los problemas. Figura 16. RPD del método iMGS en función de las características de los problemas. 39 Programación de operaciones en flujo uniforme con fechas de comienzo Figura 17. RPD del método NEH en función de las características de los problemas. Figura 18. RPD del método NEH(TBFF) en función de las características de los problemas. 46 Resultados Figura 24. Efecto de Rt en el método IGRIS(TBFF). Figura 25. Efecto de Rt en el método iMGS. 47 Programación de operaciones en flujo uniforme con fechas de comienzo Los resultados expuestos en la Figura 24 confirman el exiguo efecto del parámetro Rt en la calidad de las soluciones obtenidas mediante el método IGRIS(TBFF). Asimismo, muestra que la leve influencia de este parámetro es independiente de los valores del resto de los parámetros de estos problemas. Figura 26. Efecto de Rt en el método NEH. En la Figura 26 se puede apreciar como para la mayoría de los tipos de problemas, efectivamente, se obtienen los peores resultados con Rt = 5. Este efecto también ocurre en el método NEH(TBFF), como se puede comprobar en la Figura 27. Como también muestra ese gráfico, este método obtiene, generalmente, los mejores resultados con Rt = 0,5, independiente del número de trabajos y máquinas de los problemas. 48 Resultados Figura 27. Efecto de Rt en el método NEH(TBFF). Como se ha podido comprobar el efecto de los valores del parámetro Rt no es el mismo para los métodos NEH y NEH(TBFF). Por tanto, a continuación, Figuras 28-32, se analizará el efecto del parámetro Rt en la diferencia entre estos métodos. En la Figura 28 se presentan las diferencias medias entre la calidad de las soluciones de ambos métodos. 49 Programación de operaciones en flujo uniforme con fechas de comienzo Figura 28. Rendimiento de los métodos NEH y NEH(TBFF) en función de los valores de Rt. Figura 29. Diferencias de rendimiento máximas, mínimas y medias de los métodos NEH y NEH(TBFF) en función de los valores de Rt. 50 Resultados En la Figura 29 se puede apreciar como la calidad media de las soluciones obtenidas mediante el método NEH(TBFF) es superior a la de las obtenidas mediante el método NEH independientemente del valor de Rt, siendo esta diferencia media del 0,39% para Rt = 0,5, del 0,16% para Rt = 1 y del 0,09% para Rt = 5. Concretamente, para los casos en los que Rt = 0,5 el método NEH(TBFF) obtiene mejores resultados medios que el método NEH en todas las categorías de problemas, es decir problemas con el mismo número de trabajos y máquinas, como se puede comprobar en la Figura 28. Asimismo, en esta figura se puede confirmar que la superioridad media del método NEH(TBFF) frente al método NEH para problemas con un gran número de trabajos ( P# ≥ 200 ) es independiente del parámetro Rt. Seguidamente, Figuras 30-32, se mostrarán, junto con las diferencias medias entre la calidad de las soluciones, las diferencias entre el porcentaje de problemas en los que el método NEH(TBFF) es superior al método NEH y los problemas en los que ocurre lo contrario en función de los distintos valores de Rt. Figura 30. Diferencia de rendimiento media y diferencia entre el porcentaje de problemas en los que cada método es superior para Rt = 0,5. 51 Programación de operaciones en flujo uniforme con fechas de comienzo Figura 31. Diferencia de rendimiento media y diferencia entre el porcentaje de problemas en los que cada método es superior para Rt = 1. Los resultados reseñables obtenidos del análisis del porcentaje de problemas en los que la calidad de las soluciones obtenidas por el método NEH(TBFF) es superior a la de las obtenidas por el método NEH en función de Rt son los siguientes: • Rt = 0,5 (Figura 30): El método NEH(TBFF) consigue mejores soluciones en el 59% de los problemas e idénticas en el 17%. En todas las categorías de problemas, salvo una, 50 trabajos y 20 máquinas, el número de problemas en los que el método NEH(TBFF) consigue mejores soluciones supera al número de problemas en los que ocurre lo contrario. Por tanto, y como indicaba la diferencia media de rendimiento, el método NEH(TBFF) es consistentemente superior al método NEH para Rt = 0,5. • Rt = 1 (Figura 31): El método NEH(TBFF) consigue mejores soluciones en el 55% de los problemas e idénticas en el 12%. Aunque para los problemas con 20, 100, 200 y 500 trabajos el método NEH(TBFF) obtiene un rendimiento medio superior en un 0,27% al del método NEH, obteniendo mejores resultados en un 61% de los problemas e idénticos en un 12% de los problemas, estos resultados se ven lastrados 52 Resultados por los obtenidos para los problemas con 50 trabajos, en los que el método NEH(TBFF) obtiene un rendimiento medio inferior en un 0,18% al del método NEH, obteniendo mejores resultados en solo un 37% de los problemas e idénticos en un 10% de los problemas. • Rt = 5 (Figura 32): El método NEH(TBFF) consigue mejores soluciones en el 55% de los problemas e idénticas en el 13%. Si bien es cierto que, para los problemas con un gran número de trabajos ( P# ≥ 100 ) el método NEH(TBFF) obtiene un rendimiento medio superior en un 0,31% al del método NEH, obteniendo mejores resultados en un 68% de los problemas e idénticos en un 10% de los problemas, para los problemas con un pequeño número de trabajos ( P# ≤ 50 ) el método NEH obtiene un rendimiento medio ligeramente superior (0,13%) al del método NEH(TBFF), obteniendo mejores resultados en un 42% de los problemas e idénticos en un 18% de los problemas. Figura 32. Diferencia de rendimiento media y diferencia entre el porcentaje de problemas en los que cada método es superior para Rt = 5. 53 Programación de operaciones en flujo uniforme con fechas de comienzo Una vez se a analizado el efecto del parámetro Rt en la Figura 33 se muestran los ARPD de cada método en función de los parámetros restantes, número de trabajos y máquinas, de los problemas. Figura 33. ARPD de cada método en función del número de trabajos y máquinas. Por último, se analizará el efecto del número de trabajos y máquinas de los problemas en la calidad de las soluciones obtenidas por cada uno de los métodos. Para ello, en las Figuras 34-38 se mostrará, individualmente para cada método, la calidad de las soluciones obtenidas por estos en función del número de trabajos y máquinas de los problemas. 54 Resultados Figura 34. Efecto del número de trabajos y máquinas en el método DSJF. Figura 35. Efecto del número de trabajos y máquinas en el método IGRIS(TBFF). 55 Programación de operaciones en flujo uniforme con fechas de comienzo Figura 36. Efecto del número de trabajos y máquinas en el método iMGS. Figura 37. Efecto del número de trabajos y máquinas en el método NEH. 62 Bibliografía y referencias Nawaz, M., Enscore, E.E. & Ham, I., 1983. A heuristic algorithm for the m-machine, n-job flowshop sequencing problem. Omega, 11(1), pp.91–95. Pan Q-K, Tasgetiren M, Liang Y-C. A discrete differential evolution algorithm for the permutation flowshop scheduling problem. Comput Ind Eng 2008;55(4):795–816. Ren, T. et al., 2015. A Local Search Algorithm for the Flow Shop Scheduling Problem with Release Dates. Discrete Dynamics in Nature and Society, 2015, pp.1–8. Ribas I, Companys R, Tort-Martorell X. Comparing three-step heuristics for the permutation flow shop problem. Comput Oper Res 2010;37(12):2062–70. Ruiz R, Stützle T. A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. Eur J Oper Res 2007;177(3):2033–49. Ruiz, Rubén. Scheduling Heuristics, 2015, pp 1-24. 10.1007/978-3-319-07153-4_44-1. Taillard E. Some efficient heuristic methods for the flow shop sequencing problem. Eur J Oper Res 1990;47(1):65–74. Taillard E. Benchmarks for basic scheduling problems. Eur J Oper Res 1993;64(2):278–85. http://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/ordonnancement.html http://www.rae.es