Resumen:
El presente trabajo aborda el problema de optimización combinatoria conocido como corte de stock en dos dimensiones, mediante el estudio del algoritmo presentado por Fritsch y Vornberger. Este problema se encuentra con frecuencia en diversas áreas de la industria: del vidrio, del papel, metalúrgica, etc. Fritsch y Vornberger, por ejemplo, diseñaron su algoritmo para la industria del vidrio. En nuestro caso, el objetivo final es desarrollar una implementación satisfactoria para ser utilizada en una carpintería. En la primera parte del trabajo presentamos la teoría de los problemas 𝜨𝜬, 𝜨𝜬-completos y 𝜨𝜬-hard, con el objeto de encuadrar el problema en ella. Para esto, introducimos los conceptos de máquina de Turing determinísitica y no-determinística, de reducción polinomial y de reducción Turing. Finalmente, demostramos el Teorema de Cook y, a partir de él, una serie de resultados que llevan a concluir que el problema aquí estudiado pertenece a la clase de los 𝜨𝜬-hard. La segunda parte está dedicada al estudio del algoritmo de Fritsch y Vornberger, sus virtudes y sus limitaciones. En la sección 4 presentamos las herramientas fundamentales para el desarrollo del método y exponemos sus lineamientos generales, tal como lo describen sus autores. La sección 5 está dedicada al comentario de algunos aspectos interesantes de la implementación. Por otra parte, dado que el método en su versión original resultó ser poco eficaz para el caso que nos interesa, exponemos las variantes que introdujimos para mejorar su rendimiento. Finalmente, en la sección 6 comentamos algunos resultados obtenidos.
Citación:
---------- APA ----------
Ojea, Ignacio. (2008). Un algoritmo para el problema de corte de stock en dos dimensiones por matching iterado. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nMAT001057_Ojea
---------- CHICAGO ----------
Ojea, Ignacio. "Un algoritmo para el problema de corte de stock en dos dimensiones por matching iterado". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2008.https://hdl.handle.net/20.500.12110/seminario_nMAT001057_Ojea
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nMAT001057_Ojea.pdf
Distrubución geográfica
