El problema tratado, conocido como “Hoist Scheduling Problem”, pretende determinar la programación de una grúa, y ocasionalmente la secuencia de elementos en una línea de producción. En este caso, los objetos se desplazan entre estaciones, también llamadas baños o tanques por su contenido químico, utilizando puentes-grúas o transportadores aéreos. Los objetos deben permanecer en cada baño durante un período de tiempo limitado por dos valores predeterminados. El objetivo es minimizar el tiempo de ocupación de las instalaciones, sujeto a las limitaciones citadas. El problema puede ser tratado desde múltiples variantes, que dependen de las características de los tanques exclusivamente, de los transportadores o de otros aspectos, como el flujo de materiales.
El trabajo se enmarca en los sistemas de fabricación flexibles y en la dirección de operaciones. En el ámbito del problema, existe un conjunto de posibles variantes. En este caso, se formaliza el modelo matemático para resolver la variante del problema mono-baño, mono-función, objetos homogéneos y una grúa. Se empieza planteando una relajación sobre dicho modelo y su correspondiente grafo asociado, lo cual sirve para discutir sobre las posibles estructuras arborescentes a adoptar en la resolución.
Como principal aportación, se presenta la utilización de cotas sobre la variable del tiempo de ciclo, calculadas en el llamado grafo con Tiempo de Ciclo Acotado. En este ámbito, se justifica la presencia de propiedades de la programación dinámica para acelerar la resolución de este grafo orientado. Como complemento, se plantea un algoritmo de tipo heurístico, basado en el número de piezas tratadas por ciclo. Su objetivo es alcanzar un valor que sirva de cota superior inicial a otros algoritmos.
Se incluye una experiencia computacional que justifica la utilización del grafo con Tiempo de Ciclo Acotado. Para ello, se resuelven los ejemplares mediante un programa optimizador, y mediante los llamados branch and bound de tiempos y de baños, para adoptar ésta última estructura para grafos con Tiempo de Ciclo Acotado. La experiencia en ejemplares hasta 20 baños utiliza un algoritmo que combina los de tipo heurístico y de estructura arborescente. También se aplican los algoritmos sobre ejemplares benchmark de la literatura.
Asimismo, el uso del grafo con Tiempo de Ciclo Acotado se justifica en otras variantes del problema, como con dos grúas, para la cual Lei y Wang (1991) propusieron el algoritmo Minimum Common Cycle. La introducción del grafo señalado permite importantes reducciones en el tiempo de cálculo, ya que los grafos finalmente resueltos son aproximadamente un 60% de los visitados en la estructura arborescente. Finalmente, los datos de una industria de fabricación de placas de circuito impreso sirven para testear los algoritmos presentados en una situación productiva real. Allí, se muestra la oportunidad y eficiencia de resolver ejemplares mediante los ejemplares directo o inverso.
Las conclusiones del trabajo muestran la utilidad del grafo con Tiempo de Ciclo Acotado y posibles extensiones futuras, como el análisis de otras variantes del problema, principalmente con objetos heterogéneos, y la dualidad entre ejemplares directo e inverso.
| Identifer | oai:union.ndltd.org:TDX_UPC/oai:www.tdx.cat:10803/80622 |
| Date | 21 May 2001 |
| Creators | Mateo Doll, Manuel |
| Contributors | Companys Pascual, Ramón, Universitat Politècnica de Catalunya. Departament d'Organització d'Empreses |
| Publisher | Universitat Politècnica de Catalunya |
| Source Sets | Universitat Politècnica de Catalunya |
| Language | Catalan |
| Detected Language | Spanish |
| Type | info:eu-repo/semantics/doctoralThesis, info:eu-repo/semantics/publishedVersion |
| Format | 371 p., application/pdf |
| Source | TDX (Tesis Doctorals en Xarxa) |
| Rights | info:eu-repo/semantics/openAccess, ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs. |
Page generated in 0.0022 seconds