Una visión sobre el problema de programación de transportadores

III Jornadas de Ingeniería de Organización Barcelona, 16-17 de septiembre de 1999 UNA VISIÓN SOBRE EL PROBLEMA DE PROGRAMACIÓN DE TRANSPORTADORES Mateo, M.1; Companys, R.2; Bautista, J.1 1 Departamento de Organización de Empresas e Instituto de Organización y Control ETSEIB. Universidad Politécnica de Cataluña e-mails: [email protected], [email protected] 2 Departamento de Organización de Empresas ETSEIB. Universidad Politécnica de Cataluña e-mail: [email protected] RESUMEN El problema HSP (Hoist Scheduling Problem) consiste en establecer la programación de los movimientos de transportadores que deben trasladar piezas o contenedores a través de una línea de producción compuesta por diversas estaciones o baños, para el cual se presenta los modelos asociados a algunas variantes. Los tiempos de operación no son fijos, sino acotados inferior y superiormente. El traslado de objetos entre estaciones lo realizan uno o varios transportadores, que consumen un tiempo mayor en carga que en vacío. El objetivo es establecer una secuencia de movimientos del transportador para maximizar la tasa de producción del sistema. Palabras clave: programación, secuenciación, HSP. 1. INTRODUCCIÓN En una parte del sistema productivo de empresas dedicadas a la fabricación de circuitos integrados impresos, se utiliza una secuencia de reacciones químicas que actúan sobre las placas. Dichas placas son sumergidas secuencialmente en una serie de tanques que contienen las soluciones. Las placas se transportan en contenedores mediante transportadores o grúas aéreos, que consumen un tiempo importante. Esto lo convierte en cuello de botella del sistema productivo. Un proceso de este tipo requiere de 10 a 20 inmersiones diferentes, para las cuales se establece un tiempo mínimo en que la placa debe estar sumergida en cada tanque de proceso y, para la mayoría, un tiempo máximo de inmersión. Otras características observables en estas líneas de producción (figura 1) son: • Todos los tanques se encuentran alineados. • Las placas se colocan en un contenedor en un extremo de la línea (estación de carga). • El contenedor se desplaza entre tanques diferentes transportado por una grúa. • Habitualmente, en un instante determinado, se puede encontrar más de un contenedor en el sistema, cada uno de los cuales debe pasar por la misma secuencia de operaciones. • En ningún caso, dos contenedores pueden ocupar un mismo tanque. • Después de dejar un contenedor, la grúa puede quedar libre del contenedor y trasladarse a otro baño, donde recogerá otro contenedor. Después de levantar un contenedor, si se recoge de un tanque con contenido líquido, el transportador debe parar sobre el tanque para escurrir. • Cuando un contenedor finaliza todas sus inmersiones, se dirige a la estación de descarga, donde se extraen las placas del contenedor. Figura 1: Esquema de un proceso de galvanización. A menudo, se plantean variaciones a esta situación básica, como configuraciones alternativas en las operaciones de carga y descarga, o en la secuencia de tanques, transportadores adicionales para repartir las operaciones de transporte, o tanques con procesos duplicados para incrementar la producción. 2. DESCRIPCIÓN DEL HOIST SCHEDULING PROBLEM 2.1. Principales características del problema La situación planteada en la fabricación de componentes electrónicos se suele formalizar de una manera más simple, conocida como HSP (Hoist Scheduling Problem), de la que se va a tratar en adelante. Se supone que deben procesarse M objetos o contenedores (j=1,...,M) recibiendo un tratamiento o una operación en N baños, tanques o estaciones distintas (i=1,...,N). Estos M objetos pueden ser todos ellos idénticos o bien diferentes entre sí. La permanencia de una determinada pieza j en cada estación debe durar un tiempo comprendido entre un valor mínimo ai,j y un máximo bi,j. Si todos los objetos son iguales, los valores sólo dependen de la estación: ai : tiempo mínimo que un contenedor debe permanecer en un tanque i, bi : tiempo máximo que un contenedor puede permanecer en un tanque i. Uno o varios transportadores se encargan de realizar el movimiento de objetos entre las estaciones correspondientes a dos tratamientos consecutivos. La estación de carga se corresponde al punto de entrada de los objetos en el sistema, mientras que la estación de descarga se corresponde al punto de salida. El tiempo de movimiento del transportador no es despreciable frente a las otras magnitudes temporales del problema. Suponiendo los tanques ordenados según las etapas del proceso, y para un único tipo de objetos, se definen: c1i : tiempo que transcurre desde que el transportador retira el objeto del tanque i hasta que se deposita en el tanque i+1, c0i,j : tiempo que transcurre en el movimiento del transportador sin carga desde el tanque i hasta el tanque j. En este tipo de problemas, siempre se cumplen dos propiedades relativas al tiempo de movimiento de los transportadores: 1) c0i,j = c0j,i 2) c1i > c0i,i+1 pues c1i = c0i,i+1 + T T es un tiempo constante para subir y bajar el contenedor más el de amortiguar la oscilación del transporte antes de colocar el contenedor en el tanque. Este tiempo no es necesario si el transportador se mueve sin carga entre tanques. Todo esto plantea un problema combinatorio, cuyo objetivo es minimizar el tiempo de ocupación de las instalaciones, para así incrementar al máximo la productividad. 2.2. Clasificación de variantes en el problema HSP El Hoist Scheduling Problem puede plantear diversas situaciones en función de las características que presenten los elementos propios del sistema: baños, productos y transportadores. Así, los tanques de la cadena productiva pueden ser de diferentes tipos: • mono-baño, cuando un tanque sólo puede tratar un contenedor a la vez; • multi-baño, cuando el tanque permite tratar más de un contenedor a la vez, por tener compartimentos, o también cuando existen tanques repetidos de un mismo tipo. Por otro lado, según el número de operaciones distintas a realizarse sobre un objeto en dicho baño, los tanques se clasifican entre: • mono-función, si sólo realizan un tratamiento específico sobre los objetos; • multi-función, en caso de más de un tratamiento sobre los objetos. Si se observa los tipos de productos tratados en el proceso, éstos pueden ser: • homogéneos, si se trata de diversas unidades de un único tipo; • heterogéneos, si se trata de unidades diferentes entre sí. Esta clasificación comporta diferentes tipos de programación de operaciones para los transportadores. En caso de objetos homogéneos, la problemática se repite de manera cíclica, y el objetivo es hallar una secuencia de operaciones en las diferentes etapas tal que pueda repetirse continuamente y que minimice el tiempo de ciclo. Mientras, en caso de objetos heterogéneos se generan situaciones diversas, cada una de las cuales parte de un estado inicial del sistema vacío y finaliza cuando la última pieza abandona el sistema. Por tanto, la función objetivo minimiza el instante de finalización de proceso del último contenedor. Finalmente, la estrategia de búsqueda de secuencias también depende del número de transportadores o grúas del sistema. Combinando estos tres grupos de información, es posible establecer el estado del sistema determinado por: • El número y la localización de las grúas. • El número, tipo y la localización de los objetos o contenedores. • Los tiempos de remojo transcurridos en los baños por cada objeto, a cada momento. 2.3. Aportaciones históricas al problema El Hoist Scheduling Problem como problema de programación se puede clasificar entre los problemas de flujos de piezas “flow-shop” o “job-shop” y los problemas de una sola máquina, en caso de un solo transportador para diversas tareas. Manier y Baptiste (1994) detectaron hasta hace unos cinco años relativamente pocos trabajos sobre el tema, si bien en este tiempo se ha registrado un incremento en las aportaciones. Normalmente, se trata de estudios del caso mono-grúa, productos homogéneos y con recipientes mono-baño y mono-función. Dichos artículos buscan una secuencia de movimientos óptima, programando a las grúas para que respeten escrupulosamente las fechas de finalización de los productos, y suponiendo que el sistema padece escasas interrupciones imprevistas. Partiendo de Philips y Unger (1976), que plantean un programa lineal mixto entero, Shapiro y Nuttle (1988) y Armstrong et al. (1994) aplican la programación lineal en el contexto de un procedimiento de branch & bound. Autores como Baptiste et al. (1992) y Varnier et al. (1995) han introducido alguna otra técnica efectiva, como la propagación lógica de restricciones, proviniendo del campo de la inteligencia artificial. Finalmente, un conjunto de artículos, como los aportados por Yih (1988) y Thesen y Lei (1990), presenta un control sobre la grúa bajo reglas heurísticas para determinar fechas de entrada de los sucesivos productos, o lotes de productos, y establecer secuencias de movimientos. Esta aproximación es sumamente útil cuando se trabaja simultáneamente con diversos productos en la línea. 3. LÍNEAS DE PRODUCCIÓN CON OBJETOS IDÉNTICOS Los tamaños de lote para este tipo de líneas suelen ser bastante grandes, por lo que pasan días e incluso semanas entre cambios en la programación. Por tanto, las grúas se controlan numéricamente mediante una secuencia fijada de operaciones que se repite indefinidamente, secuencia cíclica. Esta situación se enmarcará en el caso más básico, con una grúa que visita recipientes mono-baño y mono-función. 3.1. Hipótesis del modelo matemático a plantear Las hipótesis de partida en que se basa el modelo planteado son: 1. El tiempo de proceso en cada estación debe estar entre el intervalo dado. 2. El transporte de los objetos lo realiza una única grúa. 3. La operación de transporte no se puede interrumpir. 4. La estación de carga tiene los objetos preparados cuando llega la grúa. 5. El tanque i debe estar vacío cuando llega un objeto. 6. Todos los tanques están ordenados según las etapas del proceso. 7. Todos los productos tratados son idénticos y siguen una misma ruta. El objetivo consiste, pues, en minimizar el tiempo de ciclo de las acciones de un único transportador para un conjunto de productos homogéneos que deben pasar por N etapas, con un tanque asignado a cada una de las cuales y restricciones de ventana. Esto implica que la duración de inmersión de un contenedor en un baño sea idéntica para todos los productos y que la solución buscada sea periódica. 3.2. Las secuencias de movimientos y tiempos Sean mi, movimiento del objeto del baño i al baño i+1, 0≤ i ≤ N; ti, tiempo de inicio del movimiento mi. Una secuencia cíclica (M,T) se define a partir de: 1. Secuencia (orden de movimientos): M = <m[0], m[1], ..., m[k], ..., m[N]> 2. Tiempos de inicio de los movimientos: T = <t[0], t[1], ..., t[k], ..., t[N]> La secuencia M es una permutación circular de los N+1 baños a visitar por el transportador. Las expresiones m[k] = mj; t[k] = tj indican que el movimiento de transporte del contenedor entre los baños i e i+1 ocupa la k-ésima posición de la secuencia, tomando como primer movimiento aquél que parte de la estación de carga: m[0] = 0; t[0] = 0. Finalmente, la secuencia de tiempos debe cumplir que t[0] < t[1] < ... < t[N], siendo el tiempo de ciclo TC(M,T) = t[N+1]. 3.3. Formulación del programa lineal matemático PL(M) Si bien el modelo planteado puede resolverse con diferentes procedimientos, uno primero considera las relaciones temporales en los baños y en movimientos del transportador siguiendo el esquema de un programa lineal función del vector M. Se dispone como partida de tres grupos de datos, ya definidos en apartados anteriores: 1. Restricciones de ventana (para cada baño): ai, bi para i = 1,2, ...,N 2. Tiempos de movimiento: c1i, c0i,j para i = 1,2, ...,N; 0 ≤ i,j ≤ N+1 3. Secuencia de movimientos: M = <m[0]=0, m[1], ..., m[N]> Las variables cuyos valores deben hallarse en este programa lineal son: 1. Tiempo de inicio de movimientos: T = <t[0], t[1], ..., t[N]> 2. Tiempo de ciclo: TC(M,T) = t[N+1] siendo ti el instante en el cual que se extra un contenedor del tanque i (i=0,1,..., N) y TC, el inicio del movimiento N+1, o sea, el siguiente movimiento inicial t[0]. Dichas variables se encuentran sometidas a dos tipos de restricciones: 1. Restricciones de tiempo de proceso del objeto en un tanque: si se inicia el ciclo con el tanque i vacío: ai ≤ ti – (ti-1+c1i) ≤ bi si se inicia el ciclo con el tanque i lleno: ai ≤ TC+ti – (ti-1+c1i) ≤ bi 2. Restricciones de tiempo de viaje de la grúa: t[k] - t[k-1] ≥ c1[k-1] + c0[k-1]+1,[k] tomando como objetivo: [MIN] TC(M,T) = t[N+1] Dada una secuencia de operaciones M, el programa lineal cuenta, pues, con N+1 variables y 2N+1 restricciones. 3.4. La alternativa: la resolución mediante grafo El modelo anterior puede plantearse y resolverse mediante un grafo, sin necesidad de recurrir a la programación lineal. Este método alternativo, cuya línea de trabajo plantea Fernández (1995), se denomina MCM (Método del Camino Mínimo). Los nodos de dicho grafo son los tanques a los que la grúa se desplaza con carga, en caso de tener que depositar un objeto, o sin carga, si va a recogerse un objeto: • los nodos de salida corresponden a tanques de recogida (se llega sin carga); • los nodos de llegada corresponden a tanques de depósito (se llega con carga). Los valores en los arcos se asocian a los tiempos (de la grúa o de los objetos): • los arcos de proceso son debidos a la permanencia de los objetos en los baños: valores mínimos, ai, y máximos, bi; • los arcos de movimiento son debidos a desplazamientos del transportador: con carga, c1i y sin carga: c0i,j. 4. PROCEDIMIENTO BASADO EN BRANCH & BOUND Dada una secuencia M, determinar si es secuencia factible, y en dicho caso, hallar el tiempo de ciclo óptimo TC*(M,T) implica evaluar N! secuencias, es decir: TC*(M*,T*) = Min { TC(M,T) | ∀ (M,T) factible } Se pueden seleccionar procedimientos heurísticos o exactos, como el siguiente, el cual sigue un esquema de branch & bound con las siguientes características: 1. Caracterización de los vértices de la arborescencia: El número de niveles de la arborescencia es el mismo que el número de tanques del proceso, N, siendo el número de nodos del nivel i (i=1,2,...,N) = i! Un nudo o vértice de nivel i puede definirse como: P[0][i] = <m[0], m[1], ..., m[i]>, que corresponde a una permutación de {m[0]=m0, mj | j=1,2,...,i}. 2. Procedimiento de separación: Cada P[0][i] = <m[0], m[1], ..., m[i]> se obtiene insertando mi entre dos movimientos de P[0][i-1]. Así pues, el número de descendientes de un nudo P[0][i] es de i+1, que se van creando a partir del nudo raíz P[0][1] formado por los movimientos: P[0][1] = <m[0], m[1]>. 3. Procedimiento de acotación. Para cada nudo P[0][i] = <m[0], m[1], ..., m[i]> debe resolverse el programa lineal PL(M) aplicando el MCM, que puede comportar dos tipos de resultado: permutación de movimientos no factible o factible con TC(Mi,Ti). Sea Ui, el conjunto de movimientos no asignados en la permutación P[0][i]; una cota inferior del tiempo de ciclo incorporando los movimientos no asignados mj∈Ui a una P[i][j] se calcula como: TInf(P[i][j]) = TC(Mi,Ti)+max{ ∑(mj∈Ui) c1j - ∑(0≤v≤1) ev } siendo ∑ev el tiempo muerto de la grúa hasta este momento en un ciclo. 4. Elección del vértice de exploración inmediata: Se debe escoger el nudo con menor TInf(P[i][j]); y en caso que TInf(P[i][j]) > TCbest, se elimina P[0][i], donde TCbest es la mejor solución hasta ese momento de la exploración. Algoritmo basado en branch &bound 1. TCbest = ∑(k=0;N) c1k + ∑(i=1;N) ai + c0N+1,0 ; k = 1; Q1 = { P[0][1] } 2. Construir k+1 secuencias P[0][k+1] insertando mk+1 en todas las posibles posiciones de P[0][k]. Si (k+1) < N 3.1. Resolver los k+1 nodos P[0][k+1] por el procedimiento MCM. 3.2. Si un nodo es factible y TInf(P[0][k+1]) ≤ TCbest ⇒ añadir a Qk+1. 3.3. k = k+1 3.4. Si Qk = {∅} ⇒ k = k-1; ir a 3.4. 3.5. Si k=1, entonces FIN. 3.6. Escoger P[0][k] con menor TInf(P[0][k]); Qk = Qk - P[0][k]. Ir a 2. Si (k+1) = N 4.1. Resolver cada nodo P[0][N]. 4.2. Si TC(M,T) < TCbest ⇒ TCbest =TC(M,T) 4.3. k = k-1; ir a 3.4. 5. CONCLUSIONES Las aportaciones en el problema tratado, Hoist Scheduling Problem, parecen indicar que el procedimiento aquí planteado permite encontrar de manera eficiente un programa óptimo del transportador. No obstante, la situación simple analizada suele darse pocas veces en la realidad, lo que implica utilizar modelos más complejos que incluyan las bases conceptuales aquí expuestas. 6. REFERENCIAS ARMSTRONG R., LEI L., SHANHONG G. (1994): A bounding scheme for deriving the Minimal Cycle Time of a single transporter N-stage process with time window constraints, European Journal of Operational Research, 130-140. BAPTISTE P., LEGEARD B., VARNIER C. (1992): Hoist scheduling problem : an approach based on constraints logic programming, IEEE International Conference on Robotics and Automation, vol. 2, 1139-1144. FERNÁNDEZ R. (1995): Métodos para hallar el tiempo de ciclo mínimo en un proceso de N etapas con un robot transportador y restricciones ventana. Proyecto Final de Carrera, ETSEIB. MANIER M.-A., BAPTISTE P. (1994): Etat de l’art: ordonnancement de robots de manutention en galvanoplastie, APII, vol. 28, nº 1, 7-35. PHILIPS L.W., UNGER P.S. (1976): Mathematical programming solution of a hoist scheduling program, AIEE Transactions, vol. 8, nº 2, 219-225. SHAPIRO G.W., NUTTLE H.L.W. (1988): Hoist Scheduling for a PCB electroplating facility, IEE Transactions, vol 20, nº 2, 157-167. THESEN A., LEI L. (1990): An expert scheduling system for material handling hoists, Journal of Manufacturing System, vol. 9, nº 3, 247-252. VARNIER C., GRUNDER O., BAPTISTE P. (1995): Improving the productivity of electroplating lines by changing the layout of the tanks, IEEE 0-7803-25354/95, 441-450. YIH Y. (1988): An algorithm for hoist scheduling problems, International Journal of Production Research, vol. 32, nº 3, 501-516.