Metaheurísticas para scheduling verde bajo incertidumbre

Abstract

En esta tesis se abordan problemas de scheduling bajo incertidumbre con el objetivo de optimizar el consumo de energía. Se presentan distintos modelos para considerar incertidumbre y se define una metodología y un conjunto de medidas para evaluar y comparar las diferentes alternativas. Como la mayoría de los problemas de scheduling son NP-duros, se proponen técnicas basadas en Inteligencia Artificial, en concreto, metaheurísticas, para conseguir soluciones competitivas en tiempo razonable. Se presentan estructuras de vecindad orientadas a consumo energético y nuevas cotas inferiores y superiores para replanificaciones de operaciones, con el objetivo de mejorar la eficiencia del proceso de búsqueda. Para explotar las sinergias entre los algoritmos evolutivos y la búsqueda por trayectoria se propone un algoritmo memético. Finalmente, se define un nuevo enfoque multiobjetivo jerárquico para encontrar un equilibrio entre los objetivos relacionados con producción y objetivos energéticos.

This thesis addresses scheduling problems under uncertainty with the objective of optimising energy consumption. Different models to incorporate uncertainty are presented and a methodology and a set of measures are defined to evaluate and compare the different alternatives. As most scheduling problems are NP-hard, techniques based on Artificial Intelligence, in particular, metaheuristics, are proposed to obtain competitive solutions within a reasonable time. Energy-focused neighbourhood functions and new lower and upper bounds for rescheduling operations are presented to improve the efficiency of the search process. To take advantage of the synergies between evolutionary algorithms and trajectory-based search a memetic algorithm is proposed. Finally, a new approach to hierarchical multiobjective problems is presented to find a balance between production and green objectives.