SEQUENCIAMENTO DE TAREFAS COM APLICAÇÃO DO ALGORITMO COLÔNIA DE FORMIGAS PARA MINIMIZAÇÃO DO MAKESPAN

Vol 51, 2019 - 111604
Pôster
Favorite this paper
How to cite this paper?
Abstract

Sequenciamento de tarefas consiste em uma técnica alternativa para melhorias de processos com carência por controle e monitoramento em sistemas de processamento em lote, seja em manufaturas ou serviços. Esta técnica atua no planejamento da produção, designando a ordem de execução das tarefas segundo os recursos disponíveis e as restrições do processo, a fim de minimizar o tempo de conclusão das tarefas ou o número de tarefas atrasadas. Como é o caso do makespan, uma métrica de desempenho definida como o momento em que a última tarefa sai do sistema, sendo este necessário quando as tarefas a serem executadas dependem da sequência, ou seja, o sequenciamento de tarefas apresenta tempos de preparação dependentes entre as tarefas. Assim, o trabalho objetiva minimizar o makespan em sequenciamento de tarefas com tempo de preparação dependentes da sequência, utilizando Problema do Caixeiro-Viajante (PCV) e a meta-heurística Colônia de Formigas (ACO) em um caso real e comparando seus resultados. Designar o sequenciamento com ACO, é uma boa alternativa para rápida resposta do modelo na tomada de decisão dos gestores de produção. Para tanto, foram utilizados dados reais de três setores (injeção de solados, corte de palmilhas e montagem de sapatos) em uma indústria de calçados femininos, situada na cidade de Juazeiro do Norte-CE. Para cada setor foram considerados, respectivamente, 15, 23, e 30 tarefas com o seu tempo de processamento, data de entrega do item e tempos de setup. Para tratar o problema como PCV, transformou-se as tarefas em um grafo com pesos nas arestas, acrescentando um nó fictício ao grafo original para indicar o início e o fim do sequenciamento. Os parâmetros adotados para o ACO foram escolhidos por meio de testes que mostrassem o que mais se adequava a uma solução mais atrativa. Sendo assim, α (influência do feromônio) = 1, β (influência da distância) = 1, ρ (taxa de evaporação do feromônio) = 0,3, Q (constante do ACO) = 1 e τ (valor do feromônio presente nas rotas) = 1, número de iterações para convergência = 100. Os resultados apresentaram gaps de 0,0%, 0,0% e 4,8% para os respectivos setores, em tempos inferiores a 0,05 segundos. Referente ao atraso máximo verificou-se que o mesmo número de tarefas em atraso foi encontrado, considerando o PCV e o ACO, porém algumas tarefas foram sequenciadas de forma diferente para os dois primeiros setores. Nos dois primeiros setores, a resolução do ACO apresentou valor ótimo comparado ao do PCV, com as 100 iterações aplicadas para a convergência. Já o terceiro setor apresentou uma solução de 92,86% aproximada do PCV com 2 tarefas a mais em atraso e 2 dias a mais de produção para fechar o lote.

Share your ideas or questions with the authors!

Did you know that the greatest stimulus in scientific and cultural development is curiosity? Leave your questions or suggestions to the author!

Sign in to interact

Have a question or suggestion? Share your feedback with the authors!

Institutions
  • 1 Universidade Federal de Pernambuco - UFPE
Track
  • OC – Otimização Combinatória
Keywords
sequenciamento
Colônia de Formigas
Problema do caixeiro viajante