Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time

i Equation Chapter 1 Section 1 Trabajo Fin de Grado Ingeniería de Organización Industrial Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time Autor: Marta Ariza Gamero Tutor: Paz Pérez González Dpto. de Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2021 iii Trabajo Fin de Grado Ingeniería de Organización Industrial Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time Autor: Marta Ariza Gamero Tutor: Paz Pérez González Profesor titular Dpto. de Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2021 v Trabajo Fin de Grado: Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time Autor: Marta Ariza Gamero Tutor: Paz Pérez González El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2021 El Secretario del Tribunal vii A quién siempre estuvo junto a mí. ix Índice Índice ............................................................................................................................................................ ix 1 Objetivo del estudio .............................................................................................................................. 1 2 Introducción a la Programación de la Producción .................................................................................. 3 3 Descripción del problema ...................................................................................................................... 7 3.1 Entorno Distributed Flow shop ................................................................................................................... 7 3.2 Restricciones del problema ......................................................................................................................... 7 3.3 Objetivo Total Core Idle Time ...................................................................................................................... 7 3.4 Cálculo del objetivo para el problema propuesto ...................................................................................... 8 4 Revisión de la literatura ....................................................................................................................... 11 5 Método de resolución .......................................................................................................................... 13 5.1 Adaptación de la heurística DLR ............................................................................................................... 13 5.2 Adaptación de la heurística DNEH ............................................................................................................ 14 5.3 Adaptación de las heurísticas NEH (R1, Ai), NEH (R2, Ai) ....................................................................... 15 5.4 Nuevas heurísticas ..................................................................................................................................... 18 6 Resultados obtenidos .......................................................................................................................... 21 7 Conclusiones ........................................................................................................................................ 27 Bibliografía .................................................................................................................................................. 29 Anexo Código programación en C ............................................................................................................... 31 7 3 DESCRIPCIÓN DEL PROBLEMA l problema que se va a tratar, según la tripleta 𝛼 | 𝛽 | 𝛾, es 𝐷𝐹𝑚 | 𝑝𝑟𝑚𝑢 | ∑𝐶𝐼𝑇 que se va a explicar a continuación. 3.1 Entorno Distributed Flow shop El entorno Distributed Flow shop 𝐷𝐹𝑚 es un caso particular del Flow shop 𝐹𝑚 . Recordando la Introducción, la distribución de una planta Flow shop es una disposición tipo taller con máquinas en serie y donde todos los trabajos tienen que pasar por todas las máquinas en el mismo orden. Se asume que primero pasa por la máquina 1, a continuación, la máquina 2 y así hasta la máquina m. En el Distributed Flow shop 𝐷𝐹𝑚 hay un conjunto F = {1,…,f} de fábricas idénticas con m máquinas en cada una de las fábrica. Cada una de las máquinas realiza una operación diferente en la fábrica. Cada uno de los n trabajos deben ser procesados por una única fábrica f. Cualquier trabajo puede asignarse a cualquier fábrica que actúa como un entorno Flow shop. 3.2 Restricciones del problema Es necesario asumir las suposiciones generales explicadas en la Introducción, para la definición del problema. Una operación no puede ser interrumpida. Se presupone también que todos los n trabajos están disponibles para ser procesados en el instante 0, así como que todas las m máquinas estas disponibles para procesar en el mismo instante 0. Además, un trabajo n no puede ser procesado por más de una máquina simultáneamente ni una máquina puede procesar dos trabajos al mismo tiempo. El tiempo de transporte entre máquinas se considera despreciable al igual que los buffers se consideran infinitos. Además, de seguir el mismo orden o ruta los trabajos que hay en cada fábrica con distribución Flow shop, se exige por la restricción prmu que la secuencia es la misma para todas las máquinas, es decir, el orden por el que los trabajos pasan por las máquinas para ser procesado es el mismo en cualquiera de las máquinas de una misma fábrica f. El tiempo de proceso del trabajo j en la máquina i, 𝑝𝑖𝑗, es el mismo en cualquiera de las fábricas del conjunto F. 3.3 Objetivo Total Core Idle Time El tiempo ocioso de una máquina se puede dividir en tres componenentes (Maassen et al., 2020): - Front Idle Time de la máquina i, FITi: tiempo que la máquina espera a procesar el primer trabajo programado. - Core Idle Time de la máquina i, CITi: tiempo que una máquina espera entre dos trabajos consecutivos. - Back Idle Time de la máquina i, BITi: tiempo que la máquina espera a que todos los trabajos de procesados. E Descripción del problema 8 La restricción no-idle en un modelo de programación de la producción limita los programas en los que no existen tiempos ociosos de las máquinas entre trabajos. Es posible relajar la restricción si, en lugar de impedir tiempos ociosos, se minimizan para aquellos problemas donde la restricción no sea limitante como sí que sucede en algunos sectores como las industrias alimentarias. En Ilustración 2 (Maassen et al., 2020), se muestra mediante un diagrama de Gantt el tiempo ocioso que aparece en una entorno Flow shop con valores j = 4 trabajos y m = 3 máquinas. Si la restricción no-idle se exigiera, aparecería FITi y BITi pero no CITi. Ilustración 2. Tiempos ociosos en un entorno Flow shop En la literatura, la restricción no-idle se ha estudiado junto al objetivo makespan (Ruiz et al., 2009). Para relajar dicho modelo, se sustituye el objetivo makespan denominado como 𝐶𝑚𝑎𝑥, por un nuevo objetivo que minimiza el tiempo ocioso entre trabajos dentro de una misma máquina denotado como ΣCIT desapareciendo la restricción no-idle. Además, se ha demostrado que los métodos eficientes empleados para la función objetivo clásica es aplicable a la nueva función objetivo, sabiendo que generan soluciones de calidad pero no las óptimas (Maassen et al., 2020). En este proyecto se plantea considerar como función objetivo la suma o Total Core Idle Time generados en cada fábrica, ΣCIT. Se debe a que es tiempo desperdiciado en la programación, no se puede emplear ese tiempo para realizar tareas de mantenimiento, transporte o limpieza, entre otras. Sin embargo, el Front Idle Time y el Back Idle Time son intervalos de tiempo aprovechables para realizar las tareas anteriormente mencionadas. Asimismo, la eliminación de cualquier tipo de desperdicio en la producción es uno de los principales objetivos en cualquier industria, a fin de obtener un sistema eficiente. ΣCIT proporciona información sobre la eficiencia de la producción y la utilización de las máquinas. 3.4 Cálculo del objetivo para el problema propuesto En este apartado, mediante un ejemplo numérico sencillo, se explica cómo se calcula el Total Core Idle Time para un problema con f = 2 fábricas, m = 4 máquinas y j = 7 trabajos. Los tiempos de proceso se encuentran en Tabla 1. 9 9 Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time trabajo j 1 2 3 4 5 6 7 máquina i 1 3 4 2 1 2 3 3 2 2 1 1 2 4 3 3 3 1 2 3 4 4 5 1 4 5 2 2 2 2 1 2 Tabla 1.Tiempos de proceso del ejemplo dado El programa se muestra en Ilustración 3. La fábrica 1 tiene asignada la secuencia (j1, j2, j3, j4), mientras que la fábrica 2, la secuencia (j5, j6, j7). Comenzando por la fábrica 1, cuando el trabajo j1 termina de ser procesado en la máquina 1, pasa inmediatamente a la máquina 2 ya que se está trabajando con programas semiactivos. Se puede observar que el primer trabajo secuenciado en una fábrica con entorno Flow shop con permutación y con programa semiactivo no va a generar Core Idle Time. Además, en la primera máquina de cada fábrica tampoco se puede generar CIT cuando se trabaja con programas semiactivos. En el momento que el trabajo j1 termina en la máquina 1 (𝑝1,1= 3 u.t.) pasa a la máquina 2 (𝑝2,1= 2 u.t.), y en dicho instante, el trabajo j2 comienza a ser procesado en la máquina 1 (𝑝1,2= 4 u.t.). No obstante, cuando el trabajo j1 termina en la máquina 2, no pasa el trabajo j2 a la máquina 1 puesto que su tiempo de proceso aún no ha finalizado. La máquina 2 pasa 2 u.t. sin procesar trabajos, el CIT de la máquina 2 hasta el momento es de 2 u.t. En la máquina 1, cuando el trabajo j2 termina, el trabajo j3 comienza a ser procesado en esta máquina (𝑝1,3 = 2 u.t.) pero una vez más, el trabajo j2 termina en la máquina 2 (𝑝2,2 = 1 u.t.) antes de que comienze el trabajo j3. El CIT de la máquina 2 es hasta el momento de 3 u.t. Ilustración 3. Diagrama de Gantt del programa dado De esta manera, el ΣCIT se calcula como la suma de CIT de cada fábrica y el CIT de cada fábrica se calcula como la suma de CIT de cada máquina. Se representa en Tabla 2 el cálculo de la función objetivo. En la fábrica 1, el CIT de la máquina 2 son 4 u.t., CIT de la máquina 3 son 2 u.t. y el CIT de la máquina 4 es de 2 u.t. La fábrica 1, en el programa propuesto, desaprovecha 8 u.t. en las que no se están procesando trabajos ni se están realizando tareas de limpieza o mantenimiento. Así, el CIT de la fábrica 2 es de 3 u.t. en la máquina 4. En conclusión, el problema propuesto y siguiendo el programado dado, el Total Core Idle es 11 u.t. máquina 1 máquina 2 máquina 3 máquina 4 CIT por fábrica fábrica 1 0 4 2 2 8 fábrica 2 0 0 0 3 3 CIT total 11 Tabla 2. Cálculo de la función objetivo para el programa dado máquina 1 j4 máquina 2 j2 CIT2 j3 CIT2 máquina 3 j1 máquina 4 máquina 1 máquina 2 máquina 3 j7 máquina 4 j6 u.t 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 fábrica 1 fábrica 2 j5 j6 j7 j5 j6 j7 j1 j2 j3 j1 j4 CIT3 j2 j3 j4 j4 CIT4 j3 j2 j1 CIT2 j7 CIT4 j5 j5 j6 11 4 REVISIÓN DE LA LITERATURA l problema detallado anteriormente, Descripción del problema, no ha sido estudiado con anterioridad. Es un nuevo foco de estudio a raíz de ciertos problemas relacionados que se encuentran en la literatura. En este capítulo se hace una recopilación de algunos de ellos. El problema de programación constituido por el entorno Flow shop, y más concretamente el entorno Permutation Flowshop, es un problema de optimización antiguo y bastante estudiado en la literatura (Nawaz et al., 1983). A este problema se hará referencia como Permutation Flow shop Scheduling Problem (PFSP). En él, se debe asignar el orden de los trabajos en una única fábrica con una ruta determinada. Han sido muchos los objetivos estudiados siendo el makespan el más popular de ellos (Fernandez-Viagas & Framinan, 2014). La deslocalización y la globalización han generado la necesidad de estudiar nuevos entornos, siendo el problema Distributed Permutation Flow shop (DPFSP) la evolución de PFSP. A diferencia del PFSP, no solo se asignan trabajos a máquinas con una misma ruta; sino que también esos trabajos deben ser asignados a distintas fábricas que son idénticas. El DPFSP se ha estado asociando a objetivos de consumo y eficiencia energética como consecuencia de que el sector industrial es uno de los principales consumidores de energía a nivel mundial, y como tal pretenden reducir su gasto. No obstante, (Pan et al., 2019a) y (Fernandez-Viagas et al., 2018) plantean un problema mono objetivo al minimizar el flowtime con el interés de estabilizar los recursos al disminuir el tiempo total que los trabajos permanecen en el sistema. En la literatura se encuentra el denotado problema Energy-Efficient Distributed No-idle Flow shop Scheduling problem (EEDNIFSP) (Chen et al., 2019), que además de exigir la misma ruta, no permite tiempos ociosos entre máquinas (no-idle). Mediante un algoritmo colaborativo de optimización (COA) con múltiples métodos de inicialización y operadores de búsqueda tanto para la asignación de trabajos en las secuencias de las fábricas como para la determinación de las velocidades de los trabajos por cada máquina, se ha querido minimizar el makespan y el consumo energético total (TEC). Por tanto, la solución al problema viene determinada por la asignación trabajos-fábricas y secuencias dentro de las fábricas dada por el algoritmo NEH adaptado y la velocidad dada por el método Closet Operation Time (COT). El estudio de este problema multiobjetivo en concreto se ha extendido y ha sido investigado por otros autores por el interés que supone la relación del makespan y el TEC: a medida que se desea minimizar el makespan, se maximiza el TEC porque las velocidades de las máquinas aumentan. No obstante, si se aumenta la velocidad en las operaciones no críticas, es decir, las que no determinan el makespan, se reduce el TEC sin afectar al tiempo que la fábrica está procesando trabajos. En (G. Wang et al., 2020) mediante un nuevo algoritmo multiobjetivo Whale Swarm (MOWSA), introducen nuevos operadores relacionados con la eficiencia energética y nuevas consideraciones en el TEC para buscar la mejor solución al DPFSP. En último lugar, (J. J. Wang & Wang, 2020) gracias a un algoritmo Knowledgebased Cooperative (KCA) y comparando sus resultados con los precedentes concluye que se llega a mejores soluciones con KCA. E 13 5 MÉTODO DE RESOLUCIÓN n este capítulo se van a presentar un total de veintiséis heurísticas aplicadas al problema que han sido programadas para conocer los mejores resultados al problema propuesto. Son heurísticas adaptadas ya que, tal y como se mencionó en Revisión de la literatura, el problema propuesto no se ha estudiado con anterioridad y no se encuentra en la literatura. 5.1 Adaptación de la heurística DLR La heurística DLR fue propuesta por (Pan et al., 2019b) para el problema Distributed Permutation Flow shop con objetivo flowtime, 𝐷𝐹𝑚 | 𝑝𝑟𝑚𝑢 | ∑𝐹𝑗. Al tratarse de una heurística constructiva, la secuencia se va creando al insertar los trabajos de uno en uno en ella. El procedimiento se observa en Ilustración 4. La heurística, en primer lugar, decide cuál es la mejor fábrica para procesar el siguiente trabajo. Para ello, calcula el makespan de cada fábrica y así conoce cuál es la fábrica que antes va a poder procesar el siguiente trabajo, k*. A continuación, decide cuál es el siguiente trabajo j que se va a insertar en dicha fábrica. Este trabajo se inserta en la última posición de la secuencia parcial de la mejor fábrica ,𝑛𝑘∗. El mejor trabajo es aquel que genere menor valor del índice 𝐼𝐹𝑗,𝑛𝑘∗ . Este valor es una función del tiempo de terminación o makespan de la fábrica tras insertar el trabajo que estamos evaluando, 𝐶𝑚,𝑗 y los tiempos ociosos que genera también tras su inserción, 𝐼𝑇𝑗,𝑛𝑘∗. El cálculo del índice se muestra en Ecuación 1, así como el cálculo de los tiempos ociosos Ecuación 2. Recordando la notación de Introducción a la Programación de la Producción, f hace referencia a la fábrica que se está evaluando, m a la máquina y j al trabajo. 𝐼𝐹𝑗,𝑛𝑘∗ = (𝑛𝑓 ⁄ − 𝑛𝑘∗ − 2)𝐼𝑇𝑗,𝑛𝑘∗ + 𝐶𝑚,𝑗 Ecuación 1. Índice IF (j, nk*) 𝐼𝑇𝑗,𝑛𝑘∗ =∑ 𝑚· 𝑚𝑎𝑥 { 𝐶𝑖−1,𝑗 − 𝐶𝑖,[𝑛𝑘∗],0} 𝑖+ 𝑛𝑘∗ · (𝑚 − 1)/(𝑛𝑓 ⁄ − 2) 𝑚 𝑖=2 Ecuación 2. Cálculo Idle Time para nk* El interés de esta heurística para nuestro problema proviene precisamente de este índice 𝐼𝐹𝑗,𝑛𝑘∗. Al tener en cuenta los tiempos ociosos que se generan y buscar el menor valor de ellos, el valor de la función objetivo también se verá decrementado. En las primeras f iteraciones siempre va a haber, al menos, una fábrica cuyo tiempo de terminación es 0 por no tener asignado ningún trabajo, se calcula el índice 𝐼𝐹𝑗,0 según Ecuación 3 con ayuda de Ecuación 4 y se ordenan los trabajos de manera creciente y se asignan los f primeros a las f fábricas. 𝐼𝐹𝑗,0 = (𝑛𝑓 ⁄ − 2)𝐼𝑇𝑗,0 + 𝐶𝑚,𝑗 Ecuación 3. Índice IF(j,0) E Método de resolución 14 𝐼𝑇𝑗,0 =∑𝑚·𝐶𝑖−1,𝑗 𝑖 𝑚 𝑖=2 Ecuación 4. Cálculo Idle Time para 0 Ilustración 4. Pseudocódigo adaptación DLR 5.2 Adaptación de la heurística DNEH Al igual que la heurística constructiva DLR (Adaptación de la heurística DLR), la DNEH fue propuesta por (Pan et al., 2019b) para el mismo problema. Dado el éxito de la adaptación del NEH clásico para el problema 𝐹𝑚 | 𝑝𝑟𝑚𝑢 | 𝐶𝑚𝑎𝑥 (Nawaz et al., 1983) para el problema 𝐷𝐹𝑚 | 𝑝𝑟𝑚𝑢 | 𝐶𝑚𝑎𝑥, en ese caso se adaptó para γ = flowtime, 𝐷𝐹𝑚 | 𝑝𝑟𝑚𝑢 | ∑𝐹𝑗. Una vez más se emplea el índice 𝐼𝐹𝑗,𝑛𝑘∗para ordenar los trabajos de mayor a menor en lugar de ordenarlo según suma de tiempos de procesos 𝑝𝑖𝑗, como ocurre en el NEH clásico. Los trabajos se van tomando para asignarlos a las fábricas de mayor a menor 𝐼𝐹𝑗,𝑛𝑘∗. Se asignan a aquella fábrica y a aquella posición dentro de la fábrica que genere menor incremento de la función objetivo, es decir, que genere menor incremento de tiempo de flujo. Para el problema que se está estudiando, simplemente hay que buscar el menor incremento de ΣCIT para obtener la programación. El procedimiento se muestra en Ilustración 5. Tal y como ocurría en DLR, los primeros f trabajos con mayores valores de 𝐼𝐹𝑗,0 se asignan a las f fábricas. 15 15 Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time Ilustración 5. Pseudocódigo adaptación DNEH 5.3 Adaptación de las heurísticas NEH (R1, Ai), NEH (R2, Ai) Al igual que la DNEH (Adaptación de la heurística DNEH), en el artículo (Fernandez-Viagas et al., 2018) se toma la heurística NEH para buscar la mejor solución al problema 𝐷𝐹𝑚 | 𝑝𝑟𝑚𝑢 | ∑𝐹𝑗. Esta vez se tienen en cuenta dos formas de representar las soluciones que determinarán la eficiencia de las heurísticas y seis reglas para asignar los trabajos a las fábricas, dando lugar a doce heurísticas constructivas. La denominada representación R1 da una única secuencia de trabajos para el problema. Con ella no se puede conocer la asignación de trabajos a fábricas, es necesario conocer la regla aplicada para determinar la programación. Se supone un problema con f = 2 fábricas, m = 2 máquinas y j = 4 trabajos, si la secuencia fuera (j3, j4, j1, j2), el programa es desconocido hasta que se conozca la regla y varía según el criterio de asignación tal y como se muestra en Ilustración 6 e Ilustración 7. Se ha empleado para dicha secuencia, la representación R1 y dos criterios de asignación distintos que serán explicados posteriormente, generando programas diferentes. La denominada representación R2 da la secuencia por fábricas y por tanto la solución es conocida sin conocer cuál ha sido la regla de asignación empleada. La programación es única siempre que se consideren programas semiactivos, en Ilustración 8 se indica como es la representación R2 sin necesitar secuencia alguna. Resultados obtenidos 22 Promedio RDI DNEH 0,057 NEH R2 A6 0,088 DLR 0,929 DNEH R1 A1 0,301 NEH R1 A1 0,183 DNEH R1 A2 0,209 NEH R1 A2 0,115 DNEH R1 A3 0,102 NEH R1 A3 0,136 DNEH R1 A4 0,009 NEH R1 A4 0,003 DNEH R1 A5 0,035 NEH R1 A5 0,023 DNEH R1 A6 0,044 NEH R1 A6 0,035 DNEH R2 A1 0,756 NEH R2 A1 0,335 DNEH R2 A2 0,619 NEH R2 A2 0,334 DNEH R2 A3 0,356 NEH R2 A3 0,396 DNEH R2 A4 0,053 NEH R2 A4 0,026 DNEH R2 A5 0,101 NEH R2 A5 0,084 DNEH R2 A6 0,120 Tabla 3. Promedio RDI por heurística Ilustración 13. Gráfica promedio RDI por heurística 23 23 Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time Ilustración 14. Comparativa promedio RDI Resulta interesante conocer cuál de las heurísticas programadas es mejor para evaluar un problema concreto según los tres parámetros que lo definen: el número de fábricas f, de máquinas m o de trabajos n. Para ellos se hace el promedio del 𝑅𝐷𝐼ℎ𝐼 de aquellas instancias que comparten el mismo valor de f, m o n, según el parámetro que nos interese para conocer el menor valor obtenido para un valor del parámetro en concreto. Tanto la nueva heurística propuesta DNEH (R1, A4) como la adaptada NEH (R1, A4), son las dos heurísticas que generan los mejores valores para cualquiera de los parámetros experimentados. Para los valores f = 4, m = 2, 3 y n = 6, 14, 16 la nueva heurística es mejor que la adaptada tal y como se muestra en Tabla 4, Tabla 5 y Tabla 6. Cabe destacar que el promedio de 𝑅𝐷𝐼ℎ𝐼 para la heurística NEH (R1, A4) para m = 2, 3 y n = 4, 10 es 0, es decir, para cada una de las instancias evaluadas cuyos parámetros m o n era uno de los indicados se ha obtenido la mejor solución siempre en esta heurística. Lo mismo ocurre para y n = 6, 16 con la heurística propuesto. En el caso m = 3, ambas heurísticas dan los mejores resultados. f Promedio de NEH_R1_A4 Promedio de DNEH_R1_A4 2 0,0033 0,0139 3 0,0039 0,0059 4 0,0053 0,0017 5 0,0034 0,0124 6 0,0007 0,0141 7 0,0011 0,0146 Total general 0,0033 0,0094 Tabla 4. Promedio RDI por parámetro f Resultados obtenidos 24 m Promedio de NEH_R1_A4 Promedio de DNEH_R1_A4 2 0,0000 0,0006 3 0,0000 0,0000 4 0,0058 0,0036 5 0,0061 0,0117 10 0,0018 0,0158 20 0,0039 0,0152 Total general 0,0033 0,0094 Tabla 5. Promedio RDI por parámetro m n Promedio de NEH_R1_A4 Promedio de DNEH_R1_A4 4 0,0000 0,0091 6 0,0058 0,0000 8 0,0021 0,0130 10 0,0000 0,0020 12 0,0066 0,0140 14 0,0105 0,0070 16 0,0027 0,0000 20 0,0049 0,0174 50 0,0031 0,0111 100 0,0007 0,0078 Total general 0,0033 0,0094 Tabla 6. Promedio RDI por parámetro n Para completer el análisis del índice 𝑅𝐷𝐼ℎ𝐼, se ha realizado un contraste de hipótesis suponiendo igualdad de media entre los dos métodos. Para ello, se ha calculado el intervalo de confianza (IC) para la media de DNEH (R1, A4) y de NEH (R1, A4) con un nivel de confianza del 95%. Dado que la muestra está compuesta por los RDI de las 72 instancias, se puede suponer la aproximación a una distribución Normal. El cálculo se halla en Tabla 7. No existen evidencias estadísticas para aceptar la hipótesis de que los métodos sean iguales de efiencientes en media, puesto que el IC del método adaptado NEH (R1, A4) es [0.002, 0.005] y el IC para la nueva heurística DNEH (R1, A4) es [0.006, 0.013], ambos para el mismo nivel de confianza. 25 25 Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time INTERVALO DE CONFIANZA PARA LA MEDIA DNEH MEDIA 0,009 DESV ESTÁNDAR 0,015 n 72 NIVEL DE SIGNIFICACIÓN 0,05 CANTIDAD PIVOTAL 0,003 Intervalo de confianza 0,013 0,006 NEH MEDIA 0,003 DESV ESTÁNDAR 0,007 n 72 NIVEL DE SIGNIFICACIÓN 0,05 CANTIDAD PIVOTAL 0,002 Intervalo de confianza 0,005 0,002 Tabla 7. Cálculo intervalo de confianza para la media con α=0,05 27 7 CONCLUSIONES a Programación de la Producción juega un papel bastante importante en un elevado número de empresas, ya no solo manufactureras, sino que también abarca otros sectores como la distribución o el transporte entre otras. Es una decisión operativa con bastante complejidad que precisa conocer la estructura de la planta y la demanda a satisfacer. En este proyecto, la estructura o entorno que se ha llevado al estudio es el entorno Distributed Flow shop. En este entorno se tiene un conjunto de fábricas idénticas que se comportan cada una de ellas como un Flow shop de permutación, es decir, cada una de las fábricas tiene el mismo número de máquinas, m, con una disposición tipo taller de máquinas en serie y los trabajos pasan por cada una de las maquinas en el mismo orden. Además, se exige por la restricción de permutación que la secuencia de trabajos por máquina sea la misma. En la literatura, hasta el momento este entorno había sido estudiado con distintos objetivos como es el Total Flowtime o Makespan. Ahora un nuevo problema se plantea al estudiar el Total Core Idle Time. Este objetivo busca minimizar los tiempos ociosos de las máquinas y puede ser considerado como un objetivo relacionado con la sostenibilidad, ya que los tiempos ociosos de las máquinas generan un coste energético innecesario al tener las máquinas encendidas sin procesar ningún trabajo. Además, este objetivo también tiene relación con la ineficiencia del proceso, ya que en los tiempos ociosos entre trabajos no se pueden aprovechar de forma tan clara como los tiempos ociosos al inicio o al fin de un programa, para realizar, por ejemplo, tareas de mantenimiento de las máquinas. Con la adaptación de la heurística DLR y DNEH propuesto en (Pan et al., 2019b), el clásico NEH adaptado al Distributed Flow shop con las dos representaciones de las soluciones propuesto en (Fernandez-Viagas et al., 2018) y una nueva heurística constructiva planteada como una nueva adaptación del NEH con trabajos ordenados según el índice Idle Time, 𝐼𝐹𝑗,0, de (Pan et al., 2019b), se ha buscado el mejor método de resolución para el problema propuesto. Un total de veintiséis heurísticas han sido programadas en lenguaje de programación C mediante CodeBlocks y se han resuelto las instancias extraídas de la literatura de (Naderi & Ruiz, 2010) . Los resultados obtenidos se han comparado mediante el índice RDI con el objetivo de conocer el mejor de los métodos. La existente heurísticas NEH (R1, A4) y la nueva DNEH (R1, A4) generan buenos resultados para las instancias planteadas. Para algunos valores de f, n o m una heurística funciona mejor que la otra, pero se ha demostrado que la heurística NEH (R1, A4) es estadísticamente mejor que la propuesta. No obstante, como se ha ido comentando a lo largo del proyecto, este es un nuevo problema cuyo estudio sigue abierto y los métodos propuestos pueden ser mejorados. L 29 BIBLIOGRAFÍA Chen, J. fang, Wang, L., & Peng, Z. ping. (2019). A collaborative optimization algorithm for energy-efficient multi-objective distributed no-idle flow-shop scheduling. Swarm and Evolutionary Computation, 50(July), 100557. https://doi.org/10.1016/j.swevo.2019.100557 Fernandez-Viagas, V., & Framinan, J. M. (2014). On insertion tie-breaking rules in heuristics for the permutation flowshop scheduling problem. Computers and Operations Research, 45, 60–67. https://doi.org/10.1016/j.cor.2013.12.012 Fernandez-Viagas, V., Perez-Gonzalez, P., & Framinan, J. M. (2018). The distributed permutation flow shop to minimise the total flowtime. Computers and Industrial Engineering, 118(January), 464–477. https://doi.org/10.1016/j.cie.2018.03.014 Framinan, J. M., Leisten, R., & Ruiz García, R. (2014). Manufacturing Scheduling Systems. In Manufacturing Scheduling Systems. https://doi.org/10.1007/978-1-4471-6272-8 Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. H. G. R. (1979). Optimization and heuristic in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5, 287–326. https://ac.els-cdn.com/S016750600870356X/1-s2.0-S016750600870356X-main.pdf?_tid=cbf345a3- 808d-42df-9560-bf8a52069d0e&acdnat=1550949881_e9837bfdf6316caefaf71ae2f3779b10 Librería SCHEDULE – Grupo de Investigación Organización Industrial. (n.d.). Retrieved September 3, 2021, from http://grupo.us.es/oindustrial/investigacion/software-y-librerias/libreria-schedule/ Maassen, K., Perez-Gonzalez, P., & Günther, L. C. (2020). Relationship between common objective functions, idle time and waiting time in permutation flow shop scheduling. Computers and Operations Research, 121, 104965. https://doi.org/10.1016/j.cor.2020.104965 Naderi, B., & Ruiz, R. (2010). The distributed permutation flowshop scheduling problem. Computers and Operations Research, 37(4), 754–768. https://doi.org/10.1016/j.cor.2009.06.019 Nawaz, M., Enscore, E. E., & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1), 91–95. https://doi.org/10.1016/0305-0483(83)90088-9 Pan, Q. K., Gao, L., Wang, L., Liang, J., & Li, X. Y. (2019a). Effective heuristics and metaheuristics to minimize total flowtime for the distributed permutation flowshop problem. Expert Systems with Applications, 124, 309–324. https://doi.org/10.1016/j.eswa.2019.01.062 Pan, Q. K., Gao, L., Wang, L., Liang, J., & Li, X. Y. (2019b). Effective heuristics and metaheuristics to minimize total flowtime for the distributed permutation flowshop problem. Expert Systems with Applications, 124, 309–324. https://doi.org/10.1016/j.eswa.2019.01.062 Pinedo, M. L. (2012). Scheduling. Theory, Algorithms, and Systems (Fourth). Springer New York Dordrecht Heidelberg London. https://doi.org/10.1007/978-1-4614-2361-4 Ruiz, R., Vallada, E., & Fernández-Martínez, C. (2009). Scheduling in Flowshops with No-Idle Machines. In U. K. Chakraborty (Ed.), Computational Intelligence in Flow Shop and Job Shop Scheduling (pp. 21– 51). Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-02836-6_2 Wang, G., Gao, L., Li, X., Li, P., & Tasgetiren, M. F. (2020). Energy-efficient distributed permutation flow shop scheduling problem using a multi-objective whale swarm algorithm. Swarm and Evolutionary Computation, 57(April), 100716. https://doi.org/10.1016/j.swevo.2020.100716 Wang, J. J., & Wang, L. (2020). A Knowledge-Based Cooperative Algorithm for Energy-Efficient Scheduling of Distributed Flow-Shop. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 50(5), 1805– 1819. https://doi.org/10.1109/TSMC.2017.2788879 31 ANEXO CÓDIGO PROGRAMACIÓN EN C #include <schedule.h> #include <stdio.h> #include<conio.h> #include<time.h> MAT_INT loadDPFS (char *data, int *jobs, int *machs, int *facts); void outputDPFS ( char *inputfile, char *outputfile, int time, int jobs, int machs, int facts, VECTOR_INT seq, MAT_INT seq_fabs, double objetive); int CIT (VECTOR_INT seq, MAT_INT pt, int jobs, int m, int n); int sumCIT (MAT_INT seqxfab, VECTOR_INT jobs_facts, MAT_INT pt, int jobs, int machs, int facts); void DNEH (VECTOR_INT *seq, VECTOR_INT *jobs_facts, MAT_INT *seq_fabs, MAT_INT pt, int n, int m, int f); void DLR (VECTOR_INT *seq, VECTOR_INT *jobs_facts, MAT_INT *seq_fabs, MAT_INT pt, int n, int m, int f); void NEH_R1 (VECTOR_INT *seq, VECTOR_INT *jobs_facts, MAT_INT *seq_fabs, MAT_INT pt, int n, int m, int f,int A_i); void NEH_R2 (VECTOR_INT *seq, VECTOR_INT *jobs_facts,MAT_INT *seq_fabs, MAT_INT pt, int n, int m, int f,int A_i); int A_1 (MAT_INT seqxfabs, VECTOR_INT jobs_facts,int f, int n, int m, MAT_INT pt); int A_2 (MAT_INT seqxfabs, VECTOR_INT jobs_facts,int f, int n, int m, MAT_INT pt); int A_3(VECTOR_INT *fab_insertion, MAT_INT seqxfab, VECTOR_INT jobs_facts, int job_to_insert, int f, int n, int m, MAT_INT pt); int A_4(VECTOR_INT *fab_insertion, MAT_INT seqxfab, VECTOR_INT jobs_facts, int job_to_insert, int f, int n, int m, MAT_INT pt); int A_5(VECTOR_INT *fab_insertion, MAT_INT seqxfab, VECTOR_INT jobs_facts, int job_to_insert, int f_max, int f, int n, int m, MAT_INT pt); int A_6(VECTOR_INT *fab_insertion, MAT_INT seqxfab, VECTOR_INT jobs_facts, int job_to_insert, int f, int n, int m, MAT_INT pt); void DNEH_R1(VECTOR_INT *seq, VECTOR_INT *jobs_facts, MAT_INT *seq_fabs, MAT_INT pt, int n, int m, int f,int A_i); void DNEH_R2(VECTOR_INT *seq, VECTOR_INT *jobs_facts, MAT_INT *seq_fabs, MAT_INT pt, int n, int m, int f,int A_i); void insertion (VECTOR_INT seq, VECTOR_INT *nueva_seq, int pos, int job_to_insert, int n); VECTOR_INT matriz_a_vector(MAT_INT pi, int n, int f); int makespan (VECTOR_INT seq, int n, int m, MAT_INT pt); void copy_mat_int( MAT_INT original, MAT_INT destino, int filas, int cols); Anexo Código programación en C 38 free_matrix(pt,jobs); free_matrix(seq_fabs,facts); return 0; } //LECTURA DE ENTORNO DPFS MAT_INT loadDPFS (char *data, int *jobs, int *machs, int *facts) { int temp_data; register int i,j; MAT_INT pt; FILE *input; input=fopen(data,"rt"); //Abre el archivo con el nombre dado y lee if (input==NULL) { printf("No se ha abierto el fichero\n"); } //Lectura de número de trabajos, máquinas y fábricas fscanf(input,"%d\t",&temp_data); *jobs=temp_data; fscanf(input,"%d\n",&temp_data); *machs=temp_data; fscanf(input,"%d\n",&temp_data); *facts=temp_data; //printf("JOBS:%d\t MACHINES: %d\nFACTORIES: %d\n",*jobs,*machs,*facts); //Lectuta de tiempos de procesos pt=DIM_MAT_INT(*jobs,*machs); //Tamaño de la matriz for (j=0;j<*jobs;j++) { 39 39 Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time for (i=0;i<*machs;i++) { fscanf(input,"%d\t",&temp_data); pt[j][i]=temp_data; } } //print_matrix(pt,*jobs,*machs); printf("Fin lectura de datos\n"); fclose(input); return pt; } //RESULTADOS ENTORNO DPFS void outputDPFS ( char *inputfile, char *outputfile, int CPU, int jobs, int machs, int facts, VECTOR_INT seq, MAT_INT seq_fabs, double objetive) { FILE *output; register int j,k; output=fopen(outputfile,"at"); //Crea un archivo con el nombre dado en outputfile y escribe en él time_t timer; struct tm *tblock; timer = time(NULL); tblock = localtime(&timer); fprintf(output,"\n%s\t%s\n",inputfile,asctime(tblock)); fprintf(output,"CPU(segundos) = %d\n",CPU); //Escritura valor FO fprintf(output,"FO=%f\n", objetive); //Escritura secuencia fprintf(output,"%s=(","Secuencia"); for(j=0;j<jobs;j++) { fprintf(output,"\t%d",seq[j]); Anexo Código programación en C 40 } //Escritura secuencia por fabrica fprintf(output,")\n%s","Secuencia por fabrica "); for(k=0;k<facts;k++) { fprintf(output,"\n%s %d","Fabrica",k); for(j=0;j<jobs;j++) { fprintf(output,"\t%d",seq_fabs[k][j]); } } printf("Fin escritura de resultados\n"); fclose(output); } //CIT POR FÁBRICA int CIT (VECTOR_INT seq, MAT_INT pt, int jobs, int m, int n) { printf("Entra en funcion CIT\n"); float objetive=0; int register i,j; //máquina-i, trabajo-j MAT_INT S=DIM_MAT_INT(n,m); setval_matrix(S,n,m,-1); printf("Mat S\n"); print_matrix(S,n,m); MAT_INT ct=DIM_MAT_INT(n,m); // En una matriz se guardan los completion time de cada trabajo en cada máquina setval_matrix(ct,n,m,0); printf("Mat ct\n"); print_matrix(ct,n,m); if (seq[0]!=-1) { S[seq[0]][0]=0; for (j=1;j<jobs;j++) //En la primera máquina no hay CIT, un trabajo empieza cuando termina el anterior 41 41 Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time { S[seq[j]][0]+=S[seq[j-1]][0]+pt[seq[j-1]][0]; printf("S[%d][0]=%d\n",seq[j],S[seq[j]][0]); } for (i=1;i<m;i++) //El primer trabajo secuenciado pasa a la siguiente máquina cuando termina el anterior { S[seq[0]][i]=S[seq[0]][i-1]+pt[seq[0]][i-1]; printf("S[%d][%d]=%d\n",seq[0],i,S[seq[0]][i]); } for (i=1;i<m;i++) //A partir de la segunda máquina y el segundo trabajo se generan los CIT { for (j=1;j<jobs;j++) { printf("Bucle jobs=%d\n",j); if(S[seq[j]][i-1]+pt[seq[j]][i-1]<S[seq[j-1]][i]+pt[seq[j-1]][i]) { S[seq[j]][i]=S[seq[j-1]][i]+pt[seq[j-1]][i]; printf("El trabajo anterior en la maquina tarda mas que el mismo trabajo en la maquina anterior\n"); } else { S[seq[j]][i]=S[seq[j]][i-1]+pt[seq[j]][i-1]; printf("El trabajo en la maquina anterior tarda mas que el anterior en la maquina\n"); } } } printf("Matriz start time\n"); print_matrix(S,n,m); for(j=0;j<jobs;j++) //Completion time por trabajos { for (i=0;i<m;i++) { ct[seq[j]][i]=S[seq[j]][i]+pt[seq[j]][i]; } } Anexo Código programación en C 42 printf("Matriz completion time trabajos\n"); print_matrix(ct,n,m); for (i=1;i<m;i++) //Calculo CIT { for(j=1;j<jobs;j++) { if (S[seq[j]][i]>ct[seq[j-1]][i]) //Si la diferencia es positiva, entonces se va sumando { objetive+=S[seq[j]][i]-ct[seq[j-1]][i]; } } } } free_matrix(S,n); free_matrix(ct,n); printf("Calculo de CIT=%f\n",objetive); return objetive; } //FO SUM (CIT) int sumCIT (MAT_INT seqxfab, VECTOR_INT jobs_facts, MAT_INT pt, int jobs, int machs, int facts) { printf("Entra en funcion sumCIT\n"); float objetive=0; int register i,j,f; //máquina-i, trabajo-j, fábrica-f MAT_INT C=DIM_MAT_INT(facts,machs); // En un matriz se van a guardar los completion time de cada máquina en cada fábrica setval_matrix(C,facts,machs,0); MAT_INT S=DIM_MAT_INT(jobs,machs); setval_matrix(S,jobs,machs,0); 43 43 Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time MAT_INT ct=DIM_MAT_INT(jobs,machs); // En una matriz se guardan los completion time de cada trabajo en cada máquina setval_matrix(ct,jobs,machs,0); for(f=0;f<facts;f++) //Para cada fábrica { if (seqxfab[f][0]!=-1) { S[seqxfab[f][0]][0]=0; for (j=1;j<jobs_facts[f];j++) //En la primera máquina no hay CIT, un trabajo empieza cuando termina el anterior { S[seqxfab[f][j]][0]+=S[seqxfab[f][j-1]][0]+pt[seqxfab[f][j-1]][0]; } C[f][0]=S[seqxfab[f][j-1]][0]+pt[seqxfab[f][j-1]][0]; //Completion time de la máquina 0 for (i=1;i<machs;i++) //El primer trabajo secuenciado pasa a la siguiente máquina cuando termina el anterior { S[seqxfab[f][0]][i]=S[seqxfab[f][0]][i-1] + pt[seqxfab[f][0]][i-1]; } for (i=1;i<machs;i++) //A partir de la segunda máquina y el segundo trabajo se generan los CIT { for (j=1;j<jobs_facts[f];j++) { if(S[seqxfab[f][j]][i-1]+pt[seqxfab[f][j]][i-1]<S[seqxfab[f][j-1]][i]+pt[seqxfab[f][j-1]][i]) { S[seqxfab[f][j]][i]=S[seqxfab[f][j-1]][i]+pt[seqxfab[f][j-1]][i]; //El trabajo anterior en la máquina tarda más que el mismo trabajo en la máquina anterior } else { S[seqxfab[f][j]][i]=S[seqxfab[f][j]][i-1]+pt[seqxfab[f][j]][i-1]; //El trabajo en la máquina anterior tarda más que el anterior en la máquina } } C[f][i]=S[seqxfab[f][j-1]][i]+pt[seqxfab[f][j-1]][i]; //Completion time de la máquina i } } Anexo Código programación en C 44 printf("Matriz completion time maquinas\n"); print_matrix(C,facts,machs); printf("Matriz start time\n"); print_matrix(S,jobs,machs); } for(f=0;f<facts;f++) { for(j=0;j<jobs_facts[f];j++) //Completion time por trabajos { if(seqxfab[f][j]!=-1) { for (i=0;i<machs;i++) { ct[seqxfab[f][j]][i]=S[seqxfab[f][j]][i]+pt[seqxfab[f][j]][i]; } } } } printf("Matriz completion time trabajos\n"); print_matrix(ct,jobs,machs); for (i=1;i<machs;i++) //Calculo CIT { for(f=0;f<facts;f++) { for(j=1;j<jobs;j++) { if (seqxfab[f][j]!=-1 && seqxfab[f][j-1]!=-1 && S[seqxfab[f][j]][i]>ct[seqxfab[f][j-1]][i]) //Si la diferencia es positiva, entonces se va sumando { 45 45 Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time objetive+=S[seqxfab[f][j]][i]-ct[seqxfab[f][j-1]][i]; } } } } free_matrix(C, facts); free_matrix(S,jobs); free_matrix(ct, jobs); printf("Calculo de sumCIT=%f\n",objetive); return objetive; } void DNEH (VECTOR_INT *seq, VECTOR_INT *jobs_facts, MAT_INT *seq_fabs, MAT_INT pt, int n, int m, int f) { printf("\n******Calculo de la secuencia DNEH******\n"); VECTOR_FLOAT IF0= DIM_VECTOR_FLOAT(n); VECTOR_FLOAT IT0= DIM_VECTOR_FLOAT(n); VECTOR_FLOAT C= DIM_VECTOR_FLOAT(n); VECTOR_INT landa= DIM_VECTOR_INT(n); MAT_INT pi= DIM_MAT_INT(f,n); register int i,j,k; for (k=0;k<f;k++) { for(j=0;j<n;j++) { pi[k][j]=-1; IF0[j]=0; IT0[j]=0; C[j]=0; landa[j]=-1; Anexo Código programación en C 46 } } int dim=n; // para extraer los primeros f trabajos for (j=0;j<n;j++) { for (i=1;i<m;i++) { C[j]+=pt[j][i-1]; IT0[j]+=(m*(C[j]))/(i); } C[j]+=pt[j][m-1]; // Makespan printf("C[%d]=%f",j,C[j]); IF0[j]=((n/f)-2)*IT0[j]+ C[j]; printf("IF0[%d]=%f\n",j,IF0[j]); } printf("Vector IF0\t"); print_vector(IF0,n); sort_vector(IF0,landa,n,'A'); // Vector de trabajos landa ordenado de manera creciente printf("Vector landa\t"); print_vector(landa,n); for(j=0;j<f;j++) { pi[j][0]=landa[0]; // Asignar los primeros f trabajos, uno a cada fábrica extract_vector(landa,dim,0); //Extraer los trabajos asignados de landa dim--; } setval_vector(*jobs_facts,f,1); VECTOR_INT pi_k_vector = DIM_VECTOR_INT(n); VECTOR_INT best_pi_k_insertion = DIM_VECTOR_INT(n); VECTOR_INT pi_k_insertion = DIM_VECTOR_INT(n); VECTOR_INT seq_a_evaluar=DIM_VECTOR_INT(n); VECTOR_INT best_seq_a_evaluar=DIM_VECTOR_INT(n); VECTOR_INT jobs_facts_copia =DIM_VECTOR_INT(f); copy_vector(*jobs_facts,jobs_facts_copia,f); best_seq_a_evaluar=matriz_a_vector(pi,n,f); 47 47 Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time printf("Mat pi a vector\t"); print_vector(best_seq_a_evaluar,n); int fo, best_fo; best_fo = sumCIT(pi,jobs_facts_copia,pt,n,m,f); //Actualmente tengo f trabajos asignados printf("FO tras asignar los f primeros trabajos=%d\n",best_fo); int first_job, k_inserted; register int l; while (dim>0) //Mientras queden trabajos por insertar { first_job=landa[0]; //Suponemos que la mejor fo es el trabajo insertado en la primera posicion de la primera fábrica para ir comparando for(j=0;j<n;j++) // Copia de la fila de la matriz pi en un vector { pi_k_vector[j]=pi[0][j]; } insertion(pi_k_vector,&best_pi_k_insertion,0,first_job,n); for(l=0;l<n;l++) // Copia del vector insertado en la matriz pi { pi[0][l]=best_pi_k_insertion[l]; } printf("Matriz pi tras insertion en pos 0\n"); print_matrix(pi,f,n); best_seq_a_evaluar=matriz_a_vector(pi,n,f); printf("Mejor secuencia a evaluar\n"); print_vector(best_seq_a_evaluar,n); jobs_facts_copia[0]++; printf("Jobs_facts_copia\n"); print_vector(jobs_facts_copia,f); best_fo = sumCIT(pi,jobs_facts_copia,pt,n,m,f); k_inserted=0; printf("best_fo=%d",best_fo); jobs_facts_copia[0]--; for(j=0;j<n;j++) // Copia de la fila de la matriz pi en un vector { pi[0][j]=pi_k_vector[j]; Anexo Código programación en C 54 } printf("makespan=%d \t min_makespan=%d\n",makespan,min_makespan); printf("k_opt=%d\n",k_opt); } //BUSCA j ÓPTIMO PARA LA FÁBRICA k_opt for (j=0;j<dim;j++) { for(i=1;i<m;i++) { if (S[jobs_facts_copia[k_opt]][i]+pt[jobs_facts_copia[k_opt]][i]<S[landa[j]][i-1]+pt[landa[j]][i-1]) { max=S[landa[j]][i-1]+pt[landa[j]][i-1]-S[jobs_facts_copia[k_opt]][i]- pt[jobs_facts_copia[k_opt]][i]; printf("max en IT_nk[%d] es %d\n",landa[j],max); } IT_nk[landa[j]]+=(m*max)/(i+(jobs_facts_copia[k_opt])*(m-i)*((n_f)-2)); printf("IT_nk[%d]=%f\n",landa[j],IT_nk[landa[j]]); max=0; } IF_nk[landa[j]]=((n_f)-jobs_facts_copia[k_opt]-2)*IT_nk[landa[j]]+min_makespan; } printf("Vector IF_nk\n"); print_vector(IF_nk,n); min_IF_nk=IF_nk[landa[0]]; j_opt=landa[0]; pos=0; for (j=1;j<n;j++) // Comparar los IF_nk para obtener el trabajo j { if (IF_nk[landa[j]]<min_IF_nk && IF_nk[landa[j]]!=0 ) { min_IF_nk=IF_nk[landa[j]]; j_opt=landa[j]; } } printf("min_IF_nk=%f\t corresponde al trabajo %d\n",min_IF_nk, j_opt); setval_vector(IF_nk,n,0); 55 55 Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time //INSERTAR AL FINAL DE LA SECUENCIA DE k_opt EL TRBAJO j_opt pi[k_opt][jobs_facts_copia[k_opt]]=j_opt; jobs_facts_copia[k_opt]++; printf("Matriz tras insertar j_opt en k_opt\n"); print_matrix(pi, f, n); printf("Vector jobs_facts_copia\n"); print_vector(jobs_facts_copia,f); //EXTRAER EL TRABAJO j_opt DE LA SECUENCIA landa pos=search_vector(landa,dim,j_opt); printf("Vector landa antes de extraer %d en la pos del vector %d\n",j_opt,pos); print_vector(landa,aux); aux=extract_vector(landa,dim,pos); printf("Vector landa tras extraccion\n"); print_vector(landa,aux); dim--; printf("aux=%d\tdim=%d\n",aux,dim); } copy_vector(jobs_facts_copia,*jobs_facts,f); copy_mat_int(pi,*seq_fabs, f, n); *seq=matriz_a_vector(pi,n,f); free_vector(IF0); free_vector(IT0); free_vector(C); free_vector(landa); free_vector(pi_k_vector); free_vector(jobs_facts_copia); free_vector(IF_nk); free_vector(IT_nk); free_matrix(pi,f); free_matrix(S,n); free_matrix(CT,f); printf("Sale de función DLR\n"); Anexo Código programación en C 56 } void insertion (VECTOR_INT seq, VECTOR_INT *nueva_seq, int pos, int job_to_insert, int n) { copy_vector(seq,*nueva_seq,n); extract_vector(*nueva_seq,n,n-1); //Extrae el valor -1 de la ultima posicion de la secuencia insert_vector(*nueva_seq,n,job_to_insert, pos); printf("Sale de la función insertion\n"); } VECTOR_INT matriz_a_vector(MAT_INT pi, int n, int f) { VECTOR_INT secuencia=DIM_VECTOR_INT(n); int j,k; int pos=0; for(k=0;k<f;k++) { for(j=0;j<n;j++) { if(pi[k][j]!=-1) { secuencia[pos]=pi[k][j]; pos++; } } } printf("Sale de la funcion matriz-vector\n"); return secuencia; } void NEH_R1 (VECTOR_INT *seq, VECTOR_INT *jobs_facts, MAT_INT *seq_fabs, MAT_INT pt, int n, int m, int f,int A_i) 57 57 Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time { printf("\n******Calculo de la secuencia NEH,R1******\n"); VECTOR_INT sum_pt= DIM_VECTOR_INT(n); setval_vector(sum_pt,n,0); VECTOR_INT omega=DIM_VECTOR_INT(n); setval_vector(omega,n,-1); VECTOR_INT pi_wkl=DIM_VECTOR_INT(n); setval_vector(pi_wkl,n,-1); VECTOR_INT jobs_facts_copia=DIM_VECTOR_INT(f); setval_vector(jobs_facts_copia,f,0); MAT_INT seqxfab= DIM_MAT_INT(f,n); setval_matrix(seqxfab,f,n,-1); int new_dim, dim_pi; register int i,j,l,k; //TRABAJOS ORDENADOS POR SUMA DE pt for (j=0;j<n;j++) { for (i=0;i<m;i++) { sum_pt[j]+=pt[j][i]; } } printf("Sum_pt\n"); print_vector(sum_pt,n); sort_vector(sum_pt,omega,n,'D'); printf("Omega\n"); print_vector(omega,n); ASIGNA TRABAJO CON MAYOR pt A pi free_vector(sum_pt); *seq[0]=omega[0]; dim_pi=1; seqxfab[0][0]=omega[0]; //Primer trabajo en la primera posicion de la primera fábrica copy_mat_int(seqxfab,*seq_fabs,f,n); printf("Matriz secuencia por fabricas\n"); print_matrix(*seq_fabs,f,n); Anexo Código programación en C 58 new_dim=extract_vector(omega,n,0); //Extrae el trabajo de omega secuenciado en pi int aux=new_dim; printf("Secuencia omega tras insertar el primer trabajo en pi_WKL\n"); print_vector(omega,new_dim); int CIT_seq, min_CIT, CIT_f,max_CIT, f_max, f_asignada; VECTOR_INT best_pi_wkl=DIM_VECTOR_INT(n); setval_vector(best_pi_wkl,n,-1); VECTOR_INT seq_best_l=DIM_VECTOR_INT(n); setval_vector(seq_best_l,n,-1); VECTOR_INT secuencia=DIM_VECTOR_INT(n); setval_vector(secuencia,n,-1); while (new_dim>0) { if(A_i==1) { printf("Entra en A1\n"); insertion(*seq,&best_pi_wkl,0,omega[0],n); printf("Vector best_pi_wkl tras insertion\n"); print_vector(best_pi_wkl,n); dim_pi++; printf("dim_pi=%d\n",dim_pi); seqxfab[0][0]=best_pi_wkl[0]; jobs_facts_copia[0]=1; for (j=1;j<dim_pi;j++) { f_asignada=A_1(seqxfab,jobs_facts_copia,f,n,m,pt); printf("f_asignada=%d\n",f_asignada); seqxfab[f_asignada][jobs_facts_copia[f_asignada]]=best_pi_wkl[j]; jobs_facts_copia[f_asignada]++; } copy_mat_int(seqxfab,*seq_fabs,f,n); copy_vector(jobs_facts_copia,*jobs_facts,f); setval_matrix(seqxfab,f,n,-1); setval_vector(jobs_facts_copia,f,0); 59 59 Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time printf("Matriz seq_fab\n"); print_matrix(*seq_fabs,f,n); min_CIT=sumCIT(*seq_fabs,*jobs_facts,pt,n,m,f); for(l=1;l<dim_pi;l++) { insertion(*seq,&pi_wkl,l,omega[0],n); printf("Vector pi_wkl tras insertion\t"); print_vector(pi_wkl,n); seqxfab[0][0]=pi_wkl[0]; jobs_facts_copia[0]=1; for (j=1;j<dim_pi;j++) { f_asignada=A_1(seqxfab,jobs_facts_copia,f,n,m,pt); printf("f_asignada=%d\n",f_asignada); seqxfab[f_asignada][jobs_facts_copia[f_asignada]]=pi_wkl[j]; jobs_facts_copia[f_asignada]++; } printf("Matriz seqxfab\n"); print_matrix(seqxfab,f,n); CIT_seq=sumCIT(seqxfab,jobs_facts_copia,pt,n,m,f); if (CIT_seq<min_CIT) { min_CIT=CIT_seq; copy_vector(pi_wkl,best_pi_wkl,n); copy_vector(jobs_facts_copia,*jobs_facts,f); copy_mat_int(seqxfab,*seq_fabs,f,n); printf("Se ha actualizado el min CIT cuyo valor es %d\n",min_CIT); } setval_matrix(seqxfab,f,n,-1); setval_vector(jobs_facts_copia,f,0); } } else if(A_i==2) { printf("Entra en A2\n"); insertion(*seq,&best_pi_wkl,0,omega[0],n); Anexo Código programación en C 60 printf("Vector best_pi_wkl tras insertion\n"); print_vector(best_pi_wkl,n); dim_pi++; seqxfab[0][0]=best_pi_wkl[0]; jobs_facts_copia[0]=1; for (j=1;j<dim_pi;j++) { f_asignada=A_2(seqxfab,jobs_facts_copia,f,n,m,pt); printf("f_asignada=%d\n",f_asignada); seqxfab[f_asignada][jobs_facts_copia[f_asignada]]=best_pi_wkl[j]; jobs_facts_copia[f_asignada]++; } copy_mat_int(seqxfab,*seq_fabs,f,n); copy_vector(jobs_facts_copia,*jobs_facts,f); setval_matrix(seqxfab,f,n,-1); setval_vector(jobs_facts_copia,f,0); printf("Matriz seq_fab\n"); print_matrix(*seq_fabs,f,n); min_CIT=sumCIT(*seq_fabs,*jobs_facts,pt,n,m,f); for(l=1;l<dim_pi;l++) { insertion(*seq,&pi_wkl,l,omega[0],n); printf("Vector pi_wkl tras insertion\t"); print_vector(pi_wkl,n); seqxfab[0][0]=pi_wkl[0]; jobs_facts_copia[0]=1; for (j=1;j<dim_pi;j++) { f_asignada=A_2(seqxfab,jobs_facts_copia,f,n,m,pt); printf("f_asignada=%d\n",f_asignada); seqxfab[f_asignada][jobs_facts_copia[f_asignada]]=pi_wkl[j]; jobs_facts_copia[f_asignada]++; } printf("Matriz seqxfab\n"); print_matrix(seqxfab,f,n); CIT_seq=sumCIT(seqxfab,jobs_facts_copia,pt,n,m,f); 61 61 Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time if (CIT_seq<min_CIT) { min_CIT=CIT_seq; copy_vector(pi_wkl,best_pi_wkl,n); copy_vector(jobs_facts_copia,*jobs_facts,f); copy_mat_int(seqxfab,*seq_fabs,f,n); printf("Se ha actualizado el min CIT cuyo valor es %d\n",min_CIT); } setval_matrix(seqxfab,f,n,-1); setval_vector(jobs_facts_copia,f,0); } } else if(A_i==3) { printf("Entra en A3\n"); insertion(*seq,&best_pi_wkl,0,omega[0],n); printf("Vector best_pi_wkl tras insertion\n"); print_vector(best_pi_wkl,n); dim_pi++; //2 seqxfab[0][0]=best_pi_wkl[0]; jobs_facts_copia[0]=1; for (j=1;j<dim_pi;j++) { f_asignada=A_3(&seq_best_l,seqxfab,jobs_facts_copia,best_pi_wkl[j],f,n,m,pt); printf("f_asignada=%d\n",f_asignada); print_vector(seq_best_l,n); pasterowImatrix(seqxfab,seq_best_l,f_asignada,n); jobs_facts_copia[f_asignada]++; printf("Matriz seqxfab\n"); print_matrix(seqxfab,f,n); } copy_mat_int(seqxfab,*seq_fabs,f,n); copy_vector(jobs_facts_copia,*jobs_facts,f); setval_matrix(seqxfab,f,n,-1); setval_vector(jobs_facts_copia,f,0); printf("Matriz seq_fab\n"); Anexo Código programación en C 62 print_matrix(*seq_fabs,f,n); min_CIT=sumCIT(*seq_fabs,*jobs_facts,pt,n,m,f); for(l=1;l<dim_pi;l++) { insertion(*seq,&pi_wkl,l,omega[0],n); printf("Vector pi_wkl tras insertion\t"); print_vector(pi_wkl,n); seqxfab[0][0]=pi_wkl[0]; jobs_facts_copia[0]=1; for (j=1;j<dim_pi;j++) { f_asignada=A_3(&seq_best_l,seqxfab,jobs_facts_copia,pi_wkl[j],f,n,m,pt); printf("f_asignada=%d\n",f_asignada); print_vector(seq_best_l,n); pasterowImatrix(seqxfab,seq_best_l,f_asignada,n); jobs_facts_copia[f_asignada]++; } printf("Matriz seqxfab\n"); print_matrix(seqxfab,f,n); CIT_seq=sumCIT(seqxfab,jobs_facts_copia,pt,n,m,f); if (CIT_seq<min_CIT) { min_CIT=CIT_seq; copy_vector(pi_wkl,best_pi_wkl,n); copy_vector(jobs_facts_copia,*jobs_facts,f); copy_mat_int(seqxfab,*seq_fabs,f,n); printf("Se ha actualizado el min CIT cuyo valor es %d\n",min_CIT); } setval_matrix(seqxfab,f,n,-1); setval_vector(jobs_facts_copia,f,0); } } else if (A_i==4) { printf("Entra en A4\n"); 63 63 Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time insertion(*seq,&best_pi_wkl,0,omega[0],n); printf("Vector best_pi_wkl tras insertion\n"); print_vector(best_pi_wkl,n); dim_pi++; seqxfab[0][0]=best_pi_wkl[0]; jobs_facts_copia[0]=1; for (j=1;j<dim_pi;j++) { f_asignada=A_4(&seq_best_l,seqxfab,jobs_facts_copia,best_pi_wkl[j],f,n,m,pt); printf("f_asignada=%d\n",f_asignada); print_vector(seq_best_l,n); pasterowImatrix(seqxfab,seq_best_l,f_asignada,n); jobs_facts_copia[f_asignada]++; printf("Matriz seqxfab\n"); print_matrix(seqxfab,f,n); } copy_mat_int(seqxfab,*seq_fabs,f,n); copy_vector(jobs_facts_copia,*jobs_facts,f); setval_matrix(seqxfab,f,n,-1); setval_vector(jobs_facts_copia,f,0); printf("Matriz seq_fab\n"); print_matrix(*seq_fabs,f,n); min_CIT=sumCIT(*seq_fabs,*jobs_facts,pt,n,m,f); for(l=1;l<dim_pi;l++) { insertion(*seq,&pi_wkl,l,omega[0],n); printf("Vector pi_wkl tras insertion\t"); print_vector(pi_wkl,n); seqxfab[0][0]=pi_wkl[0]; jobs_facts_copia[0]=1; for (j=1;j<dim_pi;j++) { f_asignada=A_4(&seq_best_l,seqxfab,jobs_facts_copia,pi_wkl[j],f,n,m,pt); printf("f_asignada=%d\n",f_asignada); print_vector(seq_best_l,n); pasterowImatrix(seqxfab,seq_best_l,f_asignada,n); jobs_facts_copia[f_asignada]++; Anexo Código programación en C 70 copy_vector(pi,*seq,n); seqxfab[0][0]=omega[0]; //Primer trabajo en la primera posicion de la primera fábrica copy_mat_int(seqxfab,*seq_fabs,f,n); printf("Matriz secuencia por fabricas\n"); print_matrix(seqxfab,f,n); jobs_facts_copia[0]++; new_dim=extract_vector(omega,n,0); //Extrae el trabajo de omega secuenciado en pi int aux=new_dim; printf("Secuencia omega tras insertar el primer trabajo en pi_WKL\n"); print_vector(omega,new_dim); int max_CIT, CIT_f, f_max; VECTOR_INT seq_best_l =DIM_VECTOR_INT(n); setval_vector(seq_best_l,n,-1); VECTOR_INT secuencia =DIM_VECTOR_INT(n); setval_vector(secuencia,n,-1); while (new_dim>0) { if (A_i==1) { printf("Entra en A1\n"); f_asignada=A_1(seqxfab,jobs_facts_copia,f,n,m,pt); printf("f_asignada=%d\n",f_asignada); seqxfab[f_asignada][jobs_facts_copia[f_asignada]]=omega[0]; jobs_facts_copia[f_asignada]++; pi=matriz_a_vector(seqxfab,n,f); } else if (A_i==2) { printf("Entra en A2\n"); f_asignada=A_2(seqxfab,jobs_facts_copia,f,n,m,pt); printf("f_asignada=%d\n",f_asignada); seqxfab[f_asignada][jobs_facts_copia[f_asignada]]=omega[0]; jobs_facts_copia[f_asignada]++; pi=matriz_a_vector(seqxfab,n,f); } 71 71 Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time else if (A_i==3) { printf("Entra en A3\n"); f_asignada=A_3(&seq_best_l,seqxfab,jobs_facts_copia,omega[0],f,n,m,pt); printf("f_asignada=%d, la seq de esta fab es\t",f_asignada); print_vector(seq_best_l,n); pasterowImatrix(seqxfab,seq_best_l,f_asignada,n); jobs_facts_copia[f_asignada]++; pi=matriz_a_vector(seqxfab,n,f); } else if (A_i==4) { printf("Entra en A4\n"); f_asignada=A_4(&seq_best_l,seqxfab,jobs_facts_copia,omega[0],f,n,m,pt); printf("f_asignada=%d, la seq de esta fab es\t",f_asignada); print_vector(seq_best_l,n); pasterowImatrix(seqxfab,seq_best_l,f_asignada,n); jobs_facts_copia[f_asignada]++; pi=matriz_a_vector(seqxfab,n,f); } else if (A_i==5) { printf("Entra en A5\n"); f_max=0; copyrowImatrix(seqxfab,secuencia,0,n); max_CIT=CIT(secuencia,pt,jobs_facts_copia[0],m,n); for (k=1;k<f;k++) { copyrowImatrix(seqxfab,secuencia,k,n); CIT_f=CIT(secuencia,pt,jobs_facts_copia[k],m,n); if(max_CIT<CIT_f) { max_CIT=CIT_f; f_max=k; } } Anexo Código programación en C 72 printf("fmax=%d\n",f_max); f_asignada=A_5(&seq_best_l,seqxfab,jobs_facts_copia,omega[0],f_max,f,n,m,pt); printf("f_asignada=%d, la seq de esta fab es\t",f_asignada); print_vector(seq_best_l,n); pasterowImatrix(seqxfab,seq_best_l,f_asignada,n); jobs_facts_copia[f_asignada]++; pi=matriz_a_vector(seqxfab,n,f); } else if (A_i==6) { printf("Entra en A6\n"); f_asignada=A_6(&seq_best_l,seqxfab,jobs_facts_copia,omega[0],f,n,m,pt); printf("f_asignada=%d, la seq de esta fab es\t",f_asignada); print_vector(seq_best_l,n); pasterowImatrix(seqxfab,seq_best_l,f_asignada,n); jobs_facts_copia[f_asignada]++; pi=matriz_a_vector(seqxfab,n,f); } //Tras insertar el trabajo en todas las posiciones de posibles de pi_wkl y saber cual es la fabrica que se asigna, se conoce la que genera menor CIT new_dim=extract_vector(omega,aux,0); aux=new_dim; printf("new_dim=aux, %d=%d\n",new_dim,aux); printf("Vector omega tras extraer ultimo trabajo secuenciado\t"); print_vector(omega,new_dim); printf("Secuencia pi\n"); print_vector(pi,n); copy_vector(pi,*seq,n); copy_vector(jobs_facts_copia,*jobs_facts,f); copy_mat_int(seqxfab,*seq_fabs, f, n); } free_vector(omega); free_vector(pi); free_vector(jobs_facts_copia); 73 73 Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time free_vector(seq_best_l); free_vector(secuencia); free_matrix(seqxfab,f); } int A_1 (MAT_INT seqxfabs, VECTOR_INT jobs_facts,int f, int n, int m, MAT_INT pt) { int min_C_max, C_max,best_f; register int k,j; VECTOR_INT copia_fila_seqxfabs=DIM_VECTOR_INT(n); for (j=0;j<n;j++) { copia_fila_seqxfabs[j]=seqxfabs[0][j]; } printf("Copia fila fab 0\n"); print_vector(copia_fila_seqxfabs,n); min_C_max=makespan(copia_fila_seqxfabs,n,m,pt); printf("min makespan=%d\n",min_C_max); best_f=0; for (k=1;k<f;k++) { for (j=0;j<n;j++) { copia_fila_seqxfabs[j]=seqxfabs[k][j]; } printf("Copia fila %d \n",k); print_vector(copia_fila_seqxfabs,n); C_max=makespan(copia_fila_seqxfabs,n,m,pt); printf("makespan=%d\n",C_max); if(C_max<min_C_max) { min_C_max=C_max; best_f=k; printf("Min makespan se ha actualizado(=%d), corresponde a la fabrica %d\n",min_C_max,k); } } Anexo Código programación en C 74 free_vector(copia_fila_seqxfabs); printf("Sale de funcion A_1\n"); return best_f; } int A_2 (MAT_INT seqxfabs, VECTOR_INT jobs_facts,int f, int n, int m, MAT_INT pt) { printf("Entra en función A_2\n"); VECTOR_INT copia_fila_seqxfabs=DIM_VECTOR_INT(n); int CIT_k, min_CIT, best_f; register int i,k; for (i=0;i<n;i++) { copia_fila_seqxfabs[i]=seqxfabs[0][i]; } printf("Copia fila fab 0\n"); print_vector(copia_fila_seqxfabs,n); min_CIT=CIT(copia_fila_seqxfabs,pt,jobs_facts[0],m,n); best_f=0; printf("El min_CIT se supone para la fab %d, igual a %d\n",best_f,min_CIT); for (k=1;k<f;k++) { for (i=0;i<n;i++) { copia_fila_seqxfabs[i]=seqxfabs[k][i]; } printf("Copia fila fab %d\n",k); print_vector(copia_fila_seqxfabs,n); CIT_k=CIT(copia_fila_seqxfabs,pt,jobs_facts[k],m,n); printf("CIT(k=%d)=%d\n",k,CIT_k); if(CIT_k<min_CIT) { min_CIT=CIT_k; best_f=k; 75 75 Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time printf("La mejor fab es %d, cuyo CIT es %d\n", k, min_CIT); } } free_vector(copia_fila_seqxfabs); printf("Sale de funcion A_2\n"); return best_f; } int A_3(VECTOR_INT *fab_insertion, MAT_INT seqxfab, VECTOR_INT jobs_facts, int job_to_insert, int f, int n, int m, MAT_INT pt) { printf("Entra en funcion A_3\n"); VECTOR_INT copia_fila_fab= DIM_VECTOR_INT(n); VECTOR_INT dif_CIT = DIM_VECTOR_INT(f); setval_vector(dif_CIT,f,-1); VECTOR_INT pos_f = DIM_VECTOR_INT(f); setval_vector(pos_f,f,-1); register int j,k; int best_f=-1, best_pos, min_dif, min_CIT_f, CIT_f,CIT_ini; for(k=0;k<f;k++) { for (j=0;j<n;j++) { copia_fila_fab[j]=seqxfab[k][j]; } printf("Copia seq fab %d, jobs_facts=%d\n", k, jobs_facts[k]); print_vector(copia_fila_fab,n); CIT_ini=CIT(copia_fila_fab, pt, jobs_facts[k],m,n); printf("min CIT de la fabrica %d se da antes de insertar el trabajo = %d\n", k, min_CIT_f); Anexo Código programación en C 76 if(jobs_facts[k]<n) { pos_f[k]=0; insertion(copia_fila_fab,&(*fab_insertion),0,job_to_insert,n); printf("Seq fab %d tras insertion en 0\n",k); print_vector(*fab_insertion,n); jobs_facts[k]++; printf("jobs_facts[%d]=%d tras insertion\n",k, jobs_facts[k]); min_CIT_f=CIT(*fab_insertion, pt, jobs_facts[k],m,n); printf("El CIT de esta seq es =%d\n", CIT_f); print_vector(*fab_insertion,n); jobs_facts[k]--; for(j=1;j<=jobs_facts[k];j++) { insertion(copia_fila_fab,&(*fab_insertion),j,job_to_insert,n); printf("Seq fab %d tras insertion\n",k); print_vector(*fab_insertion,n); jobs_facts[k]++; printf("jobs_facts[%d]=%d tras insertion\n",k, jobs_facts[k]); CIT_f=CIT(*fab_insertion, pt, jobs_facts[k],m,n); printf("El CIT de esta seq es =%d\n", CIT_f); print_vector(*fab_insertion,n); jobs_facts[k]--; if (CIT_f<=min_CIT_f) { min_CIT_f=CIT_f; pos_f[k]=j; printf("Min CIT se ha actualizado, es %d y la mejor pos es %d",min_CIT_f,pos_f[k]); } } dif_CIT[k]=CIT_ini-min_CIT_f; } } printf("Vector dif_CIT\t"); print_vector(dif_CIT,f); printf("\nVector pos_f\t"); 77 77 Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time print_vector(pos_f,f); for(k=0;k<f;k++) { if(best_f==-1 && pos_f[k]!=-1 ) { best_f=k; best_pos=pos_f[k]; min_dif=dif_CIT[k]; k=f; //Para salir del bucle cuando entre por primera vez en if printf("Se inicializa con la mejor pos de fab %d, best_pos=%d\n", best_f, best_pos); } } for(k=best_f;k<f;k++) { if(dif_CIT[k]<min_dif && pos_f[k]!=-1) { min_dif=dif_CIT[k]; best_f=k; best_pos=pos_f[k]; printf("Se ha actualizado min_dif=%d y best_f=%d, best_pos=%d\n", min_dif, best_f,best_pos); } } for (j=0;j<n;j++) { copia_fila_fab[j]=seqxfab[best_f][j]; } insertion(copia_fila_fab,&(*fab_insertion),best_pos,job_to_insert,n); printf("Vector fab_insertion en funcion\t"); print_vector(*fab_insertion,n); free_vector(copia_fila_fab); free_vector(dif_CIT); free_vector(pos_f); Anexo Código programación en C 78 printf("Sale de funcion A_3\n"); return best_f; } int A_4(VECTOR_INT *fab_insertion, MAT_INT seqxfab, VECTOR_INT jobs_facts, int job_to_insert, int f, int n, int m, MAT_INT pt) { printf("Entra en funcion A_4\n"); VECTOR_INT copia_fila_fab= DIM_VECTOR_INT(n); VECTOR_INT dif_CIT_sum = DIM_VECTOR_INT(f); setval_vector(dif_CIT_sum,f,-1); VECTOR_INT pos_f = DIM_VECTOR_INT(f); setval_vector(pos_f,f,-1); MAT_INT copia_seqxfab=DIM_MAT_INT(f,n); register int j,k; int best_f=-1, best_pos, max_dif=-1, min_CIT_sum, CIT_sum,CIT_sum_ini; *fab_insertion=matriz_a_vector(seqxfab,n,f); printf("fab_insertion\n"); print_vector(*fab_insertion,n); CIT_sum_ini=sumCIT(seqxfab,jobs_facts,pt,n,m,f); printf("min sumCIT de la fabrica se da antes de insertar el trabajo = %d\n", CIT_sum_ini); for(k=0;k<f;k++) { for (j=0;j<n;j++) { copia_fila_fab[j]=seqxfab[k][j]; } printf("Copia seq fab %d, jobs_facts=%d\n", k, jobs_facts[k]); print_vector(copia_fila_fab,n); if(jobs_facts[k]<n) { 79 79 Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time pos_f[k]=0; copy_mat_int(seqxfab,copia_seqxfab,f,n); insertion(copia_fila_fab,&(*fab_insertion),0,job_to_insert,n); printf("Seq fab %d tras insertion\n",k); print_vector(*fab_insertion,n); jobs_facts[k]++; pasterowImatrix(copia_seqxfab,*fab_insertion,k,n); min_CIT_sum=sumCIT(copia_seqxfab, jobs_facts, pt,n,m,f); printf("sumCIT de la seq anterior es =%d\n", CIT_sum); jobs_facts[k]--; for(j=1;j<=jobs_facts[k];j++) { copy_mat_int(seqxfab,copia_seqxfab,f,n); insertion(copia_fila_fab,&(*fab_insertion),j,job_to_insert,n); printf("Seq fab %d tras insertion\n",k); print_vector(*fab_insertion,n); jobs_facts[k]++; pasterowImatrix(copia_seqxfab,*fab_insertion,k,n); CIT_sum=sumCIT(copia_seqxfab, jobs_facts, pt,n,m,f); printf("sumCIT de la seq anterior es =%d\n", CIT_sum); jobs_facts[k]--; printf("jobs_facts[%d]=%d\n",k, jobs_facts[k]); if (CIT_sum<=min_CIT_sum) { min_CIT_sum=CIT_sum; pos_f[k]=j; dif_CIT_sum[k]=CIT_sum_ini-min_CIT_sum; printf("Min CIT se ha actualizado, es %d y la mejor pos es %d para la fab %d\n dif_CIT_sum[%d]=%d\n", min_CIT_sum, pos_f[k],k,k,dif_CIT_sum[k]); } } } dif_CIT_sum[k]=CIT_sum_ini-min_CIT_sum; } printf("Vector dif_CIT\t"); print_vector(dif_CIT_sum,f); Anexo Código programación en C 86 pasterowImatrix(copia_seqxfab,*fab_insertion,fact,n); min_CIT_sum=sumCIT(copia_seqxfab, jobs_facts, pt,n,m,f); printf("min_CIT_sum=%d\n", min_CIT_sum); jobs_facts[fact]--; dif_CIT_sum[fact]=CIT_sum_ini-min_CIT_sum; for(j=1;j<=jobs_facts[fact];j++) { insertion(copia_fila_fab,&(*fab_insertion),j,job_to_insert,n); printf("Seq fab %d tras insertion\n",fact); print_vector(*fab_insertion,n); jobs_facts[fact]++; pasterowImatrix(copia_seqxfab,*fab_insertion,fact,n); CIT_sum=sumCIT(copia_seqxfab, jobs_facts,pt,n,m,f); printf("sumCIT de esta seq es =%d\n", CIT_sum); jobs_facts[fact]--; if (CIT_sum<=min_CIT_sum) { min_CIT_sum=CIT_sum; pos_f[fact]=j; dif_CIT_sum[fact]=CIT_sum_ini-min_CIT_sum; printf("Min CIT se ha actualizado, es %d y la mejor pos es %d para la fab %d\n dif_CIT_sum[%d]=%d\n", min_CIT_sum, pos_f[k],k,k,dif_CIT_sum[k]); } } } } printf("Vector dif_CIT\t"); print_vector(dif_CIT_sum,f); printf("\nVector pos_f\t"); print_vector(pos_f,f); for(k=0;k<f;k++) { if(best_f==-1 && pos_f[k]!=-1) { best_f=k; best_pos=pos_f[k]; max_dif=dif_CIT_sum[k]; 87 87 Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time k=f; //Para salir del bucle cuando entre por primera vez en if printf("Se inicializa con best_pos=%d\n", best_pos); } } for(k=best_f;k<f;k++) { if(dif_CIT_sum[k]>=max_dif && pos_f[k]!=-1 ) { max_dif=dif_CIT_sum[k]; best_f=k; best_pos=pos_f[k]; printf("Se ha actualizado max_dif=%d y best_f=%d, best_pos=%d\n", max_dif, best_f,best_pos); } } for (j=0;j<n;j++) { copia_fila_fab[j]=seqxfab[best_f][j]; } insertion(copia_fila_fab,&(*fab_insertion),best_pos,job_to_insert,n); free_vector(copia_fila_fab); free_vector(dif_CIT_sum); free_vector(pos_f); free_vector(vector_CIT); free_vector(F_2); free_matrix(copia_seqxfab,f); printf("Sale de la funcion A_6\n"); return best_f; } int makespan (VECTOR_INT seq, int n, int m, MAT_INT pt) Anexo Código programación en C 88 { printf("Entra en funcion makespan\n"); VECTOR_INT C =DIM_VECTOR_INT(n); setval_vector(C,n,0); MAT_INT S =DIM_MAT_INT(n,m); setval_matrix(S,n,m,-1); int makespan=0, ult_trabajo_seq; register int i,j,l; if (seq[0]!=-1) { ult_trabajo_seq=seq[0]; for (l=0;l<n;l++) { printf("Entra en bucle for (l=%d)\t seq[%d]=%d\n",l,l,seq[l]); if(seq[l]!=-1) { ult_trabajo_seq=seq[l]; S[seq[0]][0]=0; //El primer trabajo secuenciado no espera C[seq[0]]=pt[seq[0]][0]; for (i=1;i<m;i++) //El primer trabajo pasa de una maquina a otra cuando ha sido finalizada { S[seq[0]][i]=C[seq[0]]; C[seq[0]]+=pt[seq[0]][i]; printf("S[%d][%d]=%d\tC[%d]=%d\n",seq[0],i,S[seq[0]][i],seq[0],C[seq[0]]); } for (j=1;j<n;j++) //En la primera maquina un trabajo se secuencia detrás de otro sin esperas { //printf("Bucle for primera maq: j=%d\n",j); if(seq[j]!=-1) { printf("Entra en if, seq[%d]=%d\n",j, seq[j]); S[seq[j]][0]=S[seq[j-1]][0]+pt[seq[j-1]][0]; } } 89 89 Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time for (i=1;i<m;i++) { for (j=1;j<n;j++) { if(seq[j]!=-1) { ult_trabajo_seq=seq[j]; if(S[seq[j]][i-1]+pt[seq[j]][i-1]<S[seq[j-1]][i]+pt[seq[j-1]][i] ) { printf("\nEntra en if, seq[%d]=%d",j, seq[j]); S[seq[j]][i]=S[seq[j-1]][i]+pt[seq[j-1]][i]; //El trabajo anterior en la máquina tarda más que el mismo trabajo en la máquina anterior } else { printf("\nEntra en if, seq[%d]=%d",j, seq[j]); S[seq[j]][i]=S[seq[j]][i-1]+pt[seq[j]][i-1]; //El trabajo en la máquina anterior tarda más que el anterior en la máquina } C[seq[j]]=S[seq[j]][i]+pt[seq[j]][i]; } } } } print_vector(C,n); } printf("Matriz S y Vector C\n"); print_matrix(S,n,m); print_vector(C,n); makespan=C[ult_trabajo_seq];//El makespan es el completion time del ultimo trabajo secuencia en la ultima maquina printf("Valor del makespan=%d\n",makespan); } Anexo Código programación en C 90 free_vector(C); free_matrix(S,n); printf("Sale de funcion makespan\n"); return makespan; } void copy_mat_int( MAT_INT original, MAT_INT destino, int filas, int cols) { register int i,j; for (i=0;i<filas;i++) { for(j=0;j<cols;j++) { destino[i][j]=original[i][j]; } } printf("Sale función copy_may_int\n"); } void DNEH_R1(VECTOR_INT *seq, VECTOR_INT *jobs_facts, MAT_INT *seq_fabs, MAT_INT pt, int n, int m, int f,int A_i) { printf("\n******Calculo de la secuencia DNEH_R1******\n"); VECTOR_FLOAT IF0= DIM_VECTOR_FLOAT(n); VECTOR_FLOAT IT0= DIM_VECTOR_FLOAT(n); VECTOR_FLOAT C= DIM_VECTOR_FLOAT(n); VECTOR_INT landa= DIM_VECTOR_INT(n); VECTOR_INT jobs_facts_copia=DIM_VECTOR_INT(f); setval_vector(jobs_facts_copia,f,0); VECTOR_INT pi_wkl=DIM_VECTOR_INT(n); setval_vector(pi_wkl,n,-1); MAT_INT seqxfab=DIM_MAT_INT(f,n); setval_matrix(seqxfab,f,n,-1); 91 91 Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time int f_asignada=-1; register int i,j,k,l; for (k=0;k<f;k++) { for(j=0;j<n;j++) { IF0[j]=0; IT0[j]=0; C[j]=0; landa[j]=-1; } } int new_dim=n, dim_pi; // para extraer los primeros f trabajos printf("Matriz pi\n"); print_matrix(pi,f,n); for (j=0;j<n;j++) { for (i=1;i<m;i++) { C[j]+=pt[j][i-1]; IT0[j]+=(m*(C[j]))/(i); } C[j]+=pt[j][m-1]; // Makespan IF0[j]=((n/f)-2)*IT0[j]+ C[j]; } printf("Vector IF0\t"); print_vector(IF0,n); sort_vector(IF0,landa,n,'A'); // Vector de trabajos landa ordenado de manera creciente printf("Vector landa\t"); print_vector(landa,n); *seq[0]=landa[0]; dim_pi=1; seqxfab[0][0]=landa[0]; //Primer trabajo en la primera posicion de la primera fábrica copy_mat_int(seqxfab,*seq_fabs,f,n); printf("Matriz secuencia por fabricas\n"); print_matrix(seqxfab,f,n); Anexo Código programación en C 92 new_dim=extract_vector(landa,n,0);//Extrae el trabajo de landa secuenciado en pi int aux=new_dim; printf("Secuencia landa tras insertar el primer trabajo en pi_wkl\n"); print_vector(landa,new_dim); int CIT_seq, min_CIT, CIT_f, max_CIT, f_max; VECTOR_INT best_pi_wkl=DIM_VECTOR_INT(n); setval_vector(best_pi_wkl,n,-1); VECTOR_INT seq_best_l=DIM_VECTOR_INT(n); setval_vector(seq_best_l,n,-1); VECTOR_INT secuencia=DIM_VECTOR_INT(n); setval_vector(secuencia,n,-1); while (new_dim>0) { if(A_i==1) { printf("Entra en A1\n"); insertion(*seq,&best_pi_wkl,0,landa[0],n); printf("Vector best_pi_wkl tras insertion\n"); print_vector(best_pi_wkl,n); dim_pi++; seqxfab[0][0]=best_pi_wkl[0]; jobs_facts_copia[0]=1; for (j=1;j<dim_pi;j++) { f_asignada=A_1(seqxfab,jobs_facts_copia,f,n,m,pt); printf("f_asignada=%d\n",f_asignada); seqxfab[f_asignada][jobs_facts_copia[f_asignada]]=best_pi_wkl[j]; jobs_facts_copia[f_asignada]++; } copy_mat_int(seqxfab,*seq_fabs,f,n); copy_vector(jobs_facts_copia,*jobs_facts,f); setval_matrix(seqxfab,f,n,-1); setval_vector(jobs_facts_copia,f,0); printf("Matriz seq_fab\n"); 93 93 Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time print_matrix(*seq_fabs,f,n); min_CIT=sumCIT(*seq_fabs,*jobs_facts,pt,n,m,f); for(l=1;l<dim_pi;l++) { insertion(*seq,&pi_wkl,l,landa[0],n); printf("Vector pi_wkl tras insertion\t"); print_vector(pi_wkl,n); seqxfab[0][0]=pi_wkl[0]; jobs_facts_copia[0]=1; for (j=1;j<dim_pi;j++) { f_asignada=A_1(seqxfab,jobs_facts_copia,f,n,m,pt); printf("f_asignada=%d\n",f_asignada); seqxfab[f_asignada][jobs_facts_copia[f_asignada]]=pi_wkl[j]; jobs_facts_copia[f_asignada]++; } printf("Matriz seqxfab\n"); print_matrix(seqxfab,f,n); CIT_seq=sumCIT(seqxfab,jobs_facts_copia,pt,n,m,f); if (CIT_seq<min_CIT) { min_CIT=CIT_seq; copy_vector(pi_wkl,best_pi_wkl,n); copy_vector(jobs_facts_copia,*jobs_facts,f); copy_mat_int(seqxfab,*seq_fabs,f,n); printf("Se ha actualizado el min CIT cuyo valor es %d\n",min_CIT); } setval_matrix(seqxfab,f,n,-1); setval_vector(jobs_facts_copia,f,0); } } else if(A_i==2) { printf("Entra en A2\n"); Anexo Código programación en C 94 insertion(*seq,&best_pi_wkl,0,landa[0],n); printf("Vector best_pi_wkl tras insertion\n"); print_vector(best_pi_wkl,n); dim_pi++; seqxfab[0][0]=best_pi_wkl[0]; jobs_facts_copia[0]=1; for (j=1;j<dim_pi;j++) { f_asignada=A_2(seqxfab,jobs_facts_copia,f,n,m,pt); printf("f_asignada=%d\n",f_asignada); seqxfab[f_asignada][jobs_facts_copia[f_asignada]]=best_pi_wkl[j]; jobs_facts_copia[f_asignada]++; } copy_mat_int(seqxfab,*seq_fabs,f,n); copy_vector(jobs_facts_copia,*jobs_facts,f); setval_matrix(seqxfab,f,n,-1); setval_vector(jobs_facts_copia,f,0); printf("Matriz seq_fab\n"); print_matrix(*seq_fabs,f,n); min_CIT=sumCIT(*seq_fabs,*jobs_facts,pt,n,m,f); for(l=1;l<dim_pi;l++) { insertion(*seq,&pi_wkl,l,landa[0],n); printf("Vector pi_wkl tras insertion\t"); print_vector(pi_wkl,n); seqxfab[0][0]=pi_wkl[0]; jobs_facts_copia[0]=1; for (j=1;j<dim_pi;j++) { f_asignada=A_2(seqxfab,jobs_facts_copia,f,n,m,pt); printf("f_asignada=%d\n",f_asignada); seqxfab[f_asignada][jobs_facts_copia[f_asignada]]=pi_wkl[j]; jobs_facts_copia[f_asignada]++; } printf("Matriz seqxfab\n"); print_matrix(seqxfab,f,n); 95 95 Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time CIT_seq=sumCIT(seqxfab,jobs_facts_copia,pt,n,m,f); if (CIT_seq<min_CIT) { min_CIT=CIT_seq; copy_vector(pi_wkl,best_pi_wkl,n); copy_vector(jobs_facts_copia,*jobs_facts,f); copy_mat_int(seqxfab,*seq_fabs,f,n); printf("Se ha actualizado el min CIT cuyo valor es %d\n",min_CIT); } setval_matrix(seqxfab,f,n,-1); setval_vector(jobs_facts_copia,f,0); } } else if(A_i==3) { printf("Entra en A3\n"); insertion(*seq,&best_pi_wkl,0,landa[0],n); printf("Vector best_pi_wkl tras insertion\n"); print_vector(best_pi_wkl,n); dim_pi++; seqxfab[0][0]=best_pi_wkl[0]; jobs_facts_copia[0]=1; for (j=1;j<dim_pi;j++) { f_asignada=A_3(&seq_best_l,seqxfab,jobs_facts_copia,best_pi_wkl[j],f,n,m,pt); printf("f_asignada=%d\n",f_asignada); pasterowImatrix(seqxfab,seq_best_l,f_asignada,n); jobs_facts_copia[f_asignada]++; printf("Matriz seqxfab\n"); print_matrix(seqxfab,f,n); } copy_mat_int(seqxfab,*seq_fabs,f,n); copy_vector(jobs_facts_copia,*jobs_facts,f); setval_matrix(seqxfab,f,n,-1); setval_vector(jobs_facts_copia,f,0); Anexo Código programación en C 102 //Tras insertar el trabajo en todas las posiciones de posibles de pi_wkl y saber cual es la fabrica que se asigna, se conoce la que genera menor CIT new_dim=extract_vector(landa,aux,0); aux=new_dim; printf("Vector omega tras extraer ultimo trabajo secuenciado\t"); print_vector(omega,new_dim); printf("Secuencia pi_wkl\n"); print_vector(best_pi_wkl,n); copy_vector(best_pi_wkl,*seq,n); } free_vector(IF0); free_vector(IT0); free_vector(landa); free_vector(C) free_vector(jobs_facts_copia); free_vector(pi_wkl); free_vector(best_pi_wkl); free_vector(seq_best_l); free_vector(secuencia); free_matrix(seqxfab,f); } void DNEH_R2(VECTOR_INT *seq, VECTOR_INT *jobs_facts, MAT_INT *seq_fabs, MAT_INT pt, int n, int m, int f,int A_i) { printf("\n******Calculo de la secuencia DNEH_R2******\n"); VECTOR_FLOAT IF0= DIM_VECTOR_FLOAT(n); VECTOR_FLOAT IT0= DIM_VECTOR_FLOAT(n); VECTOR_FLOAT C= DIM_VECTOR_FLOAT(n); VECTOR_INT landa= DIM_VECTOR_INT(n); VECTOR_INT jobs_facts_copia=DIM_VECTOR_INT(f); setval_vector(jobs_facts_copia,f,0); MAT_INT seqxfab=DIM_MAT_INT(f,n); setval_matrix(seqxfab,f,n,-1); 103 103 Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time VECTOR_INT pi= DIM_VECTOR_INT(n); setval_vector(pi,n,-1); int f_asignada=-1; register int i,j,k; for (k=0;k<f;k++) { for(j=0;j<n;j++) { IF0[j]=0; IT0[j]=0; C[j]=0; landa[j]=-1; } } int new_dim=n; // para extraer los primeros f trabajos for (j=0;j<n;j++) { for (i=1;i<m;i++) { C[j]+=pt[j][i-1]; IT0[j]+=(m*(C[j]))/(i); } C[j]+=pt[j][m-1]; // Makespan IF0[j]=((n/f)-2)*IT0[j]+ C[j]; } printf("Vector IF0\t"); print_vector(IF0,n); sort_vector(IF0,landa,n,'A'); // Vector de trabajos landa ordenado de manera creciente printf("Vector landa\t"); print_vector(landa,n); *seq[0]=landa[0]; seqxfab[0][0]=landa[0]; //Primer trabajo en la primera posicion de la primera fábrica copy_mat_int(seqxfab,*seq_fabs,f,n); printf("Matriz secuencia por fabricas\n"); print_matrix(seqxfab,f,n); Anexo Código programación en C 104 new_dim=extract_vector(landa,n,0);//Extrae el trabajo de landa secuenciado en pi int aux=new_dim; printf("Secuencia landa tras insertar el primer trabajo en pi_wkl\n"); print_vector(landa,new_dim); int max_CIT, CIT_f, f_max; VECTOR_INT best_pi_wkl=DIM_VECTOR_INT(n); setval_vector(best_pi_wkl,n,-1); VECTOR_INT seq_best_l=DIM_VECTOR_INT(n); setval_vector(seq_best_l,n,-1); VECTOR_INT secuencia=DIM_VECTOR_INT(n); setval_vector(secuencia,n,-1); while (new_dim>0) { if (A_i==1) { printf("Entra en A1\n"); f_asignada=A_1(seqxfab,jobs_facts_copia,f,n,m,pt); printf("f_asignada=%d\n",f_asignada); seqxfab[f_asignada][jobs_facts_copia[f_asignada]]=landa[0]; jobs_facts_copia[f_asignada]++; pi=matriz_a_vector(seqxfab,n,f); } else if (A_i==2) { printf("Entra en A2\n"); f_asignada=A_2(seqxfab,jobs_facts_copia,f,n,m,pt); printf("f_asignada=%d\n",f_asignada); seqxfab[f_asignada][jobs_facts_copia[f_asignada]]=landa[0]; jobs_facts_copia[f_asignada]++; pi=matriz_a_vector(seqxfab,n,f); printf("Vector pi tras insertion\n"); print_vector(pi, n); } else if (A_i==3) { 105 105 Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time printf("Entra en A3\n"); f_asignada=A_3(&seq_best_l,seqxfab,jobs_facts_copia,landa[0],f,n,m,pt); printf("f_asignada=%d, la seq de esta fab es\t",f_asignada); pasterowImatrix(seqxfab,seq_best_l,f_asignada,n); jobs_facts_copia[f_asignada]++; pi=matriz_a_vector(seqxfab,n,f); } else if (A_i==4) { printf("Entra en A4\n"); f_asignada=A_4(&seq_best_l,seqxfab,jobs_facts_copia,landa[0],f,n,m,pt); printf("f_asignada=%d, la seq de esta fab es\t",f_asignada); pasterowImatrix(seqxfab,seq_best_l,f_asignada,n); jobs_facts_copia[f_asignada]++; pi=matriz_a_vector(seqxfab,n,f); } else if (A_i==5) { printf("Entra en A5\n"); f_max=0; copyrowImatrix(seqxfab,secuencia,0,n); max_CIT=CIT(secuencia,pt,jobs_facts_copia[0],m,n); for (k=1;k<f;k++) { copyrowImatrix(seqxfab,secuencia,k,n); CIT_f=CIT(secuencia,pt,jobs_facts_copia[k],m,n); if(max_CIT<CIT_f) { max_CIT=CIT_f; f_max=k; } } printf("fmax=%d\n",f_max); f_asignada=A_5(&seq_best_l,seqxfab,jobs_facts_copia,landa[0],f_max,f,n,m,pt); printf("f_asignada=%d, la seq de esta fab es\t",f_asignada); print_vector(seq_best_l,n); Anexo Código programación en C 106 pasterowImatrix(seqxfab,seq_best_l,f_asignada,n); jobs_facts_copia[f_asignada]++; pi=matriz_a_vector(seqxfab,n,f); } else if (A_i==6) { printf("Entra en A6\n"); f_asignada=A_6(&seq_best_l,seqxfab,jobs_facts_copia,landa[0],f,n,m,pt); printf("f_asignada=%d, la seq de esta fab es\t",f_asignada); print_vector(seq_best_l,n); pasterowImatrix(seqxfab,seq_best_l,f_asignada,n); jobs_facts_copia[f_asignada]++; pi=matriz_a_vector(seqxfab,n,f); } //Tras insertar el trabajo en todas las posiciones de posibles de pi_wkl y saber cual es la fabrica que se asigna, se conoce la que genera menor CIT new_dim=extract_vector(landa,aux,0); aux=new_dim; printf("Vector omega tras extraer ultimo trabajo secuenciado\t"); print_vector(omega,new_dim); printf("Secuencia pi\n"); print_vector(pi,n); copy_vector(pi,*seq,n); copy_vector(jobs_facts_copia,*jobs_facts,f); copy_mat_int(seqxfab,*seq_fabs, f, n); } free_vector(IF0); free_vector(IT0); free_vector(landa); free_vector(C) free_vector(pi); free_vector(jobs_facts_copia); free_vector(seq_best_l); free_vector(secuencia) free_matrix(seqxfab,f); } 107 107 Análisis del problema Distributed Flow shop con permutación y objetivo Total Core Idle Time Anexo Código programación en C 108