Algoritmos para o problema de sequenciamento de tarefas em máquinas paralelas idênticas.
No Thumbnail Available
Date
2020
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Este trabalho trata do Problema de Sequenciamento de Tarefas em Máquinas Paralelas Idênticas objetivando minimizar o makespan e o custo total de energia (TEC). Neste
problema busca-se alocar um grupo de tarefas a um conjunto de máquinas disponíveis
de forma a se reduzir os custos de operação. Tal classe de problemas tem sido amplamente estudada atualmente, dada a grande busca pela eficiência energética e a otimização
dos processos de produção. Além disso, a investigação de tal problema se justifica por
ele pertencer à classe NP-difícil. Para solucioná-lo, foi ajustado um modelo bi-objetivo
da literatura para uma abordagem mono-objetiva por soma ponderada. Também foram
adaptados dois algoritmos baseados na meta-heurística Iterated Local Search (ILS): o primeiro, referido como ILS apenas, é uma versão clássica do método proposto na literatura.
Já o segundo, é uma versão aperfeiçoada, denominada Smart Iterated Local Search, ou
apenas SILS. Nessa versão adaptada, a dinâmica de perturbação é alterada em relação
ao algoritmo clássico, permitindo um melhor desempenho da busca local incorporada ao
método. Enquanto no ILS clássico o nível de perturbação é alterado sempre que não
ocorre melhora na solução, no SILS são realizadas novas tentativas de melhoria em um
mesmo nível de perturbação. Tal modificação foi realizada partindo da hipótese de que
o aumento de nível da perturbação pode ser precipitado, visto que se trata de um movimento aleatório e que o vizinho gerado por este movimento pode não ter sido bom para a
continuidade da busca. Os dois algoritmos implementados têm o mesmo método de busca
local, o Randomized Variable Neighborhood Search (RVND). Para testar os algoritmos
foram utilizadas instâncias da literatura de pequeno e grande porte. Ambos os algoritmos
foram calibrados pelo software Irace. Os resultados dos algoritmos foram comparados
entre si e também com os do otimizador CPLEX. Com base nos resultados, verificou-se que o SILS se mostrou mais eficiente do que o ILS clássico com relação à capacidade de
encontrar melhores soluções.
Description
Programa de Pós-Graduação em Instrumentação, Controle e Automação de Processos de Mineração. Departamento de Engenharia de Controle e Automação, Escola de Minas, Universidade Federal de Ouro Preto.
Keywords
Dinâmica das máquinas, Algorítimos computacionais - Makespan, Algorítimos computacionais
Citation
RIBEIRO, Klevison Daniel de Oliveira. Algoritmos para o problema de sequenciamento de tarefas em máquinas paralelas idênticas. 2020. 43 f. Dissertação (Mestrado em Instrumentação, Controle e Automação de Processos de Mineração) - Escola de Minas, Universidade Federal de Ouro Preto, Ouro Preto, 2020.