Computación evolutiva para el problema de cutting

Abstract

El problema de cutting se presenta en un gran número de situaciones. La variedad del problema es tan grande como su aplicación en el mundo real. Se puede observar en disciplinas como ciencias de la administración, ingeniería, matemáticas, logística, ciencias de la computación, etc. Este es un problema NP-completo, en el cual se pueden usar la programación entera y las técnicas de branch and bound para encontrar la solución óptima. Sin embargo, no resultan efectivas en problemas cuyo espacio de búsqueda sea de medio o de gran tamaño. Por lo cual se han desarrollados heurísticas y metaheurísticas, para obtener soluciones buenas rápidamente. Una de las metaheurísticas usada en este tipo de problemas es la computación evolutiva. A partir de la necesidad concreta presentadas por empresas de la región que buscan una distribución más eficiente de las piezas a cortar para lograr un ahorro de materia prima, se plantea el desafío de dar solución al problema de cutting mediante el desarrollo de algoritmos evolutivos.