Meta-heurísticas para resolução de alguns problemas de planejamento e controle da produção
Nome: DAYAN DE CASTRO BISSOLI
Tipo: Tese de doutorado
Data de publicação: 03/08/2018
Orientador:
Nome | Papel |
---|---|
ANDRÉ RENATO SALES AMARAL | Orientador |
Banca:
Nome | Papel |
---|---|
ANDRÉ RENATO SALES AMARAL | Orientador |
GERALDO REGIS MAURI | Examinador Interno |
JORGE PINHO DE SOUSA | Examinador Externo |
LUCIANO LESSA LORENZONI | Examinador Externo |
RENATO ELIAS NUNES DE MORAES | Examinador Interno |
Resumo: Este estudo aborda a resolução de três diferentes problemas, amplamente encontrados
no real contexto de planejamento e controle da produção. Inicialmente, é proposta uma
meta-heurística GRASP para solucionar um problema de balanceamento de linhas de
montagem (SALBP-2). O método proposto apresentou resultados competitivos em relação
à literatura, também focando numa simplicidade de operação para ser aplicada em casos
reais. Na sequência, utilizou-se o mesmo método para solucionar o problema Job Shop
Scheduling (JSP). O GRASP desenvolvido para o JSP também apresentou bons resultados,
com baixo desvio relativo médio em relação às melhores soluções conhecidas da literatura.
Em seguida, abordou-se uma extensão do JSP, o problema Job Shop Scheduling Flexível
(FJSP). O JSP limita-se ao sequenciamento de operações em máquinas fixas, enquanto que
no FJSP a atribuição de uma operação não é pré-fixada e pode assim ser processada num
conjunto de máquinas alternativas. Portanto, o FJSP não se restringe ao sequenciamento,
estendendo-se na atribuição de operações para as máquinas adequadas (roteamento). O
FJSP é, portanto, mais complexo do que o JSP, pois considera a determinação da atribuição
da máquina para cada operação. Para solucionar o FJSP, propôs-se quatro meta-heurísticas:
GRASP, Simulated Annealing (SA), Iterated Local Search (ILS) e Clustering Search (CS).
O SA apresentou resultados inferiores, porém, ao incorporá-lo numa versão híbrida do ILS,
que o utiliza como busca local, os resultados melhoraram, principalmente em instâncias
mais complexas. Considerando a característica híbrida do CS, utilizou-se também o SA,
nesse caso como meta-heurística geradora de soluções. Essa abordagem também apresentou
resultados superiores ao SA. Tanto o ILS quanto o CS geraram resultados com valores
iguais ou próximos àqueles das melhores soluções conhecidas para um extenso conjunto
de instâncias para o FJSP, assim como também proveram alguns novos melhores valores
conhecidos.