Metaheurísticas híbridas-paralelas para problemas industriales de corte, empaquetado y otros relacionados

Abstract

Los problemas de corte y empaquetado (C&P) consisten, por lo general, en el corte de materias primas para obtener un conjunto de elementos minimizando el desperdicio de material generado o en el empaquetado de un conjunto de artículos en el menor número de contenedores. Esta clase de problemas cae dentro de la categoría de problemas de optimización combinatoria. Usualmente, se presentan en muchas aplicaciones industriales, tales como: vidrio, papel y corte de acero; carga de contenedores y camiones; diseño de circuitos integrados; optimización de portfolio; y muchas otras. La mayoría de los problemas de optimización combinatoria, y por consiguiente los problemas de corte y empaquetado, son, en general, difíciles de resolver en la práctica. Estos problemas están incluidos en la clase de problemas NP-duros [11], ya que no se conocen algoritmos exactos con complejidad polinómica que permitan resolverlos. Debido a su intratabilidad, se han diseñado una gran cantidad de métodos aproximados, los cuales encuentran buenas soluciones en tiempos computacionales razonables. En esta clase de problemas, la búsqueda de una solución requiere una exploración organizada a través del espacio de búsqueda: una búsqueda sin guía es extremadamente ineficiente.