| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 21.99 MB | Adobe PDF |
Authors
Advisor(s)
Abstract(s)
A alocação e a sequenciação adequada de tarefas são problemas que aparecem frequentemente, tanto em ambientes industriais como na prestação de serviços. Neste contexto, o conjunto de decisões a ser tomadas para que o planeamento de tarefas seja mais eficaz e eficiente é um tema cada vez com maior interesse e importância para as organizações, pois um escalonamento realizado de forma a otimizar os processos para evitar desperdício de tempo, utilização de máquinas ou outros recursos, aumenta a produtividade e torna as organizações mais competitivas. A presente dissertação foca-se na aplicação e comparação das meta-heurísticas Simulated Annealing e Tabu Search para a resolução de um problema de escalonamento em máquinas paralelas considerando o tempo de conclusão, o custo de deterioração das máquinas, a penalização por atraso e antecipação. Este problema é caracterizado por ser um problema de otimização multiobjetivo. Para o resolver transformou-se num problema com um único objetivo fazendo a combinação linear dos objetivos. Foram aplicados diferentes métodos para obter a solução, nomeadamente, o método ponderado, o método das distâncias relativas ponderadas e um método proposto, no qual designou-se pelo método variante das métricas ponderadas, que é um dos contributos desta dissertação. Para analisar o comportamento das meta-heurísticas e também os métodos multiobjetivo utilizados, foram construídos 4 cenários para o problema de escalonamento em máquinas paralelas. Os cenários diferenciavam-se no número e tarefas a serem processadas e também no número de máquinas disponíveis. Para cada cenário do problema foram encontradas pelas diferentes meta-heurísticas 10 soluções para cada método utilizado. No total, cada meta-heurística encontrou 40 soluções para cada cenário do problema. De entre as soluções encontradas foram selecionadas as melhores soluções por cada metaheurística, em cada método multiobjetivo nos diferentes cenários do problema. Foi possível verificar diferentes comportamentos das meta-heurísticas em função das dimensões do problema e também com a alternância entre métodos multiobjetivo. A meta-heurística Simulated Annealing apresentou melhores resultados nos cenários de menor dimensão, no entanto o tempo de execução para determinar a solução foi superior em comparação com a meta-heurística Tabu Search. Inversamente, a meta-heurística Tabu Search apresenta melhores soluções para problemas de maior dimensão, sendo, contudo, o tempo de execução superior à do Simulated Annealing. Dos métodos multiobjetivo utilizados é possível concluir que os resultados segundo o método ponderado apresentam soluções próximas aquando a utilização do método das distâncias relativas ponderadas. Já os resultados segundo o método variante das métricas ponderadas apresentam soluções mais afastadas, podendo concluir que este explora outra zona no campo de soluções.
The allocation and proper sequencing of tasks are problems that often appear both in industrial environments and in the provision of services. In this context, the set of decisions to be taken in order to make task planning more effective and efficient is an issue of increasing interest for organizations, as an escalation carried out in order to optimize processes to avoid wasting time, use of machines or other resources, increases productivity and makes organizations more competitive. The present dissertation focuses on the application and comparison of Simulated Annealing and Tabu Search metaheuristics to solve a scheduling problem on parallel machines considering the completion time, the cost of deterioration of the machines, the penalty for delay and anticipation. This problem is characterized by being a multi-purpose optimization problem. To solve it, it became a problem with a single goal, making the linear combination of objectives. Different methods were applied to obtain the solution, namely the weighted method, the weighted relative distance method and a proposed method, in which the variant method of weighted metrics was designated, which is one of the contributions of this dissertation. In order to analyze the behavior of metaheuristics and also the multiobjective methods used, four scenarios were constructed for the problem of scaling in stop machines. The scenarios differed in the number and tasks to be processed and also in the number of machines available. For each scenario of this problem, ten different solutions for each method used were found by the different meta-heuristics. In total, each metaheuristic found 40 solutions to each problem scenario. Among the solutions found, the best solutions were selected for each metaheuristic, in each multiobjective method in the different scenarios of the problem. It was possible to verify different behaviors of metaheuristics according to the dimensions of the problem and also with the alternation between multiobjective methods. The Simulated Annealing metaheuristic showed better results in the smaller scenarios, however the execution time to determine the solution was higher compared to the Tabu Search metaheuristic. Inversely, the Tabu Search metaheuristic presents better solutions for larger problems, however the execution time is longer than that of Simulated Annealing. From the multiobjective methods used, it is possible to conclude that the results according to the weighted method present similar solutions when using the weighted relative distances method. The results according to the variant method of the weighted metrics present more distant solutions and it can be concluded that it explores another zone in the solutions field.
The allocation and proper sequencing of tasks are problems that often appear both in industrial environments and in the provision of services. In this context, the set of decisions to be taken in order to make task planning more effective and efficient is an issue of increasing interest for organizations, as an escalation carried out in order to optimize processes to avoid wasting time, use of machines or other resources, increases productivity and makes organizations more competitive. The present dissertation focuses on the application and comparison of Simulated Annealing and Tabu Search metaheuristics to solve a scheduling problem on parallel machines considering the completion time, the cost of deterioration of the machines, the penalty for delay and anticipation. This problem is characterized by being a multi-purpose optimization problem. To solve it, it became a problem with a single goal, making the linear combination of objectives. Different methods were applied to obtain the solution, namely the weighted method, the weighted relative distance method and a proposed method, in which the variant method of weighted metrics was designated, which is one of the contributions of this dissertation. In order to analyze the behavior of metaheuristics and also the multiobjective methods used, four scenarios were constructed for the problem of scaling in stop machines. The scenarios differed in the number and tasks to be processed and also in the number of machines available. For each scenario of this problem, ten different solutions for each method used were found by the different meta-heuristics. In total, each metaheuristic found 40 solutions to each problem scenario. Among the solutions found, the best solutions were selected for each metaheuristic, in each multiobjective method in the different scenarios of the problem. It was possible to verify different behaviors of metaheuristics according to the dimensions of the problem and also with the alternation between multiobjective methods. The Simulated Annealing metaheuristic showed better results in the smaller scenarios, however the execution time to determine the solution was higher compared to the Tabu Search metaheuristic. Inversely, the Tabu Search metaheuristic presents better solutions for larger problems, however the execution time is longer than that of Simulated Annealing. From the multiobjective methods used, it is possible to conclude that the results according to the weighted method present similar solutions when using the weighted relative distances method. The results according to the variant method of the weighted metrics present more distant solutions and it can be concluded that it explores another zone in the solutions field.
Description
Keywords
Escalonamento Máquinas paralelas Otimização multiobjetivo Meta-heuristicas Simulated Annealing Tabu Search Scheduling Parallel machines Multiobjective optimization Metaheuristics