Ciência e Tecnologia: bases para o Desenvolvimento Social
20 a 25 de outubro de 2014
Trabalho 2738
| 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 | Algot-Scheduling: algoritmos eficientes de otimização para problemas de sequenciamento da produção |
| Resumo | O problema estudado nesta pesquisa é o sequenciamento de tarefas em um ambiente Assembly Flowshop com três estágios. Este problema consiste em processar um conjunto de n tarefas, sendo que cada tarefa possui m componentes que são fabricados de forma independente. No primeiro estágio, os componentes das tarefas são fabricados em um ambiente de m máquinas paralelas. O segundo estágio consiste no transporte das peças processadas, no primeiro estágio, para o terceiro e ultimo estágio, onde é feita a montagem do produto. Os estágios 2 e 3 são realizadas por máquinas diferentes. Sendo assim, 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+2 operações distintas, sendo que m operações independentes são feitas no primeiro estágio e as outras duas operações são realizadas nos dois últimos estágios, respectivamente. Nos três estágios existem tempos de setup dependentes da sequência das tarefas. Estes tempos são gastos para preparar cada máquina entre o processamento de duas tarefas consecutivas (retirar a tarefa da máquina, limpar a máquina e ajustar a máquina para a próxima tarefa). Os três estágios caracterizam o problema como um ambiente de produção flowshop. Ou seja, uma tarefa j só pode iniciara a operação de transporte quando a produção de todas suas peças forem finalizadas no estágio 1, e a montagem da tarefa só poderá ser iniciada após a tarefa j chegar no estágio de montagem. O problema estudado no projeto é classificado como NP-Difícil. Neste trabalho foram desenvolvidas quatro heurísticas para resolver o problema, sendo duas heurísticas básicas e duas híbridas. As heurísticas são baseadas nas metaheurísticas Iterated Local Search (ILS), Iterated Greedy Algorithm (IGA), Variable Neighborhood Descent (VND) e Genetic Algorithm (GA). Para analisar o desempenho das heurísticas, foram geradas instâncias do problema de diferentes tamanhos, variando o número de tarefas e o número de máquinas. Para instâncias de pequeno porte, as heurísticas propostas são comparadas com o Método de Enumeração Completa (EC), que avalia todas as possíveis soluções e determinando a ótima. Para instâncias de grande porte, as soluções obtidas por cada heurística são comparadas com as soluções de referência (melhores soluções obtidas entre todas as heurísticas). As heurísticas foram executadas utilizando o mesmo critério de parada (tempo de CPU). Este tempo depende do tamanho das instâncias. A métrica utilizada para a avaliação da qualidade das soluções é o Desvio Percentual Relativo (RPD) com relação às soluções de referência. Os resultados são validados através de testes estatísticos. |
| Palavras-chave | Sequenciamento da produção, scheduling, otimização |
| Forma de apresentação..... | Oral |