Representación binaria para el strip packing utilizando algoritmos genéricos
Cargando...
Archivos
Fecha
2012
Profesor/a Guía
Facultad/escuela
Idioma
es
Título de la revista
ISSN de la revista
Título del volumen
Editor
Universidad Andres Bello
Nombre de Curso
Licencia CC
Licencia CC
Resumen
En las industrias manufactureras, la optimización de los procesos productivos son relevantes para su eficiencia, en particular en las industrias de corte y empaque. En particular el problema de Strip Packing en dos dimensiones, que dada su complejidad computacional es considerado como un problema NP-Hard, consiste en disponer un conjunto de piezas rectangulares de dimensiones conocidas dentro de una región contenedora rectangular de mayor tamaño, de ancho definido y largo variable. En este trabajo se presenta un enfoque de resolución del problema de Strip Packing utilizando un Algoritmo Genético y tres tipos de representación binaria del espacio de solución. Los resultados obtenidos presentan una mejora por sobre el 41 % de las muestras al pre ordenar – por área descendente – el conjunto de piezas de las instancias del problema. En comparación con la literatura existente, los resultados alcanzan el óptimo en un 24,24% de las muestras, mientras que se igualan a los mejores resultados registrados en un 48,48%. Adicionalmente, se concluye que la representación binaria del espacio de soluciones, que utiliza el Algoritmo Genético, no es un factor relevante en cuanto a la calidad de soluciones, dado que con tres representaciones distintas y una misma función de placement, no fue factible mejorar los resultados reportados por la literatura.
Notas
Tesis (Ingeniero Civil en Computación e Informática)
Palabras clave
Algoritmos Computacionales., Optimización Combinatoria