Conexão de Saberes e Mundialização
19 a 24 de outubro de 2015
Trabalho 4504
| 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 | Teoria e Tecnologia da informação |
| Setor | Departamento de Informática |
| Bolsa | PROBIC/FAPEMIG |
| Conclusão de bolsa | Sim |
| Apoio financeiro | FAPEMIG |
| Primeiro autor | Ricardo Gonçalves Tavares |
| Orientador | JOSE ELIAS CLAUDIO ARROYO |
| Título | Sequenciamento da Produção: Modelos e Algoritmos de Otimização |
| Resumo | Neste trabalho é estudado o problema conhecido como Assembly Flowshop Scheduling com dois estágios (2sAFS). Este problema consiste em fabricar um conjunto de n produtos (tarefas), sendo que cada tarefa possui m componentes que são fabricados de forma independente em dois estágios. No primeiro estágio, os componentes das tarefas são fabricados em um ambiente de m máquinas paralelas (cada componente é feito em uma máquina). Quando todos os componentes de um produto estiverem prontos, no segundo estágio, o produto é montado. A montagem é realizada por uma única máquina. Neste problema, todas as tarefas estão disponíveis para serem processadas em um tempo zero, todas as máquinas processam apenas uma tarefa por vez e não podem ser interrompidas durante seu processamento. Note que para cada tarefa existem m+1 operações distintas, sendo que m operações independentes são feitas no primeiro estágio e uma operação é realizada no segundo estágio. Os dois estágios caracterizam o problema como um ambiente de produção flowshop, pois uma tarefa i só pode iniciar a montagem (no estágio 2) quando todas seus componentes forem finalizadas no estágio 1. Quando m = 1 (uma única máquina no primeiro estágio), o problema 2sAFS é reduzido ao problema flowshop permutacional com duas máquinas, que é considerado NP-Difícil quando for minimizado o atraso total. O problema 2sAFS tem sido bastante abordado na literatura considerando a minimização do makespan. Há muitos problemas práticos que podem ser modelados como o problema 2sAFS, e devido a suas aplicações e importância teórica, o problema 2sAFS tem recebido, recentemente, muita atenção na literatura sobre scheduling. O objetivo do problema é determinar o sequenciamento das tarefas nas máquinas de forma soma dos atrasos das tarefas seja minimizado. No problema abordado, os seguintes dados são conhecidos: o tempo de processamento da tarefa i na máquina k do primeiro estágio, tempo de montagem da tarefa i e data de entrega da tarefa i. Para a solução deste problema, neste trabalho propõe-se um modelo de Programação Inteira Mista (PIM) e quatro heurísticas para a minimização do atraso total. As duas primeira heurísticas são baseadas nas meta-heurísticas Iterated Greedy (IG) e Iterated Local Search (ILS), respectivamente. As outras duas heurísticas são métodos híbridos que combinam IG e ILS com Variable Neighborhood Descent (VND). As heurísticas, ILS e VND são métodos simples, robustos e eficientes que são aplicados para resolver diferentes problemas de otimização combinatória. IG e ILS ainda são pouco aplicados para problemas de sequenciamento de tarefas. O modelo matemático é resolvido utilizando o solver de otimização CPLEX e são obtidas soluções ótimas para algumas instâncias do problema de pequeno e médio porte. Os experimentos computacionais mostram que os algoritmos heurísticos determinam soluções aproximadas de alta qualidade em um baixo tempo computacional. Os resultados são validados através de testes estatísticos. |
| Palavras-chave | Sequenciamento da produção, Otimização, Heurísticas |
| Forma de apresentação..... | Oral |