Avaliação de métodos heurísticos para a solução de problema de programação flowshop com tempos de setup assimétricos e dependentes da sequência (2011)
- Authors:
- Autor USP: CARNEIRO, FELIPE MARCUS - EESC
- Unidade: EESC
- Sigla do Departamento: SEP
- Subjects: HEURÍSTICA; PESQUISA OPERACIONAL; PROGRAMAÇÃO DA PRODUÇÃO
- Language: Português
- Abstract: Este trabalho é dedicado ao problema de programação em Flowshop Permutacional com tempos de preparação (setup) assimétricos e separados dos tempos de processamento e dependentes da seqüência de execução das tarefas e tem o objetivo de minimização da duração total da programação (Makespan). Através da investigação das propriedades estruturais do problema, são desenvolvidos os parâmetros XR e QR de uma programação, que indicam ociosidade das máquinas (para valores positivos) e bloqueio das tarefas (para valores negativos). Os novos parâmetros são utilizados para propor uma melhoria no cálculo eficiente de Makespan proposto por Taillard (1990). Esta melhoria é então utilizada no desenvolvimento de uma nova heurística construtiva baseada no método NEHT-RB de Ríos-Mercado e Bard (1998b) denominada CNIT, que é comparada durante a experimentação computacional com os métodos SETUP e TOTAL, de Simons (1992) com pequenas melhorias; com a proposta da utilização da propriedade UBX de Moccellin e Nagano (2007); e com o método NEHT-RB. Os métodos são então submetidos a uma busca local descendente como proposta em Ruiz e Stützle (2008) e seus desempenhos como soluções iniciais para este procedimento de busca local são avaliados. Em seguida, um método melhorativo derivado do novo método construtivo e baseado na meta-heurística IG de Ruiz e Stützle (2008) é proposto e denominado CNIT-IG. O método é comparado com a heurística IG original submetida às diferentes soluções iniciais estudadas durante a avaliação da nova heurística construtiva. As comparações são realizadas utilizando-se o banco de dados de Taillard (1990) para o flowshop permutacional adaptado para o problema de flowshop com tempos de setup assimétricos e dependentes da seqüência.Os resultados da experimentação computacional são analisados em termos da porcentagem média de sucesso, do desvio relativo médio e em relação ao tempo médio computacional e mostram a superioridade dos resultados da nova heurística construtiva CNIT e seu alto custo computacional, de complexidade 'MN POT.3'. Os resultados mostram ainda a superioridade da meta-heurística CNIT-IG sobre o método IG
- Imprenta:
- Publisher place: São Carlos
- Date published: 2011
- Data da defesa: 23.02.2011
-
ABNT
CARNEIRO, Felipe Marcus. Avaliação de métodos heurísticos para a solução de problema de programação flowshop com tempos de setup assimétricos e dependentes da sequência. 2011. Dissertação (Mestrado) – Universidade de São Paulo, São Carlos, 2011. Disponível em: http://www.teses.usp.br/teses/disponiveis/18/18156/tde-25042011-114532/. Acesso em: 23 abr. 2024. -
APA
Carneiro, F. M. (2011). Avaliação de métodos heurísticos para a solução de problema de programação flowshop com tempos de setup assimétricos e dependentes da sequência (Dissertação (Mestrado). Universidade de São Paulo, São Carlos. Recuperado de http://www.teses.usp.br/teses/disponiveis/18/18156/tde-25042011-114532/ -
NLM
Carneiro FM. Avaliação de métodos heurísticos para a solução de problema de programação flowshop com tempos de setup assimétricos e dependentes da sequência [Internet]. 2011 ;[citado 2024 abr. 23 ] Available from: http://www.teses.usp.br/teses/disponiveis/18/18156/tde-25042011-114532/ -
Vancouver
Carneiro FM. Avaliação de métodos heurísticos para a solução de problema de programação flowshop com tempos de setup assimétricos e dependentes da sequência [Internet]. 2011 ;[citado 2024 abr. 23 ] Available from: http://www.teses.usp.br/teses/disponiveis/18/18156/tde-25042011-114532/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas