Implementação de um algoritmo genético híbrido com simulated annealing para o problema job shop

Abstract

Neste trabalho apresenta-se um estudo sobre problemas de planeamento de operações do tipo job shop. Devido à sua natureza combinatória, o planeamento de operações deste tipo pertence à classe de problemas NP-difícil. Dada a complexidade destes problemas, torna-se impraticável testar todas as soluções possíveis pois tal não seria exequível em tempo computacional útil. Mesmo com a utilização de métodos de solução exata aplicados a modelos de programação inteira a solução do problema fica limitada a instâncias de pequena dimensão. Por este motivo, vai-se ao encontro do paradigma de investigação que tem sido desenvolvido nas últimas duas décadas que procura encontrar soluções recorrendo a métodos de solução aproximada. Desde a pesquisa por arrefecimento simulado (Simulated Annealing) até à optimização por enxame de partículas (Particle Swarm Optimization) é possível ainda encontrarem-se muitas variantes dentro da mesma classe de métodos aproximados. Um dos métodos que se tornou muito popular na comunidade científica é o Algoritmo Genético. A simplicidade desta técnica na representação de modelos complexos e também a facilidade de integração com outros métodos de resolução são os fatores que justificam o seu estudo. Contudo é necessário manter uma diversidade genética ao longo das iterações para evitar uma convergência prematura para mínimos locais. Para colmatar esta ineficiência recorre-se à sua hibridização, combinando com outro método de aproximação (Simulated Annealing). A abordagem proposta nesta dissertação pretende dar mais um contributo para a resolução do problema de planeamento de operações em ambiente do tipo job shop recorrendo a um algoritmo genético híbrido com arrefecimento simulado (Simulated Annealing). É realizada uma caracterização das tarefas e recursos do problema Job Shop bem como um estudo de Algoritmos Genéticos e seus componentes. Como fator diferenciador em relação aos trabalhos já publicados, pretende-se desenvolver um método que permita resolver o problema job-shop clássico, bem como a hibridização de métodos de solução aproximada. Os métodos implementados são validados através da análise dos resultados obtidos para aferir a sua eficácia e eficiência. Os testes realizados têm como base conjuntos de problemas padronizados, previamente definidos por autores reconhecidos na área.

This paper presents a study of job shop scheduling problems (JSSP). Due to its combinatorial nature, JSSP belongs to NP-hard class problems. Given the complexity of such problems, it becomes impossible to test all possible solutions in order to find the optimal solution of the problem, as this would not be feasible in useful computational time. Even with the use of exact solution methods applied to integer programming models, it is limited to small instances. For this reason, it will be followed the research paradigm that has been developed over the past two decades to find solutions using approximate methods. Since the research by simulated annealing to the particle swarm optimization it is possible to find many variants within the same class of approximate methods. One method that has become very popular in the scientific community is the Genetic Algorithm. The simplicity of this technique in the representation of complex models and also the ease of integration with other methods of resolution are the factors that justify their study. However genetic algorithms are not effective in finding the optimal solution value, but the regions where the solution is. To transcend this inefficiency one solution is the hybridization, combining with another approximation method (Simulated Annealing), whose goal is to find the optimal solution in a limited region. The approach proposed in this thesis aims to further contributes to solving the problem of planning of operations in job shop type environment using a hybrid genetic algorithm with simulated annealing. It is made a characterization of tasks and resources of the JSSP and a study of Genetic Algorithms and their components. As a differentiating factor in relation to the work already published, we intend to develop a method for solving the classical job shop problem, as well as the hybridization of distinct approximation methods. The implemented methods are validated through the analysis of the results to check their effectiveness and efficiency. The tests are based on standardized sets of problems, as established by recognized authors in the area.