Ciência, saúde e esporte: conhecimento e acessibilidade
21 a 26 de outubro de 2013
Trabalho 1680
| 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 | Automação, projetos de máquinas, equipamentos, processos e produtos |
| Setor | Departamento de Informática |
| Bolsa | PIBIC/CNPq |
| Conclusão de bolsa | Sim |
| Apoio financeiro | CNPq |
| Primeiro autor | Rodrigo Sidney Pereira |
| Orientador | JOSE ELIAS CLAUDIO ARROYO |
| Título | Uma heurística eficiente para o sequenciamento em máquinas paralelas com divisão de tarefas e tempos de preparação dependentes da sequencia |
| Resumo | O sequenciamento (scheduling) de tarefas é um dos problemas de otimização combinatória mais abordados na literatura devido a sua grande importância no meio industrial. Com a forte concorrência enfrentada pelas empresas se torna de vital importância ter um planejamento da produção que permita um aproveitamento eficiente dos recursos disponíveis e ao mesmo tempo tomadas rápidas de decisão. O Problema de de Sequenciamento de tarefas em Máquinas Paralelas (PSMP), se caracteriza por um conjunto N de n tarefas e um conjunto M de m máquinas em que cada tarefa pode ser processada por qualquer uma das máquinas sendo que o objetivo é alocar as tarefas nas máquinas de forma a minimizar o tempo total de processamento de todas as tarefas (makespan). Neste projeto é abordada uma variante do PSMP que considera a possibilidade de dividir uma tarefa em partes menores (não necessariamente inteiras) que podem ser processadas em máquinas diferentes e também a inclusão de tempos de preparação das máquinas entre a execução de duas tarefas consecutivas (tempos dependentes da ordem das tarefas ou da sequencia). Os tempos de preparação são nulos quando as partes de tarefas do mesmo tipo são processadas. O problema abordado pertence à classe NP-Difícil e por isso sua solução ótima se torna inviável para instâncias muito grandes. O objetivo deste trabalho é o desenvolvimento de métodos heurísticos eficientes para obtenção de soluções de alta qualidade do problema. Na literatura existem métodos de resolução desse problema baseados na redução ao problema do Caixeiro Viajante e que utilizam algoritmos exatos como o Branch-and-Bound. No entanto, esses métodos são inviáveis para resolver instâncias grandes do problema. Neste trabalho opta-se por utilizar algoritmos genéticos para fazer a busca de soluções heurísticas visando uma maior velocidade na execução do método e a possibilidade de trabalhar instâncias maiores do problema. A abordagem proposta considera inicialmente que, todas as tarefas precisam ser sequenciadas em uma única máquina sendo este problema resolvido como o problema do caixeiro viajante onde se minimiza a soma dos tempos de preparação. Em seguida a sequencia gerada na máquina inicial é dividida em m partes iguais considerando o tempo de execução das tarefas e essas partes são distribuídas para as outras máquinas. Depois são identificadas as máquinas que possuem os maiores tempos de execução e são removidas partes de algumas tarefas para serem inseridas em outras máquinas tornando os tempos de todas as máquinas mais homogêneos. O objetivo do algoritmo genético é determinar o melhor sequenciamento das tarefas de cada uma das máquinas. O método proposto é testado utilizando um total de 400 instâncias do problema, onde são consideradas instâncias com 40, 50, 70, 100 e 150 tarefas e 2, 3, 5 e 8 máquinas. As soluções obtidas, quando comparadas com lower bounds propostos na literatura, foram bastante interessantes e competitivos. |
| Palavras-chave | SEQUENCIAMENTO DE TAREFAS, OTIMIZAÇÃO COMBINATÓRIA, ALGORITMO GENÉTICO |
| Forma de apresentação..... | Oral |