Meta-heurísticas Iterated Local Search, GRASP e Artificial Bee Colony aplicadas ao Job Shop Flexível para minimização do atraso total (2014)
- Authors:
- Autor USP: MELO, EVERTON LUIZ DE - EP
- Unidade: EP
- Sigla do Departamento: PRO
- Subjects: OTIMIZAÇÃO COMBINATÓRIA; PROGRAMAÇÃO DA PRODUÇÃO; MODELOS MATEMÁTICOS; HEURÍSTICA
- Language: Português
- Abstract: O ambiente de produção abordado neste trabalho é o Job Shop Flexível (JSF), uma generalização do Job Shop (JS). O problema de programação de tarefas, ou jobs, no ambiente JS é classificado por Garey; Johnson e Sethi (1976) como NP-Difícil e o JSF é, no mínimo, tão difícil quanto o JS. O JSF é composto por um conjunto de jobs, cada qual constituído por operações. Cada operação deve ser processada individualmente, sem interrupção, em uma única máquina de um subconjunto de máquinas habilitadas. O principal critério de desempenho considerado é a minimização dos atrasos dos jobs. São apresentados modelos de Programação Linear Inteira Mista (PLIM) para minimizar o atraso total e o instante de término da última operação, o makespan. São propostas novas regras de prioridade dos jobs, além de adaptações de regras da literatura. Tais regras são utilizadas por heurísticas construtivas e são aliadas a estratégias cujo objetivo é explorar características específicas do JSF. Visando aprimorar as soluções inicialmente obtidas, são propostas buscas locais e outros mecanismos de melhoria utilizados no desenvolvimento de três meta heurísticas de diferentes categorias. Essas meta heurísticas são: Iterated Local Search (ILS), classificada como meta heurística de trajetória; Greedy Randomized Adaptive Search (GRASP), meta heurística construtiva; e Artificial Bee Colony (ABC), meta heurística populacional recentemente proposta. Esses métodos foram selecionados por alcançarem bons resultados para diversos problemas de otimização da literatura. São realizados experimentos computacionais com 600 instâncias do JSF, permitindo comparações entre os métodos de resolução. Os resultados mostram que explorar as características do problema permite que uma das regras de prioridade propostas supere a melhor regra da literatura em 81% das instâncias.As meta heurísticas ILS, GRASP e ABC chegam a conseguir mais de 31% de melhoria sobre as soluções iniciais e a obter atrasos, em média, somente 2,24% superiores aos das soluções ótimas. Também são propostas modificações nas meta heurísticas que permitem obter melhorias ainda mais expressivas sem aumento do tempo de execução. Adicionalmente é estudada uma versão do JSF com operações de Montagem e Desmontagem (JSFMD) e os experimentos realizados com um conjunto de 150 instâncias também indicam o bom desempenho dos métodos desenvolvidos.
- Imprenta:
- Data da defesa: 07.02.2014
-
ABNT
MELO, Everton Luiz de. Meta-heurísticas Iterated Local Search, GRASP e Artificial Bee Colony aplicadas ao Job Shop Flexível para minimização do atraso total. 2014. Tese (Doutorado) – Universidade de São Paulo, São Paulo, 2014. Disponível em: http://www.teses.usp.br/teses/disponiveis/3/3136/tde-15122014-002717/. Acesso em: 20 maio 2024. -
APA
Melo, E. L. de. (2014). Meta-heurísticas Iterated Local Search, GRASP e Artificial Bee Colony aplicadas ao Job Shop Flexível para minimização do atraso total (Tese (Doutorado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/3/3136/tde-15122014-002717/ -
NLM
Melo EL de. Meta-heurísticas Iterated Local Search, GRASP e Artificial Bee Colony aplicadas ao Job Shop Flexível para minimização do atraso total [Internet]. 2014 ;[citado 2024 maio 20 ] Available from: http://www.teses.usp.br/teses/disponiveis/3/3136/tde-15122014-002717/ -
Vancouver
Melo EL de. Meta-heurísticas Iterated Local Search, GRASP e Artificial Bee Colony aplicadas ao Job Shop Flexível para minimização do atraso total [Internet]. 2014 ;[citado 2024 maio 20 ] Available from: http://www.teses.usp.br/teses/disponiveis/3/3136/tde-15122014-002717/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
