Abordagens simheurísticas para o problema de sequenciamento em máquinas paralelas.
dc.contributor.advisor | Gomes Júnior, Aloísio de Castro | |
dc.contributor.advisor | Reis, Allexandre Fortes da Silva | |
dc.contributor.advisor | Gomes, Helton Cristiano | |
dc.contributor.author | Cota, Fernanda dos Reis | |
dc.contributor.referee | Gomes Júnior, Aloísio de Castro | |
dc.contributor.referee | Gomes, Helton Cristiano | |
dc.contributor.referee | Guimarães, Irce Fernandes Gomes | |
dc.contributor.referee | Sousa Junior, Wilson Trigueiro de | |
dc.date.accessioned | 2024-09-10T20:33:31Z | |
dc.date.available | 2024-09-10T20:33:31Z | |
dc.date.issued | 2024 | |
dc.description | Programa de Pós-Graduação em Engenharia de Produção. Departamento de Engenharia de Produção, Instituto de Ciências Exatas e Aplicadas, Universidade Federal de Ouro Preto. | |
dc.description.abstract | O problema de sequenciamento em máquinas paralelas (PMSP) é um problema combinatório clássico que, desde suas publicações seminais, oferece grandes desafios para a pesquisa, dada a sua vasta aplicação em problemas teóricos e práticos. Neste trabalho, uma variante estocástica do PMSP será abordada, considerando a minimização do makespan. Para tornar o problema mais realístico, os parâmetros estocásticos serão a disponibilidade para iniciar o processamento das atividades e as paradas programadas das máquinas. Dois algoritmos do tipo simheurística são propostos, estes baseados na Busca local iterada (Iterated local search - ILS) e no método de Busca em vizinhança variável (Variable neighborhood search - VNS), que buscarão minimizar os valores esperados para o critério de otimização adotado. As soluções iniciais são geradas através da adoção da heurística LPT (Longest processing time - Maior tempo de processamento) e novas soluções são produzidas a partir de estruturas de vizinhança que funcionam ora como buscas locais ora como métodos de perturbação. Estas estruturas realizam alterações individualmente e entre diferentes pares de máquinas. Os resultados encontrados pelos métodos propostos, ILS e VNS, foram superiores, quando comparados com a resolução pelo solver comercial AMPL/CPLEX. Obtendo 47% dos melhores valores para a esperança do makespan para o ILS e 37% para o VNS. É necessário destacar que ambos métodos obtiveram baixos tempos computacionais, onde o ILS chegou a ser até 37 vezes mais rápido que o VNS. | |
dc.description.abstracten | The parallel machine scheduling problem (PMSP) is a classic combinatorial problem that has offered great challenges for research since its seminal publications, owing to its wide application in theoretical and practical domains. In this work, we approach a stochastic variant of PMSP, considering the minimization of makespan. To make the problem more realistic, the stochastic parameters considered are the availability to start processing the activities and the unscheduled stops of the machines. We propose two simheuristic algorithms based on Iterative local search (ILS) and Variable neighborhood search (VNS), aiming to minimize the expected values for the adopted optimization criterion. The initial solutions are generated by adopting the LPT (Longest processing time) heuristic, and new solutions are produced from neighborhood structures that function as either local searches or perturbation methods. These structures perform changes individually and between different pairs of machines. The results obtained by the proposed methods, ILS and VNS, were superior when compared to the resolution using the commercial solver AMPL/CPLEX. The ILS obtained 47% of the best values for the expected makespan, and the VNS obtained 37%. It is important to highlight that both methods achieved low computational times, with the ILS being up to 37 times faster than the VNS. | |
dc.identifier.citation | COTA, Fernanda dos Reis. Abordagens simheurísticas para o problema de sequenciamento em máquinas paralelas. 2024. 60 f. Dissertação (Mestrado em Engenharia de Produção) – Instituto de Ciências Exatas e Aplicadas, Universidade Federal de Ouro Preto, João Monlevade, 2024. | |
dc.identifier.uri | https://www.repositorio.ufop.br/handle/123456789/18563 | |
dc.language.iso | pt | |
dc.rights | aberto | |
dc.rights | Attribution-NonCommercial-NoDerivs 3.0 United States | en |
dc.rights.license | Autorização concedida ao Repositório Institucional da UFOP pelo(a) autor(a) em 07/08/2024 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. | |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/us/ | |
dc.subject | Otimização combinatória | |
dc.subject | Algoritmos computacionais | |
dc.subject | Otimização matemática | |
dc.subject | Heurística | |
dc.subject | Programação heurística | |
dc.title | Abordagens simheurísticas para o problema de sequenciamento em máquinas paralelas. | |
dc.type | Dissertacao |
Arquivos
Pacote Original
1 - 1 de 1
Nenhuma Miniatura disponível
- Nome:
- DISSERTAÇÂO_AbordagensSimheurísticaProblema.pdf
- Tamanho:
- 1 MB
- Formato:
- Adobe Portable Document Format
Licença do Pacote
1 - 1 de 1
Nenhuma Miniatura disponível
- Nome:
- license.txt
- Tamanho:
- 1.71 KB
- Formato:
- Item-specific license agreed upon to submission
- Descrição: