Efecto de los tiempos de espera en talleres de flujo regular

Trabajo Fin de Grado Grado en Ingeniería de las Tecnologías Industriales Efecto de los tiempos de espera en talleres de flujo regular Autor: Fernando Guerrero Ortega Tutor: Víctor Fernández-Viagas Escudero Dpto. Organización Industrial y Gestión de Empresas Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2017 Trabajo Fin de Grado Grado en Ingeniería de las Tecnologías Industriales Efecto de los tiempos de espera en talleres de flujo regular Autor: Fernando Guerrero Ortega Tutor: Víctor Fernández-Viagas Escudero Profesor Ayudante Doctor Dpto. Organización Industrial y Gestión de Empresas Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2017 Trabajo Fin de Grado: Efecto de los tiempos de espera en talleres de flujo regular Autor: Fernando Guerrero Ortega Tutor: Víctor Fernández-Viagas Escudero El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2017 El Secretario del Tribunal Efecto de los tiempos de espera en talleres de flujo regular Agradecimientos A todo el personal docente, en todos los niveles, que me ha enseñado a aprender y no sólo a estudiar. A los profesores que desde el primer momento consiguieron que encontrara todo el interés en una especialidad respecto a la que era bastante escéptico cuando la escogí. Al tutor de este trabajo, D. Víctor Fernández-Viagas Escudero, quien además de ser uno de los incluidos en el punto anterior, me ha orientado perfectamente desde el primer día, resolviendo todas mis dudas rápida y claramente cada vez que fue necesario. A todos los que mantienen sus principios y siguen escribiendo “sólo” con tilde. Efecto de los tiempos de espera en talleres de flujo regular vii Í NDÍCE ÍNDICE DE TABLAS ..................................................................................................................................... viii ÍNDICE DE FIGURAS ...................................................................................................................................... x 1 INTRODUCCIÓN ....................................................................................................................................... 14 2 DESCRIPCIÓN DEL PROBLEMA ................................................................................................................ 19 2.1 Problemas donde se minimiza el makespan .................................................................................... 21 2.2 Problemas donde se minimiza el tiempo total de finalización ........................................................ 24 3 METODOLOGÍA ....................................................................................................................................... 26 3.1 Problemas y análisis ......................................................................................................................... 26 3.2 Indicadores y Enumeración Completa ............................................................................................. 27 4 DISEÑO DE EXPERIMENTOS .................................................................................................................... 31 5 IMPLEMENTACIÓN .................................................................................................................................. 32 5.1 Adquisición de resultados ................................................................................................................ 32 5.2 Organización de la información ....................................................................................................... 37 6 EVALUACIÓN COMPUTACIONAL ............................................................................................................ 40 6.1 Resultados óptimos de los problemas ............................................................................................. 41 6.2 Dificultad de los problemas.............................................................................................................. 46 6.3 Comportamiento de secuencias óptimas de problemas con esperas limitadas en un PFSP ........... 63 6.4 Comportamiento de la secuencia óptima de un PFSP en problemas con esperas limitadas ........... 69 7 CONCLUSIONES ....................................................................................................................................... 77 8 BIBLIOGRAFÍA ......................................................................................................................................... 79 9 ANEXOS ................................................................................................................................................... 80 9.1 Anexo - Funciones ............................................................................................................................ 80 9.2 Anexo - Análisis de los resultados mediant e distribuciones estadísticas ........................................ 90 9.3 Anexo - Secuencias óptimas de problemas con limitaciones en un PFSP ........................................ 92 Efecto de los tiempos de espera en talleres de flujo regular viii Í NDÍCE DE TABLAS Tabla 1.1 – Tiempos de proceso para un problema con cinco trabajos y cuatro máquinas Tabla 3.1 – Tiempos de proceso para un problema con dos máquinas y tres trabajos Tabla 3.2 – Valores del makespan para cada una de las secuencias de un problema con tres trabajos Tabla 3.3 – Cálculo del RPD para cada una de las secuencias de un problema, y de su ARPD Tabla 6.1 – Valores medios del óptimo para los problemas con FO: Cmax Tabla 6.2 – Incremento relativo de Cmax al aplicar cada una de las restricciones de tiempo máximo de espera Tabla 6.3 – Valores medios del óptimo para los problemas con FO: ∑𝐶𝑗 Tabla 6.4 – Incremento relativo de ∑𝐶𝑗 al aplicar cada una de las restricciones de tiempo máximo de espera Tabla 6.5 – Incremento relativo de cada FO al aplicar la restricción no-wait a un PFSP Tabla 6.6 – ARPD de los problemas con FO: Cmax para los distintos números de trabajos y máquinas, y restricciones de tiempos máximos de espera Tabla 6.7 – ARPD de los problemas con FO: ∑𝐶𝑗 para los distintos números de trabajos y máquinas, y restricciones de tiempos máximos de espera Tabla 6.8 – Probabilidad, para cada problema, de que una secuencia generada aleatoriamente aporte una solución en los primeros k tramos de valores de Cmax Tabla 6.9 – Probabilidad, para cada problema, de que una secuencia generada aleatoriamente aporte una solución en los primeros k tramos de valores de Cmax Tabla 6.10 – Incremento relativo de Cmax al usar la secuencia óptima de los problemas con esperas limitadas en el PFSP, y valores del ARPD para el PFSP Tabla 6.11 – Incremento relativo de ∑𝐶𝑗 al usar la secuencia óptima de los problemas con esperas limitadas en el PFSP, y valores del ARPD para el PFSP Tabla 6.12 – Incremento relativo de Cmax y ∑𝐶𝑗 al usar la secuencia óptima de los problemas con esperas limitadas en el PFSP Tabla 6.13 – Incremento relativo de Cmax y ∑𝐶𝑗 al usar la secuencia óptima del problema sin esperas permitidas en el PFSP Efecto de los tiempos de espera en talleres de flujo regular ix Tabla 6.14 – Incremento relativo de Cmax al usar la secuencia óptima del PFSP en problemas con esperas limitadas Tabla 6.15 – Incremento relativo de Cmax al usar la secuencia óptima del PFSP en el problema no-wait, y ARPD del problema sin esperas permitidas, para cada tamaño de problema Tabla 6.16 – Incremento relativo de ∑𝐶𝑗 al usar la secuencia óptima del PFSP en problemas con esperas limitadas Tabla 6.17 – Incremento relativo de ∑𝐶𝑗 al usar la secuencia óptima del PFSP en el problema no-wait, y ARPD del problema sin esperas permitidas, para cada tamaño de problema Tabla 6.18 – Incremento relativo de Cmax y ∑𝐶𝑗 al usar la secuencia óptima del PFSP en los problemas con esperas limitadas Tabla 6.19 – Incremento relativo de Cmax y ∑𝐶𝑗 al usar la secuencia óptima del PFSP en el problema sin esperas permitidas Efecto de los tiempos de espera en talleres de flujo regular 1. Introducción 16 En este proyecto, atendiendo a distintos criterios relacionados con el tiempo de finalización de los trabajos, se estudia cómo afecta a cada uno de ellos aplicar diversas restricciones en el proceso de fabricación. En concreto, se consideran restricciones referentes al tiempo de espera máximo de un trabajo al pasar de una máquina a la siguiente. Normalmente, a los trabajos se les permite esperar indefinidamente entre etapas si las máquinas posteriores se encuentran ocupadas, pero hay ciertos escenarios donde eso no es admisible, como aquél donde la capacidad de almacenamiento de trabajos esperando a ser tratados por una máquina sea limitada, o en el que los trabajos deban estar continuamente siendo tratados sin que haya interrupción alguna durante su procesado. Dos ejemplos de estas situaciones son los propuestos por Framiñán, Leister y Ruiz (2014), y consisten en el tratamiento del acero, donde éste no debe enfriarse entre cada una de las etapas del proceso de fabricación, y el procesado de alimentos, donde no sólo se debe evitar que se rompa la cadena del frío en caso de tratarse de congelados, sino que también hay que prevenir su posible contaminación. El uso de talleres de tipo flow shop donde no se permita esperar a los trabajos entre dos máquinas consecutivas (es decir, con restricciones no-wait) es bastante común en procesos de fabricación. Sin embargo, la minimización del makespan en estos casos es un problema no polinomial (Ye, Li, Abedini, Nault, 2017), llegando a ser muy complicado alcanzar soluciones cercanas al óptimo para casos con un número de trabajos y/o máquinas lo suficientemente altos, por lo que se usan heurísticas para intentar llegar a una solución no muy distinta a la óptima de manera relativamente sencilla. En procesos de fabricación no-wait, como todos los trabajos se procesan en el mismo orden en cada una de las máquinas y no deben esperar entre dos operaciones consecutivas, el inicio del procesado de un trabajo en la primera máquina podría demorarse con el objeto de que no hubiese interrupciones en su procesado más adelante. La figura 1.3 muestra un caso con cuatro máquinas y cinco trabajos donde no hay ninguna restricción acerca de los tiempos de espera, mientras que en la figura 1.4 se tiene el mismo caso, sólo que esta vez sí que se aplica una restricción no-wait, y por ello el trabajo 4 ve cómo sus tres primeras tareas empiezan más tarde de lo que podrían hacerlo, para así asegurarse de que podrá tratarse en la cuarta máquina inmediatamente después de finalizar su procesado en la tercera. Tabla 1.1 – Tiempos de proceso para un problema con cinco trabajos y cuatro máquinas (Elaboración propia) Efecto de los tiempos de espera en talleres de flujo regular 1. Introducción 17 Figura 1.3 – Diagrama de Gantt resultado de la secuencia π={1,2,3,4,5} para un PFSP sin más restricciones, con los tiempos de proceso de la tabla 1.1 (Elaboración propia) Figura 1.4 – Diagrama de Gantt resultado de la secuencia π={1,2,3,4,5} para un PFSP con restricción nowait, con los tiempos de proceso de la tabla 1.1 (Elaboración propia) No sólo se tratarán los casos extremos donde o no se admitan esperas o se consientan esperas indefinidas, sino que se verán casos donde, permitiéndose una cierta espera, ésta esté limitada. Por ejemplo, para el ejemplo anterior del tratamiento de alimentos se podría tener el caso en el que esperar cinco minutos no llegase a romper la cadena del frío, y por tanto una espera inferior a ese umbral entre etapa y etapa se considerase asumible. También se pueden dar casos donde cierta espera no sólo sea admisible, sino necesaria. Por ejemplo, si tras pintar un producto hubiese que esperar a que la pintura se secase para continuar trabajando sobre él, se tendría un tiempo mínimo de espera entre etapas (Framiñán, Leister, Ruiz, 2014). Aunque estas situaciones no se considerarán en este proyecto. Efecto de los tiempos de espera en talleres de flujo regular 1. Introducción 18 En los siguientes apartados, se detallará en profundidad el problema a tratar en este proyecto, el procedimiento para obtener los resultados de interés, y las conclusiones que se pueden obtener a partir de los mismos.  En el capítulo 2 se describirá más detalladamente el problema a resolver, definiendo las distintas restricciones que se aplicarán al mismo, así como los modelos matemáticos que los caracterizan.  En el capítulo 3 se explicarán los pasos que se siguen para obtener los resultados de cada problema, y los motivos por los que obtener dichos resultados resulta de interés para el objetivo del trabajo.  En el capítulo 4 se indicarán los experimentos que se han llevado a cabo para obtener los resultados que se nombraron en el capítulo previo, justificando el porqué se han considerado los más apropiados para este estudio.  En el capítulo 5 se describirán los programas informáticos construidos y usados con el fin de obtener los resultados descritos en el capítulo 3.  El capítulo 6 se compondrá de la evaluación computacional, es decir, los resultados obtenidos al ejecutar los programas, y una primera interpretación de los mismos.  En el capítulo 7 se expondrán las conclusiones que se pueden sacar a partir de la evaluación computacional realizada y expuesta previamente.  Por último, se adjuntará la bibliografía utilizada para la elaboración del documento, así como anexos con información que no se consideró relevante como para incluirse en el mismo. Efecto de los tiempos de espera en talleres de flujo regular 2. Descripción del problema 19 2 DESCRÍPCÍO N DEL PROBLEMA El proyecto consiste en el estudio del efecto de ciertas restricciones a un proceso de producción dado, donde dichas restricciones serán las que definan los distintos problemas. Los problemas consisten en un entorno de trabajo de tipo taller, flow shop, con m máquinas, donde los n trabajos que la fábrica produce deben pasar por todas las máquinas siguiendo el orden que éstas, dispuestas en serie, marcan. Se consideran dos criterios a la hora de evaluar las distintas secuencias de producción, ambos relacionados con el tiempo de finalización de la producción de los trabajos. Uno de ellos es minimizar el makespan, que es el tiempo en el que se finaliza el último de los trabajos, mientras que el otro trata de minimizar el tiempo total de finalización, que se define como la suma de los tiempos de finalización de cada uno de los trabajos procesados. Se aplica la restricción de permutación en todos los casos a tratar, que hace que el orden de procesado de los trabajos sea idéntico en cada una de las máquinas presentes en el proceso, convirtiéndose así el problema en un PFSP (permutation flow shop problem). Se considera una segunda clase de restricciones, que es donde reside el núcleo del proyecto. Estas restricciones pueden limitar el tiempo de espera máximo de los trabajos entre que salen de una máquina e inician su actividad en la posterior. Se parte del caso en el que esta restricción no se aplica, y a partir de ahí se comienza a considerar un tiempo máximo de espera, que se ve reducido de forma escalonada, hasta llegar a tener una restricción no-wait, que obliga a los trabajos a pasar de una máquina a la siguiente de forma inmediata, no permitiéndose tiempo de espera alguno entre ellas. No se considera ningún otro tipo de restricciones (llegada de trabajos, fechas de entrega, tiempos de setup, buffer…), aunque obviamente sí se consideran las restricciones comunes del entorno flow shop, es decir, que una máquina no puede procesar más de un trabajo simultáneamente, y que un trabajo no puede estar asignado a más de una máquina al mismo tiempo. Para describir el modelo del problema, usaremos la notación introducida por Graham et al. (1979), que consiste en describir los tres conceptos previamente mencionados en tres campos, α|β|γ, siendo cada uno de ellos:  α: el entorno del proceso de fabricación, es decir, la disposición de las máquinas y cuáles se deberán usar para producir los trabajos.  β: las distintas restricciones que se aplican al problema.  γ: el objetivo en el que hay que basarse para decidir qué solución es más beneficiosa. Efecto de los tiempos de espera en talleres de flujo regular 2. Descripción del problema 20 Por ejemplo, una notación R4|rj ,dj|∑ Uj hace referencia a un problema donde se tienen cuatro máquinas paralelas con velocidades de procesado no relacionadas entre ellas y donde los trabajos sólo tienen que pasar por una de dichas máquinas, aunque éstos no están disponibles en su totalidad desde el inicio, pues cada uno tiene una fecha de llegada dada, y en el que se intenta que el número de total de trabajos que finalicen después de su fecha de entrega sea el menor posible. Como se ha explicado en el capítulo 1, en este proyecto se analizarán problemas donde los trabajos puedan esperar indefinidamente, donde el paso de los trabajos de una máquina a otra haya de ser inmediato, y donde los tiempos de espera estén acotados superiormente. Es decir, que se considerarán tres posibles conjuntos de restricciones que formen el campo β. Asimismo, se tratarán dos objetivos a minimizar dependiendo del problema: el makespan y el tiempo total de finalización de los trabajos, lo que hace que se puedan tener dos campos γ distintos. El campo α, por otra parte, siempre será el mismo, porque el único entorno con el que se va a trabajar es un taller de flujo regular, aunque pueda variar el número de máquinas que conformen el taller. Todo ello que se tengan seis tipos de problemas diferentes en este proyecto, según las restricciones que se les apliquen y el objetivo que traten de minimizar. A continuación se listan las variables que se usan para el modelado de los problemas descritos, así como sus datos. La variable 𝑒𝑖𝑗 y el dato 𝑒𝑚𝑎𝑥 sólo se necesitan a la hora de modelar los problemas donde las esperas, permitiéndose, están limitadas. Notación de las variables y datos del problema 𝑝𝑖𝑗 : Tiempo que tarda en procesarse el trabajo j en la máquina i 𝐶𝑖𝑗 : Tiempo de finalización del trabajo j en la máquina i 𝐶_𝑚𝑎𝑥 : Makespan, tiempo de finalización del último trabajo en la última máquina 𝑋𝑗𝑘 : Variable binaria que vale 1 si el trabajo j se procesa antes que el k (no necesariamente inmediatamente antes) 𝐴 : Término lo suficientemente grande como para considerar despreciables el resto de sumandos de su lado de la inecuación 𝑀 : Conjunto de todas las máquinas que componen el taller 𝑁 : Conjunto de todos los trabajos que se deben procesar 𝑚 : Número de máquinas que componen el taller 𝑒𝑖𝑗 : Tiempo que espera el trabajo j antes de entrar en la máquina i 𝑒𝑚𝑎𝑥 : Tiempo máximo que puede estar esperando un trabajo entre que termina su actividad en una máquina y entra en la siguiente Efecto de los tiempos de espera en talleres de flujo regular 2. Descripción del problema 21 2.1 Problemas donde se minimiza el makespan En primer lugar, se describirán los problemas en los que el objetivo es lograr el menor valor posible de Cmax, que serán tres, según el conjunto de restricciones que se les apliquen. 2.1.1 Problemas con esperas ilimitadas Este primer problema se denota Fm|prmu|Cmax usando la notación α|β|γ, que significa:  Entorno: taller de flujo regular (flow shop) formado por m máquinas.  Restricciones: permutación, es decir, todos los trabajos se procesan en el mismo orden en todas las máquinas.  Objetivo: minimizar el makespan. Pérez, Fernández-Viagas, Framiñán (2016) expresan este problema mediante el siguiente modelo de programación lineal entera mixta (MILP): MIN 𝐶_𝑚𝑎𝑥 s.a: 𝐶1𝑗 ≥ 𝑝1𝑗 ∀𝑗 ∈ 𝑁 𝐶𝑖𝑗 − 𝐶𝑖−1,𝑗 ≥ 𝑝𝑖𝑗 ∀𝑖 ∈ 𝑀 − {1}, ∀𝑗 ∈ 𝑁 𝐶𝑖𝑗 − 𝐶𝑖𝑘 + 𝐴 𝑋𝑗𝑘 ≥ 𝑝𝑖𝑗 ∀𝑖 ∈ 𝑀, ∀𝑗 ∈ 𝑁, ∀𝑘 ∈ 𝑁, 𝑗 < 𝑘 𝐶𝑖𝑗 − 𝐶𝑖𝑘 + 𝐴 (𝑋𝑗𝑘 − 1) ≤ − 𝑝𝑖𝑘 ∀𝑖 ∈ 𝑀, ∀𝑗 ∈ 𝑁, ∀𝑘 ∈ 𝑁, 𝑗 < 𝑘 𝐶_𝑚𝑎𝑥 ≥ 𝐶𝑚𝑗 ∀𝑗 ∈ 𝑁 Este modelo es la base de la que parten los modelos que describen los otros dos problemas para este objetivo, pues éstos se forman a partir de añadir una restricción al problema con esperas ilimitadas. Efecto de los tiempos de espera en talleres de flujo regular 2. Descripción del problema 22 2.1.2 Problemas con esperas no admisibles La restricción que se tiene en este problema es una bastante común en ciertos tipos de industria, la restricción no-wait o nwt), que obliga a los trabajos a pasar de una máquina a otra sin detenerse. Estos problemas se denotan Fm|prmu,nwt|Cmax. MIN 𝐶_𝑚𝑎𝑥 s.a: 𝐶1𝑗 ≥ 𝑝1𝑗 ∀𝑗 ∈ 𝑁 𝐶𝑖𝑗 − 𝐶𝑖−1,𝑗 = 𝑝𝑖𝑗 ∀𝑖 ∈ 𝑀 − {1}, ∀𝑗 ∈ 𝑁 𝐶𝑖𝑗 − 𝐶𝑖𝑘 + 𝐴 𝑋𝑗𝑘 ≥ 𝑝𝑖𝑗 ∀𝑖 ∈ 𝑀, ∀𝑗 ∈ 𝑁, ∀𝑘 ∈ 𝑁, 𝑗 < 𝑘 𝐶𝑖𝑗 − 𝐶𝑖𝑘 + 𝐴 (𝑋𝑗𝑘 − 1) ≤ − 𝑝𝑖𝑘 ∀𝑖 ∈ 𝑀, ∀𝑗 ∈ 𝑁, ∀𝑘 ∈ 𝑁, 𝑗 < 𝑘 𝐶_𝑚𝑎𝑥 ≥ 𝐶𝑚𝑗 ∀𝑗 ∈ 𝑁 Se aprecia que en la segunda restricción ya no se trata de una inecuación, sino de una ecuación, pues debido a la ausencia de tiempos de espera, la diferencia entre el tiempo de finalización de procesado de un trabajo en una máquina i y en su predecesora será exactamente igual al tiempo de procesado de dicho trabajo en la máquina i. Efecto de los tiempos de espera en talleres de flujo regular 2. Descripción del problema 23 2.1.3 Problemas con esperas permitidas pero limitadas Este tercer tipo de problema usa la restricción menos común de las usadas hasta ahora, por lo que se le debe otorgar una notación para poder incluirla en el campo β de la denominación del problema. La restricción que limita el tiempo máximo que pueden esperar los trabajos entre máquina y máquina se denota como ‘max_t’. Así, un campo β que incluya la restricción max_20 hace que los trabajos puedan esperar hasta un máximo de 20 unidades temporales entre que terminan su actividad en una máquina y entran en la siguiente, y se denotaría Fm|prmu,max20|Cmax. MIN 𝐶_𝑚𝑎𝑥 s.a: 𝐶1𝑗 ≥ 𝑝1𝑗 ∀𝑗 ∈ 𝑁 𝐶𝑖−1,𝑗 + 𝑒𝑖𝑗 + 𝑝𝑖𝑗 = 𝐶𝑖𝑗 ∀𝑖 ∈ 𝑀 − {1}, ∀𝑗 ∈ 𝑁 𝑒𝑖𝑗 ≤ 𝑒_𝑚𝑎𝑥 ∀𝑖 ∈ 𝑀, ∀𝑗 ∈ 𝑁 𝐶𝑖𝑗 − 𝐶𝑖𝑘 + 𝐴 𝑋𝑗𝑘 ≥ 𝑝𝑖𝑗 ∀𝑖 ∈ 𝑀, ∀𝑗 ∈ 𝑁, ∀𝑘 ∈ 𝑁, 𝑗 < 𝑘 𝐶𝑖𝑗 − 𝐶𝑖𝑘 + 𝐴 (𝑋𝑗𝑘 − 1) ≤ − 𝑝𝑖𝑘 ∀𝑖 ∈ 𝑀, ∀𝑗 ∈ 𝑁, ∀𝑘 ∈ 𝑁, 𝑗 < 𝑘 𝐶_𝑚𝑎𝑥 ≥ 𝐶𝑚𝑗 ∀𝑗 ∈ 𝑁 En este modelo, el parámetro e_max presente en el tercer conjunto de restricciones es igual a la ‘t’ que acompaña a ‘max’ en la restricción correspondiente del campo β de la notación del mismo. Efecto de los tiempos de espera en talleres de flujo regular 2. Descripción del problema 24 2.2 Problemas donde se minimiza el tiempo total de finalización Se han visto los modelos de los problemas a tratar en este proyecto atendiendo a los distintos tipos de restricciones que se aplican, pero sólo para uno de los dos objetivos considerados, el makespan. Sin embargo, considerar el otro objetivo (minimización de la suma de los tiempos de finalización de procesado de todos los trabajos) sólo conlleva un cambio en la función objetivo de los modelos, pues las restricciones no se ven alteradas por ello, por lo que el modelado de estos problemas es idéntico a los anteriores salvo por el cambio en el objetivo. 2.2.1 Problemas con esperas ilimitadas A continuación se presenta el modelo de programación lineal entera para el problema Fm|prmu|∑𝐶𝑗: MIN ∑𝐶𝑚𝑗 𝑛 𝑗=1 s.a: 𝐶1𝑗 ≥ 𝑝1𝑗 ∀𝑗 ∈ 𝑁 𝐶𝑖𝑗 − 𝐶𝑖−1,𝑗 ≥ 𝑝𝑖𝑗 ∀𝑖 ∈ 𝑀 − {1}, ∀𝑗 ∈ 𝑁 𝐶𝑖𝑗 − 𝐶𝑖𝑘 + 𝐴 𝑋𝑗𝑘 ≥ 𝑝𝑖𝑗 ∀𝑖 ∈ 𝑀, ∀𝑗 ∈ 𝑁, ∀𝑘 ∈ 𝑁, 𝑗 < 𝑘 𝐶𝑖𝑗 − 𝐶𝑖𝑘 + 𝐴 (𝑋𝑗𝑘 − 1) ≤ − 𝑝𝑖𝑘 ∀𝑖 ∈ 𝑀, ∀𝑗 ∈ 𝑁, ∀𝑘 ∈ 𝑁, 𝑗 < 𝑘 𝐶_𝑚𝑎𝑥 ≥ 𝐶𝑚𝑗 ∀𝑗 ∈ 𝑁 Efecto de los tiempos de espera en talleres de flujo regular 2. Descripción del problema 25 2.1.2 Problemas con esperas no admisibles A continuación se presenta el modelo de programación lineal entera para el problema Fm|prmu,nwt|∑𝐶𝑗: MIN ∑𝐶𝑚𝑗 𝑛 𝑗=1 s.a: 𝐶1𝑗 ≥ 𝑝1𝑗 ∀𝑗 ∈ 𝑁 𝐶𝑖𝑗 − 𝐶𝑖−1,𝑗 = 𝑝𝑖𝑗 ∀𝑖 ∈ 𝑀 − {1}, ∀𝑗 ∈ 𝑁 𝐶𝑖𝑗 − 𝐶𝑖𝑘 + 𝐴 𝑋𝑗𝑘 ≥ 𝑝𝑖𝑗 ∀𝑖 ∈ 𝑀, ∀𝑗 ∈ 𝑁, ∀𝑘 ∈ 𝑁, 𝑗 < 𝑘 𝐶𝑖𝑗 − 𝐶𝑖𝑘 + 𝐴 (𝑋𝑗𝑘 − 1) ≤ − 𝑝𝑖𝑘 ∀𝑖 ∈ 𝑀, ∀𝑗 ∈ 𝑁, ∀𝑘 ∈ 𝑁, 𝑗 < 𝑘 𝐶_𝑚𝑎𝑥 ≥ 𝐶𝑚𝑗 ∀𝑗 ∈ 𝑁 2.1.3 Problemas con esperas permitidas pero limitadas A continuación se presenta el modelo de programación lineal entera para el problema Fm|prmu,max_t|∑𝐶𝑗: MIN ∑𝐶𝑚𝑗 𝑛 𝑗=1 s.a: 𝐶1𝑗 ≥ 𝑝1𝑗 ∀𝑗 ∈ 𝑁 𝐶𝑖−1,𝑗 + 𝑒𝑖𝑗 + 𝑝𝑖𝑗 = 𝐶𝑖𝑗 ∀𝑖 ∈ 𝑀 − {1}, ∀𝑗 ∈ 𝑁 𝑒𝑖𝑗 ≤ 𝑒_𝑚𝑎𝑥 ∀𝑖 ∈ 𝑀, ∀𝑗 ∈ 𝑁 𝐶𝑖𝑗 − 𝐶𝑖𝑘 + 𝐴 𝑋𝑗𝑘 ≥ 𝑝𝑖𝑗 ∀𝑖 ∈ 𝑀, ∀𝑗 ∈ 𝑁, ∀𝑘 ∈ 𝑁, 𝑗 < 𝑘 𝐶𝑖𝑗 − 𝐶𝑖𝑘 + 𝐴 (𝑋𝑗𝑘 − 1) ≤ − 𝑝𝑖𝑘 ∀𝑖 ∈ 𝑀, ∀𝑗 ∈ 𝑁, ∀𝑘 ∈ 𝑁, 𝑗 < 𝑘 𝐶_𝑚𝑎𝑥 ≥ 𝐶𝑚𝑗 ∀𝑗 ∈ 𝑁 Efecto de los tiempos de espera en talleres de flujo regular 5. Implementación 32 5 ÍMPLEMENTACÍO N En este trabajo se analiza la influencia de posibles limitaciones en los tiempos máximos de espera de los trabajos entre máquinas, para lo que se deben resolverse los problemas descritos en el capítulo 2. 5.1 Adquisición de resultados Para implementar dichos modelos se ha usado el lenguaje C, y el entorno de desarrollo integrado libre Code::Blocks para generar aplicaciones. También se ha hecho uso de las librerías aportadas por el personal docente de la asignatura “Programación de Operaciones” para el uso de funciones como imprimir por pantalla las componentes de un vector. A continuación, se procede a explicar brevemente cómo se ha realizado el código (sólo para el makespan como objetivo, por simplicidad), para qué sirve cada una de las partes del mismo, y qué resultados se obtienen de él. El código íntegro se adjuntará en el anexo, así como una explicación más detallada de cómo funciona. En este capítulo se omiten las líneas de código meramente estéticas (saltos de línea, tabulaciones…) que se han usado para lograr una mejor comprensión del mismo. Para empezar, se incluyen las librerías que se van a usar, y se definen las funciones necesarias, que serán, además de las tres que calculan el makespan para los problemas con cada uno de los tipos de restricciones existentes, las que calculan el mínimo y el máximo de dos números enteros dados, la que calcula el factorial de un número entero, y las dos aplicaciones de la enumeración completa. El funcionamiento de todas estas funciones se explica en el anexo. También se declaran las variables con las que se calcularán los diferentes indicadores explicados en el capítulo 3, como el vector que almacena la secuencia con la que se esté trabajando en cada momento, o la matriz con los tiempos de proceso para la instancia en cuestión. #include <stdio.h> #include <stdlib.h> #include <schedule_lib.h> int max(int a, int b); int min(int a, int b); int factorial (int a); int Cmax(int m, int n, MAT_INT P, VECTOR_INT sec); int CmaxNOWAIT(int m, int n, MAT_INT P, VECTOR_INT sec); int CmaxMAXWAIT(int m, int n, MAT_INT P, VECTOR_INT sec, int waitmax); void enumeracionCompleta1(VECTOR_INT sec, int n, int par_length, int m, MAT_INT P); void enumeracionCompleta2(VECTOR_INT sec, int n, int par_length, int m, MAT_INT P); int x1,x2,x3,x4,x5,x6; int x1max,x2max,x3max,x4max,x5max,x6max; int x1min,x2min,x3min,x4min,x5min,x6min; int x1tot,x2tot,x3tot,x4tot,x5tot,x6tot; float ARPD1,ARPD2,ARPD3,ARPD4,ARPD5,ARPD6; VECTOR_INT sec; Efecto de los tiempos de espera en talleres de flujo regular 5. Implementación 33 MAT_INT secMIN; VECTOR_INT prob1; VECTOR_INT prob2; VECTOR_INT prob3; VECTOR_INT prob4; VECTOR_INT prob5; VECTOR_INT prob6; MAT_INT P; A continuación, se definen el número de trabajos y máquinas que se tendrán en el entorno en el que se esté trabajando, además de dimensionar algunos de los vectores y matrices que se declararon anteriormente y que serán utilizados posteriormente. void main() { int it,i,j; int n=5; int m=20; float fact=factorial(n); sec=DIM_VECTOR_INT(n+1); secMIN=DIM_MAT_INT(6,n+1); prob1=DIM_VECTOR_INT(100); prob2=DIM_VECTOR_INT(100); prob3=DIM_VECTOR_INT(100); prob4=DIM_VECTOR_INT(100); prob5=DIM_VECTOR_INT(100); prob6=DIM_VECTOR_INT(100); P=DIM_MAT_INT(m,n); Se crean las 10 iteraciones, y para cada una de ellas se genera aleatoriamente la matriz de tiempos de proceso. Como la semilla no cambia, sus valores serán idénticos para los problemas con diferentes restricciones pero igual entorno, que es el objetivo. for(it=1;it<=10;it++) { for(i=0;i<m;i++) { for(j=0;j<n;j++) { P[i][j]=rand()%99+1; } } Para efectuar la primera aplicación de la enumeración completa, se deben inicializar los valores de los mínimos y máximos de los problemas adecuadamente, y definir una secuencia inicial. Efecto de los tiempos de espera en talleres de flujo regular 5. Implementación 34 El código se ha diseñado para secuencias que empiecen con el valor 0, aunque éste no corresponda a ningún trabajo. Es decir, que para un entorno con 6 trabajos, el vector sec tendrá 7 componentes, el primero de los cuales será un 0. Entonces, se aplica la enumeración completa, y se obtienen los valores mínimos y máximos de la FO en cada uno de los seis problemas. También se halla la secuencia óptima de cada problema, pero no se muestra por pantalla pues no es un dato que se vaya a usar, aunque sí se guarda en memoria de cara a la segunda aplicación de la enumeración completa. printf("ITERACION %d",it); x1max=x2max=x3max=x4max=x5max=x6max=1; x1min=x2min=x3min=x4min=x5min=x6min=100000; for(i=0;i<=n;i++) { sec[i]=i; } enumeracionCompleta1(sec,n,n+1,m,P); printf("makespan PFSP: MIN = %d , MAX = %d",x1min,x1max); printf("makespan max40: MIN = %d , MAX = %d",x2min,x2max); printf("makespan max30: MIN = %d , MAX = %d",x3min,x3max); printf("makespan max20: MIN = %d , MAX = %d",x4min,x4max); printf("makespan max10: MIN = %d , MAX = %d",x5min,x5max); printf("makespan nwt: MIN = %d , MAX = %d",x6min,x6max); Para aplicar la enumeración completa por segunda vez, hay que inicializar más variables, como por ejemplo los vectores donde se recogerá la función de densidad de probabilidad de cada problema. x1tot=x2tot=x3tot=x4tot=x5tot=x6tot=0; for(i=0;i<100;i++) { prob1[i]=0; prob2[i]=0; prob3[i]=0; prob4[i]=0; prob5[i]=0; prob6[i]=0; } for(i=0;i<=n;i++) { sec[i]=i; } enumeracionCompleta2(sec,n,n+1,m,P); Efecto de los tiempos de espera en talleres de flujo regular 5. Implementación 35 Ahora ya se puede conocer el ARPD de cada problema, así como mostrar por pantalla las funciones de densidad de probabilidad, y el resultado de aplicar la secuencia óptima del PFSP en los otros cinco problemas, así como las óptimas de dichos problemas en el PFSP. ARPD1=((float)x1tot/(float)x1min)*(100/fact)-100; printf("ARPD PFSP = %f",ARPD1); printf("Densidad de probabilidad PFSP:"); print_int_vector(prob1,100); printf("Optima del PFSP en el no-wait = %d",CmaxNOWAIT(m,n,P,secMIN[0])); printf("Optima del PFSP en el max10 = %d",CmaxMAXWAIT(m,n,P,secMIN[0],10)); printf("Optima del PFSP en el max20 = %d",CmaxMAXWAIT(m,n,P,secMIN[0],20)); printf("Optima del PFSP en el max30 = %d",CmaxMAXWAIT(m,n,P,secMIN[0],30)); printf("Optima del PFSP en el max40 = %d",CmaxMAXWAIT(m,n,P,secMIN[0],40)); ARPD2=((float)x2tot/(float)x2min)*(100/fact)-100; printf("ARPD max40 = %f",ARPD2); printf("Densidad de probabilidad max40:"); print_int_vector(prob2,100); printf("Optima del max40 en el PFSP = %d",Cmax(m,n,P,secMIN[1])); ARPD3=((float)x3tot/(float)x3min)*(100/fact)-100; printf("ARPD max30 = %f",ARPD3); printf("Densidad de probabilidad max30:"); print_int_vector(prob3,100); printf("Optima del max30 en el PFSP = %d",Cmax(m,n,P,secMIN[2])); ARPD4=((float)x4tot/(float)x4min)*(100/fact)-100; printf("ARPD max20 = %f",ARPD4); printf("Densidad de probabilidad max20:"); print_int_vector(prob4,100); printf("Optima del max20 en el PFSP = %d",Cmax(m,n,P,secMIN[3])); ARPD5=((float)x5tot/(float)x5min)*(100/fact)-100; printf("ARPD max10 = %f",ARPD5); printf("Densidad de probabilidad max10:"); print_int_vector(prob5,100); printf("Optima del max10 en el PFSP = %d",Cmax(m,n,P,secMIN[4])); ARPD6=((float)x6tot/(float)x6min)*(100/fact)-100; printf("ARPD no-wait = %f",ARPD6); printf("Densidad de probabilidad no-wait:"); print_int_vector(prob6,100); printf("Optima del no-wait en el PFSP = %d",Cmax(m,n,P,secMIN[5])); } } Efecto de los tiempos de espera en talleres de flujo regular 5. Implementación 36 Tras aplicar el código anterior, se muestran por pantalla los resultados obtenidos para cada una de las iteraciones del problema con el entorno y objetivo correspondientes:  Valores mínimo y máximo de la FO para cada uno de los problemas, según su restricción.  ARPD para cada uno de los problemas.  Función de densidad de probabilidad de las secuencias de cada problema, expresada como un vector de 100 componentes.  Resultados obtenidos al aplicar la secuencia óptima del PFSP en cada uno de los otros cinco problemas.  Resultados obtenidos al aplicar las secuencias óptimas de los cinco problemas con esperas limitadas en el PFSP. Figura 5.1 – Resultado de aplicar dos veces la enumeración completa a una instancia usando el código propuesto (Elaboración propia) Los resultados que se observan en la figura 5.1 corresponden a una de las diez iteraciones que se realizan para el entorno con 5 trabajos y 20 máquinas, que es solamente uno de los dieciséis entornos que se contemplan en el trabajo, como se explicó en el capítulo 4. Efecto de los tiempos de espera en talleres de flujo regular 5. Implementación 37 Es decir, que se deben recoger 160 conjuntos de resultados tales como el que describe la figura 5.1, para cada uno de los dos objetivos, pues los problemas con el makespan como objetivo se estudian de forma independiente a los que minimizan el tiempo total de finalización, aunque luego comparen algunos de sus resultados. 5.2 Organización de la información Con el fin de manejar tal volumen de información, se usa el software Microsoft Excel, ya que permite agrupar los resultados según las restricciones aplicadas, el entorno… así como representarlos gráficamente de forma relativamente sencilla. Figura 5.2 – Extracto del libro de Microsoft Excel donde se recoge la información obtenida a partir del programa (Elaboración propia) Como se puede apreciar en la figura 5.2, los valores obtenidos en las diez iteraciones de un problema no-wait para el mínimo de la FO en cada una de ellas, su ARPD, y el incremento relativo de la FO al usar la secuencia óptima del PFSP se promedian para así hallar los valores característicos de dicho entorno, menos afectados por la aleatoriedad de los tiempos de proceso generados. Los vectores de densidad de probabilidad se disponen de forma que se sumen, componente a componente, los de las diez iteraciones, para así tener la función de densidad de probabilidad de todas ellas, y a partir de ella calcular la de distribución del problema con el entorno y la restricción correspondiente. Se observa, por ejemplo, que los valores de la iteración 1 del Efecto de los tiempos de espera en talleres de flujo regular 5. Implementación 38 entorno con 5 trabajos y 20 máquinas son los que aparecen en la figura 5.1, cuando se ejecutó el programa. El volumen de datos es extremadamente alto como para considerar introducir toda la información a mano, por lo que se hace uso de ficheros. Así, al aplicar el programa, la información que interese extraer aparece en un archivo con formato .txt, que se podrá abrir desde un libro de Excel para ya disponer de los datos separados en celdas pero organizados según correspondan en filas y columnas, de forma que puedan manipularse con facilidad y minimizando la probabilidad de equivocación al copiarlos al libro donde se almacenan los resultados. Para ello, se define y crea el fichero donde se exportarán los datos mediante la siguiente línea de código, que se debe incluir antes de entrar en el bucle de las 10 iteraciones: FILE * fichero=fopen("salida.txt","a"); La “a” final hace que, para cada iteración, se añadan los resultados al final del fichero, es decir, después de las iteraciones ejecutadas previamente, para que no se sobrescriban los resultados de iteraciones previas cada vez que se ejecute una nueva. Por ejemplo, si se quisiera exportar a un fichero los vectores función de densidad de probabilidad del problema no-wait para cada una de las diez iteraciones del entorno que se esté estudiando, se añadiría al final de la función principal las siguientes líneas: for(i=0;i<99;i++) { fprintf(fichero,"%d, ",prob6[i]); } fprintf(fichero,"%d;\n",prob6[i]); De esta forma, cada uno de los 100 componentes del vector estará separado por una coma, mientras que tras el último valor habrá un punto y coma seguido de un salto de línea, que marca el paso a la siguiente iteración. Con esos signos de puntuación, al abrir el fichero exportado desde un libro Excel, aparecerán dispuestos los vectores en filas y columnas perfectos para ser copiados al libro representado en la figura 5.2. Efecto de los tiempos de espera en talleres de flujo regular 5. Implementación 39 Figura 5.3 – Ejemplo del resultado de exportar resultados del programa a un fichero, y a un libro Excel (Elaboración propia) Cuando el objetivo a minimizar es ∑𝐶𝑗 el código es idéntico, con la diferencia evidente de que las funciones no serán Cmax, CmaxNOWAIT, CmaxMAXWAIT. Para ello, también se construyen las funciones sumaCj, sumaCjNOWAIT, sumaCjMAXWAIT. Estas funciones son exactamente iguales a las anteriores, pues el método para calcular el tiempo de finalización de cada trabajo en cada máquina no cambia, pero lo que devuelven no es el tiempo en el que acaba de procesarse el último trabajo, sino la suma de los tiempos de finalización de todos ellos. En el anexo se adjuntan todas las funciones usadas en los distintos códigos:  Primera aplicación de la enumeración completa  Segunda aplicación de la enumeración completa  Máximo de dos números enteros  Mínimo de dos números enteros  Factorial de un número entero  Cmax obtenido para una secuencia dada aplicada a un PFSP  Cmax obtenido para una secuencia dada aplicada a un problema no-wait  Cmax obtenido para una secuencia dada aplicada a un problema con esperas limitadas  ∑𝐶𝑗 obtenido para una secuencia dada aplicada a un PFSP  ∑𝐶𝑗 obtenido para una secuencia dada aplicada a un problema no-wait  ∑𝐶𝑗 obtenido para una secuencia dada aplicada a un problema con esperas limitadas Efecto de los tiempos de espera en talleres de flujo regular 6. Evaluación computacional 40 6 EVALUACÍO N COMP UTACÍONAL Los códigos implementados aportan una gran cantidad de resultados, que han de ser manejados adecuadamente para su correcta comprensión. Como se comentó en el capítulo 4, se han usado cuatro valores diferentes para el número de trabajos (5, 6, 7, 8) y otros tantos para el número de máquinas (5, 10, 15, 20), teniendo hasta 16 tamaños distintos para cada tipo de problema. Asimismo, se han considerado seis restricciones: desde el caso extremo donde las esperas se permiten sin importar su duración hasta aquél en el que los trabajos que terminan de procesarse en una máquina deben comenzar a tratarse en la siguiente inmediatamente, pasando por cuatro situaciones intermedias, donde se contemplan esperas siempre y cuando no superen una duración máxima preestablecida (10, 20, 30, 40). Para cada combinación posible de número de trabajos y máquinas se han ejecutado 10 instancias, cada cual compuesta por n x m tiempos de proceso de trabajos en las máquinas, y en las que se han evaluado los diferentes problemas usando las seis distintas restricciones, obteniendo resultados de interés como la secuencia que aporta el óptimo en cada una de ellas y el valor de la función de objetivo para ella, por ejemplo. Posteriormente, se analizará el efecto de las distintas restricciones relacionadas con el tiempo de espera máximo permitido de los trabajos entre máquinas consecutivas. Se compararán los problemas con las distintas restricciones de tiempo de espera, es decir, los problemas Fm|prmu|Cmax, Fm|prmu,max10|Cmax, … , Fm|prmu,nwt|Cmax, así como los problemas que tengan como función objetivo el tiempo total de finalización, ∑𝐶𝑗. Efecto de los tiempos de espera en talleres de flujo regular 6. Evaluación computacional 41 6.1 Resultados óptimos de los problemas Se comienza analizando el valor mínimo de las distintas funciones objetivo, es decir, el caso más beneficioso posible atendiendo al criterio escogido. Para cada entorno y restricción, se ha realizado la media del óptimo de sus 10 iteraciones. En la tabla 6.1 se puede observar el valor medio del óptimo (en primer lugar teniendo como objetivo Cmax) para cada una de las 16 posibles combinaciones de número de máquinas y trabajos, y también para cada uno de los seis tiempos de espera máximos considerados en el proyecto. Tabla 6.1 – Valores medios del óptimo para los problemas con FO: Cmax (Elaboración propia) Aunque se trata de conclusiones tan evidentes que no hacía falta generar instancias aleatorias para deducirlas, se comprueba que obviamente el makespan es función del número de trabajos a procesar y del número de máquinas por los que estos deben pasar. También se aprecia que, a medida que se reduce el tiempo máximo de espera permitido de los trabajos entre máquina y máquina, el proceso se demora y el valor del makespan aumenta. Para extraer conclusiones más interesantes sobre este problema, se adjunta la tabla 6.2, donde se indica el aumento relativo (en tanto por ciento) del makespan de la secuencia óptima de cada problema respecto al valor del mismo en el PFSP de igual número de trabajos y máquinas. Efecto de los tiempos de espera en talleres de flujo regular 6. Evaluación computacional 48 Se comprueba que el problema con restricción no-wait es el que tiene un mayor ARPD, mientras que el problema que únicamente tiene la de permutación (PFSP) es el que presenta menores desviaciones en su FO. Los problemas con esperas permitidas pero limitadas están en una situación intermedia, ordenados según dicho tiempo máximo de espera permitido. También se aprecian las relaciones ya mencionadas entre el ARPD y el número de trabajos y máquinas, respectivamente, que ya se podían anticipar tras obtener la tabla 6.6, pero las gráficas parecen indicar además que se dichas relaciones tienen un comportamiento lineal. Otra forma de estudiar los distintos valores que toman las FO dependiendo de la secuencia de trabajos, sin usar el indicador ARPD, es usando distribuciones de densidad y probabilidad. Para ello, para cada instancia, se hallan las secuencias extremas (la mejor y la peor atendiendo a la FO considerada), y los valores que ésta toma para dichas secuencias marcan el inicio y el final de un intervalo que se divide en 100 tramos iguales, y en el que se encuentran los valores de la FO para todas las demás posibles secuencias de la instancia correspondiente. Se presentan a continuación dos funciones de densidad de probabilidad para dos problemas claramente diferenciados, de forma que los efectos que las esperas y el número de trabajos o máquinas tienen sobre las soluciones, que ya se pueden deducir a partir de toda la información anterior, se reflejen en ellas. El primero de los dos problemas a estudiar será el que permite esperas indefinidas, con el mayor tamaño del taller contemplado (20 máquinas), un número reducido de trabajos (6), y que trata de minimizar el makespan. Se construye la función de densidad de probabilidad de sus 6!=720 secuencias posibles tal como se explicó en el capítulo 3, es decir, acotando los valores que toma el objetivo para la mejor y peor secuencia, y distribuyendo los que se obtienen siguiendo el resto de secuencias en los cien tramos equivalentes en los que se divide dicho intervalo. El segundo de los problemas analizados será considerablemente diferente, para así apreciar las diferencias en el comportamiento de la distribución de las soluciones. Se tratará de un problema donde se permiten esperas pero de hasta un máximo de 20 unidades temporales, con un taller con la mitad de máquinas (10), más trabajos a procesar (8), pero el mismo objetivo: minimizar el makespan. Para este problema se tienen 8!=40.320 secuencias diferentes, que son 56 veces más que las que se tenían en el primer problema. Por ello, para poder comparar los resultados, no se representará la cantidad de secuencias que hay en cada intervalo, sino la proporción respecto al número total de secuencias posibles que tiene el problema. Figura 6.6 – Función de densidad de probabilidad de las secuencias para un problema F20|prmu|Cmax con 6 trabajos (Elaboración propia) Efecto de los tiempos de espera en talleres de flujo regular 6. Evaluación computacional 49 El hecho de que el problema estudiado en la figura 6.6 sea uno con pocos trabajos (y por consiguiente con no muchas posibles secuencias), conlleva que, aunque se pueda intuir la distribución normal de probabilidades, la forma de la Campana de Gauss no sea tan evidente como la que se puede apreciar en la figura 6.7, pues la aleatoriedad de los tiempos de proceso generados hace que se produzcan ciertos picos a lo largo del intervalo. La figura 6.6 tiene una peculiaridad que no ocurre en la 6.7, y es que las secuencias que se encuentran en el primer y último tramo son bastantes más que en sus tramos más inmediatamente cercanos. Esto es así porque, para cada instancia, hay al menos una secuencia (la mejor) que se encuentra en el primer tramo, y otra (la peor) que está en el tramo 100. Dado que al tener apenas 6 trabajos existen 720 secuencias posibles, se sabe que al menos una de esas 720 estará en cada uno de los extremos, que es una probabilidad considerable para tratarse de un intervalo dividido en cien tramos. En la figura 6.7, al tratarse de un problema con 8 trabajos, ya no se ven valores tan poco intuitivos en los tramos extremos. Aunque es posible que en el primer tramo haya un mayor número de secuencias que en el segundo debido al motivo que se explica anteriormente, 1 secuencia entre 40.320 posibles se trata de una probabilidad enormemente inferior en comparación a la que existe en los tramos del intervalo más alejados de los extremos. Figura 6.7 – Función de densidad de probabilidad de las secuencias para un problema F10|prmu,max20|Cmax con 8 trabajos (Elaboración propia) Asumiendo que las dos distribuciones anteriores se comportasen como distribuciones normales, se puede ver que la media de la normal de la figura 6.7 se encuentra claramente a la derecha de la de la figura 6.6, algo que no es sorprendente, pues el problema max20 con 8 trabajos y 10 máquinas tenía un ARPD claramente mayor al del PFSP con 6 trabajos y 20 máquinas. Ese ARPD superior indicaba mayor lejanía respecto al óptimo, y es precisamente lo que indica esa función de densidad desplazada hacia la derecha. Otra forma de representar la distribución de las secuencias de los problemas es usando la probabilidad acumulada, de manera que en lugar de obtener la probabilidad de que una secuencia cualquiera se encuentre en uno de los cien tramos del intervalo, lo que se obtiene es la de que esté en un tramo que parta del óptimo, es decir, del inicio del eje x. Sumando las probabilidades de cada uno de los tramos de la distribución de la figura 6.7, se obtiene la siguiente función de distribución de probabilidad acumulada. Efecto de los tiempos de espera en talleres de flujo regular 6. Evaluación computacional 50 Figura 6.8 – Función de distribución de probabilidad de las secuencias para un problema F10|prmu,max20|Cmax con 8 trabajos (Elaboración propia) Se puede ver en la figura 6.8 que sólo el 40% de todas las secuencias posibles se encuentran en los 50 primeros tramos de los 100 de los que se compone el intervalo, es decir, que si se escogiese una secuencia aleatoria de 8 trabajos para este problema concreto, sería más probable que el resultado obtenido estuviera más cerca del de la peor secuencia posible que del makespan que diera la secuencia óptima. Conviene recordar que estos 100 tramos simplemente indican la distancia relativa entre los valores de la FO para la mejor y la peor secuencia, pero no reflejan el incremento porcentual del valor de la misma. Como se quiere estudiar el comportamiento general de los problemas para cada tipo de restricción, es necesario hallar las funciones de distribución de probabilidad para cada combinación de trabajos y máquinas, aplicando a cada una de ellas las distintas limitaciones de tiempos de espera. Dichas distribuciones se deben normalizar para que indiquen probabilidad y no el número de secuencias que se encuentran en cada uno de los cien tramos (como ya se ha hecho en las figuras 6.6 y 6.7), para que así sea indiferente el número de posibles secuencias que haya en cada problema, algo que como ya se ha visto se incrementa enormemente a medida que se aumenta el número de trabajos a procesar. Una vez normalizadas todas las distribuciones, y combinadas las de todos los problemas con idéntica limitación de tiempos de espera, se obtiene la representación la distribución acumulada de probabilidad para los problemas con cada una de las restricciones, como se muestra en la figura 6.9. Efecto de los tiempos de espera en talleres de flujo regular 6. Evaluación computacional 51 Figura 6.9 – Funciones de distribución de probabilidad de las secuencias para los problemas con cada una de las restricciones de tiempos máximos de espera, con FO: Cmax (Elaboración propia) Evidentemente, cada curva tiene una forma similar a la de la figura 6.8, pues se trata del mismo tipo de distribución de probabilidad acumulada. La utilidad de esta gráfica es que se puede comprobar, una vez más, que en los problemas con una limitación estricta del tiempo de espera entre máquinas es más difícil aproximarse al óptimo que en un PFSP. Efecto de los tiempos de espera en talleres de flujo regular 6. Evaluación computacional 52 6.2.2 FO: ∑𝑪𝒋 Obtenemos, al igual que se hizo para el objetivo del makespan, el ARPD para cada uno de los problemas estudiados, para ver lo alejadas del óptimo que están las secuencias para cada uno de los problemas. Tabla 6.7 – ARPD de los problemas con FO: ∑Cj para los distintos números de trabajos y máquinas, y restricciones de tiempos máximos de espera (Elaboración propia) Se puede apreciar, al igual que ocurría con la otra FO, que el valor del ARPD es mayor para un taller pequeño, y que aumenta cuando también lo hace el número de trabajos. Sin embargo, para n=6 los problemas presentan un ARDP algo menor que para n=5, algo que se acentúa para los entornos con 10 máquinas, y especialmente cuando hay 20 máquinas. Efecto de los tiempos de espera en talleres de flujo regular 6. Evaluación computacional 53 Figura 6.11 – ARPD de los problemas con FO: ∑Cj, dependiendo del número de trabajos a procesar (Elaboración propia) Figura 6.12 – ARPD de los problemas con FO: ∑Cj, dependiendo del número de máquinas que formen el taller de flujo (Elaboración propia) Al igual que ocurría con el makespan, es más difícil acercarse al óptimo a medida que las restricciones que limitan el tiempo máximo de espera entre máquinas se hacen más estrictas, teniendo lugar una mayor diferencia entre los problemas PFSP y no-wait cuando el número de trabajos crece. Dicha diferencia, por otra parte, parece independiente del número de máquinas. Se analiza la distribución de las secuencias según el valor de ∑𝐶𝑗 para los mismos dos problemas analizados en el punto anterior, y como se puede observar, las distribuciones tienen un aspecto muy similar a las que se construyeron para el caso del Cmax. Efecto de los tiempos de espera en talleres de flujo regular 6. Evaluación computacional 54 Figura 6.13 – Función de densidad de probabilidad de las secuencias para un problema F20|prmu|∑Cj con 6 trabajos (Elaboración propia) Una pequeña diferencia es que la función representada en la figura 6.14 es algo más asimétrica que la que muestra la figura 6.7, pues la media de la Campana de Gauss a la que se asemeja la función de densidad de probabilidad está situada algo más a la derecha, lo que indicaría que para el tiempo total de finalización las soluciones están, por lo general, más alejadas del óptimo que cuando se usaba el makespan. Figura 6.14 – Función de densidad de probabilidad de las secuencias para un problema F10|prmu, max20|∑Cj con 8 trabajos (Elaboración propia) En esta ocasión, se muestra en la figura 6.15 la función de distribución acumulada de probabilidad para el problema PFSP con 6 trabajos y 20 máquinas, pero tiene una forma similar a la que se construyó para el otro problema con la otra FO, representada en la figura 6.8. Figura 6.15 – Función de distribución de probabilidad de las secuencias para un problema F20|prmu|Cmax con 6 trabajos (Elaboración propia) Efecto de los tiempos de espera en talleres de flujo regular 6. Evaluación computacional 55 La diferencia más clara e importante es que en la figura 6.15 se empiezan a alcanzar valores altos bastante antes que en la 6.8, pues se comprobó que en el problema representado en la primera las soluciones estaban más próximas al óptimo, ya que el valor de su ARPD era menor. No obstante, la forma de estas distribuciones de probabilidad acumuladas son bastante similares para todos los problemas con este objetivo, pues se vio que las diferencias entre sus ARPD no eran especialmente grandes. Así que, de nuevo, se superponen las distribuciones acumuladas para todas las restricciones estudiadas en una sola figura. Figura 6.16 – Funciones de distribución de probabilidad de las secuencias para los problemas con cada una de las restricciones de tiempos máximos de espera, con FO: ∑Cj (Elaboración propia) De la figura 6.16 se puede extraer con certeza que el PFSP es el problema menos difícil de los seis, pues sus secuencias están ligeramente más próximas a la óptima que en los otros. Sin embargo, entre dichos problemas no existe una gran diferencia, lo que significa que la limitación de los tiempos de espera no parece hacer una gran diferencia en este sentido para problemas con ∑𝐶𝑗 como objetivo, y la probabilidad de encontrar soluciones próximas al óptima no dependerá tanto de la ella. Efecto de los tiempos de espera en talleres de flujo regular 6. Evaluación computacional 56 6.2.3 Comparación entre problemas con ambos objetivos Si bien en los puntos 6.2.1 y 6.2.2 se ha estudiado la influencia del número de trabajos, máquinas y el tipo de restricción en los problemas con cada uno de los objetivos, en este punto se analiza la diferencia entre los problemas con idénticos tamaños de problema y restricciones, pero distinto objetivo. En primer lugar, se comparan los valores del ARPD obtenidos para cada una de las seis posibles restricciones. Para ello, se promedian los 16 valores del ARPD que se hallaron para cada uno de los 16 tamaños de problema estudiados en las tablas 6.6 y 6.7, todo ello para los seis tipos de problemas distintos que se contemplan según la limitación de los tiempos de espera de los trabajos. Figura 6.17 – ARPD de los problemas (eje y) con cada uno de los dos objetivos, para cada uno de los valores contemplados del tiempo de espera permitido máximo (eje x) (Elaboración propia) Como ya se observó en los puntos anteriores, limitar las esperas hace que no sólo aumente el makespan y el tiempo total de finalización, sino que también hace que las secuencias estén más alejadas del óptimo. Además, la figura 6.17 muestra cómo el makespan es más sensible que el tiempo total de finalización ante restricciones estrictas sobre los tiempos de espera, pues los problemas donde se intenta minimizar Cmax tienen un ARPD mayor que los que tienen como objetivo ∑𝐶𝑗, especialmente cuando las esperas permitidas son breves o nulas. Para seguir comparando ambas FO, también se estudiarán las funciones de distribución acumuladas de probabilidad de los problemas con las restricciones extremas (esperas indefinidas permitidas y esperas no admitidas) para cada uno de los objetivos. Efecto de los tiempos de espera en talleres de flujo regular 6. Evaluación computacional 57 Figura 6.18 – Funciones de distribución de probabilidad de las secuencias para los problemas con esperas permitidas ilimitadas, para Cmax y ∑Cj (Elaboración propia) Figura 6.19 – Funciones de distribución de probabilidad de las secuencias para los problemas con esperas no permitidas, para Cmax y ∑Cj (Elaboración propia) En la figura 6.18 se puede apreciar que las distribuciones de las secuencias de los dos problemas representados son bastante similares, algo que cuadra con la figura 6.17, donde se veía que cuando no se limitaba el tiempo máximo de espera, el ARPD era muy parecido también para los dos objetivos. Por otra parte, la figura 6.17 indicaba que cuando se tenía una restricción no-wait, el problema con el makespan como objetivo tenía un ARPD considerablemente mayor, por lo que las distintas secuencias dan soluciones más alejadas del óptimo. Y eso mismo se observa en la figura 6.19, donde la probabilidad de obtener valores próximos al óptimo siempre es mayor para el problema con ∑𝐶𝑗 como objetivo. Efecto de los tiempos de espera en talleres de flujo regular 6. Evaluación computacional 64 Se ha añadido en la tabla 6.10 los valores del ARPD para el problema de permutación que aparecían en la tabla 6.6, y se comparan dichos valores con el incremento del Cmax medio para cada uno de los problemas. Que el valor del ARPD sea claramente mayor en cualquier caso quiere decir que, en caso de tener que usar una secuencia sin conocer el óptimo del PFSP, es mucho más conveniente usar, si se conoce, la óptima de otro de los problemas (incluso del nowait, que es el más diferente) antes que una aleatoria. Figura 6.22 – Incremento relativo de Cmax al usar la secuencia óptima de los problemas con esperas limitadas en el PFSP, y valores del ARPD para el PFSP, según el número de trabajos (Elaboración propia) La figura 6.22 muestra que usar la óptima de un problema con esperas limitadas en el PFSP da soluciones más alejadas del óptimo a medida que el número de trabajos a procesar crece, así como también es más difícil acercarse al óptimo usando secuencias aleatorias (aumenta el ARPD, como indicaba la tabla 6.6). Figura 6.23 – Incremento relativo de Cmax al usar la secuencia óptima de los problemas con esperas limitadas en el PFSP, y valores del ARPD para el PFSP, según el número de máquinas (Elaboración propia) Efecto de los tiempos de espera en talleres de flujo regular 6. Evaluación computacional 65 Sin embargo, la figura 6.23 indica que el número de máquinas parece no afectar al resultado de usar las secuencias óptimas de otros problemas en el PFSP, aunque sí que hace disminuir considerable el ARPD del mismo. Esto significa que para un PFSP con un número de máquinas lo suficientemente alto y con pocos trabajos a procesar, podría haber un momento en el que fuera más favorable incluso usar una secuencia generada aleatoriamente que la óptima de uno de los problemas con esperas limitadas. 6.3.2 FO: ∑𝑪𝒋 De igual forma, el análisis del punto previo se realiza también para los problemas que tienen como objetivo minimizar el tiempo total de finalización de los trabajos. Se construye una tabla como la 6.10, y se aprecia que para este objetivo usar las secuencias óptimas de los problemas con limitación de esperas en el PFSP da soluciones muy próximas a la que se obtiene con la óptima del propio PFSP. De hecho, para entornos con sólo 5 trabajos, las secuencias óptimas de los problemas donde las esperas se limitan en 40 unidades temporales dan los mismos resultados que los problemas que sólo tienen la restricción de permutación, siempre y cuando el número de máquinas no sea lo suficientemente alto. Tabla 6.11 – Incremento relativo de ∑Cj al usar la secuencia óptima de los problemas con esperas limitadas en el PFSP, y valores del ARPD para el PFSP (Elaboración propia) Efecto de los tiempos de espera en talleres de flujo regular 6. Evaluación computacional 66 Figura 6.24 – Incremento relativo de ∑Cj al usar la secuencia óptima de los problemas con esperas limitadas en el PFSP, y valores del ARPD para el PFSP, según el número de trabajos (Elaboración propia) Al igual que ocurría con el otro objetivo, usar la solución óptima de un problema en otro tendrá mejores resultados en problemas con restricciones similares, como se puede apreciar en las figuras 6.24 y 6.25. Asimismo, un gran número de trabajos a procesar hace que la secuencia óptima de otro problema usada en el PFSP no esté tan cerca del óptimo. El número de máquinas, por otra parte, vuelve a no tener ninguna consecuencia en ese aspecto. Figura 6.25 – Incremento relativo de ∑Cj al usar la secuencia óptima de los problemas con esperas limitadas en el PFSP, y valores del ARPD para el PFSP, según el número de máquinas (Elaboración propia) Efecto de los tiempos de espera en talleres de flujo regular 6. Evaluación computacional 67 6.3.3 Comparación entre problemas con ambos objetivos Promediando los valores para cada uno de los problemas contemplados, según el número de trabajos y máquinas, que aparecen en las tablas 6.10 y 6.11, se construye la siguiente tabla, donde se resume lo expuesto en los últimos puntos, donde se analizaba cada uno de los objetivos independientemente. Tabla 6.12 – Incremento relativo de Cmax y ∑Cj al usar la secuencia óptima de los problemas con esperas limitadas en el PFSP (Elaboración propia) Para comparar ambos objetivos en este contexto, se analiza el caso donde se usa la secuencia óptima del problema no-wait en el PFSP. Tabla 6.13 – Incremento relativo de Cmax y ∑Cj al usar la secuencia óptima del problema sin esperas permitidas en el PFSP (Elaboración propia) Se confirma que, para cualquiera de los tamaños de problema, cuando el objetivo es minimizar ∑𝐶𝑗 se obtienen resultados mucho más próximos al óptimo de PFSP al usar la óptima de otros problemas que cuando se intenta minimizar Cmax. Efecto de los tiempos de espera en talleres de flujo regular 6. Evaluación computacional 68 Figura 6.26 – Incremento relativo de Cmax y ∑Cj al usar la secuencia óptima del problema sin esperas permitidas en el PFSP, según el número de trabajos (Elaboración propia) Figura 6.27 – Incremento relativo de Cmax y ∑Cj al usar la secuencia óptima del problema sin esperas permitidas en el PFSP, según el número de máquinas (Elaboración propia) Efecto de los tiempos de espera en talleres de flujo regular 6. Evaluación computacional 69 6.4 Comportamiento de la secuencia óptima de un PFSP en problemas con esperas limitadas Estudiar los resultados que se obtienen en problemas con esperas limitadas usando la secuencia óptima del PFSP tiene incluso mayor utilidad que el caso contrario, pues como se vio en puntos anteriores, éstos son problemas más difíciles, con sus secuencias más alejadas de la óptima que en el problema el PFSP. Así que si hallando la secuencia óptima del PFSP, que es el problema más sencillo de los estudiados, se pudiera usar en los otros sin obtener resultados muy alejados del óptimo, podría ser de gran utilidad en casos donde sea extremadamente difícil hallar la óptima de un problema con limitaciones en los tiempos de espera de los trabajos entre máquinas. 6.4.1 FO: Cmax De forma similar a como se procedió en el punto anterior, se usa la secuencia óptima del PFSP en los otros problemas, y se calcula en cuánto aumenta el valor del makespan respecto al que éste adquiere en el problema con esperas indefinidas permitidas. Tabla 6.14 – Incremento relativo de Cmax al usar la secuencia óptima del PFSP en problemas con esperas limitadas (Elaboración propia) La diferencia más evidente frente a lo estudiado en el punto anterior es que, para entornos complejos, usar la óptima de un PFSP en un problema no-wait puede hacer que se obtengan valores de este objetivo hasta un 20% peores, mientras que en el caso inverso dicho valor apenas llegaba al 7%. Esto tiene su explicación en el hecho de que los problemas son considerablemente Efecto de los tiempos de espera en talleres de flujo regular 6. Evaluación computacional 70 más sencillos si sus esperas permitidas son mayores, como se comprobó en el capítulo 6.2. Por ello, como la secuencia óptima del PFSP se halla sin preocuparse de los tiempos de espera, usarla en problemas que las limiten puede tener grandes consecuencias sobre el resultado, algo que no ocurre para el caso contrario. Por otro lado, en la figura 6.28 se observa que un mayor número de trabajos empeora el resultado obtenido en un problema con esperas limitadas al usar la secuencia óptima del PFSP, algo que en el capítulo 6.3 se comprobó que también ocurría en el caso contrario. Figura 6.28 – Incremento relativo de Cmax al usar la secuencia óptima del PFSP en problemas con esperas limitadas, según el número de trabajos (Elaboración propia) El número de máquinas, por su parte, vuelve a ser indiferente para lo que se está estudiando en este punto, como se aprecia en la figura 6.29 Figura 6.29 – Incremento relativo de Cmax al usar la secuencia óptima del PFSP en problemas con esperas limitadas, según el número de máquinas (Elaboración propia) Efecto de los tiempos de espera en talleres de flujo regular 6. Evaluación computacional 71 De nuevo, nos centramos en los problemas con las restricciones extremas. En este caso, se usa la secuencia óptima del PFSP en el problema no-wait sin esperas permitidas, y se calcula su RPD (el incremento relativo en comparación al resultado obtenido con la óptima del no-wait). Dichos valores ya aparecían en la tabla 6.14, pero en la 6.15 se comparan con el ARPD del problema nowait. De esta forma, el aumento del makespan se contextualiza para cada tamaño de problema, pues se compara cuán malo es el resultado obtenido al seguir la secuencia óptima del PFSP con el que se obtendría, de media, usando el resto de secuencias. Tabla 6.15 – Incremento relativo de Cmax al usar la secuencia óptima del PFSP en el problema no-wait, y ARPD del problema sin esperas permitidas, para cada tamaño de problema (Elaboración propia) Se observa que, a medida que aumenta el número de máquinas que forman el taller, la diferencia entre los dos valores se hace cada vez menor, siendo especialmente pequeña en los problemas con 5 y 8 trabajos. Precisamente se analiza este último caso, pues es el más cercano entre los estudiados a un caso real, en la figura 6.28, y de ella se puede deducir que cuando el número de máquinas alcanza un valor lo suficientemente alto, hay una mayor probabilidad de obtener un mejor resultado en el problema no-wait utilizando una secuencia aleatoria que con la óptima del PFSP. Efecto de los tiempos de espera en talleres de flujo regular 6. Evaluación computacional 72 Figura 6.30 – Incremento relativo de Cmax al usar la secuencia óptima del PFSP en el problema no-wait, y ARPD del problema sin esperas permitidas, para problemas de 8 trabajos (Elaboración propia) 6.4.2 FO: ∑𝑪𝒋 Al igual que cuando el makespan era el objetivo a minimizar, se usa la secuencia óptima del PFSP en el resto de problemas, y ∑𝐶𝑗 sufre un incremento que se refleja en la siguiente tabla: Tabla 6.16 – Incremento relativo de ∑Cj al usar la secuencia óptima del PFSP en problemas con esperas limitadas (Elaboración propia) Efecto de los tiempos de espera en talleres de flujo regular 6. Evaluación computacional 73 Como con la otra función objetivo, el incremento es mayor cuando crece el número de trabajos, y es independiente al de máquinas, como se observa en las dos siguientes figuras: Figura 6.31 – Incremento relativo de ∑Cj al usar la secuencia óptima del PFSP en problemas con esperas limitadas, según el número de trabajos (Elaboración propia) Figura 6.32 – Incremento relativo de ∑Cj al usar la secuencia óptima del PFSP en problemas con esperas limitadas, según el número de máquinas (Elaboración propia) Con el fin de contextualizar el incremento de ∑𝐶𝑗, se compara con datos ya conocidos, como es el ARPD del problema no-wait para cada uno de los tamaños de problema (ver tabla 6.7). Efecto de los tiempos de espera en talleres de flujo regular 9. Anexos 80 9 ANEXOS 9.1 Anexo – Funciones En este anexo se incluyen las once funciones que se usan en el programa y que se nombraron en el capítulo 5, pero en él no se explicó la utilidad de las mismas, cómo estaban construidas, y tampoco la forma en la se que hallaban los resultados de interés.  Máximo y mínimo de dos números enteros dados int max(int a, int b) { int x; if (a>=b) { x=a; } else{ x=b; } return x; } int min(int a, int b) { int x; if (a>=b) { x=b; } else{ x=a; } return x; }  Factorial de un número entero dado int factorial (int a) { int i; int resul=1; for(i=a;i>=1;i--) { resul=resul*i; } return resul; } Efecto de los tiempos de espera en talleres de flujo regular 9. Anexos 81  Cmax obtenido para una secuencia dada aplicada a un PFSP int Cmax(int m, int n, MAT_INT P, VECTOR_INT sec) { MAT_INT C=DIM_MAT_INT(m+1,n+1); int i,j; for(i=0;i<=m;i++) { for(j=0;j<=n;j++) { C[i][j]=0; } } for(i=1;i<=m;i++) { for(j=1;j<=n;j++) { C[i][sec[j]]=max(C[i-1][sec[j]],C[i][sec[j-1]])+P[i-1][sec[j]- 1]; } } return C[m][sec[n]]; }  ∑𝐶𝑗 obtenido para una secuencia dada aplicada a un PFSP int sumaCj(int m, int n, MAT_INT P, VECTOR_INT sec) { MAT_INT C=DIM_MAT_INT(m+1,n+1); int i,j; for(i=0;i<=m;i++) { for(j=0;j<=n;j++) { C[i][j]=0; } } for(i=1;i<=m;i++) { for(j=1;j<=n;j++) { C[i][sec[j]]=max(C[i-1][sec[j]],C[i][sec[j-1]])+P[i-1][sec[j]- 1]; } } int resul=0; for(j=1;j<=n;j++) { resul=resul+C[m][j]; } return resul; } Efecto de los tiempos de espera en talleres de flujo regular 9. Anexos 82  Cmax obtenido para una secuencia dada aplicada a un problema no-wait int CmaxNOWAIT(int m, int n, MAT_INT P, VECTOR_INT sec) { MAT_INT C=DIM_MAT_INT(m+1,n+1); int i,j,z,A,dif; for(i=0;i<=m;i++) { for(j=0;j<=n;j++) { C[i][j]=0; } } for(i=1;i<=m;i++) { C[i][sec[1]]=C[i-1][sec[1]]+P[i-1][sec[1]-1]; } for(j=2;j<=n;j++) { for(i=1;i<m;i++) { C[i][sec[j]]=max(C[i][sec[j-1]],C[i-1][sec[j]])+P[i- 1][sec[j]-1]; dif=C[i+1][sec[j-1]]-C[i][sec[j]]; A=max(0,dif); for(z=i;z>=1;z--) { C[z][sec[j]]=C[z][sec[j]]+A; } } C[m][sec[j]]=C[m-1][sec[j]]+P[m-1][sec[j]-1]; } return C[m][sec[n]]; } Efecto de los tiempos de espera en talleres de flujo regular 9. Anexos 83  ∑𝐶𝑗 obtenido para una secuencia dada aplicada a un problema no-wait int CmaxNOWAIT(int m, int n, MAT_INT P, VECTOR_INT sec) { MAT_INT C=DIM_MAT_INT(m+1,n+1); int i,j,z,A,dif; for(i=0;i<=m;i++) { for(j=0;j<=n;j++) { C[i][j]=0; } } for(i=1;i<=m;i++) { C[i][sec[1]]=C[i-1][sec[1]]+P[i-1][sec[1]-1]; } for(j=2;j<=n;j++) { for(i=1;i<m;i++) { C[i][sec[j]]=max(C[i][sec[j-1]],C[i-1][sec[j]])+P[i- 1][sec[j]-1]; dif=C[i+1][sec[j-1]]-C[i][sec[j]]; A=max(0,dif); for(z=i;z>=1;z--) { C[z][sec[j]]=C[z][sec[j]]+A; } } C[m][sec[j]]=C[m-1][sec[j]]+P[m-1][sec[j]-1]; } int resul=0; for(j=1;j<=n;j++) { resul=resul+C[m][j]; } return resul; } Efecto de los tiempos de espera en talleres de flujo regular 9. Anexos 84  Cmax obtenido para una secuencia dada aplicada a un problema con esperas limitadas int CmaxMAXWAIT(int m, int n, MAT_INT P, VECTOR_INT sec, int waitmax) { MAT_INT C=DIM_MAT_INT(m+1,n+1); int i,j,z,A,dif; for(i=0;i<=m;i++) { for(j=0;j<=n;j++) { C[i][j]=0; } } for(i=1;i<=m;i++) { C[i][sec[1]]=C[i-1][sec[1]]+P[i-1][sec[1]-1]; } for(j=2;j<=n;j++) { for(i=1;i<m;i++) { C[i][sec[j]]=max(C[i][sec[j-1]],C[i-1][sec[j]])+P[i- 1][sec[j]-1]; dif=C[i+1][sec[j-1]]-C[i][sec[j]]-waitmax; A=max(0,dif); for(z=i;z>=1;z--) { C[z][sec[j]]=C[z][sec[j]]+A; } } C[m][sec[j]]=max(C[m-1][sec[j]],C[m][sec[j-1]])+P[m- 1][sec[j]-1]; } return C[m][sec[n]]; } Efecto de los tiempos de espera en talleres de flujo regular 9. Anexos 85  ∑𝐶𝑗 obtenido para una secuencia dada aplicada a un problema con esperas limitadas int CmaxMAXWAIT(int m, int n, MAT_INT P, VECTOR_INT sec, int waitmax) { MAT_INT C=DIM_MAT_INT(m+1,n+1); int i,j,z,A,dif; for(i=0;i<=m;i++) { for(j=0;j<=n;j++) { C[i][j]=0; } } for(i=1;i<=m;i++) { C[i][sec[1]]=C[i-1][sec[1]]+P[i-1][sec[1]-1]; } for(j=2;j<=n;j++) { for(i=1;i<m;i++) { C[i][sec[j]]=max(C[i][sec[j-1]],C[i-1][sec[j]])+P[i- 1][sec[j]-1]; dif=C[i+1][sec[j-1]]-C[i][sec[j]]-waitmax; A=max(0,dif); for(z=i;z>=1;z--) { C[z][sec[j]]=C[z][sec[j]]+A; } } C[m][sec[j]]=max(C[m-1][sec[j]],C[m][sec[j-1]])+P[m- 1][sec[j]-1]; } int resul=0; for(j=1;j<=n;j++) { resul=resul+C[m][j]; } return resul; } Efecto de los tiempos de espera en talleres de flujo regular 9. Anexos 86  Primera aplicación de la enumeración completa void enumeracionCompleta1(VECTOR_INT sec, int n, int par_length, int m, MAT_INT P) { int i; if(par_length>1) { for(i=1;i<par_length;i++) { int aux=sec[i]; sec[i]=sec[par_length-1]; sec[par_length-1]=aux; enumeracionCompleta1(sec,n,par_length-1,m,P); aux=sec[i]; sec[i]=sec[par_length-1]; sec[par_length-1]=aux; } } else { x1=Cmax(m,n,P,sec); x1max=max(x1max,x1); x1min=min(x1min,x1); if(x1==x1min) { copyIVector(sec,secMIN[0],n+1); } x2=CmaxMAXWAIT(m,n,P,sec,40); x2max=max(x2max,x2); x2min=min(x2min,x2); if(x2==x2min) { copyIVector(sec,secMIN[1],n+1); } x3=CmaxMAXWAIT(m,n,P,sec,30); x3max=max(x3max,x3); x3min=min(x3min,x3); if(x3==x3min) { copyIVector(sec,secMIN[2],n+1); } x4=CmaxMAXWAIT(m,n,P,sec,20); x4max=max(x4max,x4); x4min=min(x4min,x4); if(x4==x4min) { copyIVector(sec,secMIN[3],n+1); } Efecto de los tiempos de espera en talleres de flujo regular 9. Anexos 87 x5=CmaxMAXWAIT(m,n,P,sec,10); x5max=max(x5max,x5); x5min=min(x5min,x5); if(x5==x5min) { copyIVector(sec,secMIN[4],n+1); } x6=CmaxNOWAIT(m,n,P,sec); x6max=max(x6max,x6); x6min=min(x6min,x6); if(x6==x6min) { copyIVector(sec,secMIN[5],n+1); } } } Para cada una de las posibles secuencias que se pueden tener, según el número de trabajos que haya que procesar, se obtiene el resultado de cada uno de los seis problemas estudiados. Se guardan los valores mínimo y máximo de la FO de cada problema en las variables creadas con ese propósito. Asimismo, cuando se halla una secuencia que da una solución mejor que las que se han obtenido previamente, se copia dicha secuencia en la fila correspondiente de una matriz de 6 filas y n columnas, donde se recogen las secuencias óptimas de los seis problemas estudiados. Efecto de los tiempos de espera en talleres de flujo regular 9. Anexos 88  Segunda aplicación de la enumeración completa void enumeracionCompleta2(VECTOR_INT sec, int n, int par_length, int m, MAT_INT P) { int i; if(par_length>1) { for(i=1;i<par_length;i++) { int aux=sec[i]; sec[i]=sec[par_length-1]; sec[par_length-1]=aux; enumeracionCompleta2(sec,n,par_length-1,m,P); aux=sec[i]; sec[i]=sec[par_length-1]; sec[par_length-1]=aux; } } else { x1=Cmax(m,n,P,sec); x1tot=x1tot+x1; for(i=0;i<100;i++) { if((x1>=(x1min+0.01*i*(x1max- x1min)))&(x1<=(x1min+0.01*(i+1)*(x1max-x1min)))) { prob1[i]=prob1[i]+1; } } x2=CmaxMAXWAIT(m,n,P,sec,40); x2tot=x2tot+x2; for(i=0;i<100;i++) { if((x2>=(x2min+0.01*i*(x2max- x2min)))&(x2<=(x2min+0.01*(i+1)*(x2max-x2min)))) { prob2[i]=prob2[i]+1; } } x3=CmaxMAXWAIT(m,n,P,sec,30); x3tot=x3tot+x3; for(i=0;i<100;i++) { if((x3>=(x3min+0.01*i*(x3max- x3min)))&(x3<=(x3min+0.01*(i+1)*(x3max-x3min)))) { prob3[i]=prob3[i]+1; } } Efecto de los tiempos de espera en talleres de flujo regular 9. Anexos 89 x4=CmaxMAXWAIT(m,n,P,sec,20); x4tot=x4tot+x4; for(i=0;i<100;i++) { if((x4>=(x4min+0.01*i*(x4max- x4min)))&(x4<=(x4min+0.01*(i+1)*(x4max-x4min)))) { prob4[i]=prob4[i]+1; } } x5=CmaxMAXWAIT(m,n,P,sec,10); x5tot=x5tot+x5; for(i=0;i<100;i++) { if((x5>=(x5min+0.01*i*(x5max- x5min)))&(x5<=(x5min+0.01*(i+1)*(x5max-x5min)))) { prob5[i]=prob5[i]+1; } } x6=CmaxNOWAIT(m,n,P,sec); x6tot=x6tot+x6; for(i=0;i<100;i++) { if((x6>=(x6min+0.01*i*(x6max- x6min)))&(x6<=(x6min+0.01*(i+1)*(x6max-x6min)))) { prob6[i]=prob6[i]+1; } } } } Cuando se aplica por segunda vez la enumeración completa, ya se saben los valores máximos y mínimos de la FO de cada problema. Para cada una de las posibles secuencias, se halla el resultado que se obtiene en cada problema, y se calcula en cuál de los 100 tramos en los que se divide el intervalo entre los valores extremos se encuentra el resultado, y por tanto, la secuencia en cuestión.