Minimización de los tiempos ociosos de las máquinas en el taller de flujo de permutación

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 de Fin de Grado Grado en Ingeniería de las Tecnologías Industriales Minimización de los tiempos ociosos de las máquinas en el taller de flujo de permutación Autor: Juan Raúl Castaño Huertas Tutor: Paz Pérez González Dpto. de Organización Industrial y Gestión de Empresas Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2020 Trabajo de Fin de Grado Grado en Ingeniería de las Tecnologías Industriales Minimización de los tiempos ociosos de las máquinas en el taller de flujo de permutación Autor: Juan Raúl Castaño Huertas Tutor: Paz Pérez González Profesor Titular Dpto. de Organización Industrial y Gestión de Empresas Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2020 Trabajo de Fin de Grado: Minimización de los tiempos ociosos de las máquinas en el taller de flujo de permutación Autor: Juan Raúl Castaño Huertas 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: Agradecimientos A mi abuelo, por estar conmigo durante todo el camino. Juan Raúl Castaño Huertas Sevilla, 2020 I Resumen En este Trabajo de Fin de Grado se aborda el problema de la programación de operaciones en un entorno de taller de flujo regular con permutación (permutation flowshop scheduling) proponiendo un método de resolución en el caso de la minimización de tiempo ocioso de las máquinas. Para ello, se hará una revisión de los conceptos fundamentales que involucra el problema, así como de algunos de los métodos utilizados para resolverlo para otros objetivos. Finalmente, se adaptan algunos de los métodos ya existentes y se desarrollan nuevas propuestas, analizando tanto la calidad de las soluciones obtenidas como los tiempos de ejecución de los algoritmos utilizados. III XÍndice de Figuras 5.11 Tiempos de ejecución acumulados de cada método implementado con la PRC34 5.12 ARPD del método NEHLJP implementado con la PRCen función de la dimensión de los problemas 36 5.13 ARPD del método NEHLJP implementado con la PRCen función de los pesos de los problemas 37 5.14 Tiempos de ejecución del método NEHLJP implementado con la PRC37 5.15 Tiempos de ejecución acumulados del método NEHLJP implementado con la PRC38 5.16 ARPD del método NEHLJP original vs el NEHLJP implementado con la PRC38 5.17 ARPD de cada priority rule implementada con la TBCen función de la dimensión de los problemas 40 5.18 ARPD de cada priority rule implementada con la TBCen función de los pesos de los problemas 41 5.19 Tiempos de ejecución de cada priority rule implementada con la TBC41 5.20 Tiempos de ejecución acumulados de cada priority rule implementada con la TBC42 Índice de Tablas 2.1 Notación utilizada en el documento 12 4.1 Grupos de problemas según su tamaño 23 5.1 ARPD de cada priority rule en función de la dimensión de los problemas 26 5.2 ARPD de cada priority rule en función de los pesos de los problemas 26 5.3 Tiempos de ejecución de cada priority rule 26 5.4 ARPD de cada método en función de la dimensión de los problemas 28 5.5 ARPD de cada método en función de los pesos de los problemas 29 5.6 Tiempos de ejecución de cada método 29 5.7 ARPD de cada tie breaking rule implementada con la PRCen función de la dimensión de los problemas 32 5.8 ARPD de cada tie breaking rule implementada con la PRCen función de los pesos de los problemas 32 5.9 Tiempos de ejecución de cada tie breaking rule implementada con la PRC33 5.10 ARPD del método NEHLJP implementado con la PRCen función de la dimensión de los problemas 35 5.11 ARPD del método NEHLJP implementado con la PRCen función de los pesos de los problemas 35 5.12 Tiempos de ejecución del método NEHLJP implementado con la PRC36 5.13 Diferencia entre la calidad de los resultados del NEHLJP original y el NEHLJP implementado con la PRC38 5.14 ARPD de cada priority rule implementada con la TBCen función de la dimensión de los problemas 39 5.15 ARPD de cada priority rule implementada con la TBCen función de los pesos de los problemas 39 5.16 Tiempos de ejecución de cada priority rule implementada con la TBC40 1 ARPD de cada priority rule en función de las características de los problemas 73 2 ARPD de cada método en función de las características de los problemas 77 3 ARPD de cada tie breaking rule implementada con la PRCen función de las características de los problemas 80 4 ARPD del método NEHLJP implementado con la PRCen función de las características de los problemas 83 5 ARPD de cada priority rule implementada con la TBCen función de las características de los problemas 86 XI 1 Introducción y objetivos En este capítulo se pretende introducir al lector a la temática de la programación de operaciones, así como ponerle en contexto en cuanto al objetivo del problema que se pretende resolver y su justificación. También se explican tanto la estructura que sigue el propio documento como el contenido en cada una de sus partes. Asimismo, a medida que se avance en la lectura, se irá introduciendo terminología en inglés, siendo esta identificada por aparecer en cursiva, y que será explicada a medida que vaya apareciendo. Por último, se hará uso de siglas, pertenecientes a sus respectivas expresiones en inglés, habiendo sido todas y cada una de ellas definidas con anterioridad. La programación de operaciones (operation scheduling) ocupa un papel muy importante en la industria, ya que puede suponer importantes mejoras en el desempeño de una empresa, sea cual sea su campo de producción (sector automovilístico, productos tecnológicos, etc.). Aumentos en el rendimiento, tales como el aumento de la productividad a través de la disminución de los tiempos de proceso totales, la disminución de los tiempos ociosos de las máquinas entre trabajos o de los retrasos en los trabajos son algunas de las ventajas que se pueden lograr con una eficiente programación de las operaciones de una empresa. Por otra parte, el entorno de taller de flujo uniforme (flowshop), es uno de los tipos de problema más extendidos en la actualidad, debido a que es el que más se asemeja a la configuración real de la mayor parte de los sistemas productivos de la industria. 1.1 Objetivos del proyecto En este trabajo se tiene como principal objetivo analizar la eficiencia de distintos algoritmos, cuyo propósito es minimizar la suma ponderada entre el máximo tiempo de terminación de una serie de trabajos en flujo uniforme con permutación (permutation flowshop scheduling) y la suma de los tiempos ociosos de las máquinas entre trabajos (core idle time). Para ello, se propone un nuevo algoritmo, que será comparado con algunos de los mejores algoritmos presentes en la actualidad: el propuesto por Víctor Fernández – Viagas y José Manuel Framiñán (Fernández – Viagas, Framiñán, 2014), Weibo Liu, Yan Jin y Mark Price (Weibo Liu, Yan Jin, Mark Price, 2016) y el algoritmo en que ambos métodos están basados, propuesto por Muhammad Nawaz, E. Emory Enscore e Inyong Ham (Nawaz, Enscore, Ham, 1983). 1 2Capítulo 1. Introducción y objetivos Figura 1.1 Diagrama de flujo de información en un sistema de fabricación. Para comprobar la eficiencia de los métodos anteriormente mencionados se compararán la calidad de las soluciones obtenidas mediante la desviación porcentual relativa promedio (Average relative percentage deviation) o ARPD, así como los tiempos de ejecución de cada uno de ellos. 1.2 Justificación Mediante la correcta programación de operaciones se puede lograr una disminución significativa en el tiempo total de proceso, lo que se traduce en un ahorro de costes para la empresa. Además, atendiendo al criterio de la disminución de los tiempos ociosos de las máquinas, se consigue aumentar la eficiencia de cada una de las máquinas por separado. El estudio de este tipo de problemas atiende a la necesidad de disminuir el tiempo y los recursos necesarios para resolverlos de forma óptima, ya que muchos de los problemas de tipo flowshop pertenecen a la clasificación de no polinomiales o NP-hard, que como será explicado posteriormente, necesitan de una basta cantidad de tiempo y recursos para encontrar una solución óptima al problema a tratar. Es por eso por lo que se hace uso de algoritmos que permitan encontrar una solución lo suficientemente próxima a la solución óptima del problema en una cantidad de tiempo razonable. 1.3 Estructura del documento 3 1.3 Estructura del documento El presente documento está estructurado en 6 capítulos, a lo largo de los cuales se desarrollarán los siguientes puntos: En el primer capítulo se hace una breve introducción del problema a tratar en este trabajo y los objetivos que se pretenden, pasando por la justificación del mismo. Por último, se explica la estructura que sigue el documento. En el capítulo segundo se describe el problema, tratando aspectos tales como la notación, el entorno, las restricciones a los que está sujeto y el objetivo a optimizar. Previamente a la presentación de dichas particularidades se hará una introducción a la programación de la producción, con el fin de ayudar al lector a entender de una mejor manera el contexto en el que se sitúa el problema. En el tercer capítulo se realiza una descripción de los algoritmos que han sido puestos en práctica para la comparación de las distintas soluciones al problema, explicando los pasos que sigue cada uno de ellos. En el cuarto capítulo se introduce Matlab, el software utilizado para implementar los 4 algoritmos utilizados para los experimentos, calcular y comparar las soluciones obtenidas. También se describen las instancias utilizadas para comparar dichos algoritmos, así como los indicadores usados para evaluar las soluciones. En el capítulo quinto se muestran y analizan los resultados obtenidos. Por último, en el sexto capítulo se exponen las conclusiones extraídas de los resultados mostrados en el capítulo 5. 2 Descripción del problema En este capítulo se describirá el problema objetivo de este trabajo. Tal y como se ha mencionado en el capítulo 1, se realizará una introducción previa a la programación de la producción, para posteriormente abordar las distintas particularidades del problema. 2.1 Programación de la producción La programación de la producción (manufacturing scheduling) es la rama de la organización de la producción (production management) que se encarga de asignar una serie de trabajos o recursos en el tiempo con el fin de hacer dicho proceso de producción más eficiente, ya sea disminuyendo los tiempos totales de proceso, la utilización de recursos o los costes para la empresa. Dicha asignación da lugar a un programa (production schedule), que identifica cada trabajo (job) e indica cuándo debe ser procesado en cada máquina (machine). Una de las herramientas más utilizadas para representar dichos programas de forma gráfica es el diagrama de Gantt, desarrollado por Henry Laurence Gantt entre 1910 y 1915, donde se representan las máquinas o las operaciones que componen un trabajo (vertical) frente al tiempo (horizontal). A partir de este diagrama pueden identificarse tanto las fechas de comienzo y fin de cada trabajo como su duración. Figura 2.1 Diagrama de Gantt [4]. 5 6Capítulo 2. Descripción del problema Figura 2.2 Diagrama de Gantt de dos secuencias diferentes [5]. La programación de la producción es catalogada como un proceso de toma de decisiones, y es ampliamente utilizado en el ámbito industrial, tanto en producción y ensamblaje como en la planificación de proyectos. Su cometido es el de encontrar al menos un programa admisible (feasible schedule) que logre optimizar cierto objetivo, atendiendo al mismo tiempo a las restricciones que envuelven al problema en cuestión. En el caso de que se hubieran encontrado más de un programa admisible, se deberá elegir aquel cuya solución mejor satisfaga el objetivo del problema. 2.2 Algoritmos El método utilizado para obtener un programa admisible recibe el nombre de algoritmo. Un algoritmo es una sucesión finita de operaciones ordenadas que tiene como objetivo la obtención de una solución a un problema. Dicha solución puede ser exacta o aproximada. Se entiende como solución exacta aquella que proporciona un resultado óptimo a un problema, mientras que una solución aproximada ofrecerá un resultado que, aun a pesar de no ser el óptimo, se le acerca de una forma (más o menos) razonable. Los algoritmos de aproximación resultan especialmente interesantes en aquellos casos en los que calcular la solución óptima de un problema requiere una gran cantidad de recursos. Es el caso del problema de flowshop tratado en el presente trabajo, del que se hablará en la sección 2.3 de este capítulo. 2.3 Conceptos básicos A continuación, se definen algunos de los elementos básicos que componen un problema de programación de la producción, junto con la notación que se va a usar para designarlas en este trabajo: • Máquina (machine): “Recurso productivo con capacidad para realizar operaciones de transformación/transporte de material” [ 4 ]. Hay un total de mmáquinas, designadas por el subíndice i. • Trabajo (job): “Producto que es objeto de una operación en alguna de las máquinas de la fábrica” [4]. Hay un total de ntrabajos, designados por el subíndice j. • Ruta (route): La ruta indica el orden que debe seguir un trabajo a la hora de procesarse. Es un vector de mcomponentes, que contiene los números asociados a cada una de las mmáquinas. Existen un total de nrutas, una por cada trabajo, designadas mediante la notación Rj. De este modo, tomando como ejemplo la ruta R2 =(3,1,2), el trabajo 2 deberá procesarse primero en la máquina 3, después en la 1 y por último en la 2. • Secuencia (sequence): Es un vector formado por ncomponentes. Contiene los números asociados a cada uno de los ntrabajos que, por orden, deben procesarse en cada máquina. 2.3 Conceptos básicos 7 Puede haber un total de mmáquinas o únicamente una, en caso de que todos los trabajos sean procesados en el mismo orden. La secuencia se designa mediante la notación Si. • Tiempo de proceso (processing time): El tiempo de proceso pi j indica el tiempo que el trabajo jtarda en procesarse en la máquina i. Figura 2.3 Ejemplo de diferentes tiempos de proceso para cada trabajo en las distintas máquinas [4]. • Fecha de llegada (release date): Instante de tiempo en el cual el trabajo jpasa a estar disponible para procesarse, representado por rj. • Fecha de entrega (due date): La fecha de entrega dj es el instante de tiempo en el que, como máximo, un trabajo debe acabar de procesarse. • Peso (weight): Sirve como método de ponderación para indicar la importancia de un trabajo. Se designa mediante la notación wj. • Tiempo de terminación (completion time): Instante de tiempo en el que el trabajo j termina de procesarse en la última máquina. Representado por Cj. • Tiempo de flujo (flowtime): Tiempo total que el trabajo permanece en el entorno, desde que está disponible hasta que termina de procesarse en la última máquina. Se define como Fj=Cj−rj. •Retraso (lateness): Retraso del trabajo j, definido como Lj=Cj−dj. 14 Capítulo 3. Descripción de los algoritmos Figura 3.1 Pseudocódigo del algoritmo NEH [4]. Figura 3.2 Ejemplo del método de inserción, en el que un trabajo es intercambiado de la posición j a la posición kde una secuencia [4]. 3.2 NEHFF El algoritmo NEH FF es una variante del NEH desarrollada en 2014 por Víctor Fernández – Viagas y José M. Framiñán (Fernández – Viagas, Framiñán, 2014) que, mediante la implementación de la regla de desempate TB FF , se ha consolidado como uno de los mejores algoritmos usados para resolver problemas del tipo Fm|prmu|Cmax hasta la fecha. Las reglas de desempate, o tie-breaking rules, son herramientas de decisión que sirven para resolver los desempates que pueden darse a la hora de elegir una secuencia parcial óptima durante la fase de inserción. La TB FF está basada en la disminución de los idle-time, resolviendo los desempates a favor de la secuencia parcial cuya suma entre el front delay y el core idle-time sea la de menor valor. El cálculo de esta suma se realiza de la siguiente manera: • Primero se calculan los core idle-time de cada máquina: CIT i=∑n j=2max(Ci j −pi j −Ci,j−1,0) • En segundo lugar se calculan los front delay de cada máquina, a los que se les asignará la notación de FIT (front idle-time): FIT i=∑i−1 k=1pi−k,1, siendo FIT1=0. • A continuación, se suman los CIT y los FIT para obtener los idle-time de cada máquina: IT i=∑m i=1FIT i+CIT i • Por último, se suman todos los ITi ( ∑m i=1IT i ), dando como resultado el idle-time total de la secuencia. Una vez introducida la regla de desempate, se pasa a enumerar los pasos que ha de seguir el algoritmo: En primer lugar, se ejecuta la priority rule del algoritmo NEH: •Primero: Se calculan los Pjde todos los trabajos. •Segundo: Se ordenan los trabajos de mayor a menor según sus Pj. 3.3 NEHLJP 15 Una vez se tiene la secuencia inicial, es hora de pasar a la inserción. Para ello, se partirá de la secuencia parcial formada por los 2 primeros trabajos, en la que se irán insertando el resto de trabajos siguiendo la tie-breaking rule TBFF : • Tercero: Se seleccionan los dos primeros trabajos y se determina la secuencia parcial óptima. • Cuarto: Para el resto de los trabajos (de j=3 a j=n ), se inserta el j-ésimo trabajo en todas las posiciones posibles y se retiene aquella secuencia cuya función objetivo sea la de menor valor. En caso de que haya más de una secuencia con el mismo valor de la función objetivo, se aplicará el método TB FF , siendo seleccionada aquella secuencia cuyo IT asociado sea el de menor valor. •Quinto: Repetir el cuarto paso hasta que todos los trabajos hayan sido insertados (j=n). 3.3 NEHLJP Creado en 2016 por Weibo Liu, Yan Jin y Mark Price (Weibo Liu, Yan Jin y Mark Price, 2016), el NEH LJP es uno de los algoritmos más recientes que, basándose en la heurística del NEH, ha sido diseñado para resolver el problema de permutation flowshop con los objetivos de makespan ycore idle-time ( Fm|prmu|Cmax,∑CITi ). Para ello, sus autores proponen una nueva regla de prioridad, basada en indicadores estadísticos, así como una regla de desempate. 3.3.1 PRLJP La priority rule que se propone en este algoritmo consiste en ordenar de mayor a menor los trabajos en función de: AVGj+MADj+abs(SKE j)1 3+1 KURj 1 4! A continuación se definen cada uno de los términos de la expresión anterior: • AVG: El average processing time se corresponde con la media de los processing time del trabajo jen todas las máquinas: AVGj=1 m∑m i=1pi j • MAD: Este término hace referencia a la desviación absoluta media (mean absolute deviation) de los processing time del trabajo j:MADj=1 m∑m i=1|pi j −AVGj| La desviación absoluta se utiliza como una medida de la dispersión, lo que permite conocer cómo se distribuyen los valores de una población con respecto a la media. En la figura 3.3 se puede observar cómo dos poblaciones, a pesar de compartir la misma media, presentan distribuciones muy diferentes. Por ello, estudiar la dispersión resulta de gran interés a la hora de trabajar con conjuntos de datos. 16 Capítulo 3. Descripción de los algoritmos Figura 3.3 Diferencia entre dos poblaciones de igual media y diferente dispersión. • SKE: La asimetría, o skewness, es un indicador estadístico que sirve para conocer la tendencia de una población a desviarse de la media. Se define de la siguiente manera: SKE j= 1 m∑m i=1(pi j −AVGj)3 q1 m∑m i=1(pi j −AVGj)23 Figura 3.4 Efecto del skewness en una función [1]. 3.3 NEHLJP 17 • KUR: La curtosis (en inglés kurtosis) indica la concentración de los valores de una población con respecto a la media. Su expresión matemática se puede escribir como: KURj= 1 m∑m i=1(pi j −AVGj)4 q1 m∑m i=1(pi j −AVGj)22 Figura 3.5 Efecto de la curtosis en una función [1]. 3.3.2 TBLJP La regla de desempate del algoritmo NEH LJP está basada en los tiempos de flujo dinámicos o dynamic flowtimes, partiendo de la idea de que “minimizar los tiempos de flujo conduce a una disminución del makespan, así como a un aumento de los tiempos ociosos de las máquinas, y viceversa” [11]. Se entiende por dynamic flowtime la cantidad de tiempo transcurrido entre el instante en que un trabajo comienza a procesarse en la primera máquina y el instante en que termina de procesarse en la última (no confundir este concepto con el flowtime, explicado en la sección 4.2. Se expresa de la siguiente forma: ¯ fj=Cm j −C1,j−1 , siendo Ci j el instante de tiempo en que el trabajo jtermina de procesarse en la máquina i. Atendiendo a lo explicado anteriormente, la TB LJP consiste en elegir aquella secuencia que proporcione el mayor valor para la expresión dada por: ¯ f−q1 n−1∑n jfj−¯ f2 Cmax donde ¯ f=1 n∑n j=1fjrepresenta la media de los dynamic flowtime de cada trabajo. 3.3.3 Algoritmo NEHLJP Atendiendo a todo lo expuesto anteriormente, el algoritmo NEH LJP se ejecuta siguiendo los siguientes pasos: •Primero: Se calcula el valor de AV Gj+MADj+abs(SKE j)1 3+1 KURj 1 4para cada uno. 18 Capítulo 3. Descripción de los algoritmos • Segundo: Se ordenan los trabajos de mayor a menor en función de los valores calculados en el paso primero. • Tercero: Se seleccionan los dos primeros trabajos y se determina la secuencia parcial óptima. • Cuarto: Para el resto de los trabajos (de j=3 a j=n ), se inserta el j-ésimo trabajo en todas las posiciones posibles y se retiene aquella secuencia cuya función objetivo sea la de menor valor. En caso de que haya más de una secuencia con el mismo valor de la función objetivo, se seleccionará aquella que proporcione el mayor valor de ¯ f−q1 n−1∑n j(fj−¯ f)2 Cmax ! •Quinto: Repetir el cuarto paso hasta que todos los trabajos hayan sido insertados (j=n). 3.4 Algoritmo propuesto: NEHC El algoritmo que se propone en este trabajo consiste en una variante del algoritmo NEH original, diseñada para disminuir los core idle-time de las máquinas y así cumplir con los dos objetivos del problema que se plantea (min w∗Cmax + (1−w)∗∑m i=1CIT i). Para ello, se introduce una regla de prioridad basada en la PR del NEH, así como una nueva regla de desempate, fundamentada en el concepto de la utilización de las máquinas, que será explicado en la sección 4.2. 3.4.1 PRC La priority rule, designada como PR C , consiste en ordenar los trabajos de mayor a menor en función de: m ∑ i=1 pi j+ m ∑ i=1pi j −¯p+Rj! donde Rj representa el rango de los processing times del trabajo j, es decir, la diferencia entre el valor máximo y el mínimo de los pi j , que se calcula como: Rj=max(pi j)−min(pi j),i∈(1,2, ...m) . Como se ha explicado en la sección 3.3.1, la desviación absoluta, correspondiente al segundo término de la expresión de la PR C , sirve para cuantificar la dispersión de los processing times de cada trabajo. Conocer información relativa a la dispersión de los valores de una población permite asignar una mayor prioridad a aquellas tareas que presenten una mayor variabilidad en sus tiempos de proceso, y así atenuar los efectos negativos que pueda tener sobre la solución final. Para complementar la información proporcionada por la desviación absoluta se incluye también el rango, que permite acotar los intervalos entre los que se mueven los tiempos de proceso. Un rango menor implica valores de dispersión menores, y por consiguiente, tiempos de proceso más uniformes. De este modo, aquellos trabajos cuyo rango sea mayor deberán ser procesados antes que el resto. 3.4.2 TBC La regla de desempate que se propone, como se ha mencionado anteriormente, está basada en el concepto de utilización, que hace referencia al grado en que una máquina es aprovechada, o dicho de otra forma, qué porcentaje del tiempo se está procesando un trabajo con respecto al tiempo total en el que una máquina permanece en funcionamiento. La utilización de una máquina i se puede definir de la siguiente manera: Ui=∑n j=1pi j ∑n j=1pi j +CITi 3.4 Algoritmo propuesto: NEHC19 Para un problema de m máquinas se utiliza la media de los factores de utilización: U=1 m m ∑ i=1 ∑n j=1pi j ∑n j=1pi j +CITi Es fácil comprobar que, a medida que la utilización de una máquina aumenta, su core idle-time disminuye. Por lo tanto, la tie-breaking rule del algoritmo NEH C resolverá los desempates a favor de la secuencia que tenga una mayor utilización media. Figura 3.6 Utilización media de un conjunto de máquinas [11]. 3.4.3 Algoritmo NEHC Basado en las reglas de prioridad y desempate descritas en las secciones 3.4.1 y 3.4.2 se propone el algoritmo NEHC, cuya ejecución se lleva a cabo siguiendo los pasos enumerados a continuación: • Primero: Se calcula el valor de ∑m i=1pi j+∑m i=1pi j −¯p+Rj para cada uno de los trabajos. • Segundo: Se ordenan los trabajos de mayor a menor en función de los valores calculados en el paso primero. • Tercero: Se seleccionan los dos primeros trabajos y se determina la secuencia parcial óptima • Cuarto: Para el resto de los trabajos (de j=3 a j=n ), se inserta el j-ésimo trabajo en todas las posiciones posibles y se retiene aquella secuencia cuya función objetivo sea la de menor valor. En caso de que haya más de una secuencia con el mismo valor de la función objetivo, se resolverá el empate a favor de la secuencia con el mayor valor de U=1 m∑m i=1 ∑n j=1pi j ∑n j=1pi j+CITi •Quinto: Repetir el cuarto paso hasta que todos los trabajos hayan sido insertados (j=n). 4 Desarrollo de los métodos En este capítulo se expone el software utilizado para la implementación de los algoritmos descritos en el capítulo 3, la resolución de los problemas y el posterior análisis de los resultados obtenidos. También se presentan los problemas elegidos para efectuar las pruebas anteriormente mencionadas, así como los distintos parámetros utilizados para ello. Finalmente, se describen los indicadores con los que se realizará la comparación de los algoritmos. 4.1 Programación de los algoritmos El programa elegido para la resolución de los problemas, Matlab, es un software lanzado por la compañía MathWorks en 1984. Matlab posee su propio lenguaje de programación, llamado “lenguaje M”, en el cual se han implementado los algoritmos. Una de las principales ventajas con respecto a otros entornos de programación es la facilidad para la creación y manejo de funciones, lo cual ha resultado de especial utilidad debido al carácter iterativo de los algoritmos. La posibilidad de examinar la información almacenada en las variables directamente desde el workspace es otra de las virtudes de este software, ya que al disponer los valores en celdas permite que su exportación a Excel se pueda llevar a cabo de forma rápida y sencilla sin necesidad de cambiar su formato. Figura 4.1 Workspace de Matlab. 21 22 Capítulo 4. Desarrollo de los métodos Figura 4.2 Formato de los datos almacenados en una matriz. Por otra parte, el programa que se ha elegido para el análisis y comparación de los resultados es Microsoft Excel, debido a la amplia variedad que presenta en cuanto a tablas y gráficos con los que poder representar y comparar información. Figura 4.3 Análisis de soluciones en Microsoft Excel. Finalmente, se deben considerar las siguientes condiciones experimentales: • Se utilizará el mismo ordenador durante todo el experimento. En este caso se trata de un equipo personal con procesador INTEL CORE i7-6500U CPU, 2.50GHz y 12GB de memoria RAM. • Se utilizará el mismo leguaje (lenguaje M), programa (Matlab R2020b,Microsoft Excel) y sistema operativo (Microsoft Windows 10 Home). Además, se hará uso de las mismas librerías y funciones. • Se utilizarán las mismas instancias para las comparaciones. De esto se hablará con más detalle en la siguiente sección. 4.2 Generación de las instancias 23 4.2 Generación de las instancias Para comparar la eficacia de los algoritmos se han escogido las instancias de Taillard (Éric Taillard, 1993), en las que se proponen 120 instancias, divididas en 12 grupos de 10 problemas cada uno, cuyos tiempos de proceso han sido generados a partir de una distribución uniforme, tomando valores de entre 1 y 99. Dichos grupos han sido divididos en función del número de máquinas y trabajos que los componen, expuestos en la tabla 4.1. Dado que el valor de la función objetivo depende de la ponderación que se le asigne a cada objetivo, se estudiará cada problema variando el parámetro w entre 0 y 1 en intervalos de 0.1, lo que originará un total de 1320 problemas. Tabla 4.1 Grupos de problemas según su tamaño. Máquinas Trabajos 5 20 10 20 20 20 5 50 10 50 20 50 5 100 10 100 20 100 10 200 20 200 20 500 Figura 4.4 Instancias de Taillard: disposición de los problemas [Fuente: http://mistic.heigvd.ch/taillard/problemes.dir/ordonnancement.dir/ordonnancement.html]. 30 Capítulo 5. Resultados y análisis Figura 5.4 ARPD de cada método en función de la dimensión de los problemas. Figura 5.5 ARPD de cada método en función de los pesos de los problemas. Con respecto a los tiempos de ejecución, el NEH se establece como el algoritmo de menor tiempo de ejecución medio con un total de 7.12 segundos, mientras que el tiempo medio de ejecución del algoritmo NEH C es de 8.45 segundos. La diferencia de tiempo (1.33 segundos) se justifica debido a la complejidad de ambas heurísticas y al número de operaciones implícitas en cada una de ellas, pudiéndose apreciar que la diferencia de los tiempos de ejecución de ambos métodos tiende a aumentar más cuanto mayor es la dimensión de los problemas. No obstante, dicha diferencia es razonable y no influye sobremanera en la elección de un método u otro. 5.3 PRC+ TB 31 Figura 5.6 Tiempos de ejecución de cada método. Figura 5.7 Tiempos de ejecución acumulados de cada método. 5.3 PRC+ TB Después de analizar los resultados obtenidos mediante los métodos NEH, NEH FF , NEH LJP y NEH C , se pasa a estudiar la eficacia de la PR C y la TB C por separado. En este primer ensayo se ha implementado la PR C en todos los métodos, con el fin de averiguar si ésta es capaz de obtener mejores resultados en combinación con la tie breaking rule de los demás métodos que las originales: 32 Capítulo 5. Resultados y análisis Tabla 5.7 ARPD de cada tie breaking rule implementada con la PR C en función de la dimensión de los problemas. m n PRC+ TBNEH PRC+ TBFF PRC+ TBLJP PRC+ TBC 5 20 1,06 1,30 0,54 1,08 10 20 0,37 0,32 0,33 0,26 20 20 0,16 0,13 0,22 0,15 5 50 0,25 0,23 0,55 0,65 10 50 1,44 1,36 1,21 1,19 20 50 0,42 0,38 0,27 0,40 5 100 0,18 0,17 0,49 0,21 10 100 1,00 0,90 0,58 0,74 20 100 1,44 1,42 1,15 1,34 10 200 0,81 0,86 0,94 0,84 20 200 1,49 1,48 0,87 1,30 20 500 1,32 1,23 1,05 1,26 Tabla 5.8 ARPD de cada tie breaking rule implementada con la PR C en función de los pesos de los problemas. w PRC+ TBNEH PRC+ TBFF PRC+ TBLJP PRC+ TBC 0 2,26 2,51 1,97 2,15 0,1 1,53 1,49 1,05 1,38 0,2 1,19 1,14 0,78 1,14 0,3 0,84 0,84 0,58 0,91 0,4 0,76 0,76 0,50 0,77 0,5 0,71 0,62 0,60 0,55 0,6 0,50 0,53 0,59 0,48 0,7 0,35 0,37 0,37 0,38 0,8 0,31 0,33 0,31 0,33 0,9 0,19 0,19 0,26 0,18 1 0,46 0,18 0,50 0,34 5.3 PRC+ TB 33 Tabla 5.9 Tiempos de ejecución de cada tie breaking rule implementada con la PRC. m n PRC+ TBNEH PRC+ TBFF PRC+ TBLJP PRC+ TBC 5 20 0,0115 0,0094 0,0087 0,0098 10 20 0,0041 0,0061 0,0060 0,0061 20 20 0,0060 0,0065 0,0068 0,0074 5 50 0,0601 0,0729 0,0717 0,0732 10 50 0,0570 0,0768 0,0838 0,0791 20 50 0,0719 0,0847 0,0913 0,0942 5 100 0,4574 0,5463 0,5658 0,5974 10 100 0,5517 0,6023 0,5939 0,6111 20 100 0,7720 0,6751 0,6964 0,7483 10 200 6,6557 5,0391 5,1135 5,2466 20 200 7,7572 5,6445 5,6540 6,0368 20 500 108,9591 102,4835 103,2376 109,2045 Promedio 10,4470 9,6039 9,6775 10,2262 Los resultados tras implementar la PR C en todos los algoritmos junto con sus reglas de desempate originales muestran que la tie breaking rule que mejor desempeño logra junto con esta regla de prioridad es la TB LJP , con un ARPD promedio inferior a la TB NEH , TB FF y TB C en un 17.37%, 16.25% y 12.92% respectivamente. Figura 5.8 ARPD de cada tie breaking rule implementada con la PR C en función de la dimensión de los problemas. 34 Capítulo 5. Resultados y análisis Figura 5.9 ARPD de cada tie breaking rule implementada con la PR C en función de los pesos de los problemas. Figura 5.10 Tiempos de ejecución de cada método implementado con la PRC. Figura 5.11 Tiempos de ejecución acumulados de cada método implementado con la PRC. 5.3 PRC+ TB 35 A continuación, se ha implementado la TB C en el algoritmo NEH LJP y se ha comparado con los métodos originales (NEH, NEH FF y NEH C ). Los resultados de las tablas 5.10 y 5.11 muestran que la nueva versión del algoritmo NEH LJP es superior al resto, con un ARPD promedio inferior al NEH C en un 4.99%, destacando en los problemas de dimensión 5x20, 20x50, 10x100, 20x200 y 20x500 (Figura 5.12), así como para las ponderaciones de valor 0, 0.1, 0.2, 0.3, 0.4 y 0.7 (Figura 5.13). Tabla 5.10 ARPD del método NEH LJP implementado con la PR C en función de la dimensión de los problemas. m n NEH NEHFF PRc+ TBLJP NEHC 5 20 12,14 12,10 2,27 2,76 10 20 2,52 2,44 2,32 2,26 20 20 2,17 2,16 1,82 1,74 5 50 0,73 0,69 2,53 2,64 10 50 3,38 3,35 3,58 3,51 20 50 2,63 2,60 1,21 1,34 5 100 0,96 0,95 1,10 0,83 10 100 2,25 2,23 1,00 1,16 20 100 1,57 1,50 2,12 2,31 10 200 1,50 1,54 1,78 1,69 20 200 2,44 2,38 1,10 1,53 20 500 2,09 2,03 1,04 1,25 Tabla 5.11 ARPD del método NEH LJP implementado con la PR C en función de los pesos de los problemas. w NEH NEHFF PRc+ TBLJP NEHC 0 14,39 14,39 4,93 5,04 0,1 4,42 4,43 3,10 3,44 0,2 2,67 2,66 2,47 2,84 0,3 2,16 2,06 2,06 2,40 0,4 1,92 1,96 1,37 1,64 0,5 1,53 1,51 1,56 1,52 0,6 1,31 1,34 1,51 1,39 0,7 0,98 0,96 0,93 0,93 0,8 0,85 0,82 0,89 0,91 0,9 0,62 0,61 0,61 0,54 1 0,67 0,41 0,62 0,46 36 Capítulo 5. Resultados y análisis Tabla 5.12 Tiempos de ejecución del método NEHLJP implementado con la PRC. m n NEH NEHFF PRc+ TBLJP NEHC 5 20 0,0260 0,0163 0,0176 0,0116 10 20 0,0175 0,0047 0,0065 0,0050 20 20 0,0043 0,0054 0,0057 0,0063 5 50 0,0582 0,0580 0,0631 0,0594 10 50 0,0591 0,0615 0,0635 0,0661 20 50 0,0602 0,0717 0,0724 0,0797 5 100 0,4426 0,4530 0,4565 0,4652 10 100 0,4980 0,4991 0,4817 0,5067 20 100 0,5259 0,5518 0,5605 0,6004 10 200 3,9429 4,1290 4,1874 4,3793 20 200 4,1973 4,6374 4,8859 5,0065 20 500 77,3044 84,6991 86,2719 90,4058 Promedio 7,2614 7,9323 8,0894 8,4660 Figura 5.12 ARPD del método NEH LJP implementado con la PR C en función de la dimensión de los problemas. 5.3 PRC+ TB 37 Figura 5.13 ARPD del método NEH LJP implementado con la PR C en función de los pesos de los problemas. Figura 5.14 Tiempos de ejecución del método NEHLJP implementado con la PRC. 38 Capítulo 5. Resultados y análisis Figura 5.15 Tiempos de ejecución acumulados del método NEHLJP implementado con la PRC. Uno de los efectos que se logra con la implementación de la PR C es “suavizar” la función de los ARPD eliminando los “picos” provocados por los valores atípicos que aparecen en aquellos problemas en los que la ponderación es igual a 0, es decir, el objetivo es únicamente minimizar los core idle-time. Esto ocurre gracias a que se produce una mejor distribución en los trabajos, disminuyendo considerablemente los CIT y con ello el valor de la función objetivo. Además, no se producen cambios significativos en la calidad de los resultados, como se puede observar en la tabla 5.13: Figura 5.16 ARPD del método NEHLJP original vs el NEHLJP implementado con la PRC. Tabla 5.13 Diferencia entre la calidad de los resultados del NEH LJP original y el NEH LJP implementado con la PRC. NEHLJP PRC+ TBLJP Variación fo 5727,89 5730,53 -0,0005% Cmax 7045,52 7043,58 0,0275% ∑CITi4770,15 4774,93 -0,1002% 5.4 PR + TBC39 5.4 PR + TBC Por último, se ha implementado la TB C en todos los algoritmos junto con sus priority rules originales, con el fin de averiguar si ésta es capaz de obtener mejores resultados en combinación con la priority rule de los demás métodos que las originales. Los resultados señalan de nuevo al NEH C como el método que presenta una mayor calidad en sus soluciones, con un ARPD promedio un 30.21% inferior al de la PRLJP y un 25% inferior al de la PRNEH. Tabla 5.14 ARPD de cada priority rule implementada con la TB C en función de la dimensión de los problemas. m n PRNEH + TBCPRFF + TBCPRLJP + TBCPRC+ TBC 5 20 8,48 8,48 15,82 2,42 10 20 3,35 3,35 4,20 3,12 20 20 3,18 3,18 1,64 2,73 5 50 0,97 0,97 2,02 2,79 10 50 4,09 4,09 2,30 4,34 20 50 3,16 3,16 1,88 1,91 5 100 2,45 2,45 2,97 0,97 10 100 2,00 2,00 1,19 1,32 20 100 1,65 1,65 2,48 2,57 10 200 1,72 1,72 1,32 1,82 20 200 2,29 2,29 1,20 1,32 20 500 2,03 2,03 0,98 1,23 Tabla 5.15 ARPD de cada priority rule implementada con la TB C en función de los pesos de los problemas. w PRNEH + TBCPRFF + TBCPRLJP + TBCPRC+ TBC 0 13,08 13,08 16,96 5,16 0,1 4,73 4,73 4,56 4,04 0,2 2,96 2,96 3,25 3,36 0,3 2,58 2,58 2,37 2,85 0,4 2,33 2,33 1,77 2,10 0,5 1,84 1,84 1,66 1,88 0,6 1,55 1,55 1,24 1,58 0,7 1,14 1,14 1,01 1,10 0,8 0,96 0,96 0,89 1,06 0,9 0,76 0,76 0,67 0,67 1 0,50 0,50 0,46 0,51 46 Capítulo 6. Anexo: Códigos de Matlab PRLJP function [seqinic]=seqinicialnehljp(seq,pij,m,n) \%Creo dos vectores, uno que almacene los índices de los trabajos \%y otro con sus valores a ordenar asociados: seqaux=[1:n]; seqini=[1:n]; \%Relleno el vector con los valores a ordenar: for j=1:n seqaux(j)=(sumapj(j,seq,pij,m)/m)+(desviacionabsolutapj(j,seq,pij,m)/m)+ (skepj(j,seq,pij,m)^(1/3))+(1/(kurpj(j,seq,pij,m)^(1/4))); end \%Y ahora lo ordeno: seqinic=ordenamam(seqini,seqaux,n); end PRC function [seqinic]=seqinicialnehc(seq,pij,m,n) \%Creo dos vectores, uno que almacene los índices de los trabajos \%y otro con sus valores a ordenar asociados: seqaux=[1:n]; seqini=[1:n]; \%Relleno el vector con los valores a ordenar: for j=1:n seqaux(j)=sumapj(j,seq,pij,m)+desviacionabsolutapj(j,seq,pij,m)+rangopj(j,seq,pij,m); end \%Y ahora lo ordeno: seqinic=ordenamam(seqini,seqaux,n); 47 end TB TBNEH seqf=[seqi(1),seqi(2)]; \%Primero compruebo que la subsecuencia sea la mejor de las dos posibles: seqfalt=[seqi(2),seqi(1)]; \%Evalúo la función objetivo de ambas subsecuencias: [c,cit]=implementa(seqf,pij,m,2); cmax=makespan(c,2); sumacit=sumcit(cit,m); fo1=funcionobjetivo(w,cmax,sumacit); [c,cit]=implementa(seqfalt,pij,m,2); cmax=makespan(c,2); sumacit=sumcit(cit,m); fo2=funcionobjetivo(w,cmax,sumacit); \%Y comparo: if fo2<fo1 seqf=seqfalt; end \%Una vez tengo la subsecuencia óptima inserto el resto de trabajos: for i=3:n \%Hago la inserción del siguiente trabajo seqf(i)=seqi(i); \%Ahora saco todas las posibles combinaciones: combi=combinaciones(seqf,i); 48 Capítulo 6. Anexo: Códigos de Matlab \%Busco el menor valor de la FO: \%Empiezo por darle el menor a la primera combinacion: [c,cit]=implementa(combi(1,1:i),pij,m,i); cmax=makespan(c,i); sumacit=sumcit(cit,m); minfo=funcionobjetivo(w,cmax,sumacit); \%Ahora busco una FO menor: for j=2:i [c,cit]=implementa(combi(j,1:i),pij,m,i); cmax=makespan(c,i); sumacit=sumcit(cit,m); foaux=funcionobjetivo(w,cmax,sumacit); if foaux<minfo seqf=combi(j,1:i); minfo=foaux; end end end TBFF seqf=[seqi(1),seqi(2)]; \%Primero compruebo que la subsecuencia sea la mejor de las dos posibles: seqfalt=[seqi(2),seqi(1)]; \%Evalúo la función objetivo de ambas subsecuencias: \%Guardo el valor del IT por si fuera necesario resolver un desempate [c,cit]=implementa(seqf,pij,m,2); cmax=makespan(c,2); 49 sumacit=sumcit(cit,m); fo1=funcionobjetivo(w,cmax,sumacit); tit1=tbrnehff(seqf,pij,m,sumacit); [c,cit]=implementa(seqfalt,pij,m,2); cmax=makespan(c,2); sumacit=sumcit(cit,m); fo2=funcionobjetivo(w,cmax,sumacit); tit2=tbrnehff(seqfalt,pij,m,sumacit); \%Y comparo: if fo2<fo1 seqf=seqfalt; end if fo2==fo1 && tit2<tit1 seqf=seqfalt; end \%Una vez tengo la subsecuencia óptima inserto el resto de trabajos: for i=3:n \%Hago la inserción del siguiente trabajo seqf(i)=seqi(i); \%Ahora saco todas las posibles combinaciones combi=combinaciones(seqf,i); \%Busco el menor valor de la FO: \%Empiezo por darle el menor a la primera combinacion: [c,cit]=implementa(combi(1,1:i),pij,m,i); cmax=makespan(c,i); 50 Capítulo 6. Anexo: Códigos de Matlab sumacit=sumcit(cit,m); minfo=funcionobjetivo(w,cmax,sumacit); \%Ahora busco una FO menor: for j=2:i [c,cit]=implementa(combi(j,1:i),pij,m,i); cmax=makespan(c,i); sumacit=sumcit(cit,m); foaux=funcionobjetivo(w,cmax,sumacit); if foaux<minfo minfo=foaux; end end \%ahora que tengo la menor funcion objetivo elijo de entre todas la \%que mejor satisfaga la condición de la TB: menorit=inf; for j=1:i [c,cit]=implementa(combi(j,1:i),pij,m,i); cmax=makespan(c,i); sumacit=sumcit(cit,m); foaux=funcionobjetivo(w,cmax,sumacit); titaux=tbrnehff(combi(j,1:i),pij,m,sumacit); if foaux==minfo && titaux<menorit seqf=combi(j,1:i); menorit=titaux; end 51 end end function [tit]=tbrnehff(seq,pij,m,sumacit) \%Primero calculo los front idle-time: fit=zeros(1,m); fit(1)=0; for j=2:m fit(j)=fit(j-1)+pij(j-1,seq(1)); end \%Ahora la suma: sumfit=0; for j=1:m sumfit=sumfit+fit(j); end \%Y la suma del fit con el cit: tit=sumfit+sumacit; end TBLJP seqf=[seqi(1),seqi(2)]; \%Primero compruebo que la subsecuencia sea la mejor de las dos posibles: seqfalt=[seqi(2),seqi(1)]; \%Evalúo la función objetivo de ambas subsecuencias: \%Guardo el valor de "p" por si fuera necesario resolver un desempate: [c,cit]=implementa(seqf,pij,m,2); 52 Capítulo 6. Anexo: Códigos de Matlab cmax=makespan(c,2); sumacit=sumcit(cit,m); fo1=funcionobjetivo(w,cmax,sumacit); p1=tbrnehljp(seqf,pij,2,c,cmax); [c,cit]=implementa(seqfalt,pij,m,2); cmax=makespan(c,2); sumacit=sumcit(cit,m); fo2=funcionobjetivo(w,cmax,sumacit); p2=tbrnehljp(seqfalt,pij,2,c,cmax); \%Y comparo: if fo2<fo1 seqf=seqfalt; end if fo2==fo1 && p2>p1 seqf=seqfalt; end \%Una vez tengo la subsecuencia óptima inserto el resto de trabajos: for i=3:n \%Hago la inserción del siguiente trabajo seqf(i)=seqi(i); \%Ahora saco todas las posibles combinaciones combi=combinaciones(seqf,i); \%Busco el menor valor de la FO: \%Empiezo por darle el menor a la primera combinacion: [c,cit]=implementa(combi(1,1:i),pij,m,i); 53 cmax=makespan(c,i); sumacit=sumcit(cit,m); minfo=funcionobjetivo(w,cmax,sumacit); \%Ahora busco una FO menor: for j=2:i [c,cit]=implementa(combi(j,1:i),pij,m,i); cmax=makespan(c,i); sumacit=sumcit(cit,m); foaux=funcionobjetivo(w,cmax,sumacit); if foaux<minfo minfo=foaux; end end \%ahora que tengo la menor funcion objetivo elijo de entre todas la \%que mejor satisfaga la condición de la TB: mayorp=0; for j=1:i [c,cit]=implementa(combi(j,1:i),pij,m,i); cmax=makespan(c,i); sumacit=sumcit(cit,m); foaux=funcionobjetivo(w,cmax,sumacit); paux=tbrnehljp(combi(j,1:i),pij,i,c,cmax); if foaux==minfo && paux>mayorp seqf=combi(j,1:i); mayorp=paux; 54 Capítulo 6. Anexo: Códigos de Matlab end end end function [p]=tbrnehljp(seq,pij,i,c,cmax) \%Primero calculo los completion times en la primera máquina: cm1=zeros(1,i); cm1(1)=pij(1,seq(1)); for j=2:i cm1(j)=cm1(j-1)+pij(1,seq(j)); end \%A continuación calculo los flowtimes: f=zeros(1,i); f(1)=c(1); for j=2:i f(j)=c(j)-cm1(j-1); end \%Calculo la media de los flowtimes: mediaf=0; for j=1:i mediaf=mediaf+f(j); end mediaf=mediaf/i; \%Por último calculo el término del sumatorio: terminosum=0; for j=1:i 55 terminosum=terminosum+(f(j)-mediaf)^2; end \%Lo multiplico por 1/n-1, así luego es más cómodo al hacer la raíz: terminosum=terminosum*(1/(i-1)); p=(mediaf-sqrt(terminosum))/cmax; TBC seqf=[seqi(1),seqi(2)]; \%Primero compruebo que la subsecuencia sea la mejor de las dos posibles: seqfalt=[seqi(2),seqi(1)]; \%Evalúo la función objetivo de ambas subsecuencias: \%Guardo el valor de "u" por si fuera necesario resolver un desempate [c,cit]=implementa(seqf,pij,m,2); cmax=makespan(c,2); sumacit=sumcit(cit,m); fo1=funcionobjetivo(w,cmax,sumacit); u1=tbrnehc(seqf,pij,m,2,cit); [c,cit]=implementa(seqfalt,pij,m,2); cmax=makespan(c,2); sumacit=sumcit(cit,m); fo2=funcionobjetivo(w,cmax,sumacit); u2=tbrnehc(seqfalt,pij,m,2,cit); \%Y comparo: if fo2<fo1 seqf=seqfalt; end 62 Capítulo 6. Anexo: Códigos de Matlab mcput(1,1)=mcput(1,1)+mcpu(i,3); mcput(1,2)=mcput(1,2)+mcpu(i,4); mcput(1,3)=mcput(1,3)+mcpu(i,5); mcput(1,4)=mcput(1,4)+mcpu(i,6); end mcput(1,1)=mcput(1,1)/12; mcput(1,2)=mcput(1,2)/12; mcput(1,3)=mcput(1,3)/12; mcput(1,4)=mcput(1,4)/12; 63 Funciones auxiliares Valor de la función objetivo function [fo]=funcionobjetivo(w,cmax,sumacit) fo=(w*cmax)+((1-w)*sumacit); end Identificación de la mejor solución function [bfo]=bestfo(neh,nehff,nehljp,nehc) soluciones=[neh,nehff,nehljp,nehc]; bfo=min(soluciones); end Intercambio de posiciones en vectores function [v]=cambio(v,i,j) vaux=[1,2]; vaux(1)=v(i); vaux(2)=v(j); v(i)=vaux(2); v(j)=vaux(1); end Combinaciones para una secuencia de nelementos function [combi]=combinaciones(seqf,i) combi=zeros(i,i); \%Copio seqf: for j=1:i for k=1:i combi(j,k)=seqf(k); end 64 Capítulo 6. Anexo: Códigos de Matlab end \%Ahora creo las i combinaciones: flag=1; for j=2:i for k=flag:i-1 combi(j,1:i)=cambio(combi(j,1:i),k,i); end flag=flag+1; end end Desviación absoluta function[desvabs]=desviacionabsolutapj(j,seq,pij,m) desvabs=0; for i=1:m desvabs=desvabs+abs(pij(i,seq(j))-mediapj(j,seq,pij,m)); end Completion times y CIT de una secuencia function [c,cit]=implementa(seq,pij,m,n) \%Creo un vector para el makespan y otro para el CIT: c=[1:n]; cit=[1:m]; for j=1:n c(j)=0; end for i=1:m cit(i)=0; 65 end \%Primero preparo el trabajo 1 fuera del bucle porque no tiene \%antecesores y después meto el resto de trabajos en el bucle: for i=1:m c(1)=c(1)+pij(i,seq(1)); for j=2:n if c(j-1)<c(j) \%Si el trabajo anterior acabó antes que el nuevo, este debe \%esperar a acabar y habrá que añadir el CIT: cit(i)=cit(i)+(c(j)-c(j-1)); c(j)=c(j)+pij(i,seq(j)); end if c(j-1)==c(j) \%Si coinciden simplemente se suma el tiempo de proceso: c(j)=c(j-1)+pij(i,seq(j)); end if c(j-1)>c(j) \%Si el c del trabajo anterior supera al nuevo, entonces el \%nuevo trabajo va inmediatamente después de este: c(j)=c(j-1)+pij(i,seq(j)); end end end end 66 Capítulo 6. Anexo: Códigos de Matlab Makespan function [cmax]=makespan(c,n) cmax=0; for j=1:n if c(j)>cmax cmax=c(j); end end end Suma de los CIT de todas las máquinas function [sumacit]=sumcit(cit,m) sumacit=0; for i=1:m sumacit=sumacit+cit(i); end end Kurtosis function [kur]=kurpj(j,seq,pij,m) numerador=0; for i=1:m numerador=numerador+(pij(i,seq(j))-(mediapj(j,seq,pij,m)))^4; end numerador=numerador/m; denominador=0; for i=1:m denominador=denominador+(pij(i,seq(j))-(mediapj(j,seq,pij,m)))^2; 67 end denominador=denominador/m; denominador=denominador^; kur=numerador/denominador; end Skewness function[ske]=skepj(j,seq,pij,m) numerador=0; for i=1:m numerador=numerador+(pij(i,seq(j))-(mediapj(j,seq,pij,m)))^3; end numerador=numerador/m; denominador=0; for i=1:m denominador=denominador+(pij(i,seq(j))-(mediapj(j,seq,pij,m)))^2; end denominador=denominador/m; denominador=sqrt(denominador); denominador=denominador^3; ske=numerador/denominador; end Media de los pi j de un trabajo function [mediapj]=mediapj(j,seq,pij,m) aux=sumapj(j,seq,pij,m); mediapj=aux/m; end 68 Capítulo 6. Anexo: Códigos de Matlab Suma de los pi j de un trabajo function [sumpj]=sumapj(j,seq,pij,m) sumpj=0; for i=1:m sumpj=sumpj+pij(i,seq(j)); end end Ordenar una secuencia de mayor a menor en función de sus ppi j function [seqorden]=ordenamam(seq,seqaux,n) \%copio el vector de la secuencia y de los pij seqorden=[1:n]; seqaux2=[1:n]; for i=1:n seqorden(i)=seq(i); end for i=1:n seqaux2(i)=seqaux(i); end \%ahora repaso el vector de pij para ordenarlos for i=1:n for j=1:n if seqaux2(i)>seqaux2(j) seqaux2=cambio(seqaux2,i,j); seqorden=cambio(seqorden,i,j); end end 69 end end Rango de los pi j de un trabajo function [rango]=rangopj(j,seq,pij,m) \%Pongo como valor de referencia el primer componente para poder comparar: max=pij(1,seq(j)); min=pij(1,seq(j)); for i=1:m if pij(i,seq(j))>max max=pij(i,seq(j)); end if pij(i,seq(j))<min min=pij(i,seq(j)); end rango=max-min; end 70 Capítulo 6. Anexo: Códigos de Matlab Ejemplo de implementación del algoritmo NEHC \%Cargo las instancias: ta=importdata('taillardbenchmark.txt'); \%Inicio el flag para recorrer las posiciones de las instancias: flag=0; \%Creo la matriz de las soluciones: msolnehc=zeros(1320,7); \%Inicio un segundo flag para rellenar la matriz de soluciones: flag2=1; \%Recorro cada uno de los 120 problemas: for s=1:120 \%Inicio el contador del tiempo de CPU: tinicio1=cputime; \%Incluyo los datos del problema (Es necesario adaptar el formato \%de los tiempos de proceso) n=ta(1+flag); m=ta(2+flag); dim=2+flag+(m*n); pij=ta(3+flag:dim); pij=reshape(pij,n,m); pij=transpose(pij); seq=[1:n]; \%Se ejecuta la priority rule: seqi=seqinicialnehc(seq,pij,m,n); \%tinicio1 es el tiempo que se tarda en resolver la secuencia inicial: tinicio1=cputime-tinicio1; 71 \%Ahora relleno la tabla con las combinaciones de w por cada \%problema: for k=0:10 \%tinicio2 es el tiempo que se tarda en calcular la fo: tinicio2=cputime; msolnehc(flag2,1)=m; msolnehc(flag2,2)=n; w=0.1*k; msolnehc(flag2,3)=w; \%Se aplica la TB: tiebreakingnehc; \%Se implementa la secuencia final: [c,cit]=implementa(seqf,pij,m,n); \%Se calcula el makespan y el CIT: cmax=makespan(c,n); sumacit=sumcit(cit,m); \%Se almacenan los resultados en la tabla: msolnehc(flag2,4)=funcionobjetivo(w,cmax,sumacit); msolnehc(flag2,5)=cmax; msolnehc(flag2,6)=sumacit; \%El tiempo de ejecución es la suma entre ambos tiempos: msolnehc(flag2,7)=cputime-tinicio2+tinicio1; flag2=flag2+1; end flag=dim; end 78 Capítulo 6. Anexo: ARPD en función de las características del problema m n w NEH NEHFF NEHLJP NEHC 5 50 0,9 1,54 1,54 2,38 3,68 5 50 1,0 1,53 1,53 2,00 2,82 10 50 0,0 4,51 4,51 2,43 7,34 10 50 0,1 4,24 4,24 2,20 6,67 10 50 0,2 3,98 3,98 1,97 6,00 10 50 0,3 3,72 3,72 1,75 5,33 10 50 0,4 3,48 3,48 1,54 4,69 10 50 0,5 3,26 3,26 1,34 4,05 10 50 0,6 3,03 3,03 1,14 3,42 10 50 0,7 2,82 2,82 0,94 2,80 10 50 0,8 2,64 2,64 0,77 2,20 10 50 0,9 2,53 2,53 0,68 1,67 10 50 1,0 2,53 2,53 0,68 1,25 20 50 0,0 3,34 3,34 6,61 5,84 20 50 0,1 3,25 3,25 6,40 5,62 20 50 0,2 3,15 3,15 6,14 5,37 20 50 0,3 3,04 3,04 5,85 5,08 20 50 0,4 2,90 2,90 5,51 4,75 20 50 0,5 2,73 2,73 5,11 4,34 20 50 0,6 2,53 2,53 4,61 3,86 20 50 0,7 2,28 2,28 4,00 3,25 20 50 0,8 1,96 1,96 3,24 2,49 20 50 0,9 1,58 1,58 2,27 1,54 20 50 1,0 1,33 1,33 1,24 0,52 5 100 0,0 0,97 0,97 10,47 13,06 5 100 0,1 0,79 0,79 7,44 9,30 5 100 0,2 0,68 0,68 5,66 7,00 5 100 0,3 0,62 0,62 4,47 5,44 5 100 0,4 0,57 0,57 3,61 4,31 5 100 0,5 0,53 0,53 2,96 3,45 5 100 0,6 0,51 0,51 2,46 2,78 5 100 0,7 0,52 0,52 2,08 2,27 5 100 0,8 0,53 0,53 1,77 1,85 5 100 0,9 0,56 0,56 1,54 1,51 5 100 1,0 0,64 0,64 1,40 1,29 10 100 0,0 4,32 4,32 12,75 14,11 10 100 0,1 3,88 3,88 11,33 12,53 10 100 0,2 3,47 3,47 9,98 11,03 10 100 0,3 3,07 3,07 8,68 9,60 10 100 0,4 2,70 2,70 7,44 8,22 10 100 0,5 2,34 2,34 6,24 6,89 10 100 0,6 2,00 2,00 5,09 5,61 10 100 0,7 1,68 1,68 3,98 4,38 10 100 0,8 1,36 1,36 2,91 3,19 79 m n w NEH NEHFF NEHLJP NEHC 10 100 0,9 1,08 1,08 1,89 2,06 10 100 1,0 1,23 1,23 1,32 1,37 20 100 0,0 0,76 0,76 11,05 8,85 20 100 0,1 0,73 0,73 10,63 8,52 20 100 0,2 0,70 0,70 10,16 8,15 20 100 0,3 0,67 0,67 9,61 7,72 20 100 0,4 0,63 0,63 8,97 7,22 20 100 0,5 0,60 0,60 8,23 6,66 20 100 0,6 0,57 0,57 7,36 5,98 20 100 0,7 0,53 0,53 6,29 5,15 20 100 0,8 0,48 0,48 4,97 4,12 20 100 0,9 0,42 0,42 3,27 2,81 20 100 1,0 0,75 0,75 1,42 1,46 10 200 0,0 9,09 9,09 5,22 6,01 10 200 0,1 8,15 8,15 4,68 5,37 10 200 0,2 7,25 7,25 4,16 4,75 10 200 0,3 6,39 6,39 3,65 4,16 10 200 0,4 5,57 5,57 3,17 3,59 10 200 0,5 4,78 4,78 2,71 3,05 10 200 0,6 4,01 4,01 2,26 2,52 10 200 0,7 3,28 3,28 1,83 2,02 10 200 0,8 2,57 2,57 1,43 1,54 10 200 0,9 1,98 1,98 1,11 1,16 10 200 1,0 1,53 1,53 0,95 0,92 20 200 0,0 0,43 0,43 7,20 7,82 20 200 0,1 0,41 0,41 6,89 7,49 20 200 0,2 0,39 0,39 6,54 7,12 20 200 0,3 0,36 0,36 6,15 6,70 20 200 0,4 0,33 0,33 5,70 6,22 20 200 0,5 0,29 0,29 5,18 5,66 20 200 0,6 0,25 0,25 4,57 5,01 20 200 0,7 0,20 0,20 3,86 4,25 20 200 0,8 0,14 0,14 3,00 3,33 20 200 0,9 0,10 0,10 1,98 2,23 20 200 1,0 0,29 0,29 0,95 1,10 20 500 0,0 4,80 4,80 3,82 3,36 20 500 0,1 4,55 4,55 3,63 3,18 20 500 0,2 4,27 4,27 3,41 2,99 20 500 0,3 3,97 3,97 3,17 2,77 20 500 0,4 3,63 3,63 2,91 2,54 20 500 0,5 3,25 3,25 2,62 2,27 20 500 0,6 2,82 2,82 2,29 1,98 20 500 0,7 2,34 2,34 1,93 1,65 20 500 0,8 1,80 1,80 1,52 1,28 20 500 0,9 1,20 1,20 1,08 0,87 20 500 1,0 0,67 0,67 0,75 0,58 Promedio 2,856 2,856 5,348 6,949 80 Capítulo 6. Anexo: ARPD en función de las características del problema ARPD de cada tie breaking rule implementada con la PRCen función de las características de los problemas Tabla 3 ARPD de cada tie breaking rule implementada con la PR C en función de las características de los problemas. m n w PRC+ TBNEH PRC+ TBFF PRC+ TBLJP PRC+ TBC 5 20 0,0 4,88 7,83 4,52 4,88 5 20 0,1 2,11 2,11 0,00 2,11 5 20 0,2 2,38 2,38 0,00 2,38 5 20 0,3 0,56 0,56 0,14 0,56 5 20 0,4 0,28 0,28 0,09 0,28 5 20 0,5 0,21 0,21 0,10 0,21 5 20 0,6 0,21 0,21 0,00 0,21 5 20 0,7 0,10 0,10 0,23 0,10 5 20 0,8 0,07 0,02 0,14 0,02 5 20 0,9 0,03 0,03 0,49 0,03 5 20 1,0 0,86 0,63 0,26 1,07 10 20 0,0 0,58 0,58 0,00 0,58 10 20 0,1 0,53 0,47 0,06 0,47 10 20 0,2 0,35 0,35 0,00 0,35 10 20 0,3 0,29 0,29 0,00 0,29 10 20 0,4 0,23 0,23 0,00 0,23 10 20 0,5 1,54 0,00 1,29 0,00 10 20 0,6 0,07 0,91 1,02 0,00 10 20 0,7 0,20 0,20 0,17 0,01 10 20 0,8 0,05 0,05 0,20 0,05 10 20 0,9 0,02 0,02 0,11 0,04 10 20 1,0 0,21 0,41 0,73 0,81 20 20 0,0 0,87 0,87 0,20 0,27 20 20 0,1 0,00 0,00 0,20 0,00 20 20 0,2 0,13 0,13 0,19 0,13 20 20 0,3 0,12 0,12 0,15 0,12 20 20 0,4 0,00 0,29 0,44 0,29 20 20 0,5 0,00 0,00 0,14 0,00 20 20 0,6 0,17 0,00 0,17 0,25 20 20 0,7 0,00 0,00 0,30 0,19 20 20 0,8 0,00 0,00 0,00 0,00 20 20 0,9 0,04 0,00 0,04 0,00 20 20 1,0 0,40 0,00 0,61 0,35 5 50 0,0 0,63 0,63 1,55 1,89 5 50 0,1 0,18 0,18 1,18 1,36 5 50 0,2 0,08 0,08 0,98 1,00 5 50 0,3 0,14 0,14 0,75 0,94 5 50 0,4 0,00 0,00 0,41 0,25 5 50 0,5 0,41 0,52 0,01 0,51 5 50 0,6 0,51 0,37 0,36 0,37 81 m n w PRC+ TBNEH PRC+ TBFF PRC+ TBLJP PRC+ TBC 5 50 0,7 0,24 0,16 0,13 0,24 5 50 0,8 0,11 0,14 0,26 0,15 5 50 0,9 0,25 0,17 0,13 0,25 5 50 1,0 0,16 0,17 0,27 0,20 10 50 0,0 3,61 3,61 3,45 3,28 10 50 0,1 3,71 3,71 1,16 3,36 10 50 0,2 1,14 1,14 2,14 0,87 10 50 0,3 1,82 1,82 1,26 1,34 10 50 0,4 1,63 1,28 1,56 0,95 10 50 0,5 0,59 1,06 0,70 0,78 10 50 0,6 0,55 0,55 1,25 0,70 10 50 0,7 0,87 0,87 0,11 0,87 10 50 0,8 0,34 0,39 0,60 0,39 10 50 0,9 0,42 0,48 0,24 0,34 10 50 1,0 1,12 0,05 0,84 0,18 20 50 0,0 0,57 0,57 0,11 0,57 20 50 0,1 0,48 0,48 0,10 0,48 20 50 0,2 0,45 0,45 0,03 0,45 20 50 0,3 0,18 0,18 0,16 0,18 20 50 0,4 0,43 0,43 0,37 0,43 20 50 0,5 0,20 0,20 0,31 0,00 20 50 0,6 0,17 0,17 0,36 0,17 20 50 0,7 0,54 0,75 0,39 0,98 20 50 0,8 0,60 0,60 0,02 0,53 20 50 0,9 0,17 0,17 0,24 0,17 20 50 1,0 0,84 0,22 0,87 0,45 5 100 0,0 0,60 0,60 2,95 1,14 5 100 0,1 0,11 0,11 0,60 0,11 5 100 0,2 0,03 0,03 0,37 0,03 5 100 0,3 0,19 0,19 0,04 0,19 5 100 0,4 0,07 0,07 0,21 0,06 5 100 0,5 0,10 0,10 0,04 0,13 5 100 0,6 0,20 0,17 0,04 0,17 5 100 0,7 0,15 0,15 0,41 0,15 5 100 0,8 0,22 0,31 0,27 0,22 5 100 0,9 0,01 0,01 0,13 0,01 5 100 1,0 0,28 0,08 0,26 0,09 10 100 0,0 3,62 3,62 1,00 2,09 10 100 0,1 2,51 2,51 1,42 1,81 10 100 0,2 1,08 0,81 0,82 0,74 10 100 0,3 0,57 0,57 0,60 0,92 10 100 0,4 0,77 0,66 0,31 0,66 10 100 0,5 0,46 0,03 0,95 0,03 10 100 0,6 0,48 0,48 0,30 0,52 82 Capítulo 6. Anexo: ARPD en función de las características del problema m n w PRC+ TBNEH PRC+ TBFF PRC+ TBLJP PRC+ TBC 10 100 0,7 0,31 0,31 0,19 0,42 10 100 0,8 0,59 0,52 0,22 0,43 10 100 0,9 0,21 0,21 0,15 0,21 10 100 1,0 0,39 0,23 0,38 0,27 20 100 0,0 3,63 3,63 2,74 2,49 20 100 0,1 1,04 1,04 2,50 1,10 20 100 0,2 2,41 2,08 1,94 2,15 20 100 0,3 2,19 2,19 0,47 2,43 20 100 0,4 2,02 2,23 0,16 2,12 20 100 0,5 0,89 1,17 1,14 1,08 20 100 0,6 1,24 0,98 1,06 0,98 20 100 0,7 0,75 0,75 0,72 0,71 20 100 0,8 0,74 1,07 0,86 1,07 20 100 0,9 0,30 0,28 0,39 0,36 20 100 1,0 0,59 0,17 0,70 0,29 10 200 0,0 3,61 3,61 4,42 4,34 10 200 0,1 2,04 2,04 1,49 1,80 10 200 0,2 1,13 1,15 0,48 1,00 10 200 0,3 0,27 0,66 1,34 0,08 10 200 0,4 0,56 0,56 0,61 0,49 10 200 0,5 0,46 0,70 0,36 0,78 10 200 0,6 0,26 0,32 0,24 0,27 10 200 0,7 0,16 0,16 0,50 0,12 10 200 0,8 0,15 0,06 0,25 0,18 10 200 0,9 0,08 0,07 0,30 0,10 10 200 1,0 0,17 0,13 0,33 0,12 20 200 0,0 2,89 2,89 1,38 1,94 20 200 0,1 2,55 2,55 1,82 1,66 20 200 0,2 2,21 2,21 1,07 2,12 20 200 0,3 1,98 1,74 0,47 2,33 20 200 0,4 1,89 1,97 0,53 2,30 20 200 0,5 2,11 2,27 0,76 1,71 20 200 0,6 1,01 1,08 1,28 0,89 20 200 0,7 0,38 0,38 0,73 0,29 20 200 0,8 0,49 0,53 0,47 0,50 20 200 0,9 0,48 0,61 0,59 0,43 20 200 1,0 0,36 0,04 0,52 0,16 20 500 0,0 1,66 1,66 1,27 2,39 20 500 0,1 3,05 2,68 2,11 2,29 20 500 0,2 2,86 2,91 1,34 2,49 20 500 0,3 1,75 1,58 1,60 1,57 20 500 0,4 1,19 1,14 1,28 1,16 20 500 0,5 1,49 1,21 1,34 1,42 20 500 0,6 1,05 1,13 1,03 1,23 20 500 0,7 0,56 0,64 0,61 0,44 20 500 0,8 0,44 0,31 0,39 0,47 20 500 0,9 0,25 0,28 0,29 0,26 20 500 1,0 0,18 0,03 0,28 0,12 Promedio 0,83 0,82 0,68 0,78 83 ARPD del método NEHLJP implementado con la PRCen función de las características de los problemas Tabla 4 ARPD del método NEHLJP implementado con la PRCen función de las características de los problemas. m n w NEH NEHFF PRc+ TBLJP NEHC 5 20 0,0 108,33 108,33 11,30 10,84 5 20 0,1 11,16 11,16 3,24 5,61 5 20 0,2 2,92 2,92 1,54 4,05 5 20 0,3 4,00 4,00 0,29 0,71 5 20 0,4 2,25 2,25 0,40 0,59 5 20 0,5 1,37 1,37 0,60 0,70 5 20 0,6 0,79 0,79 1,55 1,77 5 20 0,7 0,50 0,50 1,17 1,04 5 20 0,8 0,28 0,27 2,65 2,52 5 20 0,9 0,93 0,93 1,63 1,17 5 20 1,0 1,04 0,61 0,59 1,40 10 20 0,0 4,82 4,82 2,90 3,50 10 20 0,1 5,70 5,70 4,44 4,84 10 20 0,2 4,06 4,06 2,41 2,76 10 20 0,3 3,37 3,31 2,19 2,48 10 20 0,4 1,78 1,91 1,52 1,75 10 20 0,5 1,95 1,95 3,87 2,58 10 20 0,6 2,11 2,11 3,47 2,45 10 20 0,7 0,94 0,94 1,18 1,02 10 20 0,8 0,71 0,71 1,91 1,77 10 20 0,9 0,89 0,89 0,91 0,84 10 20 1,0 1,40 0,48 0,75 0,83 20 20 0,0 3,17 3,17 2,56 2,63 20 20 0,1 2,89 2,89 2,20 2,00 20 20 0,2 1,38 1,38 2,78 2,71 20 20 0,3 3,11 3,11 3,41 3,37 20 20 0,4 2,99 2,99 2,11 1,95 20 20 0,5 2,56 2,56 2,44 2,30 20 20 0,6 2,91 2,91 1,10 1,17 20 20 0,7 1,59 1,59 1,53 1,42 20 20 0,8 1,23 1,23 0,63 0,63 20 20 0,9 1,23 1,23 0,49 0,45 20 20 1,0 0,78 0,76 0,76 0,50 5 50 0,0 2,43 2,43 11,11 11,56 5 50 0,1 1,17 1,17 5,29 5,49 5 50 0,2 0,64 0,64 3,52 3,53 5 50 0,3 0,89 0,45 2,53 2,72 5 50 0,4 0,45 0,45 0,69 0,53 5 50 0,5 0,65 0,65 0,35 0,86 5 50 0,6 0,34 0,34 1,87 1,87 5 50 0,7 0,10 0,10 1,06 1,16 5 50 0,8 0,77 0,77 0,61 0,49 5 50 0,9 0,35 0,35 0,28 0,40 5 50 1,0 0,25 0,25 0,52 0,45 84 Capítulo 6. Anexo: ARPD en función de las características del problema m n w NEH NEHFF PRc+ TBLJP NEHC 10 50 0,0 12,06 12,06 10,22 9,66 10 50 0,1 6,05 6,05 6,26 8,33 10 50 0,2 4,86 4,86 6,67 5,32 10 50 0,3 2,72 2,72 3,62 3,77 10 50 0,4 3,62 3,62 3,68 3,06 10 50 0,5 1,82 1,82 2,25 2,32 10 50 0,6 2,09 2,09 2,83 2,27 10 50 0,7 1,64 1,38 1,12 1,88 10 50 0,8 0,65 0,69 0,96 0,75 10 50 0,9 0,81 0,81 0,84 0,96 10 50 1,0 0,92 0,77 0,96 0,30 20 50 0,0 7,81 7,81 1,04 1,49 20 50 0,1 5,21 5,21 0,83 1,20 20 50 0,2 2,73 2,73 2,06 2,49 20 50 0,3 1,79 1,79 2,02 2,04 20 50 0,4 2,65 2,65 1,48 1,53 20 50 0,5 1,53 1,53 1,39 1,07 20 50 0,6 1,11 1,11 1,35 1,17 20 50 0,7 2,37 2,37 0,52 1,11 20 50 0,8 2,11 2,11 1,03 1,54 20 50 0,9 0,62 0,69 0,58 0,50 20 50 1,0 0,99 0,56 1,08 0,66 5 100 0,0 5,55 5,55 6,75 4,97 5 100 0,1 1,28 1,28 1,78 1,29 5 100 0,2 1,00 1,00 0,59 0,25 5 100 0,3 0,51 0,51 0,71 0,87 5 100 0,4 0,35 0,35 0,56 0,42 5 100 0,5 0,33 0,33 0,21 0,30 5 100 0,6 0,84 0,81 0,08 0,20 5 100 0,7 0,38 0,38 0,54 0,29 5 100 0,8 0,04 0,04 0,35 0,29 5 100 0,9 0,08 0,06 0,22 0,09 5 100 1,0 0,19 0,10 0,32 0,14 10 100 0,0 8,23 8,23 1,91 3,00 10 100 0,1 5,36 5,36 1,88 2,28 10 100 0,2 3,54 3,54 1,68 1,61 10 100 0,3 1,98 1,98 1,06 1,38 10 100 0,4 1,67 1,67 0,76 1,11 10 100 0,5 0,99 1,12 1,31 0,39 10 100 0,6 0,71 0,78 0,53 0,74 10 100 0,7 0,68 0,68 0,51 0,74 10 100 0,8 0,55 0,57 0,51 0,72 10 100 0,9 0,36 0,36 0,31 0,37 10 100 1,0 0,66 0,26 0,54 0,44 20 100 0,0 2,80 2,80 3,19 2,94 20 100 0,1 2,16 2,16 3,07 1,66 20 100 0,2 1,89 1,89 3,14 3,39 20 100 0,3 1,83 1,83 3,71 5,70 20 100 0,4 1,65 1,65 1,08 3,04 20 100 0,5 1,46 1,47 2,80 2,75 20 100 0,6 0,88 0,88 2,75 2,66 85 m n w NEH NEHFF PRc+ TBLJP NEHC 20 100 0,7 1,42 1,42 1,37 1,36 20 100 0,8 1,50 1,35 0,86 1,06 20 100 0,9 0,69 0,66 0,56 0,53 20 100 1,0 0,96 0,44 0,74 0,33 10 200 0,0 6,13 6,13 5,37 5,39 10 200 0,1 2,05 2,25 4,73 5,00 10 200 0,2 2,33 2,33 2,52 3,03 10 200 0,3 1,73 1,73 2,55 1,27 10 200 0,4 1,26 1,26 1,31 1,19 10 200 0,5 0,38 0,74 0,94 1,36 10 200 0,6 0,93 0,89 0,42 0,46 10 200 0,7 0,51 0,51 0,64 0,26 10 200 0,8 0,67 0,67 0,25 0,19 10 200 0,9 0,21 0,20 0,41 0,21 10 200 1,0 0,35 0,25 0,44 0,23 20 200 0,0 5,89 5,89 1,34 1,89 20 200 0,1 5,43 5,43 1,94 1,78 20 200 0,2 3,89 3,66 1,38 2,43 20 200 0,3 1,41 1,41 0,77 2,65 20 200 0,4 2,75 3,08 1,36 3,14 20 200 0,5 2,61 2,01 1,17 2,11 20 200 0,6 1,67 1,86 1,38 0,99 20 200 0,7 0,83 0,83 0,93 0,48 20 200 0,8 1,12 0,88 0,53 0,55 20 200 0,9 0,84 0,89 0,82 0,65 20 200 1,0 0,38 0,20 0,49 0,12 20 500 0,0 5,41 5,41 1,46 2,60 20 500 0,1 4,52 4,52 1,57 1,75 20 500 0,2 2,84 2,88 1,35 2,50 20 500 0,3 2,60 1,89 1,86 1,83 20 500 0,4 1,67 1,69 1,47 1,34 20 500 0,5 2,65 2,60 1,41 1,50 20 500 0,6 1,36 1,54 0,76 0,96 20 500 0,7 0,83 0,82 0,60 0,43 20 500 0,8 0,53 0,51 0,36 0,44 20 500 0,9 0,42 0,25 0,31 0,28 20 500 1,0 0,17 0,23 0,29 0,13 Promedio 2,87 2,83 1,82 1,92 86 Capítulo 6. Anexo: ARPD en función de las características del problema ARPD de cada priority rule implementada con la TBCen función de las características de los problemas Tabla 5 ARPD de cada priority rule implementada con la TB C en función de las características de los problemas. m n w PRNEH + TBCPRFF + TBCPRLJP + TBCPRC+ TBC 5 20 0,0 72,12 72,12 129,02 7,21 5 20 0,1 8,60 8,60 18,52 5,01 5 20 0,2 1,61 1,61 9,24 3,46 5 20 0,3 3,24 3,24 5,75 0,42 5 20 0,4 2,17 2,17 2,49 0,81 5 20 0,5 1,62 1,62 1,93 0,96 5 20 0,6 1,04 1,04 1,18 2,02 5 20 0,7 0,51 0,51 1,35 1,05 5 20 0,8 0,56 0,56 1,74 2,80 5 20 0,9 1,27 1,27 1,14 1,50 5 20 1,0 0,60 0,60 1,69 1,35 10 20 0,0 7,94 7,94 8,56 6,61 10 20 0,1 7,45 7,45 9,55 6,59 10 20 0,2 5,48 5,48 6,32 4,20 10 20 0,3 3,94 3,94 4,51 3,16 10 20 0,4 3,21 3,21 4,26 2,97 10 20 0,5 2,45 2,45 3,53 3,02 10 20 0,6 2,20 2,20 3,29 2,54 10 20 0,7 1,00 1,00 1,96 1,08 10 20 0,8 0,91 0,91 2,49 1,96 10 20 0,9 1,08 1,08 1,27 1,03 10 20 1,0 1,17 1,17 0,44 1,11 20 20 0,0 5,11 5,11 2,78 4,50 20 20 0,1 4,93 4,93 2,03 3,97 20 20 0,2 3,99 3,99 1,85 5,28 20 20 0,3 3,84 3,84 3,88 4,12 20 20 0,4 3,84 3,84 2,58 2,83 20 20 0,5 3,65 3,65 2,02 3,36 20 20 0,6 3,50 3,50 0,59 1,75 20 20 0,7 1,94 1,94 0,82 1,75 20 20 0,8 1,51 1,51 0,78 0,90 20 20 0,9 1,74 1,74 0,39 0,90 20 20 1,0 0,88 0,88 0,27 0,63 5 50 0,0 3,70 3,70 8,85 11,71 5 50 0,1 1,20 1,20 4,26 5,53 5 50 0,2 0,98 0,98 2,93 3,90 5 50 0,3 0,78 0,78 2,05 3,07 5 50 0,4 0,80 0,80 0,82 0,87 5 50 0,5 0,62 0,62 0,48 0,83 5 50 0,6 0,50 0,50 1,24 2,03 87 m n w PRNEH + TBCPRFF + TBCPRLJP + TBCPRC+ TBC 5 50 0,7 0,40 0,40 0,44 1,47 5 50 0,8 0,82 0,82 0,47 0,55 5 50 0,9 0,58 0,58 0,25 0,30 5 50 1,0 0,24 0,24 0,40 0,47 10 50 0,0 13,01 13,01 5,09 10,43 10 50 0,1 7,95 7,95 4,06 10,20 10 50 0,2 6,17 6,17 2,95 7,71 10 50 0,3 3,84 3,84 3,22 4,85 10 50 0,4 3,96 3,96 2,50 3,57 10 50 0,5 3,01 3,01 1,74 3,67 10 50 0,6 2,53 2,53 2,12 2,49 10 50 0,7 2,03 2,03 0,60 2,48 10 50 0,8 0,84 0,84 1,21 0,90 10 50 0,9 0,77 0,77 1,48 0,92 10 50 1,0 0,91 0,91 0,34 0,55 20 50 0,0 7,62 7,62 3,10 1,32 20 50 0,1 5,45 5,45 3,50 1,43 20 50 0,2 3,87 3,87 3,48 3,60 20 50 0,3 3,31 3,31 2,42 3,56 20 50 0,4 4,24 4,24 2,15 3,06 20 50 0,5 2,66 2,66 1,74 2,13 20 50 0,6 1,59 1,59 0,74 1,64 20 50 0,7 2,50 2,50 1,73 1,24 20 50 0,8 2,09 2,09 0,41 1,52 20 50 0,9 1,05 1,05 0,65 0,86 20 50 1,0 0,40 0,40 0,76 0,60 5 100 0,0 21,13 21,13 26,59 5,74 5 100 0,1 1,80 1,80 1,36 1,79 5 100 0,2 1,14 1,14 1,22 0,38 5 100 0,3 0,55 0,55 0,68 0,90 5 100 0,4 0,36 0,36 0,64 0,43 5 100 0,5 0,41 0,41 0,42 0,37 5 100 0,6 0,71 0,71 0,61 0,11 5 100 0,7 0,32 0,32 0,68 0,23 5 100 0,8 0,31 0,31 0,24 0,42 5 100 0,9 0,10 0,10 0,13 0,13 5 100 1,0 0,08 0,08 0,09 0,16 10 100 0,0 6,82 6,82 2,92 3,06 10 100 0,1 4,00 4,00 2,03 2,27 10 100 0,2 2,45 2,45 1,95 2,10 10 100 0,3 2,62 2,62 1,16 1,63 10 100 0,4 1,97 1,97 0,74 1,40 10 100 0,5 1,17 1,17 1,64 0,55 10 100 0,6 0,80 0,80 0,69 0,74