"A Transversalidade da Ciência, Tecnologia e Inovações para o Planeta"
5 a 7 de outubro de 2021
Trabalho 15424
| ISSN | 2237-9045 |
|---|---|
| Instituição | Universidade Federal de Viçosa |
| Nível | Graduação |
| Modalidade | Pesquisa |
| Área de conhecimento | Ciências Exatas e Tecnológicas |
| Área temática | Ciência da computação |
| Setor | Departamento de Informática |
| Bolsa | PIBIC/CNPq |
| Conclusão de bolsa | Sim |
| Apoio financeiro | CNPq |
| Primeiro autor | Gabriel de Paula Félix |
| Orientador | JOSE ELIAS CLAUDIO ARROYO |
| Título | Otimização Combinatória Aplicada em Problemas de Programação da Produção e Transporte |
| Resumo | Neste projeto foi estudado o problema bi-objetivo de programação de tarefas em máquinas paralelas no ambiente no-wait flowshop permutacional. Neste problema, um conjunto de tarefas deve ser processado nas máquinas disponíveis em uma fábrica, sendo cada tarefa processada sem interrupções. As tarefas possuem prazos de entrega e tempos de processamento diferentes que são influenciados por um fator de velocidade inversamente proporcional ao consumo de energia das máquinas. O objetivo do problema é determinar a sequência de processamento das tarefas e o fator de velocidade no qual cada tarefa será executada, de tal forma que seja minimizado o atraso total e o consumo de energia das máquinas. Utilizando modelos convencionais de programação linear inteira, o tempo de execução requerido torna inviável encontrar soluções otimizadas para o problema a medida em que o número de tarefas ou máquinas aumenta. Desta forma, são propostos: um algoritmo baseado na meta-heurística Iterated Local Search (ILS), um algoritmo construtivo com critério de construção flexível e dois conjuntos de vizinhanças diferentes. Para testar a eficiência dos algoritmos, é utilizado um conjunto de 110 instâncias de pequeno a grande porte disponíveis na literatura, contando com até 200 tarefas e 20 máquinas. Desenvolvidos na linguagem C++11, os algoritmos visam executar o conjunto de instâncias de forma rápida e utilizando estruturas de dados eficientes para atingir este objetivo. Após sua implementação, os algoritmos passaram por uma calibragem de parâmetros para aprimorar seus resultados. O desempenho do algoritmo heurístico proposto é avaliado e comparado através de experimentos computacionais. Os resultados mostram que a heurística proposta possui um desempenho de destaque quando comparada a algoritmos baseados nas meta-heurísticas Artificial Bee Colony (ABC), Iterated Local Search (ILS) e Genetic Algorithm (GA), além de apresentar um tempo de execução rápido. Em projetos futuros, é interessante estudar o comportamento da heurística e outras técnicas de solução para o caso de uma fábrica que atenda demandas de clientes em tempo real. |
| Palavras-chave | Otimização, no-wait flowshop scheduling, heurísticas |
| Forma de apresentação..... | Painel |
| Link para apresentação | Painel |
|---|