Representación binaria para el strip packing utilizando algoritmos genéricos

Tesis (Ingeniero Civil en Computación e Informática)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