Santos, André Borges Guimarães Serra eDias, Daniel Joaquim da Silva2024-11-272024-11-272024-10-08http://hdl.handle.net/10400.22/26516Os Problemas de Escalonamento são desafios comuns em diversas áreas, e envolvem a procura por soluções ótimas em espaços de soluções que, muitas vezes, crescem exponencialmente com a dimensão do problema. Enumerar todas as soluções torna-se rapidamente inviável. Como alternativa, surgem as Meta-Heurísticas, que são eficazes, oferecendo estratégias flexíveis e robustas para encontrar soluções boas em intervalos de tempo reduzidos. No entanto, o desempenho destas técnicas depende fortemente da escolha adequada dos valores dos seus parâmetros. Neste trabalho, propõe-se um Protótipo de um Framework de Parametrização de Meta-Heurísticas, no qual um Agente Inteligente é responsável pela seleção e ajuste dinâmico dos valores dos parâmetros do Simulated Annealing, que é a técnica implementada para resolver o Problema de Escalonamento de Minimização do Makespan em Job-Shop. O Agente utiliza o algoritmo Q-Learning para guiar o processo de parametrização. À medida que recebe recompensas com base no desempenho de cada configuração, o Agente ajusta os valores dos parâmetros e refina a sua política de decisão de forma contínua, aprendendo assim a selecionar os parâmetros mais adequados. Como consequência, este processo progressivo permite que a Meta-Heurística se torne cada vez mais eficiente na procura pelas melhores soluções. Para avaliar o desempenho do modelo, foi conduzido um estudo computacional focado na eficiência do processo de aprendizagem do Agente e na eficácia das diferentes combinações de parâmetros que permitem obter a melhor solução. O Protótipo encontrou a melhor solução em 85% das instâncias, e, nas restantes, as melhores soluções aproximam-se significativamente das melhores documentadas na literatura, com diferenças que não são expressivas. Em instâncias de menor dimensão, o Agente não só encontrou a melhor solução, como também adquiriu a capacidade de fazê-lo num número reduzido de iterações. Por sua vez, em espaços de soluções mais irregulares, o sistema obteve a melhor solução, identificou as combinações de parâmetros que permitiram alcançá-la, tendeu a revisitá-las, no entanto, em vários momentos, a mesma configuração de parâmetros nem sempre produziu os mesmos resultados consistentemente, o que, em alguns casos, dificultou o processo de aprendizagem do Agente e afetou a qualidade dos resultados. Mesmo assim, o Protótipo demostrou ser uma excelente estratégia para ajustar, de forma contínua e inteligente, os parâmetros de uma Meta-Heurística.Scheduling Problems are common challenges across various fields and involving the search for optimal solutions within a solution spaces that, often, grow exponentially with the problem's size. Enumerating all possible solutions quickly becomes infeasible. As an alternative, Meta-Heuristics have emerged as effective approaches, offering flexible and robust strategies for finding good solutions requiring low computational times. However, the performance of these techniques is highly dependent on the appropriate selection of their parameter values. In this work, a Prototype of a Meta-Heuristic Parameterization Framework is proposed, wherein an Intelligent Agent is responsible for the dynamic selection and adjustment of the parameters of Simulated Annealing, which is the technique implemented to solve the Job-Shop Scheduling Problem, specifically for minimizing makespan. The Agent employs the Q-Learning algorithm to guide the Meta-Heuristic parameter tuning process. As it receives rewards based on the performance of each parameter configuration, the Agent continuously adjusts the parameters values and refines its decision-making policy, progressively learning to select the most suitable parameters. As a results, this process enables the Meta-Heuristic to become increasingly efficient in the search for optimal solutions. To evaluate the model's performance, a computational study was conducted, focusing on the efficiency of the Agent’s learning process and the effectiveness of different parameter configurations that lead to optimal solutions. The Prototype identified the optimal solution in 85% of the instances, and in the remaining cases, the solutions obtained were significantly close to the best documented in the literature, with negligible differences. In instances of smaller dimensions, the Agent not only found the best solution but also acquired the ability to achieve it within a reduced number of iterations. Conversely, when the solution space is more irregular, the system successfully achieved the best solution and identified the parameter configurations that yield the best result. It tended to revisit these combinations; however, in several instances, the same parameter configuration did not consistently produce the same results, which, in some cases, hindered the Agent’s learning process and affected the quality of the results. Nevertheless, the Prototype proved to be an excellent strategy for continuously and intelligently tuning the parameters of a Meta-Heuristic.porScheduling problemMeta-heuristicsParameter tuningReinforcement learningQ-LearningSimulated annealingProblema de escalonamentoMeta-heurísticasParametrizaçãoAprendizagem por reforçomaster thesis203732499