Algoritmos para o problema de sequenciamento de tarefas em máquinas paralelas idênticas.

Simple item page
dc.contributor.advisorSouza, Marcone Jamilson Freitaspt_BR
dc.contributor.advisorCota, Luciano Perdigãopt_BR
dc.contributor.authorRibeiro, Klevison Daniel de Oliveira
dc.contributor.refereeSouza, Marcone Jamilson Freitaspt_BR
dc.contributor.refereeCota, Luciano Perdigãopt_BR
dc.contributor.refereeGuimarães, Frederico Gadelhapt_BR
dc.contributor.refereeRibeiro, Roberto Gomespt_BR
dc.contributor.refereeHaddad, Matheus Nohrapt_BR
dc.date.accessioned2020-06-12T17:02:44Z
dc.date.available2020-06-12T17:02:44Z
dc.date.issued2020
dc.descriptionPrograma 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.pt_BR
dc.description.abstractEste 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.pt_BR
dc.description.abstractenThis 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.pt_BR
dc.identifier.citationRIBEIRO, 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.pt_BR
dc.identifier.urihttp://www.repositorio.ufop.br/handle/123456789/12339
dc.language.isopt_BRpt_BR
dc.rightsabertopt_BR
dc.rights.licenseAutorizaçã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.pt_BR
dc.subjectDinâmica das máquinaspt_BR
dc.subjectAlgorítimos computacionais - Makespanpt_BR
dc.subjectAlgorítimos computacionaispt_BR
dc.titleAlgoritmos para o problema de sequenciamento de tarefas em máquinas paralelas idênticas.pt_BR
dc.title.alternativeAlgorithms for identical parallel machine scheduling problem.pt_BR
dc.typeDissertacaopt_BR
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
DISSERTAÇÃO_AlgoritmosProblemaSequenciamento.pdf
Size:
2.55 MB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
924 B
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
PROFICAM - Mestrado (Dissertações)