Modelos de programación Lineal para flowshop de permutación con restricciones de disponibilidad

Proyecto Fin de Carrera Ingeniería de Telecomunicación Formato de Publicación de la Escuela Técnica Superior de Ingeniería Autor: F. Javier Payán Somet Tutor: Juan José Murillo Fuentes Dep. Teoría de la Señal y Comunicaciones Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2013 Trabajo Fin de Grado Grado en Ingeniería de Organización Industrial Modelos de Programación Lineal para flowshop de permutación con restricciones de disponibilidad Autor: María del Carmen Barberá Quijano Tutor: Paz Pérez González Dep. de Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2018 Trabajo Fin de Grado Grado en Ingeniería de Organización Industrial Modelos de Programación Lineal para flowshop de permutación con restricciones de disponibilidad Autor: María del Carmen Barberá Quijano Tutor: Paz Pérez González Dep. de Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2018 Trabajo Fin de Grado: Modelos de Programación Lineal para flowshop de permutación con restricciones de disponibilidad Autor: María del Carmen Barberá Quijano Tutor: Paz Pérez González El tribunal nombrado para juzgar el trabajo arriba indicado, compuesto por los siguientes profesores: Presidente: Vocal/es: Secretario: acuerdan otorgarle la calificación de: El Secretario del Tribunal Fecha: Índice 1 Introducción 1 1.1 Objetivos del Proyecto 1 1.2 Sumario 2 2 Descripción del problema 3 2.1 Introducción 3 2.2 Descripción del problema 3 3 Modelos 5 3.1 Introducción 5 3.2 Datos, índices y variables empleados 5 3.2.1 Datos 5 3.2.2 Índices 6 3.2.3 Variables 6 3.3 Modelos originales y sus adaptaciones 7 3.3.1 Familia de modelos Wagner 7 Modelo WST 7 Modelo WST adaptado 8 Modelo Wilson 10 Modelo Wilson adaptado 11 Modelo TS2 12 Modelo TS2 adaptado 12 3.3.2 Familia de modelos Manne 14 Modelo SGST 14 Modelo SGST adaptado 14 Modelo LYeq 15 Modelo LYeq adaptado 15 3.3.3 Modelos formulados por Baker (2013) 16 Idle-time version 16 Idle-time version adaptado 18 Completion-time version 19 Completion-time version adaptado 19 4 Análisis 21 4.1 Resolución del modelo 21 4.2 Análisis estadístico de los resultados 21 4.2.1 Influencia del Modelo en el CPU Time 22 4.2.2 Influencia del periodo de disponibilidad (T) en el CPU time 24 4.2.3 Influencia del modelo y el periodo de disponibilidad (T) en el CPU Time 25 4.2.4 Influencia del modelo y el número de trabajos (N) en el CPU Time 25 I II Índice 4.2.5 Influencia del modelo y el número de máquinas (M) en el CPU Time 27 5 Conclusiones 31 Apéndice A Anexo 33 A.0.1 Modelo WST 33 A.0.2 Modelo Wilson 37 A.0.3 Modelo TS2 41 A.0.4 Modelo Idle-time 45 A.0.5 Modelo Completion-time 49 A.0.6 Modelo SGST 53 A.0.7 Modelo LYeq 56 Índice de Figuras 61 Índice de Tablas 63 Bibliografía 65 1 Introducción En la mayoría de los sectores empresariales existe un problema común: la asignación de los recursos existentes a las tareas cuya realización es necesaria para el correcto funcionamiento de la empresa. Este problema es lo que conocemos como programación y su resolución irá encaminada a conseguir unos objetivos preestablecidos de forma óptima. Existen numerosos enfoques para la programación si partimos de la definición anterior, y este trabajo se centra en uno de ellos, la programación de la producción. El problema que se plantea es el siguiente: disponemos de un número de máquinas (recursos), las cuales trabajan en un entorno de tipo flowshop, que se destinan al procesamiento de una serie de trabajos. El objetivo de esta asignación será minimizar el retraso de todos los trabajos (tardiness) con respecto a su fecha de entrega, cuyo cumplimiento no es considerado estrictamente necesario. Asimismo, existen una serie de limitaciones a la hora de resolver este problema: existen periodos de indisponibilidad de las máquinas y los trabajos se consideran ininterrumpibles, por lo que la solución óptima debe cumplir con estos aspectos. A lo largo de la literatura, se han estudiado múltiples problemas de programación de la producción. Algunos de ellos se emplean como base a la hora de resolver la problemática expuesta, realizando adaptaciones según el objetivo y las restricciones que consideramos. Para crear este documento, se ha optado por emplear el sistema de composición de textos LaTeX. Este sistema presenta numerosas ventajas, como la calidad en la edición de ecuaciones y la facilidad al estructurar el texto, razones que han provocado su elección frente a otros procesadores de texto. 1.1 Objetivos del Proyecto El objetivo último de este proyecto es la caracterización de un modelo que logre resolver de forma óptima el problema presentado en la introducción. Este modelo, además de proporcionar la mejor solución, debe hacerlo en el menor tiempo posible. Por consiguiente, realizaremos un análisis del desempeño de todos los modelos para alcanzar así la meta final, encontrar el modelo más eficiente. Podemos desglosar este objetivo en las siguientes fases que desembocan en su consecución: 1. Adaptar los modelos existentes en la literatura para el problema propuesto. 2. Programar los modelos para su posterior resolución. 3. Resolver los modelos para un número pequeño de instancias mediante el software Gurobi. 4. Validar los modelos. 5. Resolver de nuevo los modelos para una batería de instancias. 6. Evaluar los tiempos de cómputo para cada uno de los modelos. 1 8Capítulo 3. Modelos Min Cmax = N ∑ i=1 TMi + N ∑ p=1 XMp (3.1) sa : N ∑ j=1 Zi j =1(1≤i≤N)(3.2) N ∑ i=1 Zi j =1(1≤j≤N)(3.3) N ∑ i=1 TriZi,j+1+Xr,j+1+Yr,j+1= N ∑ i=1 Tr+1,iZi j+ +Xr+1,j+1+Yr j (1≤r≤M−1,1≤j≤N−1) (3.4) Xr+1,1=Xr,1+Yr,1+ N ∑ i=1 TriZi1(1≤r≤M−1)(3.5) Er j = j ∑ l=1 (Xrl + N ∑ i=1 TriZil) (1≤r≤M,1≤j≤N)(3.6) Er j ≤bT +P(1−Binr jb) (1≤r≤M,1≤j≤N,1≤b≤Bines)(3.7) Er j − N ∑ i=1 TriZi j +P(1−Binr jb)≥T(b−1) (1≤r≤M,1≤j≤N,1≤b≤Bines) (3.8) Bines ∑ b=1 Binr jb =1(1≤r≤M,1≤j≤N)(3.9) Xr j,Yr j,Er j ≥0; 1 ≤r≤M,1≤j≤N Zi j,Binr jb ∈ {0,1}; 1 ≤r≤M,1≤i≤N,1≤j≤N,1≤b≤Bines Este modelo tiene como objetivo minimizar el makespan, el cual viene dado por la suma de los tiempos de proceso y los tiempos ociosos en la última máquina antes del procesamiento de cada trabajo (3.1). Los conjuntos de restricciones (3.2 y 3.3) garantizan la asignación de cada trabajo a una única posición en la secuencia, así como que cada posición sea ocupada por un solo trabajo. Las restricciones (3.4 y 3.5) aseguran que el trabajo en la posición j+1 no empiece a ser procesado en la máquina r hasta que el trabajo en la posición j haya sido completamente procesado. Asimismo, garantizan que el trabajo en la posición j no comience a ser procesado en la máquina r+1 hasta que no finalice su procesamiento en la máquina r . La variable Er j , incorporada para facilitar la inclusión de la restricción de disponibilidad, se define como la suma de los tiempos de espera y de proceso de los trabajos (3.6). Las restricciones (3.7 y 3.8) proporcionan la cota superior del tiempo de finalización y la cota inferior del tiempo de comienzo de cada trabajo, respectivamente, para que sea procesado dentro del bin que le corresponda. Finalmente, cada trabajo (referido por su posición j ) podrá ser asignado a un único bin en cada máquina r (3.9). Modelo WST adaptado El modelo modificado incorpora la variable tdjy las siguientes restricciones: tdj≥EM j −dj(1≤j≤n)(3.10) dj= N ∑ i=1 diZi j (1≤j≤n)(3.11) 3.3 Modelos originales y sus adaptaciones 9 La restricción (3.10) limita el tardiness, es decir, la diferencia entre el tiempo de finalización del trabajo en la posición j y su fecha de entrega, la cual se define en la restricción (3.11) teniendo en cuenta la variable de asignación de trabajos a posiciones en la secuencia. El modelo adaptado quedaría de la siguiente forma: Min N ∑ j=1 tdj sa : N ∑ j=1 Zi j =1(1≤i≤N) N ∑ i=1 Zi j =1(1≤j≤N) N ∑ i=1 TriZi,j+1+Xr,j+1+Yr,j+1= N ∑ i=1 Tr+1,iZi j+ +Xr+1,j+1+Yr,j(1≤r≤M−1,1≤j≤N−1) Xr+1,1=Xr,1+Yr,1+ N ∑ i=1 TriZi1(1≤r≤M−1) Er j = j ∑ l=1 (Xrl + N ∑ i=1 TriZil) (1≤r≤M,1≤j≤N) Er j ≤bT +P(1−Binr jb) (1≤r≤M,1≤j≤N,1≤b≤Bines) Er j − N ∑ i=1 TriZi j +P(1−Binr jb)≥T(b−1) (1≤r≤M,1≤j≤N,1≤b≤Bines) Bines ∑ b=1 Binr jb =1,(1≤r≤M,1≤j≤N) tdj≥EM j −dj(1≤j≤n) dj= N ∑ i=1 diZi j (1≤j≤n) Xr j,Yr j,Er j,tdj≥0; 1 ≤r≤M,1≤j≤N Zi j,Binr jb ∈ {0,1}; 1 ≤r≤M,1≤i≤N,1≤j≤N,1≤b≤Bines 10 Capítulo 3. Modelos Modelo Wilson Este modelo emplea las variables Br j,Zi j yBinr jb. Min BMN + N ∑ i=1 TMiZiN (3.12) sa : N ∑ j=1 zi j =1(1≤i≤N)(3.13) N ∑ i=1 zi j =1(1≤j≤N)(3.14) B1j+ N ∑ i=1 T1iZi j ≤B1,j+1(1≤j≤N−1)(3.15) B11 =0(3.16) Br1+ N ∑ i=1 TriZi1≤Br+1,1(1≤r≤M−1)(3.17) Br j + N ∑ i=1 TriZi j ≤Br+1,j(1≤r≤M−1,2≤j≤N)(3.18) Br j + N ∑ i=1 TriZi j ≤Br,j+1(2≤r≤M,1≤j≤N−1)(3.19) Br j + N ∑ i=1 TriZi j −bT ≤P(1−Binr jb) (1≤r≤M,1≤j≤N,1≤b≤Bines)(3.20) Br j +P(1−Binr jb)≥T(b−1) (1≤r≤M,1≤j≤N,1≤b≤Bines)(3.21) Bines ∑ b=1 Binr jb =1,(1≤r≤M,1≤j≤N)(3.22) Br j ≥0; 1 ≤r≤M,1≤j≤N Zi j,Binr jb ∈ {0,1}; 1 ≤r≤M,1≤i≤N,1≤j≤N,1≤b≤Bines La función objetivo (makespan) se expresa adicionando al tiempo de comienzo del último trabajo en la última máquina su tiempo de proceso en esta máquina (3.12). Los dos primeros conjuntos de restricciones (3.13 y 3.14) coinciden con las del modelo WST y tienen el mismo significado. La ecuación (3.15) fuerza que todos los trabajos comiencen en la primera máquina de forma inmediata a la finalización de su predecesor. En cuanto al primer trabajo, será procesado en el instante 0 en la primera máquina (3.16) y comenzará en el resto de máquinas tras ser procesado en la anterior (3.17). El conjunto de restricciones (3.18) actúa como la restricción (3.17) para todas las máquinas y trabajos. Asimismo, cada trabajo (referido por su posición j+1 ) no podrá ser procesado en una máquina hasta que acabe el trabajo j(3.19). Las restricciones (3.20 y 3.21) proporcionan la cota superior del tiempo de finalización y la cota inferior del tiempo de comienzo de cada trabajo, respectivamente, para que sea procesado dentro del bin que le corresponda. Finalmente, cada trabajo (referido por su posición j ) podrá ser asignado a un único bin en cada máquina r (3.22). 3.3 Modelos originales y sus adaptaciones 11 Modelo Wilson adaptado El modelo modificado incorpora la variable tdjy las siguientes restricciones: tdj≥BM j + N ∑ i=1 TMiZi j −dj(1≤j≤n)(3.23) dj= N ∑ i=1 diZi j (1≤j≤n)(3.24) La restricción (3.23) limita el tardiness, es decir, la diferencia entre el tiempo de finalización (en este caso, definido como la suma del tiempo de comienzo y el tiempo de proceso) del trabajo en la posición j y su fecha de entrega, la cual se define en la restricción (3.24) teniendo en cuenta la variable de asignación de trabajos a posiciones en la secuencia. El modelo adaptado quedaría de la siguiente forma: Min N ∑ j=1 tdj sa : N ∑ j=1 zi j =1(1≤i≤N) N ∑ i=1 zi j =1(1≤j≤N) B1j+ N ∑ i=1 T1iZi j ≤B1,j+1(1≤j≤N−1) B11 =0 Br1+ N ∑ i=1 TriZi1≤Br+1,1(1≤r≤M−1) Br j + N ∑ i=1 TriZi j ≤Br+1,j(1≤r≤M−1,2≤j≤N) Br j + N ∑ i=1 TriZi j ≤Br,j+1(2≤r≤M,1≤j≤N−1) Br j + N ∑ i=1 TriZi j −bT ≤P(1−Binr jb) (1≤r≤M,1≤j≤N,1≤b≤Bines) Br j +P(1−Binr jb)≥T(b−1) (1≤r≤M,1≤j≤N,1≤b≤Bines) Bines ∑ b=1 Binr jb =1,(1≤r≤M,1≤j≤N) tdj≥BM j + N ∑ i=1 TMiZi j −dj(1≤j≤n) dj= N ∑ i=1 diZi j (1≤j≤n) Br j,tdj≥0; 1 ≤r≤M,1≤j≤N Zi j,Binr jb ∈ {0,1}; 1 ≤r≤M,1≤i≤N,1≤j≤N,1≤b≤Bines 12 Capítulo 3. Modelos Modelo TS2 Este modelo emplea las variables Er j,Zi j yBinr jb. Min EMN (3.25) sa : N ∑ j=1 zi j =1(1≤i≤N)(3.26) N ∑ i=1 zi j =1(1≤j≤N)(3.27) Er j + N ∑ i=1 TriZi,j+1≤Er,j+1(1≤r≤M,1≤j≤N−1)(3.28) Er j + N ∑ i=1 Tr+1,iZi j ≤Er+1,j(1≤r≤M−1,1≤j≤N)(3.29) E11 ≥ N ∑ i=1 T1iZi1(3.30) Er j −bT ≤P(1−Binr jb) (1≤r≤M,1≤j≤N,1≤b≤Bines)(3.31) Er j − N ∑ i=1 TriZi j +P(1−Binr jb)≥T(b−1) (1≤r≤M,1≤j≤N,1≤b≤Bines)(3.32) Bines ∑ b=1 Binr jb =1,(1≤r≤M,1≤j≤N)(3.33) Er j ≥0; 1 ≤r≤M,1≤j≤N Zi j,Binr jb ∈ {0,1}; 1 ≤r≤M,1≤i≤N,1≤j≤N,1≤b≤Bines Las restricciones son similares a las del modelo TS2, considerando en lugar del tiempo de inicio de cada trabajo (referido por su posición j) en cada máquina r,Br j, el tiempo de finalización, Er j. La función objetivo (makespan) coincide con el tiempo de finalización del último trabajo en la última máquina (3.25). Los dos primeros conjuntos de restricciones (3.26 y 3.27) coinciden con las de los dos modelos anteriores y tienen el mismo significado. La ecuación (3.28) fuerza que todos los trabajos finalicen en cada máquina tras finalizar su predecesor y ser procesado él mismo. El conjunto de restricciones (3.29) segura para todos los trabajos que no puedan comenzar en la máquina r+1 hasta que finalicen en r . El primer trabajo en la primera máquina comenzará en el instante 0, por lo que su tiempo de finalización coincidirá con su tiempo de proceso (3.30). Las restricciones (3.31 y 3.32) proporcionan la cota superior del tiempo de finalización y la cota inferior del tiempo de comienzo de cada trabajo, respectivamente, para que sea procesado dentro del bin que le corresponda. Finalmente, cada trabajo (referido por su posición j ) podrá ser asignado a un único bin en cada máquina r(3.33). Modelo TS2 adaptado El modelo modificado incorpora la variable tdjy las siguientes restricciones: tdj≥EM j −dj(3.34) dj= N ∑ i=1 diZi j (3.35) 3.3 Modelos originales y sus adaptaciones 13 La restricción (3.34) limita el tardiness, es decir, la diferencia entre el tiempo de finalización del trabajo en la posición j y su fecha de entrega, la cual se define en la restricción (3.35) teniendo en cuenta la variable de asignación de trabajos a posiciones en la secuencia. El modelo adaptado quedaría de la siguiente forma: Min N ∑ j=1 tdj sa : N ∑ j=1 zi j =1(1≤i≤N) N ∑ i=1 zi j =1(1≤j≤N) Er j + N ∑ i=1 TriZi,j+1≤Er,j+1(1≤r≤M,1≤j≤N−1) Er j + N ∑ i=1 Tr+1,iZi j ≤Er+1,j(1≤r≤M−1,1≤j≤N) E11 ≥ N ∑ i=1 T1iZi1 Er j −bT ≤P(1−Binr jb) (1≤r≤M,1≤j≤N,1≤b≤Bines) Er j − N ∑ i=1 TriZi j +P(1−Binr jb)≥T(b−1) (1≤r≤M,1≤j≤N,1≤b≤Bines) Bines ∑ b=1 Binr jb =1,(1≤r≤M,1≤j≤N) tdj≥EM j −dj dj= N ∑ i=1 diZi j Er j,tdj≥0; 1 ≤r≤M,1≤j≤N Zi j,Binr jb ∈ {0,1}; 1 ≤r≤M,1≤i≤N,1≤j≤N,1≤b≤Bines 14 Capítulo 3. Modelos 3.3.2 Familia de modelos Manne SGST y LYeq son los modelos pertenecientes a la familia Manne. El modelo SGST utiliza pares de restricciones dicotómicas para resolver el problema de asignación de los trabajos a las máquinas mientras que el modelo LYeq combina estas dos restricciones utilizando una nueva variable, Qrik . Como consecuencia de esto, nos referimos a los trabajos por el índice i, y no por su posición como en los modelos de la familia Wagner. Modelo SGST Este modelo emplea las variables Cri,Cmax,Dik yBinrib. Min Cmax (3.36) sa :C1i≥T1i(1≤i≤N)(3.37) Cr+1,i−Cri ≥Tr+1,i(1≤r≤M−1,1≤i≤N)(3.38) Cri −Crk +PDik ≥Tri (1≤r≤M,1≤i<k≤N)(3.39) Crk −Cri +P(1−Dik)≥Trk (1≤r≤M,1≤i<k≤N)(3.40) Cmax ≥CMi (1≤i≤N)(3.41) Cri −bT ≤P(1−Binrib) (1≤r≤M,1≤i≤N,i≤b≤Bines)(3.42) Cri −Tri +P(1−Binrib)≥T(b−1) (1≤r≤M,1≤i≤N,1≤b≤Bines)(3.43) Bines ∑ b=1 Binrib =1,(1≤r≤M,1≤i≤N)(3.44) Cri,Cmax ≥0; 1 ≤r≤M,1≤i≤N Dik,Binrib ∈ {0,1}; 1 ≤r≤M,1≤i≤N,1≤k≤N,1≤b≤Bines Para este modelo, la función objetivo coincide con la variable Cmax (3.36) cuyo valor debe coincidir con el tiempo de finalización del último de los trabajos en la última máquina (3.41). Cada trabajo debe finalizar en la máquina 1 tras ser procesado (3.37). El conjunto de restricciones (3.38) garantiza para cada trabajo que no pueda finalizar en la máquina r+1 tras ser procesado en ella y en la anterior, r . Los pares de restricciones dicotómicas (3.39 y 3.40) relacionan dos trabajos i y k , asegurando que cada trabajo iprecede o sigue a ken la secuencia, pero no ambas opciones. Las restricciones (3.42 y 3.43) proporcionan la cota superior del tiempo de finalización y la cota inferior del tiempo de comienzo de cada trabajo, respectivamente, para que sea procesado dentro del bin que le corresponda. Finalmente, cada trabajo (referido por su posición j ) podrá ser asignado a un único bin en cada máquina r(3.44). Modelo SGST adaptado El modelo modificado incorpora la variable tdi y cambia la restricción (3.41), que indica la cota inferior del makespan, por la restricción (3.45), que indica la del tardiness: tdi≥CMi −di(1≤i≤N)(3.45) 3.3 Modelos originales y sus adaptaciones 15 El modelo adaptado quedaría de la siguiente forma: Min N ∑ i=1 tdi sa :C1i≥T1i(1≤i≤N) Cr+1,i−Cri ≥Tr+1,i(1≤r≤M−1,1≤i≤N) Cri −Crk +PDik ≥Tri (1≤r≤M,1≤i<k≤N) Crk −Cri +P(1−Dik)≥Trk (1≤r≤M,1≤i<k≤N) Cri −bT ≤P(1−Binrib) (1≤r≤M,1≤i≤N,i≤b≤Bines) Cri −Tri +P(1−Binrib)≥T(b−1) (1≤r≤M,1≤i≤N,1≤b≤Bines) Bines ∑ b=1 Binrib =1,(1≤r≤M,1≤i≤N) tdi≥CMi −di(1≤i≤N) Cri,tdi≥0; 1 ≤r≤M,1≤i≤N Dik,Binrib ∈ {0,1}; 1 ≤r≤M,1≤i≤N,1≤k≤N,1≤b≤Bines Modelo LYeq Este modelo emplea, además de las variables Cri , Cmax , Dik y Binrib del modelo SGST, la variable auxiliar Qrik. Min Cmax (3.46) sa :C1i≥T1i(1≤i≤N)(3.47) Cr+1,i−Cri ≥Tr+1,i(1≤r≤M−1,1≤i≤N)(3.48) Cmax ≥CMi (1≤i≤N)(3.49) PDik +Cri −Crk −Tri =Qrik (1≤r≤M,1≤i<k≤N)(3.50) Qrik ≤P−Tri −Trk (1≤r≤M,1≤i<k≤N)(3.51) Cri −bT ≤P(1−Binrib) (1≤r≤M,1≤i≤N,1≤b≤Bines)(3.52) Cri −Tri +P(1−Binrib)≥T(b−1) (1≤r≤M,1≤i≤N,1≤b≤Bines)(3.53) Bines ∑ b=1 Binrib =1,(1≤r≤M,1≤i≤N)(3.54) Cri,Cmax,Qrik ≥0; 1 ≤r≤M,1≤i≤K≤N Dik,Binrib ∈ {0,1}; 1 ≤r≤M,1≤i≤N,1≤k≤N,1≤b≤Bines La función objetivo (3.46) y las restricciones (3.47, 3.48 y 3.49) se corresponden con las ecuaciones (3.36, 3.37 y 3.41) del modelo SGST, respectivamente. Con respecto a los conjuntos de restricciones (3.50 y 3.51) establecen el par de restricciones dicotómicas. El resto de restricciones actúa del mismo modo que en el resto de modelos, garantizando la restricción de disponibilidad de las máquinas. Modelo LYeq adaptado El modelo modificado incorpora la variable tdi y cambia la restricción (3.49), que indica la cota inferior del makespan, por la restricción (3.55), que proporciona la del tardiness: tdi≥CMi −di(1≤i≤N)(3.55) 16 Capítulo 3. Modelos El modelo adaptado quedaría de la siguiente forma: Min N ∑ i=1 tdi sa :C1i≥T1i(1≤i≤N) Cr+1,i−Cri ≥Tr+1,i(1≤r≤M−1,1≤i≤N) PDik +Cri −Crk −Tri =Qrik (1≤r≤M,1≤i<k≤N) Qrik ≤P−Tri −Trk (1≤r≤M,1≤i<k≤N) Cri −bT ≤P(1−Binrib) (1≤r≤M,1≤i≤N,1≤b≤Bines) Cri −Tri +P(1−Binrib)≥T(b−1) (1≤r≤M,1≤i≤N,1≤b≤Bines) Bines ∑ b=1 Binrib =1,(1≤r≤M,1≤i≤N) tdi≥CMi −di(1≤i≤N) Cri,Qrik,tdi≥0; 1 ≤r≤M,1≤i≤K≤N Dik,Binrib ∈ {0,1}; 1 ≤r≤M,1≤i≤N,1≤k≤N,1≤b≤Bines 3.3.3 Modelos formulados por Baker (2013) Las versiones Idle-time yCompletion-time resuelven el problema de asignación de igual forma que los modelos de la familia Wagner, empleando una variable binaria Xjk cuyo valor es 1 en el caso de que el trabajo j sea asignado a la posición k de la secuencia. Como consecuencia, nos referimos a cada trabajo por su posición k. Idle-time version El modelo emplea las variables Ck,Iik,Hki,tkyxjk. Min N ∑ k=1 tk(3.56) sa : N ∑ j=1 xjk =1(1≤k≤N)(3.57) N ∑ k=1 xjk =1(1≤j≤N)(3.58) Ii,k+1+ n ∑ u=1 piuxu,k+1+Hi,k+1−Hik − N ∑ u=1 pi+1,uxu,k−Ii+1,k+1=0 (1≤k≤N−1,1≤i≤M−1) (3.59) Ii1+ N ∑ u=1 piuxu1+Hi1−Ii+1,1=0(1≤i≤M−1)(3.60) C0=0(3.61) tk≥Ck−1+IMk + N ∑ j=1 pM jxjk − N ∑ j=1 djxjk (1≤k≤N)(3.62) Cik,Iik,Hki,tk≥0; 1 ≤i≤M,1≤k≤N xjk ∈ {0,1}; 1 ≤j≤N,1≤k≤N 3.3 Modelos originales y sus adaptaciones 17 El objetivo de este modelo es minimizar el tardiness total (3.56). Los conjuntos de restricciones (3.57 y 3.58) garantizan la asignación de cada trabajo a una única posición en la secuencia, así como que cada posición sea ocupada por un solo trabajo. La relación entre las variables que indican el tiempo ocioso se expresa en la ecuación (3.59) para todas las posiciones en la secuencia, y en la (3.60) para la primera posición. Consideramos un trabajo cuyo índice es 0 y finaliza en el instante 0. Finalmente, el retraso del trabajo en la posición k es limitado inferiormente en el conjunto de restricciones (3.62). 24 Capítulo 4. Análisis recorrido intercuartílico de mejor forma. El 54.36% de las observaciones eliminadas pertenecen a instancias de 20 máquinas y el 34.74% a instancias de 15 máquinas. El porcentaje restante será de 10 máquinas. Por tanto, deducimos que el tiempo de cómputo aumenta con el número de máquinas. La gráfica resultante se muestra en la figura 4.3. Figura 4.3 Diagrama de cajas y bigotes reducido. CPU Time por modelo. Con estos datos y representaciones podemos llegar a las siguientes conclusiones: • La media del tiempo de cómputo es notablemente superior para los modelos WST e Idle-time (39.95s y 41.73s, respectivamente) y tiene un valor muy bajo para el modelo SGST (1.48s). • La dispersión de los datos es llamativa principalmente para los modelos Idle-time y WST, a pesar de que su valor es alto para la mayoría de modelos. Por tanto, podemos afirmar para los modelos Idle-Time y WST que el tiempo de cómputo para algunas instancias ha sido destacadamente alto. Esto lo observamos tanto en el Diagrama de Cajas y Bigotes como en la desviación estándar. • Finalmente podemos concluir que el modelo SGST es el más eficiente en cuanto a CPU Time empleado. Asimismo, es el único que garantiza la optimalidad de todas las soluciones. Los modelos Idle-time y WST los que obtienen los peores resultados. 4.2.2 Influencia del periodo de disponibilidad (T) en el CPU time En este apartado se analiza la influencia del periodo de disponibilidad en el tiempo de cómputo. Para realizar este análisis, basta con representar la función de densidad del tiempo empleado para los tres valores que puede tomar el periodo de disponibilidad, 100, 200 y 300 (figura 4.4). La función de densidad representa la frecuencia (número de observaciones) con que aparecen las mediciones. De la figura 4.4 podemos llegar a la siguiente conclusión: 4.2 Análisis estadístico de los resultados 25 Figura 4.4 Función de densidad para cada periodo de disponibilidad (T). •A medida que aumenta el periodo de disponibilidad, la frecuencia de las observaciones para tiempos pequeños aumenta, es decir, la mayoría de las instancias requieren un tiempo de cómputo menor. Este resultado se debe a que mayor valor de T requiere menor número de Bines, por tanto la resolución del modelo se simplifica. 4.2.3 Influencia del modelo y el periodo de disponibilidad (T) en el CPU Time En este apartado se analiza la influencia del periodo de disponibilidad y el modelo en el tiempo de cómputo. Representamos los datos en el Diagrama de cajas y bigotes (figura 4.5) y vemos que presentan gran dispersión. Por tanto, al igual que en los casos anteriores, filtramos las observaciones de tiempos altos para ver los datos con claridad (figura 4.6). Por otra parte, representamos las medias y sus desviaciones estándar en la tabla 4.3. Con estos datos, llegamos a las siguientes conclusiones: • Con periodos de disponibilidad de 200 y 300 los modelos se comportan de forma similar en cuanto a media de tiempo empleado. Para T=100 observamos que la diferencia de medias entre modelos es muy alta. Para los modelos Idle-time y WST su valor es notablemente superior al resto. •Con relación a la dispersión de los datos, disminuye de forma inversa a T. 4.2.4 Influencia del modelo y el número de trabajos (N) en el CPU Time En este apartado se estudia la influencia del modelo y el número de trabajos en el CPU Time. 26 Capítulo 4. Análisis Figura 4.5 Diagrama de cajas y bigotes. CPU Time por modelo y periodo de disponibilidad (T). Figura 4.6 Diagrama de cajas y bigotes. CPU Time por modelo y periodo de disponibilidad (T) para valores del CPU Time menores que 6.. Para llevar a cabo este análisis, calculamos las medias y sus desviaciones estándar en la tabla 4.4 y las representamos para cada uno de los modelos y número de trabajos a asignar (figura 4.7). De este estudio podemos extraer las siguientes conclusiones: • Para N=5 , todos los modelos actúan de forma similar y no presentan desviaciones destacables con respecto a la media, es decir, no hay ningún valor atípico. Para N=10 los valores medios del CPU time son levemente superiores, así como las desviaciones. No obstante, podemos concluir que no presentan notables diferencias. • A medida que aumenta N, podemos observar con mayor claridad las diferencias entre modelos, concluyendo, como en apartados anteriores, que el modelo Idle-time presenta los peores resultados para estos valores, seguido del WST. 4.2 Análisis estadístico de los resultados 27 Tabla 4.3 CPU Time(s) medio y desviación estándar en función del modelo y el periodo de disponibilidad (T). CPU Time (s) Media Desv. Est. WST T=100 107.54 253.00 T=200 8.88 37.80 T=300 3.43 35.80 Wilson T=100 17.42 107.20 T=200 2.26 35.75 T=300 1.70 35.58 TS2 T=100 23.05 159.39 T=200 2.23 35.85 T=300 1.71 35.58 SGST T=100 3.70 32.45 T=200 0.47 1.16 T=300 0.27 0.77 LYeq T=100 14.12 55.83 T=200 3.61 11.03 T=300 1.91 5.62 Idle-Time T=100 112.63 435.20 T=200 8.96 38.44 T=300 3.61 35.86 Completion-time T=100 18.06 108.30 T=200 2.12 35.63 T=300 1.76 35.60 Figura 4.7 Media y desviación estándar de cada modelo para cada número de trabajos. • Asimismo, cabe destacar que el aumento del número de trabajos no implica en todos los casos el aumento del tiempo medio de computación, ya que en modelos como el Completion-time esto no ocurre. 4.2.5 Influencia del modelo y el número de máquinas (M) en el CPU Time En este apartado se estudia la influencia del modelo y el número de trabajos en el CPU Time. 28 Capítulo 4. Análisis Tabla 4.4 CPU Time(s) medio y desviación estándar en función del modelo y el número de trabajos (N).. CPU Time (s) Media Desv. Est. WST N=5 23.62 130.68 N=10 12.42 62.26 N=15 50.80 180.16 N=20 72.97 206.24 Wilson N=5 18.77 122.46 N=10 5.04 58.16 N=15 1.79 7.99 N=20 2.92 17.53 TS2 N=5 22.49 173.77 N=10 5.30 58.43 N=15 1.85 10.06 N=20 6.36 61.06 SGST N=5 3.22 37.42 N=10 0.63 2.11 N=15 0.82 1.91 N=20 1.24 2.10 LYeq N=5 8.03 61.66 N=10 3.47 9.91 N=15 5.80 14.96 N=20 8.90 18.38 Idle-Time N=5 21.13 121.44 N=10 14.08 70.66 N=15 60.89 453.93 N=20 70.83 195.57 Completion-time N=5 16.86 113.61 N=10 4.20 47.38 N=15 1.75 9.29 N=20 6.45 62.38 Para llevar a cabo este análisis, calculamos las medias y sus desviaciones estándar en la tabla 4.5 y las representamos para cada uno de los modelos y número de trabajos a asignar (figura 4.8). Figura 4.8 Media y desviación estándar de cada modelo para cada número de máquinas. 4.2 Análisis estadístico de los resultados 29 Tabla 4.5 CPU Time(s) medio y desviación estándar en función del modelo y el número de máquinas (M). CPU Time (s) Media Desv. Est. WST M=2 23.62 130.68 M=3 12.42 62.26 M=4 50.80 180.16 M=5 72.97 206.24 Wilson M=2 18.77 122.46 M=3 5.04 58.16 M=4 1.79 7.99 M=5 2.92 17.53 TS2 M=2 22.49 173.77 M=3 5.30 58.43 M=4 1.85 10.06 M=5 6.36 61.06 SGST M=2 3.22 37.42 M=3 0.63 2.11 M=4 0.82 1.91 M=5 1.24 2.10 LYeq M=2 8.03 61.66 M=3 3.47 9.91 M=4 5.80 14.96 M=5 8.90 18.38 Idle-Time M=2 21.13 121.44 M=3 14.08 70.66 M=4 60.89 453.93 M=5 70.83 195.57 Completion-time M=2 16.86 113.61 M=3 4.20 47.38 M=4 1.75 9.29 M=5 6.45 62.38 Como vemos en los datos, la influencia de las máquinas no permite sacar ideas concluyentes. Únicamente observamos que los modelos Idle-time y WST se comportan de forma muy similar 5 Conclusiones En este trabajo se han adaptado siete modelos diferentes existentes en la literatura para resolver el siguiente problema de programación de la producción: la asignación de máquinas, las cuales trabajan en un entorno de tipo flowshop de permutación, al procesamiento de trabajos, con el objetivo de minimizar el tardiness total y teniendo en cuenta las restricciones de disponibilidad de las máquinas. Este problema queda caracterizado de la siguiente forma: Fm|prmu,nr −pm|∑ j Tj. Todos los modelos deben obtener la solución óptima según el modelado previo. No obstante, no resultan igual de eficientes a la hora de lograrlo. Por tanto, el objetivo último de este proyecto es analizar el desempeño de los modelos en cuanto a tiempo de cómputo empleado, para tratar determinar qué modelo resulta más eficiente. Para lograr este objetivo, los modelos se han programado en lenguaje C para que puedan resolver una batería de 13.440 instancias mediante el software de optimización Gurobi. A partir de las observaciones alcanzadas, se ha realizado un análisis estadístico evaluando el desempeño de los modelos según los factores que pueden influir en él: el periodo de disponibilidad, el número de máquinas y el número de trabajos. En todos los casos se ha observado que el modelo SGST es el más eficiente a la hora de resolver el problema propuesto. 31 Apéndice A Anexo En esta apartado se adjunta el código en lenguaje C que implementa cada uno de los siete modelos desarrollados para resolver la problemática expuesta. A.0.1 Modelo WST modelo_WST(MAT_INT p_ri, int n, int m, int Bines, int T, int P, MAT_INT di,char **argv) { int j,i,r,l,b; FILE *fichero=fopen(argv[5],"w"); fprintf(fichero,"Minimize\n"); //FO fprintf(fichero,"td[1]"); for(j=2;j<=n;j++) { fprintf(fichero, " + td[%d]",j); } //Restricciones fprintf(fichero, "\nSubject To"); //R1 for(i=1; i<=n;i++) { fprintf(fichero,"\nR1.%d:",i); fprintf(fichero," Z[%d][1]",i); for(j=2;j<=n;j++) { fprintf(fichero, " + Z[%d][%d]",i,j); } fprintf(fichero, " = 1"); } //R2 for(j=1; j<=n;j++) { fprintf(fichero,"\nR2.%d:",j); fprintf(fichero," Z[1][%d]",j); for(i=2;i<=n;i++) { fprintf(fichero, " + Z[%d][%d]",i,j); } 33 40 Appendix A. Anexo fprintf(fichero, "\nBounds"); for(r=1;r<=m;r++) { for(j=1;j<=n;j++) { fprintf(fichero, "\nB[%d][%d] >= 0",r,j); } } for(j=1;j<=n;j++) { fprintf(fichero, "\ntd[%d] >= 0",j); } for(j=1;j<=n;j++) { fprintf(fichero, "\nd[%d] >= 0",j); } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { fprintf(fichero, "\n0 <= Z[%d][%d] <= 1",i,j); } } for(r=1;r<=m;r++) { for(j=1;j<=n;j++) { for(b=1;b<=Bines;b++) { { fprintf(fichero, "\n0 <= Bin[%d][%d][%d] <= 1",r,j,b); } } } } //Binary fprintf(fichero, "\nBinary\n"); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { fprintf(fichero, "Z[%d][%d] ",i,j); } } fprintf(fichero, "\n"); for(r=1;r<=m;r++) { for(j=1;j<=n;j++) { for(b=1;b<=Bines;b++) { fprintf(fichero, "Bin[%d][%d][%d] ",r,j,b); } } } //General fprintf(fichero, "\nGeneral\n"); 41 for(r=1;r<=m;r++) { for(j=1;j<=n;j++) { fprintf(fichero, "B[%d][%d] ",r,j); } } for(j=1;j<=n;j++) { fprintf(fichero, "td[%d] ",j); } for(j=1;j<=n;j++) { fprintf(fichero, "d[%d] ",j); } fprintf(fichero, "\nEnd"); fclose(fichero); return 0; } A.0.3 Modelo TS2 modelo_TS2(MAT_INT p_ri, int n, int m, int Bines,int T, int P, MAT_INT di,char **argv) { int i,j,r,b; FILE *fichero=fopen(argv[5],"w"); fprintf(fichero,"Minimize\n"); //FO fprintf(fichero,"td[1]"); for(j=2;j<=n;j++) { fprintf(fichero, " + td[%d]",j); } //Restricciones fprintf(fichero, "\nSubject To"); //R1 for(i=1; i<=n;i++) { fprintf(fichero,"\nR1.%d:",i); fprintf(fichero," Z[%d][1]",i); for(j=2;j<=n;j++) { fprintf(fichero, " + Z[%d][%d]",i,j); } fprintf(fichero, " = 1"); } //R2 for(j=1; j<=n;j++) { fprintf(fichero,"\nR2.%d:",j); fprintf(fichero," Z[1][%d]",j); for(i=2;i<=n;i++) { 42 Appendix A. Anexo fprintf(fichero, " + Z[%d][%d]",i,j); } fprintf(fichero, " = 1"); } //R3 for(r=1;r<=m;r++) { for(j=1;j<=n-1;j++) { fprintf(fichero, "\nR3.%d.%d: E[%d][%d]",r,j,r,j); for(i=1;i<=n;i++) { fprintf(fichero, " + %d Z[%d][%d]",p_ri[r-1][i-1],i,j+1); } fprintf(fichero, " - E[%d][%d] <= 0",r,j+1); } } //R4 for(r=1;r<=m-1;r++) { for(j=1;j<=n;j++) { fprintf(fichero, "\nR4.%d.%d: E[%d][%d]",r,j,r,j); for(i=1;i<=n;i++) { fprintf(fichero, " + %d Z[%d][%d]",p_ri[r][i-1],i,j); } fprintf(fichero, " - E[%d][%d] <= 0",r+1,j); } } //R5 fprintf(fichero, "\nR5: E[1][1]"); for(i=1;i<=n;i++) { fprintf(fichero, " - %d Z[%d][1]", p_ri[0][i-1],i); } fprintf(fichero, " >= 0"); //R6 for(r=1;r<=m;r++) { for(j=1;j<=n;j++) { for(b=1;b<=Bines;b++) { fprintf(fichero, "\nR6.%d.%d.%d: E[%d][%d] + %d Bin[%d][%d][%d] <= %d",r,j,b,r,j,P,r,j,b,P+(b*T)); } } } //R7 for(r=1;r<=m;r++) { for(j=1;j<=n;j++) { for(b=1;b<=Bines;b++) { 43 fprintf(fichero, "\nR7.%d.%d.%d: E[%d][%d]",r,j,b,r,j); for(i=1;i<=n;i++) { fprintf(fichero, " - %d Z[%d][%d]",p_ri[r-1][i-1],i,j); } fprintf(fichero, " - %d Bin[%d][%d][%d] >= %d",P,r,j,b, T*(b-1)- P); } } } //R8 for(r=1;r<=m;r++) { for(j=1;j<=n;j++) { fprintf(fichero, "\nR8.%d.%d: Bin[%d][%d][1]",r,j,r,j); for(b=2;b<=Bines;b++) { fprintf(fichero, " + Bin[%d][%d][%d]",r,j,b); } fprintf(fichero, " = 1"); } } //R9 for(j=1;j<=n;j++) { fprintf(fichero, "\nR11.%d: td[%d] - E[%d][%d] + d[%d] >= 0",j,j,m,j,j); } //R10 for(j=1;j<=n;j++) { fprintf(fichero, "\nR12.%d: d[%d]",j,j,di[0],j); for(i=1;i<=n;i++) { fprintf(fichero, " - %d Z[%d][%d]",di[0][i-1],i,j); } fprintf(fichero, " = 0"); } //Bounds fprintf(fichero, "\nBounds"); for(r=1;r<=m;r++) { for(j=1;j<=n;j++) { fprintf(fichero, "\nE[%d][%d] >= 0",r,j); } } for(j=1;j<=n;j++) { fprintf(fichero, "\ntd[%d] >= 0",j); } for(j=1;j<=n;j++) { fprintf(fichero, "\nd[%d] >= 0",j); } for(i=1;i<=n;i++) 44 Appendix A. Anexo { for(j=1;j<=n;j++) { fprintf(fichero, "\n0 <= Z[%d][%d] <= 1",i,j); } } for(r=1;r<=m;r++) { for(j=1;j<=n;j++) { for(b=1;b<=Bines;b++) { { fprintf(fichero, "\n0 <= Bin[%d][%d][%d] <= 1",r,j,b); } } } } //Binary fprintf(fichero, "\nBinary\n"); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { fprintf(fichero, "Z[%d][%d] ",i,j); } } fprintf(fichero, "\n"); for(r=1;r<=m;r++) { for(j=1;j<=n;j++) { for(b=1;b<=Bines;b++) { fprintf(fichero, "Bin[%d][%d][%d] ",r,j,b); } } } //General fprintf(fichero, "\nGeneral\n"); for(r=1;r<=m;r++) { for(j=1;j<=n;j++) { fprintf(fichero, "E[%d][%d] ",r,j); } } for(j=1;j<=n;j++) { fprintf(fichero, "td[%d] ",j); } for(j=1;j<=n;j++) { fprintf(fichero, "d[%d] ",j); } fprintf(fichero, "\nEnd"); fclose(fichero); 45 return 0; } A.0.4 Modelo Idle-time modelo_idle_time(MAT_INT p_ri, int n, int m, int Bines, int T, int P, MAT_INT di,char **argv) { int k,j,i,u,l,b; FILE *fichero=fopen(argv[5],"w"); fprintf(fichero,"Minimize\n"); //FO fprintf(fichero,"td[1]"); for(k=2;k<=n;k++) { fprintf(fichero, " + td[%d]",k); } //Restricciones fprintf(fichero, "\nSubject To"); //R1 for(k=1; k<=n;k++) { fprintf(fichero,"\nR1.%d:",k); fprintf(fichero," x[1][%d]",k); for(j=2;j<=n;j++) { fprintf(fichero, " + x[%d][%d]",j,k); } fprintf(fichero, " = 1"); } //R2 for(j=1; j<=n;j++) { fprintf(fichero,"\nR2.%d:",j); fprintf(fichero," x[%d][1]",j); for(k=2;k<=n;k++) { fprintf(fichero, " + x[%d][%d]",j,k); } fprintf(fichero, " = 1"); } //R3 for(k=1;k<=n-1;k++) { for(i=1;i<=m-1;i++) { fprintf(fichero, "\nR3.%d.%d: I[%d][%d]",k,i,i,k+1); for(u=1;u<=n;u++) { fprintf(fichero, " + %d x[%d][%d]",p_ri[i-1][u-1],u,k+1); } fprintf(fichero, " + H[%d][%d] - H[%d][%d]",i,k+1,i,k); for(u=1;u<=n;u++) { 46 Appendix A. Anexo fprintf(fichero, " - %d x[%d][%d]", p_ri[i][u-1],u,k); } fprintf(fichero, " - I[%d][%d] = 0",i+1,k+1); } } //R4 for(i=1;i<=m-1;i++) { fprintf(fichero, "\nR4.%d: I[%d][1]",i,i); for(u=1;u<=n;u++) { fprintf(fichero, " + %d x[%d][1]", p_ri[i-1][u-1],u); } fprintf(fichero, " + H[%d][1] - I[%d][1] = 0",i,i+1); } //R5 fprintf(fichero, "\nR5: C[%d][0] = 0",m); //R6 for(k=1;k<=n;k++) { fprintf(fichero, "\nR6.%d: td[%d] - C[%d][%d] + d[%d] >= 0",k,k,m,k,k); } //R7 for(k=1;k<=n;k++) { fprintf(fichero, "\nR7.%d: d[%d]",k,k); for(j=1;j<=n;j++) { fprintf(fichero, " - %d x[%d][%d]", di[0][j-1],j,k); } fprintf(fichero, " = 0"); } //R8 for(i=1;i<=m;i++) { for(k=1;k<=n;k++) { fprintf(fichero, "\nR8.%d.%d: C[%d][%d]",i,k,i,k); for(l=1;l<=k;l++) { fprintf(fichero, " - I[%d][%d]",i,l); for(j=1;j<=n;j++) { fprintf(fichero, " - %d x[%d][%d]",p_ri[i-1][j-1],j,l); } } fprintf(fichero, " = 0"); } } //R9 for(i=1;i<=m;i++) { for(k=1;k<=n;k++) { for(b=1;b<=Bines;b++) { 47 fprintf(fichero, "\nR9.%d.%d.%d: C[%d][%d] + %d Bin[%d][%d][%d] <= %d",i,k,b,i,k,P,i,k,b,b*T+P); } } } //R10 for(i=1;i<=m;i++) { for(k=1;k<=n;k++) { for(b=1;b<=Bines;b++) { fprintf(fichero, "\nR10.%d.%d.%d: C[%d][%d]",i,k,b,i,k); for(j=1;j<=n;j++) { fprintf(fichero, " - %d x[%d][%d]", p_ri[i-1][j-1],j,k); } fprintf(fichero, " - %d Bin[%d][%d][%d] >= %d",P,i,k,b,T*(b-1)-P ); } } } //R11 for(i=1;i<=m;i++) { for(k=1;k<=n;k++) { fprintf(fichero, "\nR11.%d.%d: Bin[%d][%d][1] ",i,k,i,k); for(b=2;b<=Bines;b++) { fprintf(fichero, " + Bin[%d][%d][%d]",i,k,b); } fprintf(fichero, " = 1"); } } //Bounds fprintf(fichero, "\nBounds"); for(i=1;i<=m;i++) { for(k=1;k<=n;k++) { fprintf(fichero, "\nC[%d][%d] >= 0",i,k); } } for(i=1;i<=m;i++) { for(k=1;k<=n;k++) { fprintf(fichero, "\nI[%d][%d] >= 0",i,k); } } for(k=1;k<=m;k++) { for(i=1;i<=n;i++) { fprintf(fichero, "\nH[%d][%d] >= 0",k,i); } 48 Appendix A. Anexo } for(k=1;k<=n;k++) { fprintf(fichero, "\ntd[%d] >= 0",k); } for(k=1;k<=n;k++) { fprintf(fichero, "\nd[%d] >= 0",k); } for(j=1;j<=n;j++) { for(k=1;k<=n;k++) { fprintf(fichero, "\n0 <= x[%d][%d] <= 1",j,k); } } for(i=1;i<=m;i++) { for(k=1;k<=n;k++) { for(b=1;b<=Bines;b++) { { fprintf(fichero, "\n0 <= Bin[%d][%d][%d] <= 1",i,k,b); } } } } //Binary fprintf(fichero, "\nBinary\n"); for(j=1;j<=n;j++) { for(k=1;k<=n;k++) { fprintf(fichero, "x[%d][%d] ",j,k); } } fprintf(fichero, "\n"); for(i=1;i<=m;i++) { for(k=1;k<=n;k++) { for(b=1;b<=Bines;b++) { fprintf(fichero, "Bin[%d][%d][%d] ",i,k,b); } } } //General fprintf(fichero, "\nGeneral\n"); for(i=1;i<=m;i++) { for(k=1;k<=n;k++) { fprintf(fichero, "C[%d][%d] ",i,k); } } 49 for(i=1;i<=m;i++) { for(k=1;k<=n;k++) { fprintf(fichero, "I[%d][%d] ",i,k); } } for(k=1;k<=m;k++) { for(i=1;i<=n;i++) { fprintf(fichero, "H[%d][%d] ",k,i); } } for(k=1;k<=n;k++) { fprintf(fichero, "td[%d] ",k); } for(k=1;k<=n;k++) { fprintf(fichero, "d[%d] ",k); } fprintf(fichero, "\nEnd"); fclose(fichero); return 0; } A.0.5 Modelo Completion-time modelo_completion_time(MAT_INT p_ri, int n, int m, int Bines, int T, int P, MAT_INT di,char **argv) { int k,i,j,b; FILE *fichero=fopen(argv[5],"w"); fprintf(fichero,"Minimize\n"); //FO fprintf(fichero,"td[1]"); for(k=2;k<=n;k++) { fprintf(fichero, " + td[%d]",k); } //Restricciones fprintf(fichero, "\nSubject To"); //R1 for(k=1; k<=n;k++) { fprintf(fichero,"\nR1.%d:",k); fprintf(fichero," x[1][%d]",k); for(j=2;j<=n;j++) { fprintf(fichero, " + x[%d][%d]",j,k); } fprintf(fichero, " = 1"); } //R2 56 Appendix A. Anexo return 0; } A.0.7 Modelo LYeq modelo_LYeq(MAT_INT p_ri, int n, int m, int Bines,int T, int P, MAT_INT di,char **argv) { int i,r,k,b; FILE *fichero=fopen(argv[5],"w"); fprintf(fichero,"Minimize\n"); //FO fprintf(fichero,"td[1]"); for(i=2;i<=n;i++) { fprintf(fichero, " + td[%d]",i); } //Restricciones fprintf(fichero, "\nSubject To"); //R1 for(i=1; i<=n;i++) { fprintf(fichero, "\nR1.%d: C[1][%d] >= %d",i,i,p_ri[0][i-1]); } //R2 for(r=1;r<=m-1;r++) { for(i=1;i<=n;i++) { fprintf(fichero, "\nR2.%d.%d: C[%d][%d] - C[%d][%d] >= %d",r,i,r+1,i ,r,i,p_ri[r][i-1]); } } //R3 { for(r=1;r<=m;r++) { for(i=1;i<=n-1;i++) { for(k=i+1;k<=n;k++) { fprintf(fichero, "\nR3.%d.%d.%d: %d D[%d][%d] + C[%d][%d] - C [%d][%d] - Q[%d][%d][%d] = %d",r,i,k,P,i,k,r,i,r,k,r,i,k, p_ri[r-1][i-1]); } } } } //R4 { for(r=1;r<=m;r++) { for(i=1;i<=n-1;i++) 57 { for(k=i+1;k<=n;k++) { fprintf(fichero, "\nR4.%d.%d.%d: Q[%d][%d][%d] <= %d",r,i,k,r ,i,k,P-p_ri[r-1][i-1]-p_ri[r-1][k-1]); } } } } //R5 for(r=1;r<=m;r++) { for(i=1;i<=n;i++) { for(b=1;b<=Bines;b++) { fprintf(fichero, "\nR5.%d.%d.%d: C[%d][%d] + %d Bin[%d][%d][%d] <= %d",r,i,b,r,i,P,r,i,b,P+(b*T)); } } } //R6 for(r=1;r<=m;r++) { for(i=1;i<=n;i++) { for(b=1;b<=Bines;b++) { fprintf(fichero, "\nR6.%d.%d.%d: C[%d][%d] - %d Bin[%d][%d][%d] >= %d",r,i,b,r,i,P,r,i,b,T*(b-1)+p_ri[r-1][i-1]-P); } } } //R7 for(r=1;r<=m;r++) { for(i=1;i<=n;i++) { fprintf(fichero, "\nR7.%d.%d: Bin[%d][%d][1] ",r,i,r,i); for(b=2;b<=Bines;b++) { fprintf(fichero, " + Bin[%d][%d][%d]",r,i,b); } fprintf(fichero, " = 1"); } } //R8 for(i=1;i<=n;i++) { fprintf(fichero, "\nR8.%d: td[%d] - C[%d][%d] >= %d",i,i,m,i,-di[0][i -1]); } //Bounds fprintf(fichero, "\nBounds"); for(r=1;r<=m;r++) { for(i=1;i<=n;i++) 58 Appendix A. Anexo { fprintf(fichero, "\nC[%d][%d] >= 0",r,i); } } for(r=1;r<=m;r++) { for(i=1;i<=m;i++) { for(k=1;k<=n;k++) { fprintf(fichero, "\nQ[%d][%d][%d] >= 0",r,i,k); } } } for(i=1;i<=n;i++) { fprintf(fichero, "\ntd[%d] >= 0",i); } for(i=1;i<=n;i++) { for(k=1;k<=n;k++) { fprintf(fichero, "\n0 <= D[%d][%d] <= 1",i,k); } } for(r=1;r<=m;r++) { for(i=1;i<=n;i++) { for(b=1;b<=Bines;b++) { { fprintf(fichero, "\n0 <= Bin[%d][%d][%d] <= 1",r,i,b); } } } } //Binary fprintf(fichero, "\nBinary\n"); for(i=1;i<=n;i++) { for(k=1;k<=n;k++) { fprintf(fichero, "D[%d][%d] ",i,k); } } fprintf(fichero, "\n"); for(r=1;r<=m;r++) { for(i=1;i<=n;i++) { for(b=1;b<=Bines;b++) { fprintf(fichero, "Bin[%d][%d][%d] ",r,i,b); } } } 59 //General fprintf(fichero, "\nGeneral\n"); for(r=1;r<=m;r++) { for(i=1;i<=n;i++) { fprintf(fichero, "C[%d][%d] ",r,i); } } for(r=1;r<=m;r++) { for(i=1;i<=m;i++) { for(k=1;k<=n;k++) { fprintf(fichero, "Q[%d][%d][%d] ",r,i,k); } } } for(i=1;i<=n;i++) { fprintf(fichero, "td[%d] ",i); } fprintf(fichero, "\nEnd"); fclose(fichero); return 0; } Índice de Figuras 2.1 Diagrama de Gantt sin restricción de disponibilidad en las máquinas 4 2.2 Diagrama de Gantt con restricción de disponibilidad en las máquinas 4 4.1 Medias de cada modelo y media total 23 4.2 Diagrama de cajas y bigotes. CPU Time por modelo 23 4.3 Diagrama de cajas y bigotes reducido. CPU Time por modelo 24 4.4 Función de densidad para cada periodo de disponibilidad (T) 25 4.5 Diagrama de cajas y bigotes. CPU Time por modelo y periodo de disponibilidad (T) 26 4.6 Diagrama de cajas y bigotes. CPU Time por modelo y periodo de disponibilidad (T) para valores del CPU Time menores que 6. 26 4.7 Media y desviación estándar de cada modelo para cada número de trabajos 27 4.8 Media y desviación estándar de cada modelo para cada número de máquinas 28 61 Índice de Tablas 4.1 Modelos objeto de estudio 22 4.2 CPU Time (s) medio, desviación estándar y porcentaje de instancias para las que se garantiza optimalidad por modelo. 22 4.3 CPU Time(s) medio y desviación estándar en función del modelo y el periodo de disponibilidad (T) 27 4.4 CPU Time(s) medio y desviación estándar en función del modelo y el número de trabajos (N). 28 4.5 CPU Time(s) medio y desviación estándar en función del modelo y el número de máquinas (M) 29 63 Bibliografía Baker, K. R. (2013). Computational results for the flowshop tardiness problem. Computers and Industrial Engineering, 64(3):812–816. Framinan, J. M., Leisten, R., and Ruiz García, R. (2014). Manufacturing Scheduling Systems. An Integrated View on Models, Methods and Tools. Graham, R., Lawler, E. L., Lenstra, J. K., and Rinnooy Kan, A. (1979). Optimization and heuristic in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5:287–326. Ramos Salgado, C. (2017). Soluciones exactas para el problema de flowshop de permutación con restricciones de disponibilidad periódicas. Stafford, E. F., Tseng, F. T., and Gupta, J. N. (2005). Comparative evaluation of MILP flowshop models. Journal of the Operational Research Society, 56(1):88–101. 65