Loading...
Publication
Análise e comparação do desempenho de metaheurísticas aplicadas a problemas de escalonamento das operações
| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 7.58 MB | Adobe PDF |
Advisor(s)
Abstract(s)
O Escalonamento das Operações é um elemento fundamental para o funcionamento eficiente
de indústrias de serviços e manufatura, sendo o processo de decisão responsável pela alocação
de recursos limitados entre atividades ao longo do tempo. Apesar de um bom Escalonamento
das Operações proporcionar diversas vantagens, este acarreta alguns problemas de elevada
complexidade e de difícil resolução. As Metaheurísticas surgem como técnicas de otimização
que podem ser aplicadas na resolução destes problemas atingindo uma solução aproximada,
pelo que a sua utilização tem vindo a crescer ao longo dos anos. Neste trabalho, foram
selecionadas quatro Metaheurísticas (Genetic Algorithm, Particle Swarm Optimization, Tabu
Search e Simulated Annealing) e um tipo específico de Problema de Escalonamento Industrial
(Job-Shop com makespan como critério de otimização), com base na sua relevância e
popularidade na comunidade científica, para serem o alvo de foco de testes estatísticos. Para
cada Metaheurística foram reunidos dados de vinte artigos científicos, posteriormente os dados
foram organizados para servirem de base à análise estatística. Inicialmente, procedeu-se à
realização de uma análise descritiva com os dados dos artigos, com o objetivo de compreender
a distribuição dos artigos por diferentes categorias e extrair observações preliminares.
Seguidamente, com recurso ao software estatístico IBM SPSS Statistics, realizaram-se cinco
análises de inferência estatística: Evolução dos Resultados ao longo dos Anos, Comparação de
Desempenho entre as Metaheurísticas, Variabilidade de Resultados dentro de cada
Metaheurística, Influência dos Métodos de Comparação de Resultados e Análise por tipo de
Metaheurística (Híbrida e Não Híbrida). Estas análises permitiram chegar a diversas conclusões,
entre as quais se destaca a ausência de correlação significativa entre o ano de publicação e a
proximidade ao resultado ótimo, por de parte das Metaheurísticas, a evidência de que o Genetic
Algorithm proporciona, em média, as maiores reduções de makespan entre as Metaheurísticas
analisadas e o facto de este algoritmo também se destacar pela sua consistência, apresentando
a menor variabilidade de resultados. Assim, este trabalho oferece uma fonte de informação
valiosa para a seleção de Metaheurísticas, no contexto industrial, mais especificamente para os
Problemas de Escalonamento Industrial do tipo Job-Shop que apresentam makespan como
critério de otimização, realçando o facto que a seleção de uma Metaheurística deve ser baseada
numa avaliação multicritério, e não apenas com base no desempenho médio de cada
Metaheurística.
Operations Scheduling is a fundamental element in the efficient operation of service and manufacturing industries and is the decision-making process responsible for allocating limited resources between activities over time. Despite the fact that good Operations Scheduling offers a number of advantages, it also entails some highly complex problems that are difficult to solve. Metaheuristics emerge as optimization techniques that can be applied to solve these problems and achieve an approximate solution, which is why their use has been growing over the years. In this work, four Metaheuristics (Genetic Algorithm, Particle Swarm Optimisation, Tabu Search and Simulated Annealing) and a specific type of Industrial Scheduling Problem (Job-Shop with makespan as an optimization criterion) were selected, based on their relevance and popularity in the scientific community, to be the focus of statistical tests. For each Metaheuristic, data was gathered from twenty scientific articles and then organized to serve as the basis for statistical analysis. Initially, a descriptive analysis was carried out on the article data, with the aim of understanding the distribution of articles by different categories and extracting preliminary observations. Then, using IBM SPSS Statistics software, five statistical inference analyses were carried out: Evolution of Results over the Years, Comparison of Performance between Metaheuristics, Variability of Results within each Metaheuristic, Influence of Methods for Comparing Results and Analysis by Type of Metaheuristic (Hybrid and Non-Hybrid). These analyses led to a number of conclusions, including the absence of a significant correlation between the year of publication and proximity to the optimum result, on the part of the Metaheuristics, evidence that the Genetic Algorithm provides, on average, the greatest reductions in makespan among the Metaheuristics analyzed and the fact that this algorithm also stands out for its consistency, showing the least variability in results. Thus, this work offers a valuable source of information for the selection of Metaheuristics, in the industrial context, more specifically for Industrial Job-Shop Scheduling Problems that have makespan as an optimization criterion, emphasizing the fact that the selection of a Metaheuristic should be based on a multi-criteria evaluation, and not just on the average performance of each Metaheuristic.
Operations Scheduling is a fundamental element in the efficient operation of service and manufacturing industries and is the decision-making process responsible for allocating limited resources between activities over time. Despite the fact that good Operations Scheduling offers a number of advantages, it also entails some highly complex problems that are difficult to solve. Metaheuristics emerge as optimization techniques that can be applied to solve these problems and achieve an approximate solution, which is why their use has been growing over the years. In this work, four Metaheuristics (Genetic Algorithm, Particle Swarm Optimisation, Tabu Search and Simulated Annealing) and a specific type of Industrial Scheduling Problem (Job-Shop with makespan as an optimization criterion) were selected, based on their relevance and popularity in the scientific community, to be the focus of statistical tests. For each Metaheuristic, data was gathered from twenty scientific articles and then organized to serve as the basis for statistical analysis. Initially, a descriptive analysis was carried out on the article data, with the aim of understanding the distribution of articles by different categories and extracting preliminary observations. Then, using IBM SPSS Statistics software, five statistical inference analyses were carried out: Evolution of Results over the Years, Comparison of Performance between Metaheuristics, Variability of Results within each Metaheuristic, Influence of Methods for Comparing Results and Analysis by Type of Metaheuristic (Hybrid and Non-Hybrid). These analyses led to a number of conclusions, including the absence of a significant correlation between the year of publication and proximity to the optimum result, on the part of the Metaheuristics, evidence that the Genetic Algorithm provides, on average, the greatest reductions in makespan among the Metaheuristics analyzed and the fact that this algorithm also stands out for its consistency, showing the least variability in results. Thus, this work offers a valuable source of information for the selection of Metaheuristics, in the industrial context, more specifically for Industrial Job-Shop Scheduling Problems that have makespan as an optimization criterion, emphasizing the fact that the selection of a Metaheuristic should be based on a multi-criteria evaluation, and not just on the average performance of each Metaheuristic.
Description
Keywords
Escalonamento das Operações Metaheurísticas Hibridização Job-Shop Makespan Resultado Ótimo Análise Descritiva Inferência Estatística Escalonamento de operações Metahuerísticas Hibridização Resultado ótico Análise descritiva Inferência estatística