Correlación entre criterios clásicos de secuenciación y medidores de producción en procesos de fabricación de flujo regular

V Congreso de Ingeniería de Organización Valladolid-Burgos, 4-5 Septiembre 2003 ƒ Índice Correlación entre criterios clásicos de secuenciación y medidores de producción en procesos de fabricación de flujo regular* José M. Framiñán1, Rafael Ruiz-Usano2, Pedro L. González3, 1 Ingeniero Industrial, Escuela Superior de Ingenieros, Universidad de Sevilla, Camino de los Descubrimientos, s/n, 41092, Sevilla [email protected] 2 Ingeniero Industrial, Escuela Superior de Ingenieros, Universidad de Sevilla, Camino de los Descubrimientos, s/n, 41092, Sevilla [email protected] 3 Ingeniero de Organización Industrial, Escuela Superior de Ingenieros, Universidad de Sevilla, Camino de los Descubrimientos, s/n, 41092, Sevilla pedrol[email protected] RESUMEN En esta comunicación se estudia la relación existente entre los criterios empleados para la secuenciación de operaciones y los indicadores de funcionamiento habituales en el nivel operativo de la planificación y control de la producción (es decir: el inventario en proceso y los niveles de servicio y/o tasas de producción). Aunque la relación entre algunos de los criterios de secuenciación y alguno de los indicadores de funcionamiento es bien conocida, aquí se aborda el problema para el conjunto de criterios de secuenciación y de indicadores de funcionamiento más empleados en la literatura y la práctica, aplicado a procesos de fabricación de flujo regular. Mediante la generación de un conjunto de problemas aleatorios, se minimiza cada uno de los criterios de secuenciación y se analizan los valores de los distintos indicadores de funcionamiento considerados. Los resultados ponen de manifiesto que alguno de los criterios de secuenciación empleados se encuentran dominados por otros en el sentido de que ofrecen peores valores para todos los indicadores de funcionamiento considerados. 1. Introducción En la literatura clásica sobre secuenciación de trabajos se ha venido empleando como objetivo la minimización de una serie de criterios tales como el tiempo máximo de terminación (makespan), el tiempo total de terminación (flowtime), o la máxima tardanza sobre una fecha dada (tardiness). Por otra parte y de forma independiente, la mayor parte de referencias relativas a los sistemas de control de la producción hacen énfasis en criterios como la tasa de producción (throughput), el nivel de servicio (fill rate o service level), la utilización de las máquinas y el inventario en proceso. Aunque las relaciones entre alguno de los criterios empleados en secuenciación y alguno de los empleados en control de la producción son fácilmente demostrables (por ejemplo, es bien conocido que la minimización del tiempo máximo de terminación de los trabajos maximiza la tasa de producción y la utilización de las máquinas), no es posible determinar de forma teórica el efecto de algunos criterios de secuenciación sobre los de control de la producción (por ejemplo, no es posible establecer de forma cerrada el efecto de la minimización de la máxima tardanza sobre el inventario en * Este trabajo ha sido desarrollado en colaboración con Rainer Leisten (Universidad de Duisburg-Essen, Alemania), quien no figura como coautor al no estar inscrito en el congreso. Este trabajo se deriva de la participación de sus autores en un proyecto de investigación con financiación procedente del Ministerio de Ciencia y Tecnología (Proyecto DPI2001-3110), y con cofinanciación proveniente del Fondo Europeo de Desarrollo Regional (FEDER). V Congreso de Ingeniería de Organización Valladolid-Burgos, 4-5 Septiembre 2003 proceso). Además, dentro del control de la producción es habitual buscar un compromiso entre varios de los criterios empleados (principalmente entre nivel de servicio/tasa de producción e inventario en proceso), por lo que también es de interés el conocer la contribución de cada uno de los criterios empleados en secuenciación respecto a los distintos criterios habitualmente empleados en control de la producción. Este conocimiento también sería de utilidad en el campo de la secuenciación multicriterio, ya que permitiría emparejar criterios de secuenciación complementarios respecto a criterios de control de la producción. Por último, este estudio podría permitir discernir la utilidad del empleo de criterios de secuenciación cuya influencia sobre los inventarios en proceso o la tasa de producción no es obvia (como la minimización de la varianza del tiempo total de terminación o CTV – Completion Time Variance, ver [1,2,3]), o criterios de secuenciación que admiten definiciones alternativas (como sucede con las diferentes definiciones posibles del criterio de minimización de tiempos muertos – idle time –). Esta comunicación presenta los primeros resultados de un trabajo más amplio para el estudio de la correlación entre criterios de secuenciación y criterios de control de la producción. Los resultados que se presentan aquí se centran en entornos de producción de flujo regular (tipo flowshop) y bajo criterios de secuenciación no relacionados con fechas de entrega. La comunicación se estructura de la siguiente forma: en la siguiente sección se discuten los principales criterios usados en secuenciación y en control de la producción, así como la justificación para su empleo. En la sección 3 se presenta el diseño de los experimentos para estudiar la relación entre ambos tipos de criterios. Los resultados, así como unos breves comentarios sobre los mismos se muestran en la sección 4. 2. Criterios de control de la producción y criterios de secuenciación 2.1. Criterios de control de la producción En entornos de producción estrictamente contra pedido, cada trabajo pertenece a un cliente concreto, el cual espera que le sea entregado en una fecha prefijada. Por lo tanto, el cumplimiento de las fechas de entrega será la principal medida de eficiencia de un sistema de control de la producción de estas características. El grado de cumplimiento de las fechas de entrega se mide habitualmente como nivel de servicio o fracción de pedidos atendidos dentro de la fecha de entrega prevista. Cuando los pedidos no tienen asociada una fecha de entrega diferenciada para cada pedido, es habitual manejar como criterio de eficiencia del sistema la tasa de producción del mismo, expresada como número de pedidos que puede procesar el sistema por unidad de tiempo. A corto plazo, el aumento de la tasa de producción del sistema implica la explotación al máximo de las capacidades y recursos del mismo, mientras que a largo plazo implica la posibilidad de acortar los plazos de entrega de los pedidos, ofreciendo los productos en menor tiempo y disminuyendo la longitud del ciclo dinero – productos – dinero. Junto con el grado de cumplimiento de las fechas de entrega o la tasa de producción, otra medida importante es el volumen de inventario en proceso del sistema. Mientras que el nivel de servicio tiene un efecto positivo sobre los ingresos de la empresa, el inventario está ligado directamente a los costes de operación. Desde esta perspectiva, la minimización del inventario V Congreso de Ingeniería de Organización Valladolid-Burgos, 4-5 Septiembre 2003 es deseable. Sin embargo, el inventario sirve también para proteger el sistema frente a la variabilidad (para una discusión sobre las fuentes de variabilidad en un sistema de control de la producción, ver por ejemplo [4]). Por lo tanto, aceptar niveles de inventario por encima de los estrictamente requeridos en el caso determinista puede ser de interés en escenarios con un cierto grado de variabilidad. Por todo lo anterior, el cumplimiento de las fechas de entrega/tasa de producción y la reducción de inventarios son considerados por la mayor parte de los autores (por ejemplo [5], [4], [6]) como objetivos primordiales en el nivel operativo de la planificación de la producción. 2.2. Criterios de secuenciación Mientras que las definiciones de tiempo total de terminación y tiempo máximo de terminación son claras, la definición de tiempos muertos puede ser (al menos) definida de tres formas distintas: - incluyendo la ‘cabeza’ y la ‘cola’ de cada máquina, es decir, el tiempo antes de que el primer trabajo sea procesado en esa máquina, y el tiempo después de que el último trabajo sea procesado en la máquina. El incluir estos dos aspectos en la definición de tiempo muerto hace que, como es bien sabido, su minimización sea equivalente a la del tiempo máximo de terminación (ver, por ejemplo, [7] o [8]). Por tanto, este caso no se considerará de forma independiente, sino que las conclusiones correspondientes al tiempo máximo de terminación se considerarán aplicables a esta definición del tiempo muerto. - Excluyendo ‘cabeza’ y ‘cola’ de cada máquina, lo que implícitamente equivale a suponer que la máquina puede ser empleada para realizar otros trabajos fuera de la secuencia considerada antes o después de que la secuencia bajo consideración haya pasado la máquina en cuestión. En adelante, nos referiremos a esta definición como TM (tiempo muerto) a secas. - Otros autores (por ejemplo [9,10]) incluyen la ‘cabeza’ de cada máquina en la definición de tiempo muerto, mientras que no incluyen la ‘cola’. Esto tiene el significado de que las máquinas están reservadas para los trabajos de la secuencia pero que, una vez que todos los trabajos han sido procesados en una máquina, ésta queda libre para el siguiente grupo de trabajos. Nos referiremos a esta definición de tiempo muerto como TMC. Aunque es posible obtener otras definiciones de tiempo muerto, no conocemos ninguna de ellas que haya sido empleada en la literatura sobre secuenciación. Por tanto, no serán tenidas en cuenta en los experimentos. 3. Diseño de los experimentos Para comparar los resultados de los distintos criterios de secuenciación, se ha diseñado un conjunto de 660 problemas. El número de trabajos, n, toma los siguientes valores: n ∈{5, 10, 20, 25, 50, 100}, mientras que el número de máquinas m toma los siguientes valores m ∈{5, 10, 20, 30, 50}. Para cada tamaño de problema, se han generado 30 problemas y los V Congreso de Ingeniería de Organización Valladolid-Burgos, 4-5 Septiembre 2003 respectivos tiempos de procesos obtenidos a partir de una distribución discreta uniforme [1,99]. Los experimentos han sido llevados a cabo de la siguiente forma: para cada uno de los problemas, se buscan las secuencias que minimizan cada uno de los criterios de secuenciación siguientes: tiempo máximo de terminación, tiempo total de terminación, TM, TMC, y CTV. Para problemas de pequeño tamaño (hasta 10 trabajos) ha sido posible encontrar la secuencia óptima de cada uno de estos criterios mediante búsqueda exhaustiva (exploración del espacio completo de soluciones). Para problemas de mayor tamaño, cada secuencia se ha obtenido mediante la aplicación de un algoritmo de búsqueda tabú que genera vecinos mediante el intercambio de dos posiciones cualesquiera. El criterio de terminación del algoritmo ha sido el de parar si en las últimas 500 iteraciones del mismo no ha sido posible encontrar una solución mejor. Para chequear la potencia de este algoritmo, se ha comprobado que la solución encontrada por el mismo para todos los problemas de pequeño tamaño coincidía con la encontrada por la búsqueda exhaustiva. Una vez que se ha encontrado la secuencia que minimiza un criterio de secuenciación determinado, se calculan la tasa de producción y el nivel de inventario en proceso asociados de la siguiente manera: la tasa de producción (TP) equivale al número de trabajos de la secuencia entre el tiempo máximo de terminación de la misma. A continuación, se obtiene el tiempo de ciclo (TC) tras dividir la suma de los tiempos de terminación de los trabajos de la secuencia entre el número de trabajos. Finalmente, el inventario en proceso se obtiene de multiplicar TP y TC, de acuerdo con la ley de Little. 4. Resultados de los experimentos En la tabla 1 se muestran los valores medios de la tasa de producción y WIP para cada tamaño de problema y para criterio de secuenciación. En negrita se muestran los valores correspondientes a tamaños de problema para las que se han encontrado las secuencias óptimas. En la tabla 2 se muestra, para cada criterio de secuenciación, el porcentaje de problemas de un tamaño dado para los que ese criterio de secuenciación es un óptimo débil de Pareto respecto al resto de los demás criterios de secuenciación. Más formalmente: Sea Si la secuencia que se obtiene al minimizar un criterio de secuenciación i, y sean WIP(Si) y TH(Si) el inventario en proceso y la tasa de producción asociadas a esa secuencia (calculadas de la forma descrita en el apartado anterior). Sj es un óptimo débil de Pareto con respecto al conjunto de criterios considerados si cumple que WIP(Si) ≤ WIP(Sj) y TH (Si) ≥ TH (Sj) ∀ j ≠ i. Esta ‘optimalidad débil de Pareto’ puede ser medida de forma individual para cada problema dentro de un tamaño determinado (porcentaje de veces que esto sucede sobre el total de problemas considerados), o bien de forma agregada (considerando las medias de inventario en proceso y tasa de producción para un tamaño de problemas determinado). En la tabla 2 se muestran los porcentajes y se sombrean aquellas celdas en las que dicha ‘optimalidad débil de Pareto’ se verifica para la media sobre los 30 problemas de un tamaño considerado. V Congreso de Ingeniería de Organización Valladolid-Burgos, 4-5 Septiembre 2003 Makespan Flowtime IT ITH CTV n m TH WIP TH WIP TH WIP TH WIP TH WIP 5 5 0.010 2.961 0.009 2.560 0.009 3.107 0.010 2.959 0.009 3.138 5 10 0.006 3.664 0.006 3.205 0.006 3.749 0.006 3.661 0.006 3.790 10 5 0.013 4.489 0.012 3.583 0.012 4.796 0.013 4.536 0.012 4.803 10 10 0.009 5.871 0.009 5.020 0.008 6.086 0.009 5.871 0.009 6.036 20 5 0.016 5.958 0.015 4.564 0.015 6.580 0.016 5.997 0.015 6.214 20 10 0.013 8.676 0.011 7.135 0.011 9.288 0.012 8.676 0.011 8.936 20 20 0.009 11.661 0.008 9.954 0.008 12.029 0.008 11.570 0.008 11.949 20 30 0.007 13.227 0.006 11.458 0.006 13.366 0.007 13.031 0.006 13.567 20 50 0.005 15.055 0.005 13.316 0.004 15.033 0.005 14.683 0.005 15.236 25 5 0.017 6.920 0.016 4.946 0.016 7.571 0.017 6.973 0.015 7.283 25 10 0.013 10.087 0.012 8.293 0.012 10.912 0.013 10.209 0.012 10.337 25 20 0.010 13.737 0.009 11.547 0.009 14.248 0.009 13.707 0.009 14.050 25 30 0.008 15.704 0.007 13.422 0.007 15.960 0.007 15.434 0.007 15.834 25 50 0.006 17.781 0.005 15.551 0.005 17.945 0.005 17.393 0.005 18.056 50 5 0.018 9.344 0.017 6.012 0.017 10.322 0.018 9.754 0.017 10.219 50 10 0.016 14.574 0.015 11.014 0.015 15.388 0.016 14.773 0.015 15.174 50 20 0.013 20.704 0.012 17.214 0.012 21.366 0.012 20.700 0.012 21.309 50 30 0.011 24.041 0.010 20.553 0.010 24.637 0.010 24.001 0.010 24.103 50 50 0.008 29.439 0.008 25.719 0.008 29.594 0.008 29.040 0.008 29.873 100 5 0.019 12.795 0.018 7.108 0.018 13.916 0.019 13.384 0.018 15.468 100 10 0.018 19.979 0.017 14.264 0.017 21.222 0.017 20.184 0.017 21.570 100 20 0.015 28.832 0.014 23.659 0.014 29.779 0.015 28.861 0.014 30.221 Tabla 1. Valores medios de WIP y tasa de producción obtenidos para las secuencias que minimizan un criterio determinado Ni en la tabla 1 ni en la tabla 2 se deducen diferentes patrones de comportamiento entre aquellos tamaños de problemas para los que se ha podido encontrar la secuencia óptima mediante exploración exhaustiva y aquellos para los que se ha debido emplear el algoritmo de búsqueda tabú. De alguna manera, ello vendría a certificar la validez de los resultados en el segundo grupo de problemas. De las tablas 1 y 2 se pueden extraer las siguientes conclusiones: i) Cuando se intenta minimizar una de las dos definiciones de tiempo muerto consideradas, se tiene que para todos los tamaños de problema la definición TMC domina a la TM. Este resultado es de alguna manera previsible, ya que si se incluye la ‘cabeza’ de la secuencia dentro del proceso de minimización, ello ayuda a reducir los tiempos de terminación, lo que a su vez disminuye el tiempo de ciclo (TC) y la tasa de producción (que es proporcional a la inversa del tiempo máximo de terminación). Según la ley de Little, esto también hace que se reduzca el inventario en proceso. ii) La minimización del criterio CTV está dominado por la minimización del tiempo máximo de terminación (y en parte, por la minimización de TMC). Por tanto, de acuerdo a estos resultados, el criterio CTV no parece ser un buen criterio de secuenciación al menos desde el punto de vista de reducción de los inventarios en proceso y de aumento de las tasas de producción. V Congreso de Ingeniería de Organización Valladolid-Burgos, 4-5 Septiembre 2003 Makespan domina Flowtime domina IT domina ITH domina CTV domina n m F IT ITH CTV C IT ITH CTV C F ITH CTV C F IT CTV C F IT ITH 20 5 0.00 0.87 0.63 0.73 0.07 0.50 0.07 0.63 0.00 0.00 0.00 0.17 0.30 0.00 0.93 0.60 0.00 0.00 0.13 0.00 20 10 0.00 0.90 0.63 0.67 0.00 0.40 0.10 0.53 0.00 0.00 0.00 0.10 0.03 0.00 0.90 0.63 0.00 0.00 0.37 0.00 20 20 0.00 0.83 0.80 0.80 0.00 0.63 0.17 0.40 0.00 0.00 0.00 0.00 0.00 0.00 0.80 0.40 0.00 0.00 0.40 0.07 20 30 0.00 0.53 0.87 0.87 0.00 0.60 0.10 0.43 0.00 0.00 0.03 0.13 0.00 0.00 0.73 0.67 0.00 0.00 0.30 0.00 20 50 0.00 0.50 0.73 0.73 0.00 0.67 0.17 0.30 0.00 0.00 0.00 0.03 0.00 0.00 0.80 0.53 0.00 0.00 0.27 0.00 25 5 0.00 0.93 0.60 0.77 0.03 0.50 0.03 0.70 0.00 0.00 0.00 0.27 0.13 0.00 0.90 0.60 0.00 0.00 0.10 0.00 25 10 0.00 0.90 0.57 0.63 0.00 0.50 0.03 0.53 0.00 0.00 0.00 0.03 0.10 0.00 0.90 0.67 0.00 0.00 0.47 0.00 25 20 0.00 0.87 0.83 0.83 0.00 0.43 0.03 0.23 0.00 0.00 0.00 0.03 0.00 0.00 0.77 0.63 0.00 0.00 0.37 0.10 25 30 0.00 0.70 0.67 0.67 0.00 0.53 0.07 0.27 0.00 0.00 0.03 0.10 0.00 0.00 0.70 0.40 0.00 0.00 0.43 0.03 25 50 0.00 0.77 0.70 0.70 0.00 0.50 0.13 0.27 0.00 0.00 0.00 0.03 0.00 0.00 0.87 0.57 0.00 0.00 0.17 0.00 50 5 0.00 0.73 0.53 0.83 0.00 0.47 0.10 0.77 0.00 0.00 0.00 0.40 0.23 0.00 0.83 0.80 0.00 0.00 0.17 0.00 50 10 0.00 0.83 0.67 0.83 0.00 0.43 0.07 0.77 0.00 0.00 0.00 0.27 0.17 0.00 0.70 0.73 0.00 0.00 0.07 0.00 50 20 0.00 0.87 0.70 0.73 0.00 0.50 0.07 0.40 0.00 0.00 0.00 0.13 0.03 0.00 0.77 0.73 0.00 0.00 0.40 0.00 50 30 0.00 0.87 0.57 0.57 0.00 0.50 0.20 0.30 0.00 0.00 0.03 0.03 0.00 0.00 0.67 0.47 0.00 0.00 0.53 0.03 50 50 0.00 0.60 0.77 0.77 0.00 0.70 0.33 0.23 0.00 0.00 0.00 0.03 0.00 0.00 0.53 0.37 0.00 0.00 0.33 0.07 100 5 0.00 0.70 0.70 1.00 0.00 0.53 0.03 0.87 0.03 0.00 0.03 0.67 0.17 0.00 0.60 0.93 0.00 0.00 0.00 0.00 100 10 0.00 0.77 0.57 0.90 0.00 0.33 0.03 0.77 0.00 0.00 0.00 0.67 0.20 0.00 0.87 0.83 0.00 0.00 0.00 0.00 100 20 0.00 0.77 0.90 0.93 0.00 0.63 0.23 0.83 0.00 0.00 0.03 0.37 0.03 0.00 0.80 0.80 0.00 0.00 0.10 0.00 0.00 0.77 0.69 0.78 0.01 0.52 0.11 0.51 0.00 0.00 0.01 0.19 0.08 0.00 0.78 0.63 0.00 0.00 0.26 0.02 Tabla 2. Resultados en términos de ‘optimalidad débil de Pareto’ V Congreso de Ingeniería de Organización Valladolid-Burgos, 4-5 Septiembre 2003 Referencias [1] Merten, A.G., y Muller, A.E., (1972), “Variance minimisation in single machine sequencing problems”, Management Science, 18, pp. 518-528. [2] Kubiak, W., (1993), “Completion time variance minimisation on a single machine is difficult”, Operations Research Letters, 14, pp. 49-59. [3] Gowrishankar, K., Rajendran, C., y Srinivasan, G., (2001), “Flow shop scheduling algorithms for minimising the completion time variance and the sum of squares of completion time deviations form a common due date”, European Journal of Operational Research, 132, pp. 643-665. [4] Hopp, W.J., y Spearman, M.L., (1996), “Factory Physics”, Irwin. [5] McClain, J.O., Thomas, J.L., y Mazzola, J.B., (1992), “Operations Management: Production of Goods and Services”, Prentice Hall. [6] T’Kindt, V., y Billaut, J.C., (2002), “Multicriteria scheduling: Theory, models and algorithms”, Springer. [7] French, S., (1982), “Sequencing and Scheduling: An Introduction to the Methodologies of the Job-Shop”, Ellis Horwood. [8] Rinnooy Kan, A.H.G., (1976), “Machine scheduling problems: Classification, Complexity, and Computations”, Martinus Nijhoff. [9] Sridhar, J., y Rajendran, C., (1996), “Scheduling in flowshop an cellular manufacturing systems with multiple objectives – a genetic algorithmic approach”, Production Planning and Control, 7, pp. 374-382. [10] Ho, J. C. y Chang, Y. L., (1991), “A new heuristic for the n-job, m-machine flowshop problem”, European Journal of Operational Research, 52, pp. 194-202.