English español
Search
 

Repositorio de la Universidad de Oviedo. > Producción Bibliográfica de UniOvi: RECOPILA > Tesis >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10651/20285

Title: Métodos heurísticos avanzados para problemas de scheduling
Author(s): Mencía Cascallana, Carlos
Advisor: Varela Arias, José Ramiro
Sierra Sánchez, María Rita
Other authors: Informática, Departamento de
Keywords: Inteligencia artificial
Issue date: 4-Jul-2013
Publisher: Universidad de Oviedo
Format extent: 141 p.
Abstract: Los problemas de scheduling están presentes en numerosos ámbitos reales. En general, consisten en organizar la ejecución de un conjunto de operaciones en diferentes recursos, satisfaciendo diversas restricciones con el fin de optimizar alguna métrica o función objetivo. Muchos de ellos, como el paradigmático problema Job Shop Scheduling, pertenecen a la clase de complejidad NP-hard, lo que significa que pueden ser realmente difíciles de resolver. En las últimas décadas ha habido un estudio intensivo de los problemas de scheduling por parte de campos científicos como la Inteligencia Artificial o la Investigación Operativa, dando lugar a un notorio número de técnicas de resolución, tanto exactas como aproximadas. Esta tesis doctoral tiene como objetivo el diseño de algoritmos exactos eficientes para problemas de scheduling, capaces de resolver de forma óptima instancias del problema de hasta cierto tamaño y de calcular tanto cotas inferiores no triviales como buenas soluciones para instancias más difíciles en un tiempo corto y empleado recursos de memoria escasos. Concretamente, la investigación se ha centrado en el problema Job Shop Scheduling y en el problema Job Shop Scheduling con Operarios, una generalización del primero que considera restricciones complejas derivadas de la presencia de trabajadores humanos en entornos productivos. Por medio de técnicas de búsqueda heurística y de razonamiento basado en restricciones, hemos contribuido a este campo en varios modos. En primer lugar, evaluamos dos variantes de algoritmos de búsqueda primero en profundidad en el contexto del problema Job Shop Scheduling, y proponemos un algoritmo de búsqueda en profundidad parcialmente informada que explota eficazmente el conocimiento del domino del problema para guiar la búsqueda hacia zonas prometedoras del espacio de búsqueda. Este algoritmo saca partido de un heurístico original que explota un método de propagación de restricciones. En segundo lugar, proponemos una nueva estrategia de búsqueda, que extiende la técnica Iterative Deepening A* para resolver problemas de scheduling y de optimización con restricciones. La nueva estrategia, denominada Intensified Iterative Deepening A*, emplea la propagación de restricciones de un modo no conservativo, actualiza el umbral de coste de forma liberal entre iteraciones consecutivas y lanza búsquedas en profundidad limitadas desde algunos estados para muestrear distintas regiones del espacio de búsqueda. Esta técnica se ha mostrado muy efectiva en el problema Job Shop Scheduling. Por último, diseñamos varias componentes de algoritmos de búsqueda heurística para el problema Job Shop Scheduling con Operarios: una definición de un espacio de búsqueda basado en un nuevo esquema de generación de planificaciones denominado OG&T, dos heurísticos y una relación de dominancia empleada para podar estados. Asimismo, proponemos una nueva estrategia de búsqueda heurística, denominada A*DFS, que combina de un modo original los algoritmos A* y búsqueda primero en profundidad, obteniendo muy buenos resultados.
Description: Tesis doctoral por el sistema de Compendio de Publicaciones
URI: http://hdl.handle.net/10651/20285
Local notes: DT(SE) 2013-109
Appears in Collections:Tesis
Tesis doctorales a texto completo

Files in This Item:

File Description SizeFormat
TD_carlosmenciacascallana.pdf2,82 MBAdobe PDFView/Open


Exportar a Mendeley


This item is licensed under a Creative Commons License
Creative Commons

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 

Base de Datos de Autoridades Biblioteca Universitaria Consultas / Sugerencias