• Author / Uploaded
• oskarts5875

• Categories
• Teoría de la complejidad computacional
• Algoritmos
• Conceptos matemáticos
• Ciencias de la Computación
• Informática teórica

Citation preview

>Universidad Distrital Francisco José de Caldas – Ingeniería Industrial

1

Formulación del Procedimiento Cuellos de Botella Móvil The Shifting Bottle Neck, Procedure and Formulation (Diciembre 2011) Oscar A. Téllez, Estudiante de Ingeniería Industrial, Universidad Distrital Francisco José de Caldas, Bogotá D.C.  Resumen—Este artículo pretende mostrar el algoritmo denominado cuellos de botella móvil más conocido en como the Shifting Bottleneck Procedure.publicado en 1988 por Joseph Adams, Egon Balas y Daniel Zawack. Además estudia la contextualización del problema, su formulación, los fundamentos teóricos y algunas mejoras realizadas mediante la meta-heurística Búsqueda Tabú. Abstract— This paper pretend to show the Shifting Bottleneck procedure publish in 1988 by Joseph Adams, Egon Balas y Daniel Zawack. Besides we present the contextualization, the formulation, theoretic foundations and better performance with some combination of the metaheuristic called Tabu Search. Índice de Términos— Cuello de Botella (Bottleneck), Sistemas tipo taller (Job Shop), Deterministico (Deterministic), Grafo (Graph), Secuenciación (Scheduling)

de optimización combinatoria, porque problemas como el agente viajero TSP se resuelven con 300 - 400 nodos y cerca de 100.000 variables, pero no se ha podido optimizar programas de 10 máquinas con 10 trabajos (Adams, Balas, & Zawack, March 1988) El problema inicial fue planteado para minimizar el makespan. Sin embargo, se le puede incluir distintas métricas según el objetivo que se desee. Entre las métricas más conocidas se encuentra la medida Lateness definida como la diferencia entre el tiempo de entrega y la finalización del trabajo. También se usa la medida Tardiness que es igula que el Lateness cuando es negativo y cero cuando es positivo. (HOPP & SPEARMAN, 2001)

II. OBJETIVO I.

INTRODUCCIÓN

E

l algoritmo cuello de botella móvil está inmerso dentro de un contexto de la Programación de la Producción, más específicamente de la secuenciación de operaciones. No obstante aunque este método surge y se desarrolla en un ambiente eminentemente productivo, su utilización puede extenderse a otras áreas del conocimiento como los servicios de mensajería, servicios electrónicos, atención hospitalaria entre otros, sin perder por ello su validez ni dificultad de solución. Programar la producción constituye uno de los retos más grandes que enfrentan los ingenieros industriales, debido a que la complejidad algorítmica que requiere. De acuerdo con la teoría de complejidad computacional existen dos clases de problema. Los problemas tipo P denominados polinomiales cuyo tiempo de computacional de solución obedece a una función polinómica determinada y por otro lado se encuentran los problemas NP-Hard cuyo tiempo de evaluación no es polínómico sino que tiene un crecimiento ascelerado que puede ser exponencial o de otra naturaleza. Los problemas Job shop scheuduling son considerados los problemas más duros

Este artículo será presentado al P. PhD. Jairo Humberto Torres Acosta para cumplir un requisito de la materia Plan y Control de la Producción II Presenta: Oscar Augusto Téllez Sánchez Cód. 20071015018 Información de contacto: [email protected], [email protected].

Estudiar los fundamentos teóricos, la formulación contextualización del procedimiento Shifting Bottleneck.

y

III. FORMULACIÓN DEL PROBLEMA A. Sistemas Tipo Taller (JOB SHOP) El sistema de producción Job shop se caracteriza por manejar bajos volúmenes de producción y gran variedad de productos. La empresa Colombiana se caracteriza porque predominan este tipo de sistemas productivos, propios de pequeñas y medianas empresas (pymes). Por esta razón el estudio de este tipo de modelos tiene un impacto significativo en Colombia y en general en Latinoamérica. B. Supuestos La mayoría de los problemas clásicos de scheduling manejan los siguiente supuestos (HOPP & SPEARMAN, 2001) - Todos los trabajos están disponibles al comienzo de la programación (no llegan trabajos después de que comience el proceso) - Los tiempos de proceso son determinísticos. - Los tiempos de proceso no dependen de la programación (p.e. no hay setups) - Las máquinas nunca fallan. - No hay interrupciones programadas (preemption) - No hay cancelación de trabajos

>Universidad Distrital Francisco José de Caldas – Ingeniería Industrial

2

Además se agregan algunos los siguientes supuestos específicos del algoritmo cuello de botella móvil (Adams, Balas, & Zawack, March 1988) - La secuencia de máquinas para cada trabajo está dada. - Cada máquina puede procesar un solo trabajo a la vez. C. Grafo Disyuntivo La programación tipo taller se suele representar como un grafo disyuntivo G(N, A, B) donde N representa al conjunto de nodos, A al conjunto de arcos conjuntos y B los arcos disyuntos. En la Ilustración 1 se encuentra representado un grafo disyuntivo en el que cada nodo tiene dos sub índices (i,j) el subíndice i representa la máquina que se usa y el j la operación a realizar. Como es sabido, en cada máquina es posible realizar distintas operaciones dependiendo del trabajo o producto que se desee realizar. Los números que aparecen sobre los arcos representan el tiempo de operación. Por ejemplo entre el nodo (1,1) y el nodo (2,1) hay un arco con el número 5, lo que quiere decir que en la máquina 1 se realiza la operación 1 que tiene una duración de 5 unidades de tiempo y luego se traslada a la segunda máquina.

Ilustración 2 Grafo cíclico, fuente. SHITING BOTTLENECK (PDF)

IV. EL PROCEDIMIENTO SHIFTING BOTTLE NECK A. Algoritmo La heurística SBN se establece a partir de precepto de que todos los sistemas tienen un recurso escaso denominado cuello de botella y este recurso por ser el que presenta mayor utilización es el que gobierna el comportamiento de todo el sistema. Por consiguiente la secuenciación se debe trabajar sobre la máxima utilización para los cuellos de botella, lo que logrará disminuir el número de iteraciones para encontrar una buena solución. A demás descompone el problema global en m sub-problemas de una sola máquina y la secuenciación se realiza iterativamente en el recurso más crítico. Un diagrama de flujo que representa los pasos de la heurística se muestra en el Algoritmo 1.

Ilustración 1 Gráfico disyuntivo para un problema de programación tipo taller con n=3,m=3. fuente: (Britto, Gonzalo, & Caballero, 2007)

La información de entrada para graficar el grafo disyuntivo se puede presentar de la siguiente forma tabular Tabla 1. Se indican las secuencias por las que pasan los tres productos en cada una de las máquinas y sus respectivos tiempos de tiempos de operación.

Tabla 1 Información de entrada. Fuente: (Britto, Gonzalo, & Caballero, 2007)

D. Grafo Cíclico El algoritmo Shiftin bottleneck como cualquier algoritmo de secuenciación supone que una solución básica factible no contiene ciclos además de que no es posible establecer un orden topológico. Un ciclo en teoría de grafos tiene la característica de que se parte de un nodo y se llega al mismo nodo como se representa en la siguiente Ilustración 2.

Algoritmo 1 Shifting Bottle Neck fuente: SHITING BOTTLENECK(PDF)

>Universidad Distrital Francisco José de Caldas – Ingeniería Industrial B. Inicialización del problema Inicialización, consiste en construir el grafo, solamente con las restricciones iniciales de precedencia es decir con las restricciones conjuntivas, ya en la programación del cuello de botella se incluyen las restricciones disyuntivas. C. Búsqueda del Cuello de Botella

3

BOTTLENECK(PDF)

-

Ruta Crítica

La ruta crítica representa el camino más largo que posee una red. Para el caso de Shiftin bottle neck se require el cálculo de dos caminos más largos que dadas las característica propias de este tipo de problemas, en su publicación Adams Balas y Zawack desarrollaron un algoritmo específico que simplificaba la complejidad algorítmica del orden O(n2) al orden O(n), la razón es que el camino más largo representaba el tiempo más significativo en la eficiencia del shiftin bottleneck. -

Selección cuello de botella

En el contexto SBN el cuello de botella es aquella máquina k que es crítica con respecto a una selección parcial S=U(SK: K Mo) si Sk tiene un arco en el camino más largo. Para identificar la máquina cuello de botella en cada iteración, para cada: Donde M= Número de máquinas Mo=Máquinas que ya ha sido secuenciadas di representa el tiempo de operación Se resuelve el problema

Algorítmo 2 Selección del Cuello de Botella fuente: SHITING BOTTLENECK (PDF)

-

Orden Topológico

Se enumeran los nodos de tal forma que un nodo precedente no tenga un número mayor al del nodo que busco enumerar. Si el grafo contiene un ciclo, entonces éste no puede ser ordenado Topológicamente. En la figura 1podemos observar un ejemplo de la numeración.

figura 1 Representación del orden topológico a la izquierda grafo mal ordenado y a la derecha bien ordenado. Fuente: SHITING

El problema P (k, M) es equivalente a encontrar la secuencia para la máquina k the minimiza el máximo lateness, dado que cada operación I debe ser ejecutada en la máquina k. el tiempo de procesamiento di tiene una teimpo de liberación ri y una fecha de entrega fi aquí:

ri=L(0,i)

; L=longitud del camino en unidades de tiempo.

fi=L(0,n)- L(i,n) + di Como se puede observar e la última ecuación es necesario calcular dos caminos más largos L(0,n) y L(i,n). Un procedimiento detallado del algoritmo se presenta más adelante. D. Programación del problema de una sola máquina En términos generales el algoritmo planteado por Carlier y Pinson e 1989 es del tipo ramificación y acotamieto el cual limita la búsqueda del árbol usando selecciones inmediatas. Este algoritmo es muy famoso porque fue el primero en resolver problema Job shop 10x10 planteado por Muth y Thomsom en 1953.

>Universidad Distrital Francisco José de Caldas – Ingeniería Industrial

4

por consiguiente, mejorar el makespan del programa del JobShop1. A modo sintético se muestra el algoritmo Shifting bottleneck Escrito en pseudocódigo. Paso 1. Inicialización Mo = 0 G= grafo con todos los arcos conjutivos Cmax(Mo)= camino más largo en G. Paso 2. Analice máquinas no secuenciadas Para toda i є M\Mo haga Para todas las operaciones (i,j) haga rij = camino más largo de 0 a (i,j) en G qij = camino más largo de (i,j) a * en G Resuelva el problema para una sola máquina f(i) Paso 3. Selección del Cuello de Botella Determine k tal que f(k)=max {f(i)} Secuencie la máquina k de acuerdo con la solución óptima del paso 2. Agregue los arcos disyuntos correspondientes a G Realice Mo = Mo U {k} Paso 4 Re-secuencie las máquinas Para todo i i є M\Mo haga Borre los arcos disyuntos correspondientes a la maquina k Para toda operación (i,j) haga rij = camino más largo de 0 a (i,j) en G qij = camino más largo de (i,j) a * en G Resuelva el problema para una sola máquina f(i) Inserte los correspondientes arcos disyuntos a G. Paso5 Condición de Paro Si Mo=M => Pare De lo contrario => vaya al paso 2. Algoritmo 4 Pseudocódigo Shifting bottleneck. Fuente: Autoría propia, basado en. THE SHIFTING BOTTLENECK FOR JOB SHOP, Scheduling, Lecture 8. (PDF) V. MEJORAS AL SBN

Algoritmo 3 Secuenciación de una sola máquina fuente. (Carlier & Pinzón, Febrero 1989)

Donde N= número del nodo terminal f= cota superior

Dada la antigüedad del algoritmo, a lo largo de los años se han realizado mejas parciales mediante la mejora en la eficiencia de cada una de las fases o mediante la combinación con metaheurística como la búsqueda tabú. Como se presenta en la figura 2 Rodrigo, Gonzales y Caballero desarrollaron un híbrido que consta de 2 módulos que los que el cuello de botella móvil cumple la función de solución inicial.

Para una presentación detallada del uso y aplicación del algoritmo vea (Carlier & Pinzón, Febrero 1989) E. Procedimiento de Re- optimización local Después de programar una máquina, el paso de reoptimización consiste en reprogramar todas las máquinas ya programadas de manera que se mejore el programa parcial actual. A cada máquina programada se le borran las restricciones disyuntivas y se vuelve a programar la secuencia de los trabajos en ella, buscando mejorar su máximo retraso y

figura 2 Modulos principales para el algoritmo combinado fuete. (Britto, Gonzalo, & Caballero, 2007)

De esta manera se lograron mejoras significativas en diferentes problemas replicados. Lo autores recomiendan que 1

SHIFTING BOTTLENECK (PDF)

>Universidad Distrital Francisco José de Caldas – Ingeniería Industrial se preste especial atención al tamaño de lista y búsqueda de vecindarios para garantizar la mejora de los resultados. VI. CONCLUSIONES A modo de conclusión se puede decir que aunque este algoritmo fue desarrollado en la década de los 80’su aplicación a la vida práctica todavía es limitada, seguramente por la complejidad matemática que maneja, razón por la cual no es común verlo en un curso de pregrado. Por otro lado es importante resaltar que este tipo de algoritmos propios de ambientes Job shop son muy útiles en entornos productivos como el de Colombia, que dada una serie de condiciones económicas, políticas y sociales predomina llegando incluso a abarcar el más del 70% de las empresas nacionales. El algoritmo de por sí es muy eficiente en la búsqueda de soluciones por lo que obtiene mejoras considerables en comparación con las reglas de prioridad de despacho, además si se le agregan los avance realizados al combinarlo con metaheuríticas como la búsqueda tabú, mejora su rendimiento para la muchos de los problemas. En búsqueda tabú es importante los parámetros más importantes son el tamaño de la lista y la selección de vecindarios. VII. BIBLIOGRAFÍA Adams, J., Balas, E., & Zawack, D. (March 1988). The Shifting Bottle Neck Procedure for Job Shop Scheduling. Management Science Vol 34 . Britto, R., Gonzalo, M., & Caballero, J. P. (2007). Programación de la producción en sistemas de manufactura tipo taller con el algorítmo combinado cuello de botella móvio y búsqueda tabú. Ingeniería Unversidad. Carlier, J., & Pinzón, E. (Febrero 1989). An algorithm for solving the job shop problem. Management Science Vol 35, 165-176. HOPP, W. J. (2003). Supply Chain Science. Wallace J. Hopp. HOPP, W., & SPEARMAN, M. (2001). Factory Physics: Foundations of Manufacturing Management. New york: Irwin/McGraw-Hill.

VIII. INFOGRAFÍA Los autores no se indican porque el documento no los menciona. Documentos libres disponibles en la web. -

SHIFTING BOTTLENECK (PDF) THE SHIFTING BOTTLENECK FOR JOB SHOP, Scheduling, Lecture 8. (PDF)

5