Esquemas algorítmicos para optimización combinatoria: paralelizaciones y aplicaciones

• Autores: Gara Miranda Valladares
• Directores de la Tesis: Coromoto León Hernández (dir. tes.)
• Lectura: En la Universidad de La Laguna ( España ) en 2009
• Idioma: español
• Tribunal Calificador de la Tesis: Casiano Rodríguez León (presid.) , Jesús Manuel Jorge Santiso (secret.) , Carlos Manuel Mira Da Fonseca (voc.) , Enrique Salvador Quintana Ortí (voc.) , Domingo Benítez Díaz (voc.)
• Texto completo no disponible (Saber más ...)
• Resumen

  • En general, la calidad de las soluciones obtenidas en la resolución de un determinado problema de optimización combinatoria dependerá de la técnica algorítmica aplicada, de la eficiencia de la implementación de la técnica en cuestión, de su parametrización y, por supuesto, del conocimiento específico del problema que el usuario introduzca en el algoritmo, El proporcionar implementaciones eficientes y flexibles de técnicas algorítmicas, permite a los usuarios centrarse únicamente en el propio problema, evitándoles tener que introducirse en áreas distintas a las de su dominio. Es por ello que en este trabajo nos hemos centrado en el diseño de esqueletos y herramientas eficientes, que combinen el uso de algoritmos eficaces con técnicas específicas de paralelización. De esta forma, el usuario puede despreocuparse de la implementación y optimización de la estrategia algorítmica y centrarse en las mejoras dependientes del propio problema. Las ventajas que ofrece el uso de estas herramientas hace que constituyan un área de importante interés en el ámbito de la optimización combinatoria y la resolución de problemas.

    La investigación que se ha realizado en esta tesis se centra, pues, en las áreas de la algoritmia y técnicas de optimización avanzadas en entornos paralelos y distribuidos. El objetivo principal de este trabajo se basa en el estudio de aplicaciones reales y de su resolución usando técnicas algorítmicas, tanto exactas como heurísticas, buscando su generalización para el desarrollo de herramientas eficientes de propósito general. Para obtener herramientas lo más eficientes posibles se han empleado y diseñado los esquemas paralelos necesarios. El objetivo principal de este trabajo es proponer esquemas para la resolución eficiente de problemas de complejidad controlable que puedan, en el futuro, servir de puente entre los problemas típicos de corte académico y los problemas de gran complejidad que son abordables mediante las técnicas de optimización estudiadas. En este sentido, se propone el diseño, implementación y análisis de variantes sofisticadas (paralelas e híbridas) de técnicas algorítmicas para resolver problemas complejos en los dominios de la optimización combinatoria tradicional.

    Como caso de estudio, este trabajo se centra en la resolución de problemas de corte y empaquetado. Los problemas de corte y empaquetado son una familia de problemas de optimización combinatoria, ampliamente estudiados en la literatura por su importancia y gran variedad de aplicaciones en ámbitos reales. En estos problemas, el objetivo principal consiste en encontrar la distribución óptima de los elementos menores, de forma que se obtenga el mayor aprovechamiento de los materiales o espacios disponibles. Aunque también se pueden considerar algunos criterios de optimización adicionales: rapidez en la generación de los patrones, ubicación de conjuntos de elementos menores en un mismo elemento mayor, etc. Dependiendo del conjunto de restricciones que se haga y del tipo de objetivos considerado, se obtendrá una determinada subclase o formulación del problema. En cualquier caso, incluso suponiendo una formulación de lo más sencilla, los problemas de corte y empaquetado se clasifican generalmente como problemas NP-completos.

    De entre las múltiples variantes del problema, se han seleccionado dos de las más representativas y que, por tanto, han sido más estudiadas en la literatura relacionada: Two-Dimensional Cutting Stock Problem (2DCSP) y Two-Dimensional Strip Packing Problem (2DSPP). Con el fin de proporcionar un análisis más detallado de las metodologías de resolución existentes, el primer problema se ha afrontado como un problema de optimización mono-objetivo, mientras que la formulación del segundo se ha basado en múltiples objetivos. Para la resolución de estas variantes del problema, se han probado distintas estrategias de resolución: algorítmos exactos, heurísticas y metaheurísticas.