Publicado no Encontro de Saberes 2015
Evento: XXIII Seminário de Iniciação Científica
Área: ENGENHARIAS
Subárea: Engenharia de Controle e Automação
| Título |
| Estudo e implementação de técnicas de busca em vizinhança de grande porte ao problema de sequenciamento de máquinas paralelas |
| Autores |
|
RODRIGO RIBEIRO FRANCO (Autor) GUSTAVO PEIXOTO SILVA (Orientador) |
| Resumo |
| O trabalho aborda o problema de sequenciamento de tarefas em máquinas paralelas e uniformes. Para cada tarefa é dado o tempo de processamento, a data de entrega, e o peso por dia de atraso. O objetivo é sequenciar as tarefas nas máquinas minimizando a soma ponderada dos atrasos (Parallel machines total weighted tardiness problem). Neste trabalho o problema foi resolvido pela metaheurística Iterated Local Search (ILS). A solução inicial foi obtida pelo um método guloso baseado na estratégia Early Due Date, que prioriza a alocação das tarefas com menor data de entrega. Duas estruturas de vizinhança foram utilizadas. A primeira se aplica uma máquina isoladamente (intra-máquina) e combina vizinhanças de trocas generalizadas entre pares (Generalized pairwise interchange). Neste caso, dadas duas tarefas de uma máquina temos: i) a troca da posição das duas tarefas (swap) e ii) a inversão da sequencia das tarefas que se encontram entre as duas tarefas (twist). A segunda estrutura de vizinhança se aplica a um par de máquinas distintas (entre-máquinas). Os movimentos são: i) a troca de duas tarefas entre as máquinas (exchange) e ii) a realocação de uma tarefa de uma máquina para outra (realocate). As estruturas de vizinhança foram combinadas em um algoritmo, sendo que no laço principal é realizada uma descida completa pelo método de busca de melhor de melhora (best improvement search). Em seguida é realizada uma busca completa utilizando a estrutura entre-máquinas. Esta sequencia de operações é realizada enquanto são obtidas soluções melhores. A fase de perturbação consiste em aplicar um número limitado de movimentos aleatórios do tipo swap, exchange e realocate entre máquinas escolhidas aleatoriamente. A metaheurística foi testada com problemas benchmark para os quais são conhecidos os resultados ótimos. Nos testes computacionais o ILS foi capaz de encontrar os resultados ótimos em um tempo de processamento razoável de 0.163. |
