Por favor, use este identificador para citar o enlazar este ítem: http://www.repositorio.ufop.br/jspui/handle/123456789/12339
Título : Algoritmos para o problema de sequenciamento de tarefas em máquinas paralelas idênticas.
Otros títulos : Algorithms for identical parallel machine scheduling problem.
Autor : Ribeiro, Klevison Daniel de Oliveira
metadata.dc.contributor.advisor: Souza, Marcone Jamilson Freitas
Cota, Luciano Perdigão
Palabras clave : Dinâmica das máquinas
Algorítimos computacionais - Makespan
Algorítimos computacionais
Fecha de publicación : 2020
metadata.dc.contributor.referee: Souza, Marcone Jamilson Freitas
Cota, Luciano Perdigão
Guimarães, Frederico Gadelha
Ribeiro, Roberto Gomes
Haddad, Matheus Nohra
Citación : 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.
Resumen : 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.
metadata.dc.description.abstracten: This work deals with the Identical Parallel Machine Scheduling Problem aiming to minimize the makespan and Total Energy Cost (TEC). In this problem, it is searched for a better way to allocate a group of jobs in a set of available machines to reduce operating costs. Such a class of problems has been widely studied today, given the search for energy efficiency and the optimization of production processes. Besides, this problem belongs to the NP-hard class, thus justifying the investigation of it. A bi-objective model from the literature was adjusted to a mono-objective approach by weighted sum to solve this problem. Also, two algorithms based on the Iterated Local Search (ILS) metaheuristic were adapted: the first referred to as ILS only, is a classic version of the method proposed in the literature. The second is an improved version, called Smart Iterated Local Search, or just SILS. In this adapted version, the perturbation dynamics are changed concerning the classic algorithm, allowing better performance of the local search incorporated into the method. While in the classic ILS, the level of perturbation is changed whenever there is no improvement in the solution, in SILS, further improvement attempts are made at the same level. Such modification was made based on the hypothesis that the increase in the perturbation level may be precipitated since it is a random movement, and the neighbor generated by this movement may not have been good for the continuity of the search. The two algorithms implemented have the same local search method, Randomized Variable Neighborhood Search (RVND). Small and large instances of literature were used for testing the algorithms. Both algorithms were calibrated using the Irace software. The results of the algorithms were compared with each other and also with the CPLEX solver. Based on the results, it was found that SILS proved to be more efficient than classic ILS concerning the ability to find better solutions.
Descripción : 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.
URI : http://www.repositorio.ufop.br/handle/123456789/12339
metadata.dc.rights.license: Autorização concedida ao Repositório Institucional da UFOP pelo(a) autor(a) em 04/06/2020 com as seguintes condições: disponível sob Licença Creative Commons 4.0 que permite copiar, distribuir e transmitir o trabalho desde que sejam citados o autor e o licenciante. Não permite o uso para fins comerciais nem a adaptação.
Aparece en las colecciones: PROFICAM - Mestrado (Dissertações)

Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
DISSERTAÇÃO_AlgoritmosProblemaSequenciamento.pdf2,61 MBAdobe PDFVisualizar/Abrir


Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons Creative Commons