Taller de flujo regular con recursos humanos y minimización del makespan: Modelos de programación lineal entera

Dpto. Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 20 20 Trabajo Fin de Grado Grado en Ingeniería de Organización Industrial Taller de flujo regular con recursos humanos y minimización del makespan: Modelos de programación lineal entera. Autor: David Gómez Medina Tutor: Víctor Fernández-Viagas Escudero Trabajo Fin de Grado Grado en Ingeniería de Organización Industrial Taller de flujo regular con recursos humanos y minimización del makespan: Modelos de programación lineal entera. Autor: David Gómez Medina Tutor: Víctor Fernández-Viagas Escudero Dpto. Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2020 Trabajo Fin de Grado: Taller de flujo regular con recursos humanos y minimización del makespan: Modelos de programación lineal entera. Autor: David Gómez Medina 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, 2020 El Secretario del Tribunal I ÍNDICE Capítulo 1 Introducción ............................................................................................................ 1 1.1 Objetivos ......................................................................................................................... 2 1.2 Sumario ........................................................................................................................... 3 Capítulo 2 Descripción del problema ....................................................................................... 5 2.1 Introducción .................................................................................................................... 5 2.2 Notación genérica de la descripción ............................................................................... 5 2.3 Descripción del problema particular ............................................................................... 7 Capítulo 3 Modelización ........................................................................................................ 10 3.1 Introducción .................................................................................................................. 10 3.2 Modelos MILP. ............................................................................................................. 10 3.2.1 Datos ...................................................................................................................... 11 3.2.2 Índices .................................................................................................................... 11 3.2.3 Variables ................................................................................................................ 11 3.2.4 Ejemplificación ...................................................................................................... 12 3.3 Modelo Wilson ............................................................................................................. 15 3.3.1 Introducción ........................................................................................................... 15 3.3.2 Modelo Wilson original ......................................................................................... 15 3.3.3 Modelo Wilson adaptado ....................................................................................... 16 3.4 Modelo TS2 .................................................................................................................. 19 3.4.1 Introducción ........................................................................................................... 19 3.4.2 Modelo TS2 original .............................................................................................. 19 3.4.3 Modelo TS2 adaptado ............................................................................................ 20 3.5 Modelo HFS/HR ........................................................................................................... 23 3.5.1 Introducción. .......................................................................................................... 23 II 3.5.2 Modelo HFS/HR original ...................................................................................... 23 3.5.3 Modelo HFS/HR adaptado .................................................................................... 25 3.6 Modelo Naderi (2014) Modelo 1 .................................................................................. 28 3.6.1 Introducción ........................................................................................................... 28 3.6.2 Naderi (2014) Modelo 1 original. .......................................................................... 28 3.6.3 Naderi (2014) Modelo 1 adaptado ......................................................................... 29 Capítulo 4 Resultados y análisis ............................................................................................. 32 4.1 Resolución de los modelos ........................................................................................... 32 4.2 Análisis de resultados ................................................................................................... 33 4.2.1 Análisis de las soluciones según tipología ............................................................ 34 4.2.2 Análisis del tiempo de computación ...................................................................... 36 4.2.3 Análisis del indicador ARPD. ............................................................................... 37 Capítulo 5 Conclusiones ......................................................................................................... 40 Bibliografía ............................................................................................................................. 43 Anexo ..................................................................................................................................... 45 Declaración de variables y generación aleatoria de datos .............................................. 45 Main y creación de ficheros............................................................................................ 46 Modelo Wilson adaptado ................................................................................................ 49 Modelo TS2 adaptado ..................................................................................................... 55 Modelo HFSHR adaptado .............................................................................................. 60 Modelo Naderi (2014) adaptado ..................................................................................... 65 III ÍNDICE DE ILUSTRACIONES Ilustración 2-1 Diagrama de Gantt sin server ........................................................................... 8 Ilustración 2-2 Diagrama de Gantt con un server ..................................................................... 8 Ilustración 3-1 Diagrama de Gantt para instancia ejemplo resuelto con modelo Wilson adaptado .................................................................................................................................. 18 Ilustración 3-2 Diagrama de Gantt para instancia ejemplo resuelto con modelo TS2 adaptado ................................................................................................................................................ 22 Ilustración 3-3 Diagrama de Gantt para instancia ejemplo resuelto con modelo HFSHR adaptado .................................................................................................................................. 27 Ilustración 3-4 Diagrama de Gantt para instancia ejemplo resuelto con modelo Naderi (2014) adaptado .................................................................................................................................. 31 5 Capítulo 2 Descripción del problema A lo largo del capítulo 2 se expondrá, en primer lugar, la notación que se empleará a lo largo del TFG (Trabajo de Fin de Grado) mientras que en segundo lugar se realizará la descripción del problema particular que se estudiará. 2.1 Notación genérica de la descripción Como se puede prever, a lo largo de la historia, las diferentes industrias han ido evolucionando hacia nuevos entornos productivos con el fin de optimizar su producción. Por ello, cada industria plantea un sistema productivo diferente adaptándose tanto a sus necesidades como a los objetivos que la dirección desea alcanzar. Por todo esto, para definir el problema a tratar en este TFG, se empleará el formato que plantea Pinedo en su libro “Scheduling” (2016). En este libro, se define que un problema de programación se puede describir en base a tres elementos α | β | γ cuyos significados se detallan a continuación: α: “Describe el entorno de las máquinas”. Alpha hace referencia al entorno productivo, número de máquinas y cómo han de circular los diferentes trabajos por ellas. Los entornos más conocidos, definidos por Pinedo (2016) son: - (1) Single Machine: Una única máquina por la que han de pasar uno o más trabajos. - (Pm) Parallel machines: Hay m máquinas idénticas paralelas. - (Qm) Uniform parallel machines: Un número m de máquinas que realizan la misma operación, pero con tiempos de procesos proporcionales según una constante de velocidad. - (Rm) Unrelated parallel machines: Un número m de máquinas paralelas con tiempos de procesos sin relación entre ellas. - (Fm) Flow shop: Hay m máquinas en serie en las que cada trabajo tiene que ser procesado una vez en cada máquina. Por ejemplo: F2 hace referencia a un Flow shop 6 de dos máquinas por las que tienen que pasar n trabajos siguiendo la misma ruta definida, máquina 1 y después máquina 2. - (Jm) Job shop: Hay m máquinas por las que deberán pasar diferentes trabajos, cada uno, con una ruta predeterminada. - (Om) Open shop: Un número m de máquinas por las que deben pasar todos los diferentes trabajos sin una ruta determinada en el que se hagan las operaciones sobre ellos. β: Hace referencia a las “ restricciones del sistema”. En el apartado de restricciones se pueden incluir desde restricciones en cuanto a la fecha en la que el trabajo puede empezar a ser procesado hasta la obligación de que, para cada trabajo, la máquina deba incluir un tiempo de preparación o setup. Las más comunes comentadas por Pinedo (2016) son : - (𝒓𝒋) Release dates: El trabajo j no se puede procesar antes de instante 𝑟. - (prmp) Preemptions: Permite la interrupción de la operación de un trabajo en una máquina para insertar un trabajo diferente en dicha máquina. - (prec) Precedence constrains: Requisito de que uno o más trabajos tienen que ser completados antes que otros. - (𝒔𝒋𝒌) Sequence dependent setup times: Representa la existencia de un tiempo de setup entre el trabajo j y k. Este tiempo de setup puede depender de cada máquina en caso de tener más de una, en este caso se denota como 𝑠. - (prmu) Permutation: Restricción común en los entornos Fm. Hace referencia a que el orden de procesamiento en cada máquina sigue la disciplina FIFO (First In First Out). - (nwt) No-wait: Restricción común en entornos Fm. Hace referencia a que los trabajos no pueden esperar entre dos máquinas sucesivas. γ: “Describe el objetivo que se quiere minimizar”. Para poder comentar los diferentes objetivos debemos definir dos conceptos: 𝐶 (momento en el que el trabajo j termina de procesarse en la última máquina y 𝑑 (en caso de existir, fecha en la que la empresa se ha comprometido a tener el trabajo finalizado). 7 Una vez definidos estos conceptos, Pinedo (2016) describe tres indicadores para cada trabajo que son útiles para los diferentes objetivos. - 𝐿 Lateness: 𝐿 = 𝐶− 𝑑 - 𝑇 Tardiness: 𝑇 = max (𝐿,0) - 𝑈 Unit penalty: 1 𝑠𝑖 𝐶> 𝑑 0 𝑒𝑛 𝑜𝑡𝑟𝑜 𝑐𝑎𝑠𝑜 Los objetivos (γ) más conocidos se definen en el libro de Pinedo, (2016) de la siguiente manera: - (𝑪𝒎𝒂𝒙) Makespan: Momento en el que termina de procesarse el último trabajo en la última máquina. - (∑𝑪𝒋) Total completion time: Suma total de tiempos de finalización. - (𝑳𝒎𝒂𝒙) Maximum lateness: Máxima violación de las fechas comprometidas. - (∑𝑻𝒋) Total tardiness: Suma de los tiempos de retraso de cada trabajo. - (∑𝑼𝒋) Number of tardy jobs: Número de trabajos que van tarde. Los objetivos planteados son los más comunes, aunque pueden aparecer más ajustándose al objetivo de la empresa. Del mismo modo, puede que se dé el caso en el que no todos los trabajos tengan la misma importancia para la empresa por diferentes motivos y por ello, se puede incluir un peso 𝑤 en los objetivos para que se contemple la importancia relativa de cada trabajo. 2.2 Descripción del problema particular Este TFG se centrará en el modelado y resolución de un problema con entorno Flow shop con m máquinas en el que habrá n trabajos que deberán ser procesados siguiendo la misma secuencia en las diferentes máquinas, es decir, con la restricción prmu. Adicionalmente, existe una restricción de tiempos de setup dependientes de la secuencia y de la máquina por lo que será de la forma 𝑠. Dicho setup será no anticipatorio, es decir, que no se puede comenzar a preparar la máquina hasta que se haya terminado de procesar el trabajo en la máquina anterior. Por último, el objetivo a minimizar es 𝐶. 8 La característica diferencial de este problema es que el tiempo de setup, que hace referencia a una puesta a punto de la máquina, lo realiza un server o un recurso humano (operario) siendo s (número de servers) menor al número de máquinas. La definición de server se puede encontrar en numerosos artículos de la programación de la producción como por ejemplo en el artículo de Fernandez-Viagas et al., (2020) donde se define server como “un recurso reutilizable encargados de ejecutar los cambios entre trabajos o grupos de trabajos”. La concepción de los servers supone un avance en la programación ya que permite el estudio de estos recursos humanos encargados del setup para optimizar el proceso productivo al tener un modelo que se acerque más a la realidad. Tal y como se puede apreciar en las ilustraciones 2-1 y 2-2, la concepción de la limitación de los servers puede producir cambios en el problema que se presenta. Sea un entorno de F3 sin y con server respectivamente, con tres trabajos que han de procesarse en las 3 máquinas según la secuencia (2,3,1). Por simplificar, para este ejemplo se supone constante el tiempo de setup a 2 u.t. Si se compara el makespan de las dos ilustraciones, se aprecia un aumento de 4 u.t. en el caso en el que hay un server. M1 S 2 S 3 S 1 M2 S 2 S 3 S 1 M3 S 2 S 3 S 1 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 Ilustración 2-1 Diagrama de Gantt sin server [Fuente: Elaboración propia] M1 S 2 S 3 S 1 M2 S 2 S 3 S 1 M3 S 2 S 3 S 1 S1 S S S S S S S S S 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 Ilustración 2-2 Diagrama de Gantt con un server [Fuente: Elaboración propia] Por todo ello, en este trabajo se tendrá en cuenta la presencia de varios servers que se formularán como máquinas paralelas cuyos trabajos son los diferentes setups por lo que los servers se incluirán en el entorno de las máquinas siguiendo el siguiente ejemplo: α = Pm, S2 9 (Werner y Kravchenko, 2010) que hace referencia a un problema con m máquinas paralelas y dos servers. A modo de resumen, empleando la nomenclatura planteada en el apartado 2.1, el problema se nombrará de la siguiente manera: 𝐹𝑚,𝑆𝑠  𝑆𝑖𝑗𝑘,prmu 𝐶𝑚𝑎𝑥  En cuanto a la complejidad de este problema, se puede afirmar que la complejidad es NP-Hard ya que, tal y como afirman en su artículo Tseng, F.T., Stafford Jr., E.F. (2008), los problemas del tipo Flow Shop con más de tres máquinas serán del tipo NP-Hard. Por otro lado, Gupta et al., (1986) afirman que el problema ⟨𝐹2 |𝑆𝐷𝑆𝑇 |𝐶 ⟩ tiene una complejidad del tipo NP-Hard. Sin embargo, Brucker et al. (2005) afirmaron en su artículo, que la complejidad del problema específico 𝐹2,𝑆1 𝑃 =p,𝑆 =s 𝐶 , versión simplificada del problema de este TFG, es de tipo polinomial O(n). 10 Capítulo 3 Modelización 3.1 Introducción En este capítulo se presentarán diferentes modelos de programación lineal propuestos para resolver el problema de estudio. Cada uno de los modelos toma como referencia modelos previos de la literatura y, en la medida de lo posible, se realizarán sus adaptaciones respetando la misma tipología de variables. Así, para cada uno de los modelos, se planteará en primer lugar el modelo original del que parte y posteriormente, la adaptación de ese modelo para la resolución del problema 𝐹,𝑆  𝑆,prmu 𝐶 . En total se propondrán y analizarán cuatro modelos, tomando como referencia modelos en artículos previos de la literatura . Se comenzará con dos modelos, el Wilson y el TS2, pertenecientes a la familia Wagner del artículo de Stafford et al. (2005) planteados para el problema ⟨𝐹 | prmu |𝐶 ⟩. Estos dos modelos emplean una variable de asignación de un trabajo a una posición de una secuencia. A continuación, se adaptará un modelo desarrollado para el entorno Flow Shop híbrido 𝐻𝐹𝑆/𝐻𝑅 𝑠 𝐶  con restricciones de servers que ejecutan los setups en las diferentes etapas. El modelo por adaptar ha sido propuesto por Costa et al., (2020). Por último, se analizará y adaptará el “Modelo 1” propuesto en el artículo de Naderi et al. (2014), que fue planteado para un entorno de Flow Shop híbrido sin tiempos de setup. 3.2 Modelos MILP. En primer lugar, se presentarán los datos de entrada para los modelos seguido de los índices que se emplearán. Tras esto, se expondrán las variables empleadas en los cuatro modelos adaptados por lo que variables que se emplean en los modelos originales, se explicarán en cada uno de ellos, cuando sea necesario. Por último, se presentará un ejemplo con sus datos asociados que se irá resolviendo con cada uno de los modelos adaptados con la finalidad de verificarlos y poder entender, en mayor medida, el funcionamiento de cada uno de ellos. 11 3.2.1 Datos 𝑁: Número de trabajos. 𝑀: Número de máquinas. 𝑆: Número de servers. 𝑇,: Tiempo de proceso del trabajo j en la máquina i. 𝑆,,: Tiempo de setup del trabajo k cuando va después del trabajo j en la máquina i V: “Valor lo suficientemente grande para asegurar que solo una restricción de una relación dicotómica se cumpla” Sttaford, (2005). 3.2.2 Índices i,h para máquinas. (1≤𝑖,ℎ ≤𝑀) j,k para trabajos. (1≤𝑗,𝑘 ≤𝑁) p para la posición en la secuencia. (1≤𝑝≤𝑁) s para los servers. (1≤𝑠 ≤𝑆) 3.2.3 Variables Debido al estudio y adaptación de diversos modelos provenientes de diferentes artículos y autores se dispondrán de diversas maneras de modelar el problema con su tipología específica de variables. A continuación, se detallan todas ellas, aunque no todas se usen en todos los modelos. 𝑍, ∈{0,1} 1 si el trabajo j ocupa la posición p de la secuencia, 0 en caso contrario. (1≤ 𝑗≤𝑁) (1≤𝑝 ≤𝑁). 12 𝛼,, ∈{0,1} 1 si el trabajo j está en la posición p y le sigue el trabajo k, 0 en caso contrario. (1≤𝑗,𝑘 ≤𝑁) (1≤𝑝 ≤𝑁). 𝐸, Tiempo de fin del trabajo en posición p en máquina i. (1≤𝑖 ≤𝑀) (1≤𝑝 ≤ 𝑁). 𝐵, Tiempo de inicio del trabajo en posición p en la máquina i. (1≤𝑖 ≤𝑀) (1≤ 𝑝≤𝑁). Dadas las restricciones del problema abordado, también pueden ser consideradas con el tiempo de fin del setup del trabajo en posición p en la máquina i. 𝑋,, ∈{0,1} 1 si el setup del trabajo j en la máquina i lo hace el server s, 0 en caso contrario. (1≤𝑖 ≤𝑀) (1≤𝑗≤𝑁) (1≤𝑠 ≤𝑆). 𝛾,, ∈{0,1} 1 si el server s realiza el setup del trabajo en posición p en máquina i, 0 en caso contrario. (1≤𝑠 ≤𝑆) (1≤𝑖 ≤ 𝑀) (1≤𝑝 ≤𝑁). 𝐷, ∈{0,1} 1 si el trabajo j inmediatamente antes que k, 0 en caso contrario. (1≤𝑗,𝑘 ≤ 𝑁). 𝑈, Tiempo de inicio del trabajo j en la máquina i (antes del setup). (1≤𝑖 ≤ 𝑀)(1≤𝑗 ≤𝑁). 𝐶, Tiempo de fin de operación del trabajo k en máquina i. (1≤𝑖 ≤𝑀) (1≤𝑘 ≤ 𝑁). 𝐹,,, ∈{0,1} Para los setups del trabajo j en máquina i y trabajo k en h, realizados por el mismo server. Vale 1 si el setup del trabajo j se procesa antes que el de k, 0 en caso contrario. (1≤𝑖,ℎ ≤𝑀) (1≤ 𝑗,𝑘 ≤𝑁). 𝑌,,,, ∈{0,1} 1 si el server s hace el setup del trabajo j en la máquina i inmediatamente antes que el setup de k en la máquina h, 0 en caso contrario. (1≤𝑠≤𝑆) (1≤ 𝑖,ℎ ≤𝑀) (1≤𝑗,𝑘 ≤𝑁). 3.2.4 Ejemplo Para una mayor ilustración del comportamiento de los modelos, se procederá a la resolución de un problema de pequeñas dimensiones, de esta manera, se podrá comprender 13 mejor la filosofía que plantea cada uno de ellos. Del mismo modo, al ser modelos que buscan la solución óptima del problema, los resultados de los modelos adaptados deberán coincidir en el makespan y en la secuencia solución (en el caso de que únicamente hubiese un óptimo del problema, no teniendo por qué coincidir en caso contrario). El ejemplo se irá desarrollando para cada uno de los modelos analizando sus variables específicas junto al diagrama de Gantt asociado para una mejor comprensión. Datos para el ejemplo: Número de máquinas, M =3. Número de trabajos, N = 4. Número de servers, S=2. Tiempos de proceso. Tabla 3-1. 𝑇  ,  Trabajos (j) Máquinas (i) 1 2 3 4 1 18 12 9 10 2 10 18 15 8 3 14 8 13 17 Tabla 3-1 Tiempos de proceso para instancia de ejemplo. [Fuente: Elaboración propia] Tiempos de setup para la máquina 1. Tabla 3-2. 𝑆  ,  ,  Trabajos (k) Trabajos (j) 1 2 3 4 0 4 6 3 4 1 6 5 7 2 2 3 3 3 2 9 5 4 5 3 9 Tabla 3-2 Tiempos de setup para máquina 1 para instancia de ejemplo. [Fuente: Elaboración propia] 14 Tiempos de setup para la máquina 2. Tabla 3-3. 𝑆  ,  ,  Trabajos (k) Trabajos (j) 1 2 3 4 0 2 4 5 3 1 7 4 6 2 8 5 2 3 2 7 6 4 4 2 3 Tabla 3-3 Tiempos de setup para máquina 2 para instancia de ejemplo. [Fuente: Elaboración propia] Tiempos de setup para la máquina 3. Tabla 3-4. 𝑆  ,  ,  Trabajos (k) Trabajos (j) 1 2 3 4 0 8 5 7 3 1 3 7 4 2 6 1 6 3 1 1 9 4 4 4 8 Tabla 3-4 Tiempos de setup para máquina 3 para instancia de ejemplo. [Fuente: Elaboración propia] 21 𝑍, ∈{0,1} (1≤𝑗 ≤𝑁)(1≤𝑝≤𝑁) 𝛼,, ∈{0,1} (1≤𝑗,𝑘 ≤𝑁) 𝑗 ≠𝑘(1≤𝑝≤𝑁) 𝛼,, ∈{0,1} (1≤𝑘 ≤𝑁) 𝛾,, ∈{0,1} (1≤𝑠 ≤𝑆)(1≤𝑖 ≤𝑖′≤𝑀)(1≤𝑝≤𝑝′≤𝑁) En el modelo TS2 adaptado se mantiene la función objetivo como el tiempo de finalización del proceso del trabajo secuenciado en última posición en la última máquina (7). Con los conjuntos de restricciones (8-11) se establece la asignación de trabajos a posiciones de la secuencia y se establece la precedencia y sucesión de cada trabajo en cada posición, teniendo en cuenta con el conjunto (11’) el trabajo en la primera posición para el setup inicial. Los conjuntos de restricciones (12) y (13) regulan que un trabajo no comience en la siguiente máquina hasta que haya acabado en la anterior y se haya realizado el setup y que un trabajo no empiece a procesarse en una máquina hasta que no haya acabado el secuenciado antes y se haya realizado el setup. Los conjuntos (14 y 15) marcan el momento de inicio del primer trabajo secuenciado en la primera máquina y que el paso de ese trabajo por las máquinas posteriores. Con las restricciones del conjunto (16), se asigna cada setup a un único server. Por último, el conjunto de restricciones (17) regulan la restricción de los servers siguiendo la filosofía empleada en el apartado 3.3.3 para el modelo adaptado de Wilson. Resolución de la instancia de ejemplo. A continuación, se presenta la solución que plantea este modelo para la instancia planteada en el punto 3.2.4. La secuencia óptima es (4,2,3,1). En la tabla 3-6 se presentan las variables binarias que se activan (con valor igual a 1) y las variables que hacen referencia a tiempos con los valores que toman. El valor del makespan coincide con el presentado en el modelo de Wilson de 98 u.t. En la figura 3-2 se puede apreciar el diagrama de Gantt para la solución óptima en la que se representa cada trabajo en la posición correspondiente de la secuencia solución. 22 Posición Asignación a server Tiempos fin proceso 𝑍  ,  𝛼  ,  ,  𝛾  ,  ,  𝛾  ,  ,  𝐸  ,  = 14 𝐸  ,  = 69 𝑍  ,  𝛼  ,  ,  𝛾  ,  ,  𝛾  ,  ,  𝐸  ,  = 29 𝐸  ,  = 81 𝑍  ,  𝛼  ,  ,  𝛾  ,  ,  𝛾  ,  ,  𝐸  ,  = 41 𝐸  ,  = 51 𝑍  ,  𝛼  ,  ,  𝛾  ,  ,  𝛾  ,  ,  𝐸  ,  = 61 𝐸  ,  = 63 𝛾  ,  ,  𝛾  ,  ,  𝐸  ,  = 25 𝐸  ,  = 83 𝛾  ,  ,  𝛾  ,  ,  𝐸  ,  = 49 𝐸  ,  = 98 4 14 17 18 29 31 33 35 41 42 43 44 49 50 52 55 56 69 70 71 72 83 84 98 M1 (1,0,4) 4 (1,4,2) 2 (1,2,3) 3 (1,3,1) 1 M2 (2,0,4) 4 (2,4,2) 2 (2,2,3) 3 (2,3,1) 1 M3 (3,0,4) 4 (3,4,2) 2 (3,2,3) 3 (3,3,1) 1 S1 (1,0,4) (1,4,2) (1,2,3) (1,3,1) (2,2,3) (2,3,1) (3,3,1) S2 (2,0,4) (2,4,2) (3,0,4) (3,4,2) (3,2,3) 4 14 17 18 29 31 33 35 41 42 43 44 49 50 52 55 56 69 70 71 72 83 84 98 Ilustración 3-2 Diagrama de Gantt para instancia ejemplo resuelto con modelo TS2 adaptado. Para una mejor visualización de la gráfica, los tiempos de proceso no presentan escalas uniformes. [Fuente: Elaboración propia] Tabla 3-6 Resultados de la instancia de ejemplo con modelo TS2 Adaptado. [Fuente: Elaboración propia] 23 3.5 Modelo HFS/HR 3.5.1 Introducción. Este modelo presentado en el artículo de Costa et al., (2020), está diseñado para un entorno híbrido con diferentes etapas que se denotará con el índice w. Dentro de cada etapa hay un número definido de máquinas paralelas. El modelo está diseñado de forma que cada etapa dispone de un número determinado de servers que atenderán los setups (independientes de la secuencia y de la máquina) de las diferentes máquinas dentro de su etapa. De cara a la adaptación, se considerará que cada etapa consta de una única máquina lo que significa que hay una equivalencia entre etapa y máquina. Del mismo modo, se considerará que los servers puedan operar en cualquier máquina del sistema. 3.5.2 Modelo HFS/HR original Además de las variables de la Sección 3.2.3, este modelo emplea las siguientes variables, ajustadas a la notación empleada en este TFG: Xw,i,j,s ∈{0,1} 1 si el server s realiza el setup del trabajo j en la máquina i en la etapa w. Fw,k,j ∈{0,1} Para los trabajos j y k cuyos setup los realice el mismo server en la etapa w, 1 si k precede a j. Gw,k,j ∈{0,1} En caso en el que los trabajos j y k se procesen en la misma máquina en la etapa w, 1 si k precede a j. Uw,j Tiempo de inicio del trabajo j en la etapa w. Cw,j Tiempo finalización del proceso del trabajo j en la etapa w. 𝐶 Makespan. 24 MIN 𝐶 𝑠.𝑎: ∑ ∑ 𝑋,,, =1     ∀𝑤,𝑗 (1) 𝐹,, +𝐹,, ≥∑(𝑋,,, +𝑋,,,)−1   ∀𝑤,𝑗,𝑘 (1≤𝑠 ≤𝑠) 𝑗≠𝑘 (2) 𝐺,, +𝐺,, ≥∑(𝑋,,,   +𝑋,,,) − 1 ∀𝑤,𝑗,𝑘 (1≤𝑠 ≤𝑠) (1≤𝑖 ≤𝑚) (3) 𝑈, ≥𝐶, −𝑀1−𝐺,, ∀𝑤,𝑗,𝑘 (4) 𝑈, ≥𝑈, +𝑆, −𝑀1−𝐹,, ∀𝑤,𝑗,𝑘 (5) 𝐶, ≥𝐶(), +𝑇, ∀𝑤(2,𝑊) ∀𝑗 (6) 𝐶, ≥𝑈, +𝑆, +𝑇, ∀𝑤,𝑗 (7) 𝐶 ≥𝐶, ∀𝑗 (8) 𝑋,,, ∈{0,1} (1≤𝑤 ≤𝑊)(1≤𝑗≤𝑁)(1≤𝑘 ≤𝑁) (1≤𝑖 ≤ 𝑚) 𝐹,, ,𝐺,, ∈{0,1} (1≤𝑤 ≤𝑊)(1≤ 𝑗 ≤𝑁)(1≤𝑘 ≤𝑁) 𝑈,,𝐶, ≥0 (1≤𝑤 ≤𝑊)(1≤𝑗≤𝑁) Con el conjunto de restricciones (1), el sistema asegura que cada trabajo está asignado a una máquina en cada etapa y a un server de los disponibles en esa etapa para que realice el setup. El conjunto (2) impone que para aquellos trabajos cuyos setup los realice el mismo server, uno vaya antes que el otro. Del mismo modo, el conjunto (3) emplea la misma filosofía, pero para dos trabajos que se procesen en la misma máquina. El conjunto de restricciones (4) asegura que un trabajo no empiece a ser procesado en una máquina hasta que los anteriores trabajos asignados a la misma máquina se hayan completado. Del mismo modo, el conjunto (5) aplica la misma filosofía, pero para los setups de dos trabajos asignados al mismo server en el que uno no puede comenzar hasta que se haya completado el anterior. Con las restricciones del conjunto (6), el sistema asegura que un trabajo no se procesa en la siguiente etapa hasta que no se haya terminado de procesar en la anterior. La relación entre el tiempo 25 de inicio del procesamiento de un trabajo en una etapa con el tiempo de finalización se modela con el conjunto (7). Por último, con el conjunto de restricciones (8) se calcula el makespan. 3.5.3 Modelo HFS/HR adaptado 𝑀𝐼𝑁 𝐶 𝑠.𝑎: ∑𝐷, =1    ∀𝑘 (9) ∑𝐷, ≤1    ∀𝑗 (0,𝑁) (10) ∑𝐷,    ≥ 𝐷, ∀𝑗,𝑘,𝑗 ≠𝑘 (11) ∑𝑋,, =1 ∀𝑖,𝑗   (12) 𝐹,,, +𝐹,,, ≥𝑋,, +𝑋,, − 1 ∀ℎ,𝑖,𝑗,𝑘,𝑠 (𝑖,𝑗 ≠ℎ,𝑘) (13) 𝑈, ≥𝐶, −𝑉1−𝐷, ∀𝑖,𝑗(0,𝑁),𝑘,𝑗≠𝑘 (14) 𝑈, ≥ 𝑈, +∑𝑆,, ∗𝐷, −𝑉1−𝐹,,,∀𝑖,ℎ,𝑗,𝑘  , (𝑖,𝑗≠ℎ,𝑘) (15) 𝐶, ≥𝑈, +∑𝑆,, ∗𝐷, +    𝑇, ∀𝑖,𝑗 (16) 𝐶, ≤𝑈, ∀𝑖(2,𝑀)∀𝑗 (17) 𝐶, =𝑈, =0 ∀𝑖 (18 y 19) 𝐶 ≥𝐶, ∀𝑗 (20) 𝑋,, ∈{0,1} (1≤𝑖 ≤𝑀)(1≤𝑗≤𝑁)(1≤𝑠 ≤𝑆) 𝐹,,, ∈{0,1} (1≤𝑖,ℎ≤𝑀)(1≤𝑗,𝑘 ≤𝑁) (𝑖,𝑗≠ℎ,𝑘) 𝐷, ∈{0,1} (0≤𝑗≤𝑁)(1≤𝑘 ≤𝑁)(𝑗≠𝑘) 𝑈,,𝐶, ≥0 (1≤𝑖 ≤𝑀)(0≤𝑗 ≤𝑁) Los tres primeros conjuntos de restricciones del modelo (9, 10 y 11) ajustan la precedencia y sucesión de un trabajo respecto a otro. Con el conjunto (12), el modelo asegura 26 que el setup de cada trabajo en cada máquina se asigna a un único server. El conjunto (13) impone que para aquellos trabajos cuyos setup los realice el mismo server, uno vaya antes que el otro. El conjunto de restricciones (14) impone que un trabajo no puede empezar hasta que el que iba inmediatamente antes no haya acabado. Las restricciones que imponen los servers de que solo pueden procesar un setup a la vez se ve reflejada en el conjunto (15). El modelo impone con el conjunto de restricciones (16) la relación entre el tiempo de inicio de procesamiento de un trabajo en una máquina con su tiempo de finalización. EL conjunto (17) asegura que un trabajo no comienza a procesarse en la siguiente máquina hasta que no haya acabado en la anterior. Por último, los conjuntos de restricciones (18 y 19) establecen los tiempos de inicio y acabado del trabajo dummy inicial mientras que el conjunto (20) calcula el makespan. Resolución de la instancia de ejemplo. A continuación, se presenta la solución que plantea este modelo para la instancia planteada en el punto 3.2.4. En la tabla 3-7 se presentan las variables binarias que se activan en el modelo HFSHR adaptado, así como los valores de las variables que hacen referencia a tiempos. Como se puede comprobar, tanto la secuencia óptima como el valor del makespan coinciden con los presentados en los modelos de Wilson y TS2 en los apartados 3.3.3 y 3.4.3 siendo (4,2,3,1) y makespan igual a 98 u.t. La figura 3-3 se corresponde con el diagrama de Gantt para la solución óptima en la que se representa cada trabajo en la posición correspondiente de la secuencia solución. Posición Asignación a server Tiempos inicio setup Tiempos fin proceso 𝐷  ,  𝑋  ,  ,  𝑋  ,  ,  𝑈  ,  = 51 𝑈  ,  = 49 𝐶  ,  = 71 𝐶  ,  = 69 𝐷  ,  𝑋  ,  ,  𝑋  ,  ,  𝑈  ,  = 14 𝑈  ,  = 18 𝐶  ,  = 29 𝐶  ,  = 29 𝐷  ,  𝑋  ,  ,  𝑋  ,  ,  𝑈  ,  = 34 𝑈  ,  = 83 𝐶  ,  = 46 𝐶  ,  = 98 𝐷  ,  𝑋  ,  ,  𝑋  ,  ,  𝑈  ,  = 0 𝑈  ,  = 57 𝐶  ,  = 14 𝐶  ,  = 69 𝑋  ,  ,  𝑋  ,  ,  𝑈  ,  = 71 𝑈  ,  = 69 𝐶  ,  = 83 𝐶  ,  = 83 𝑋  ,  ,  𝑋  ,  ,  𝑈  ,  = 29 𝑈  ,  = 37 𝐶  ,  = 49 𝐶  ,  = 57 Precedencia en ejecución de los setups 𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  27 𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  𝐹  ,  ,  ,  4 14 17 19 21 29 30 31 32 34 38 40 49 51 52 53 54 57 58 61 69 70 72 74 84 98 M1 (1,0,4) 4 (1,4,2) 2 (1,2,3) 3 (1,3,1) 1 M2 (2,0,4) 4 (2,4,2) 2 (2,2,3) 3 (2,3,1) 1 M3 (3,0,4) 4 (3,4,2) 2 (3,2,3) 3 (3,3,1) 1 S1 (1,0,4) (2,2,3) (3,2,3) (2,3,1) (3,3,1) S2 (1,4,2) (2,0,4) (2,4,2) (1,2,3) (3,0,4) (1,3,1) (3,4,2) 4 14 17 19 21 29 30 31 32 34 38 40 49 51 52 53 54 57 58 61 69 70 72 74 84 98 Tabla 3-7 Resultados de la instancia de ejemplo con modelo HFSHR Adaptado. [Fuente: Elaboración propia] Ilustración 3-3 Diagrama de Gantt para instancia ejemplo resuelto con modelo HFSHR adaptado. Para una mejor visualización de la gráfica, los tiempos de proceso no presentan escalas uniformes. [Fuente: Elaboración propia] 28 3.6 Modelo Naderi (2014) Modelo 1 3.6.1 Introducción Este modelo del artículo de Naderi et al., (2014) está planteado para la resolución de un entorno Flow Shop híbrido flexible, es decir, que todos los trabajos tienen que ser procesados en todas las etapas, pero únicamente en una de las máquinas disponibles en cada etapa. El índice que se empleará para las etapas será w. Para la adaptación se empleará una variable binaria de precedencia inmediata de dos setup asignados al mismo server. 3.6.2 Naderi (2014) Modelo 1 original. El modelo emplea las siguientes variables: 𝑌,,, 1 si el trabajo j de procesa inmediatamente antes que k en la máquina i en la etapa w MIN 𝐶 𝑠.𝑎: ∑ ∑ 𝑌𝑤,𝑖,𝑗,𝑘 𝑚𝑤 𝑖=1 𝑘𝜖{0∪𝐸𝑤},𝑗≠𝑘 =1 ∀𝑤,𝑗𝜖𝐸𝑤 (1) ∑ ∑ 𝑌𝑤,𝑖,𝑗,𝑘 𝑚𝑤 𝑖=1 𝑗𝜖𝐸𝑤,𝑗≠𝑘 ≤1 ∀𝑤,𝑘𝜖𝐸𝑤 (2) ∑𝑌𝑤,𝑖,0,𝑗 𝑗𝜖𝐸𝑤=1 ∀𝑤,𝑖 (3) ∑𝑌𝑤,𝑖,𝑗,𝑘 𝑗𝜖𝐸𝑤,𝑗≠𝑘 ≤∑𝑌𝑤,𝑖,𝑘,𝑗 𝑗𝜖{0∪𝐸𝑤},𝑗≠𝑘 ∀𝑤,𝑖,𝑘 𝜖𝐸𝑤 (4) ∑( 𝑚𝑤 𝑖=1 𝑌𝑤,𝑖,𝑗,𝑘 +𝑌𝑤,𝑖,𝑘,𝑗 )≤1 ∀𝑤,(𝑗,𝑘)𝜖𝐸𝑤 (5) 𝐶, ≥𝑇, ∀𝑗𝜖𝐸 (6) 𝐶, ≥𝑇, ∀𝑤(2,𝑊)∀𝑗𝜖𝐸 (7) 𝐶, ≥𝐶, +𝑇, −𝑉(1−∑𝑌,,, )   ∀𝑤,∀(𝑗,𝑘)𝜖𝐸,𝑗 ≠𝑘 (8) 𝐶 ≥ 𝐶, ∀𝑗 (9) 𝐶, ≥0 ∀𝑤,𝑗 29 𝑌,,, ∈{0,1} ∀𝑤,𝑖,𝑗𝜖𝐸,𝑗𝜖{0∪𝐸},𝑗 ≠𝑘 El conjunto de restricciones (1) asegura que, en cada etapa, cada trabajo tiene un solo predecesor y con el conjunto (2), que como mucho, cada trabajo tiene un sucesor. Con las restricciones del conjunto (3), el modelo impone que hay un único trabajo inicial. Estas tres restricciones expuestas anteriormente, se modelan para todas las etapas asegurando que solo hay una máquina en cada etapa que lo cumple con el conjunto (4). Las restricciones pertenecientes al conjunto (5) imponen la precedencia inmediata para los trabajos que se procesen en la misma máquina. El conjunto (6) marca el tiempo de finalización del proceso de los trabajos en la primera etapa para que, con el conjunto de restricciones (7), se asegure de que un trabajo no pase a la siguiente etapa hasta que no se haya completado en la anterior. El conjunto (8) asegura que se cumple la relación de dos trabajos consecutivos cumple la secuencia. Por último, el conjunto de restricciones (9) calcula el makespan. 3.6.3 Naderi (2014) Modelo 1 adaptado 𝑌,,,, =1 Si el server s hace el setup del trabajo j en la máquina i inmediatamente antes que el setup de k en la máquina h MIN 𝐶 𝑠.𝑎: ∑𝐷, =1    ∀𝑘 (10) ∑𝐷, ≤1    ∀𝑗 (0,𝑁) (11) ∑𝐷,    ≥ 𝐷, ∀𝑗,𝑘,𝑗 ≠𝑘 (12) 𝐶, ≥𝑇, + ∑(𝑆,,    ∗𝐷,) ∀𝑘 (13) 𝐶, −𝐶, ≥𝑇, + ∑(𝑆,,    ∗𝐷,) ∀𝑖(2,𝑀) ∀𝑘 (14) 𝐶, −𝐶, +𝑉1−𝐷,≥𝑇, + 𝑆,, ∀𝑗(0,𝑁)∀𝑘,𝑗 ≠𝑘,∀𝑖 (15) ∑(𝑌,,,, +∑ ∑ 𝑌,,,, )   =1 ∀ℎ,𝑘     (𝑖,𝑗 ≠ℎ,𝑘) (16) ∑ ∑ ∑ 𝑌,,,,   ≤1 ∀𝑖,𝑗     (𝑖,𝑗≠ℎ,𝑘) (17) 30 ∑ ∑ 𝑌,,,,   =1 ∀𝑠   (18) ∑ ∑ 𝑌,,,,     +𝑌,,,, ≥∑ ∑ 𝑌,,,,     ∀𝑠,𝑖,𝑗 (𝑖,𝑗 ≠ℎ,𝑘) (𝑖,𝑗 ≠𝑜,𝑙) (19) 𝐶, − 𝑇, + 𝑉1 − 𝑌,,,, ≥ 𝐶, − 𝑇, +∑(𝑆,,    ∗𝐷,) (20) ∀𝑠,ℎ,𝑖,𝑗,𝑘 (𝑖,𝑗 ≠ℎ,𝑘) 𝐶, − 𝑇, + 𝑉1 − 𝑌,,,, ≥ ∑(𝑆,,    ∗𝐷,) ∀𝑠,ℎ,𝑘 (21) 𝐶 ≥ 𝐶, ∀𝑗 (22) 𝐷, ∈{0,1} (0≤𝑗≤𝑁)(1≤𝑘 ≤𝑁)(𝑗≠𝑘) 𝐶, ≥0 ∀𝑖,𝑗(0,𝑁) 𝑌,,,, ∈{0,1} ∀𝑠,ℎ,𝑖,𝑗,𝑘(𝑖,𝑗 ≠ℎ,𝑘) 𝑌,,,, ∈{0,1} ∀𝑠,ℎ,𝑘 En el modelo adaptado, los conjuntos de restricciones (10) y (11) aseguran que cada trabajo tenga un predecesor y un sucesor mientras que el conjunto (12), restringe a que cada trabajo tenga como máximo un sucesor. El conjunto de restricciones (13) asegura que todos los trabajos se procesen en la primera máquina. Con las restricciones pertenecientes al conjunto (14) y (15), se impone que un trabajo no se procese en la siguiente máquina hasta que no haya finalizado en la anterior y se haya realizado el setup y que no se empiece a procesar un trabajo hasta que no haya acabado de procesarse en esa máquina el trabajo anterior. Las restricciones de los conjuntos (16-19) modelan la variable de asignación de setup a servers sabiendo qué setup precede inmediatamente a otro. Finalmente, con los conjuntos (20 y 21) se impone que cada server solo puede procesar un setup a la vez mientras que el conjunto de restricciones (22) calcula el makespan. Resolución de la instancia de ejemplo. A continuación, se presenta la solución que plantea este modelo para la instancia planteada en el punto 3.2.4. En la tabla 3-8 se presentan las variables binarias que se activan 37 Ilustración 4-2 Gráfico análisis tiempo computacional. [Fuente: Elaboración propia] Como se podía prever, los modelos HFSHR y Naderi (2014) han tardado más tiempo computacional en resolver las diferentes instancias. Cabe destacar el rápido paso de estos dos modelos de tiempos menores a 100 segundos a llegar al tiempo límite de los 500 segundos lo que provoca que tengan además una gran desviación. Por otro lado, los modelos Wilson y TS2 han tardado menos y con un aumento progresivo en relación con el aumento en el tamaño de la instancia. 4.2.3 Análisis del indicador ARPD. En la tabla 4.3 se pueden visualizar los promedios de los valores que ha tomado el indicador ARPD en los diferentes modelos e instancias. Para aquellos casos en los que el modelo no haya encontrado una solución factible, el ARPD se calculará solo con las soluciones factibles para esa instancia y en caso de no haber encontrado ninguna se 0,00 50,00 100,00 150,00 200,00 250,00 300,00 350,00 Wilson TS2 HFSHR Naderi (2014) SEGUNDOS MODELOS Análisis tiempo computacional Promedio Desviación 38 representará como E (error). Posteriormente, en la figura 4.3 se puede visualizar el valor promedio total de este indicador para todas las instancias. N M Wilson TS2 HFSHR Naderi (2014) 4 4 0,00 0,00 0,00 0,00 5 0,00 0,00 0,00 0,00 6 0,00 0,00 0,00 0,00 5 4 0,00 0,00 0,00 0,00 5 0,00 0,00 0,00 0,00 6 0,00 0,00 0,00 0,00 7 4 0,00 0,00 0,00 0,00 5 0,00 0,00 0,00 23,78 6 0,00 0,00 0,00 10,70* 10 4 0,00 0,00 4,32 21,75* 5 0,00 0,00 11,23 E 6 0,00 0,00 9,65 E 15 4 0,00 0,00 15,37 E 5 0,00 0,00 22,17 E 6 0,00 0,00 21,30 E 20 4 0,00 0,06 22,52 E 5 1,15 1,02 37,07 E 6 1,32 2,67 61,50 E Promedio % 0,14 0,21 11,40 5,62** Tabla 4-3 Análisis del indicador ARPD. [Fuente: Elaboración propia] * Valores calculados con las soluciones factibles alcanzadas al haber muchos casos en los que no se ha llegado a una solución factible. ** Valor calculado con el promedio de las instancias en las que se ha llegado a alguna solución factible dentro del tiempo límite. 39 En primer lugar, se puede apreciar que los modelos Wilson y TS2 presentan una variación mínima respecto a las soluciones óptimas encontradas mientras que los promedios de los modelos HFSHR adaptado y Naderi (2014) adaptado son más alto. Hay que destacar que, pese a que la adaptación del modelo Naderi (2014) presenta un promedio de solo un 5,62% este dato no es del todo real debido a que hay un gran número de instancias para las que no ha encontrado una solución factible por lo que, si se aumentase el tiempo límite, este valor seguiría creciendo conforme el sistema empiece a encontrar soluciones factibles para dichas instancias. Por último, haciendo referencia a lo mencionando anteriormente, se puede apreciar que en los casos en los que el modelo de Naderi encontraba soluciones factibles para todas las instancias (antes de problemas con siete trabajos y seis máquinas), el modelo HFSHR ha presentado un menor o igual ARPD. 0,00 2,00 4,00 6,00 8,00 10,00 12,00 Wilson TS2 HFSHR Naderi (2014) PORCENTAJE % MODELOS Análisis ARPD Ilustración 4-3 Gráfica análisis ARPD. [Fuente: Elaboración propia] 40 Capítulo 5 Conclusiones En este proyecto se ha realizado diseñado cuatro modelos de programación lineal entera partiendo de modelos ya existentes en la literatura de la programación de la producción sobre entornos flowshop con el fin de ser capaz de resolver aquellas situaciones en las que haya recursos humanos (servers) que realicen los setups entre los diferentes trabajos. El estudio tiene como finalidad principal la búsqueda de la filosofía más eficiente para la resolución de las instancias con servers. Por ello se ha trabajado con tres filosofías diferentes para las restricciones de los servers que se podrían resumir en:  Adaptación de la metodología planteada por Samarghandi (2015) en su artículo. Utilizado para modelos Wilson adaptado y TS2 adaptado.  Asignación de setups a servers y emplear un variable de precedencia entre setups. Utilizado en modelo HFSHR adaptado.  Asignación de setups a servers en una variable que marca la precedencia inmediata entre ellos. Utilizado en modelo Naderi (2014) “Modelo 1” adaptado. Tras haber diseñado estos modelos, se procede a la resolución de 720 instancias diferentes con cada uno de los modelos para hacer un análisis del comportamiento de cada uno de ellos. Los resultados presentados en el capítulo 4 son bastantes reveladores en cuanto al comportamiento de los modelos. Los modelos Wilson y TS2 presentan unos resultados más favorables en los tres indicadores empleados: mayor número de soluciones óptimas, menor tiempo de computación y menor ARPD. Esto se debe al menor número de restricciones y de variables que se emplean para modelar la instancia. Por otro lado, los modelos HFSHR y Naderi (2014) han demostrado ser menos eficientes a la hora de resolver las diferentes instancias. Estos dos modelos presentan una gran cantidad de variables con las que se modelan las restricciones de los servers ( 𝐹,,, en el caso del modelo HFSHR adaptado y 𝑌,,,, en el caso del de Naderi et al.,2014 “Modelo 1” adaptado) y sus respectivas restricciones asociadas lo que provoca un aumento en el tiempo de computación tal y como se ve reflejado en los resultados del capítulo 4. 41 Si bien es cierto que tanto el modelo Wilson adaptado como el TS2 adaptado presentan los mejores resultados, se puede apreciar un ligero mejor comportamiento del modelo Wilson tardando un segundo menos de media en encontrar la solución óptima. Esta pequeña diferencia entre ambos se debe al número de variables que emplea cada uno trabajando Wilson solamente con la variable de tiempo de inicio de procesamiento tras setup mientras que el modelo de TS2 adaptado utiliza tanto esas como el tiempo de finalización de la operación. Se puede afirmar con estas leves diferencias que estos dos modelos presentan un comportamiento prácticamente idéntico. Este estudio aporta como resultados, evidencias que afirman que la filosofía más eficiente en cuanto al modelado de la restricción de recursos humanos en el entorno flowshop es la planteada en los modelos Wilson y TS2 adaptados. Este resultado no implica que el comportamiento de los modelos originales sea menos eficiente que los modelos originales planteados en los artículos de Costa et al. (2020) y Naderi et al. (2014) ya que para cada uno de ellos se han empleado diferentes filosofías como ha sido mencionado al inicio de este capítulo por lo que una posible línea de estudio, sería el modelado y posterior análisis de estos cuatro modelos empleando una filosofía adaptada a la planteada para los modelos Wilson y TS2 adaptados. Por otro lado, otra posible línea de estudio podría ser analizar estos modelos añadiendo una restricción para que la tarea que desempeñen los servers esté compensadas a fin de que el tiempo que estén ocupados los servers sea similar y facilitar, así, la implantación en una industria con estas características en cuanto a su entorno productivo. Por último, es necesario constatar que actualmente no hay muchos estudios sobre este entorno productivo por lo que es un campo bastante abierto que permite una mayor profundización en cuanto a la resolución exacta y con posibles futuras resoluciones aproximadas para instancias más extensas. 42 43 Bibliografía Brucker, P., Knust, S., & Wang, G. (2005). Complexity results for flow-shop problems with a single server. European Journal of Operational Research, 165(2), 398-407. doi:10.1016/j.ejor.2004.04.010. Costa, A., Fernandez-Viagas, V., & Framinan, J. M. (2020). Solving the hybrid flow shop scheduling problem with limited human resource constraint. Computers and Industrial Engineering, 146 doi:10.1016/j.cie.2020.106545 Fernandez-Viagas, V., Costa, A., & Framinan, J. M. (2020). Hybrid flow shop with multiple servers: A computational evaluation and efficient divide-and-conquer heuristics. Expert Systems with Applications, 153 doi:10.1016/j.eswa.2020.113462 Framinan, J. M., Leisten, R., & García, R. R. (2014). Manufacturing scheduling systems: An integrated view on models, methods and tools (pp. 1-400) doi:10.1007/978-1-4471-6272-8 Gupta, J. N. D., & Darrow, W. P. (1986). The two-machine sequence dependent flowshop scheduling problem. European Journal of Operational Research, 24(3), 439-446. doi:10.1016/0377-2217(86)90037-8 Naderi, B., Gohari, S., & Yazdani, M. (2014). Hybrid flexible flowshop problems: Models and solution methods. Applied Mathematical Modelling, 38(24), 5767-5780. doi:10.1016/j.apm.2014.04.012 Pinedo, M. L. (2016). Scheduling: Theory, algorithms, and systems, fifth edition (pp. 1-670) doi:10.1007/978-3- 319-26580-3 Samarghandi, H. (2015). Studying the effect of server side-constraints on the makespan of the no-wait flow-shop problem with sequence-dependent set-up times. International Journal of Production Research, 53(9), 2652-2673. doi:10.1080/00207543.2014.974846 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(1), 88-101. doi:10.1057/palgrave.jors.2601805 44 Tseng, F. T., & Stafford Jr., E. F. (2008). New MILP models for the permutation flowshop problem. Journal of the Operational Research Society, 59(10), 1373-1386. doi:10.1057/palgrave.jors.2602455 Werner, F., & Kravchenko, S. A. (2010). Scheduling with multiple servers. Automation and Remote Control, 71(10), 2109-2121. doi:10.1134/S0005117910100103 45 Anexo Declaración de variables y generación aleatoria de datos public int trabajos, operations; public int posiciones, positions; public int maquinas, machines; public int servers, workers; public int[,] tp; public int[,,] set; public int i, h, j, k, l, p, s; public double V = 9999; public LecturaDatos(int maq, int trab, int serv) { maquinas = maq; servers = serv; trabajos = trab; posiciones = trabajos; machines = maquinas + 1; operations = trabajos + 1; workers = servers + 1; positions = posiciones + 1; tp = new int[machines, operations]; set = new int[machines, operations, operations]; } //Generación aleatoria de tiempos de proceso y de setup public void GeneracionAleatoria(Random rd, int range) { int i, j, k; for (i = 1; i <= maquinas; i++) { for (j = 1; j <= trabajos; j++) { tp[i, j] = rd.Next(1,100); } } for (i = 1; i <= maquinas; i++) { for (j = 0; j <= trabajos; j++) { for (k = 1; k <= trabajos; k++) { if (j != k) { set[i, j, k] = rd.Next(1, range); } } } } } //Fin generación aleatoria 46 Main y creación de ficheros static void Main(string[] args) { Stopwatch reloj = new Stopwatch(); //Creacion fichero System.IO.StreamWriter FicheroCSV1; creacionFicherosCSV_ARPD_nuevo_sinN(out FicheroCSV1); FicheroCSV1.Close(); //Parametros de entrada int[] m = new int[] { 4,5,6 }; int[] n = new int[] { 4, 5, 7, 10, 15, 20 }; int[] server = new int[] {2,3}; int[] rangesetup = new int[] {10, 50, 100, 125 }; int numeroIteraciones = 5; int problema = 0; for (int a = 0; a < n.Length; a++) { for (int b = 0; b < m.Length; b++) { for (int c = 0; c < server.Length; c++) { for (int d = 0; d < rangesetup.Length; d++) { for (int it = 0; it < numeroIteraciones; it++) { Random rd = new Random(problema); problema++; creacionFicherosCSV_ARPD_sinN(out FicheroCSV1); LecturaDatos input = new LecturaDatos(m[b], n[a], server[c]); input.GeneracionAleatoria(rd, rangesetup[d]); int optimo, otro, infactible, factible; double tiempoMilisegundos, tiempo, FO1, FO3 , FO2, FO4 , tiempolimite = 500; //Llamada a modelo 1 reloj.Restart(); input.ModeloWilson(out optimo, out otro, out infactible, out factible, out FO1, tiempolimite); tiempoMilisegundos = reloj.ElapsedMilliseconds; tiempo = tiempoMilisegundos / 1000; FicheroCSV1.Write(n[a] + ";" + m[b] + ";" + server[c] + ";" + rangesetup[d] + ";" + it + ";" + problema + ";"); FicheroCSV1.Write(""); //Escritura solución modelo 1 FicheroCSV1.Write(";" + FO1); FicheroCSV1.Write(";" + tiempo); FicheroCSV1.Write(";" + optimo + ";" + factible + ";" + otro + ";" + infactible); FicheroCSV1.Write(";"); //Llamada a modelo 2 reloj.Restart(); input.ModeloTS2(out optimo, out otro, out infactible, out factible, out FO2, tiempolimite); tiempoMilisegundos = reloj.ElapsedMilliseconds; tiempo = tiempoMilisegundos / 1000; 53 for (l = 2; l <= posiciones; l++) { for (p = 1; p < l; p++) { GRBLinExpr sum1 = 0.0; for (j = 0; j <= trabajos; j++) { for (k = 1; k <= trabajos; k++) { if (j != k) { sum1.AddTerm(set[h, j, k], alpha[j, p - 1, k]); } } } model.AddConstr(B[h, p] - B[i, l] - sum1 + V * (2 - gamma[s, h, p] - gamma[s, i, l]) >= 0, "c11"); } } } } } //Función objetivo GRBLinExpr sumcmax = 0.0; for (j = 1; j <= trabajos; j++) { sumcmax.AddTerm(tp[maquinas, j], Z[j, posiciones]); } model.AddConstr(sumcmax + B[maquinas, posiciones] - makespan1 == 0, "cmax"); model.Write("modeloWilson.lp"); model.Set(GRB.DoubleParam.TimeLimit, tiempolimite); model.Optimize(); //Devolución de Gurobi optimo = 0; otro = 0; infactible = 0; factible = 0; FO1 = -1; int modelstatus = model.Get(GRB.IntAttr.Status); if (modelstatus == GRB.Status.OPTIMAL) { optimo = 1; otro = 0; infactible = 0; FO1 = model.Get(GRB.DoubleAttr.ObjVal); factible = 0; } else if (modelstatus == GRB.Status.INFEASIBLE) { optimo = 0; otro = 0; infactible = 1; factible = 0; } else if (modelstatus == 9) 54 { optimo = 0; otro = 0; infactible = 0; factible = 1; FO1 = model.Get(GRB.DoubleAttr.ObjVal); } else { optimo = 0; otro = 1; infactible = 0; factible = 0; } } //Fin modelo Wilson 55 Modelo TS2 adaptado //Modelo TS2 public void ModeloTS2(out int optimo, out int otro, out int infactible, out int factible, out double FO2, double tiempolimite) { Console.WriteLine("Modelo TS2 Adaptado"); GRBEnv env = new GRBEnv("ModeloTS2.log"); GRBModel model = new GRBModel(env); //Declaración de variables GRBVar[,] E = new GRBVar[machines, positions]; for (i = 1; i <= maquinas; i++) { for (p = 1; p <= posiciones; p++) { E[i, p] = model.AddVar(0.0, GRB.INFINITY, 0.0, GRB.CONTINUOUS, "E[" + i + "," + p + "]"); } } GRBVar[,] Z = new GRBVar[operations, positions]; for (j = 1; j <= trabajos; j++) { for (p = 1; p <= posiciones; p++) { Z[j, p] = model.AddVar(0.0, 1.0, 0.0, GRB.BINARY, "Z[" + j + "," + p + "]"); } } GRBVar[,,] alpha = new GRBVar[operations, positions, operations]; for (j = 0; j <= trabajos; j++) { for (p = 0; p <= posiciones; p++) { for (k = 1; k <= trabajos; k++) { if (j != k) { alpha[j, p, k] = model.AddVar(0.0, 1.0, 0.0, GRB.BINARY, "alpha[" + j + "," + p + "," + k + "]"); } } } } GRBVar[,,] gamma = new GRBVar[workers, machines, positions]; for (s = 1; s <= servers; s++) { for (i = 1; i <= maquinas; i++) { for (p = 1; p <= posiciones; p++) { gamma[s, i, p] = model.AddVar(0.0, 1.0, 0.0, GRB.BINARY, "gamma[" + s + "," + i + "," + p + "]"); } } } _ = new GRBVar(); 56 GRBVar makespan2 = model.AddVar(0.0, GRB.INFINITY, 1.0, GRB.CONTINUOUS, "Cmax"); model.Update(); //RESTRICCIONES // Nota: Los números de las restricciones se corresponden a los que aparecen en el documento del TFG. //Restricción 8 for (j = 1; j <= trabajos; j++) { GRBLinExpr sum = 0.0; for (p = 1; p <= posiciones; p++) { sum.AddTerm(1.0, Z[j, p]); } model.AddConstr(sum == 1, "c8"); } //Restricción 9 for (p = 1; p <= posiciones; p++) { GRBLinExpr sum = 0.0; for (j = 1; j <= trabajos; j++) { sum.AddTerm(1.0, Z[j, p]); } model.AddConstr(sum == 1, "c9"); } //Restricción 10 for (j = 1; j <= trabajos; j++) { for (p = 1; p <= (posiciones - 1); p++) { GRBLinExpr sum = 0.0; for (k = 1; k <= trabajos; k++) { if (j != k) { sum.AddTerm(1.0, alpha[j, p, k]); } } model.AddConstr(sum == Z[j, p], "c10"); } } //Restricción 11 for (j = 1; j <= trabajos; j++) { for (p = 2; p <= posiciones; p++) { GRBLinExpr sum = 0.0; for (k = 1; k <= trabajos; k++) { if (j != k) { sum.AddTerm(1.0, alpha[k, p - 1, j]); } } model.AddConstr(sum == Z[j, p], "c11"); } } //Restricción 11prima for (k = 1; k <= trabajos; k++) { 57 model.AddConstr(alpha[0, 0, k] == Z[k, 1], "c11prima"); } //Restricción 12 for (i = 1; i <= maquinas; i++) { for (p = 1; p <= (posiciones - 1); p++) { GRBLinExpr sum1 = 0.0; for (j = 1; j <= trabajos; j++) { for (k = 1; k <= trabajos; k++) { if (j != k) { sum1.AddTerm(set[i, j, k], alpha[j, p, k]); } } } GRBLinExpr sum2 = 0.0; for (j = 1; j <= trabajos; j++) { sum2.AddTerm(tp[i, j], Z[j, p + 1]); } model.AddConstr(E[i, p] + sum1 + sum2 - E[i, p + 1] <= 0, "c12"); } } //Restricción 13 for (i = 1; i <= maquinas - 1; i++) { for (p = 2; p <= posiciones; p++) { GRBLinExpr sum1 = 0.0; for (j = 1; j <= trabajos; j++) { for (k = 1; k <= trabajos; k++) { if (j != k) { sum1.AddTerm(set[i + 1, j, k], alpha[j, p - 1, k]); } } } GRBLinExpr sum2 = 0.0; for (j = 1; j <= trabajos; j++) { sum2.AddTerm(tp[i + 1, j], Z[j, p]); } model.AddConstr(E[i, p] + sum1 + sum2 - E[i + 1, p] <= 0, "c13"); } } //Restricción 14 for (i = 1; i <= maquinas - 1; i++) { GRBLinExpr sum1 = 0.0; for (k = 1; k <= trabajos; k++) { sum1.AddTerm(set[i + 1, 0, k], alpha[0, 0, k]); } GRBLinExpr sum2 = 0.0; for (j = 1; j <= trabajos; j++) { 58 sum2.AddTerm(tp[i + 1, j], Z[j, 1]); } model.AddConstr(E[i, 1] + sum1 + sum2 - E[i + 1, 1] <= 0, "c14"); } //Restricción 15 GRBLinExpr suma = 0.0; for (k = 1; k <= trabajos; k++) { suma.AddTerm(set[1, 0, k], alpha[0, 0, k]); } GRBLinExpr sumb = 0.0; for (j = 1; j <= trabajos; j++) { sumb.AddTerm(tp[1, j], Z[j, 1]); } model.AddConstr(E[1, 1] - suma - sumb == 0, "c15"); //Restricción 16 Servers for (i = 1; i <= maquinas; i++) { for (p = 1; p <= posiciones; p++) { GRBLinExpr sum = 0.0; for (s = 1; s <= servers; s++) { sum.AddTerm(1.0, gamma[s, i, p]); } model.AddConstr(sum == 1, "c16"); } } //Restricción 17 Servers adaptación a variables del modelo: l=p';h=i' for (s = 1; s <= servers; s++) { for (h = 2; h <= maquinas; h++) { for (i = 1; i < h; i++) { for (l = 2; l <= posiciones; l++) { for (p = 1; p < l; p++) { GRBLinExpr sum1 = 0.0; for (j = 0; j <= trabajos; j++) { for (k = 1; k <= trabajos; k++) { if (j != k) { sum1.AddTerm(set[h, j, k], alpha[j, p - 1, k]); } } } GRBLinExpr sum2 = 0.0; for (j = 1; j <= trabajos; j++) { sum2.AddTerm(tp[h, j], Z[j, p]); } GRBLinExpr sum3 = 0.0; 59 for (j = 1; j <= trabajos; j++) { sum3.AddTerm(tp[i, j], Z[j, l]); } model.AddConstr(E[h, p]-sum2 -( E[i, l]-sum3 ) - sum1 + V * (2 - gamma[s, h, p] - gamma[s, i, l]) >= 0, "c17"); } } } } } //Función objetivo model.AddConstr(makespan2 - E[maquinas, posiciones] == 0, "cmax"); model.Write("modeloTS2.lp"); model.Set(GRB.DoubleParam.TimeLimit, tiempolimite); model.Optimize(); //Devolución de Gurobi optimo = 0; otro = 0; infactible = 0; factible = 0; FO2 = -1; int modelstatus = model.Get(GRB.IntAttr.Status); if (modelstatus == GRB.Status.OPTIMAL) { optimo = 1; otro = 0; infactible = 0; FO2 = model.Get(GRB.DoubleAttr.ObjVal); factible = 0; } else if (modelstatus == GRB.Status.INFEASIBLE) { optimo = 0; otro = 0; infactible = 1; factible = 0; } else if (modelstatus == 9) { optimo = 0; otro = 0; infactible = 0; factible = 1; FO2 = model.Get(GRB.DoubleAttr.ObjVal); } else { optimo = 0; otro = 1; infactible = 0; factible = 0; } } //Fin modelo TS2 60 Modelo HFSHR adaptado // Modelo HFS/HR public void ModeloHFSHR(out int optimo, out int otro, out int infactible, out int factible, out double FO3, double tiempolimite) { Console.WriteLine("Modelo HFSHR Adaptado"); GRBEnv env = new GRBEnv("ModeloHFSHR.log"); GRBModel model = new GRBModel(env); //Declaración de variables GRBVar[,,] X = new GRBVar[machines, operations, workers]; for (i = 1; i <= maquinas; i++) { for (j = 1; j <= trabajos; j++) { for (s = 1; s <= servers; s++) { X[i, j, s] = model.AddVar(0.0, 1.0, 0.0, GRB.BINARY, "X[" + i + "," + j + "," + s + "]"); } } } GRBVar[,,,] F = new GRBVar[machines, operations, machines, operations]; for (i = 1; i <= maquinas; i++) { for (j = 1; j <= trabajos; j++) { for (h = 1; h <= maquinas; h++) { for (k = 1; k <= trabajos; k++) { if (i == h && j == k) { } else { F[i, j, h, k] = model.AddVar(0.0, 1.0, 0.0, GRB.BINARY, "F[" + i + "," + j + "," + h + "," + k + "]"); } } } } } GRBVar[,] D = new GRBVar[operations, operations]; for (j = 0; j <= trabajos; j++) { for (k = 1; k <= trabajos; k++) { if (k != j) { D[j, k] = model.AddVar(0.0, 1.0, 0.0, GRB.BINARY, "D[" + j + "," + k + "]"); } } } GRBVar[,] C = new GRBVar[machines, operations]; for (i = 1; i <= maquinas; i++) { 61 for (j = 0; j <= posiciones; j++) { C[i, j] = model.AddVar(0.0, GRB.INFINITY, 0.0, GRB.CONTINUOUS, "C[" + i + "," + j + "]"); } } GRBVar[,] U = new GRBVar[machines, operations]; for (i = 1; i <= maquinas; i++) { for (j = 0; j <= posiciones; j++) { U[i, j] = model.AddVar(0.0, GRB.INFINITY, 0.0, GRB.CONTINUOUS, "U[" + i + "," + j + "]"); } } GRBVar makespan3 = new GRBVar(); makespan3 = model.AddVar(0.0, GRB.INFINITY, 1.0, GRB.CONTINUOUS, "Cmax"); model.Update(); //Fin declaración de variables //RESTRICCIONES // Nota: Los números de las restricciones se corresponden a los que aparecen en el documento del TFG. //Restricción 9 for (k = 1; k <= trabajos; k++) { GRBLinExpr sum = 0.0; for (j = 0; j <= trabajos; j++) { if (j != k) { sum.AddTerm(1.0, D[j, k]); } } model.AddConstr(sum == 1, "c9"); } //Restricción 10 for (j = 0; j <= trabajos; j++) { GRBLinExpr sum = 0.0; for (k = 1; k <= trabajos; k++) { if (j != k) { sum.AddTerm(1.0, D[j, k]); } } model.AddConstr(sum <= 1, "c10"); } //Restricción 11 for (j = 1; j <= trabajos; j++) { for (k = 1; k <= trabajos; k++) { if (j != k) { GRBLinExpr sum = 0.0; for (h = 0; h <= trabajos; h++) { 62 if (h != j) { sum.AddTerm(1.0, D[h, j]); } } model.AddConstr(sum - D[j, k] >= 0, "c11"); } } } //Restricción 12 for (i = 1; i <= maquinas; i++) { for (j = 1; j <= trabajos; j++) { GRBLinExpr sum = 0.0; for (s = 1; s <= servers; s++) { sum.AddTerm(1.0, X[i, j, s]); } model.AddConstr(sum == 1, "c12"); } } //Restricción 13 for (i = 1; i <= maquinas; i++) { for (j = 1; j <= trabajos; j++) { for (h = 1; h <= maquinas; h++) { for (k = 1; k <= trabajos; k++) { if (i == h && j == k) { } else { for (s = 1; s <= servers; s++) { model.AddConstr(-X[i, j, s] - X[h, k, s] + F[i, j, h, k] + F[h, k, i, j] + 1 >= 0, "c13"); } } } } } } //Restricción 14 for (i = 1; i <= maquinas; i++) { for (j = 0; j <= trabajos; j++) { for (k = 1; k <= trabajos; k++) { if (j != k) { model.AddConstr(U[i, k] - C[i, j] + V * (1 - D[j, k]) >= 0, "c3"); } } } } 69 for (j = 1; j <= trabajos; j++) { GRBLinExpr sum1 = 0.0; GRBLinExpr sum2 = 0.0; int o; for (o = 1; o <= maquinas; o++) { for (l = 1; l <= trabajos; l++) { if (i == o && j == l) { } else { sum1.AddTerm(1.0, Y[s, o, l, i, j]); } } } for (h = 1; h <= maquinas; h++) { for (k = 1; k <= trabajos; k++) { if (i == h && j == k) { } else { sum2.AddTerm(1.0, Y[s, i, j, h, k]); } } } model.AddConstr(sum1 + Y[s, 0, 0, i, j] - sum2 >= 0, "c19"); } } } //Restricción 20 for (s = 1; s <= servers; s++) { for (i = 1; i <= maquinas; i++) { for (j = 1; j <= trabajos; j++) { for (h = 1; h <= maquinas; h++) { for (k = 1; k <= trabajos; k++) { if (i == h && j == k) { } else { GRBLinExpr sum1 = 0.0; for (l = 0; l <= trabajos; l++) { if (l != k) { sum1.AddTerm(set[h, l, k], D[l, k]); } } model.AddConstr(C[h, k]-tp[h,k] - (C[i, j]- tp[i,j]) - sum1 + V * (1 - Y[s, i, j, h, k]) >= 0, "c20"); } 70 } } } } } //Restricción 21 for (s = 1; s <= servers; s++) { for (h = 1; h <= maquinas; h++) { for (k = 1; k <= trabajos; k++) { GRBLinExpr sum1 = 0.0; for (l = 0; l <= trabajos; l++) { if (l != k) { sum1.AddTerm(set[h, l, k], D[l, k]); } } model.AddConstr(C[h, k]-tp[h,k] - sum1 + V * (1 - Y[s, 0, 0, h, k]) >= 0, "c21"); } } } //Función Objetivo for (k = 1; k <= trabajos; k++) { model.AddConstr(makespan4 - C[maquinas, k] >= 0, "c22"); } model.Write("modeloNaderi.lp"); model.Set(GRB.DoubleParam.TimeLimit, tiempolimite); model.Optimize(); //Devolución de Gurobi optimo = 0; otro = 0; infactible = 0; factible = 0; FO4 = -1; int modelstatus = model.Get(GRB.IntAttr.Status); if (modelstatus == GRB.Status.OPTIMAL) { optimo = 1; otro = 0; infactible = 0; FO4 = model.Get(GRB.DoubleAttr.ObjVal); factible = 0; } else if (modelstatus == GRB.Status.INFEASIBLE) { optimo = 0; otro = 0; infactible = 1; factible = 0; } else if (modelstatus == 9) { optimo = 0; otro = 0; 71 infactible = 0; factible = 1; FO4 = model.Get(GRB.DoubleAttr.ObjVal); } else { optimo = 0; otro = 1; infactible = 0; factible = 0; } }