Heuristicas para a minimização dos atrasos em sequenciamento de maquinas paralelas com tempos de preparação dependentes da sequência

AUTOR(ES)

Mateus Rocha de Paula

DATA DE PUBLICAÇÃO

2008

RESUMO

Considere o problema de sequenciar um conjunto de tarefas, a serem processadas exatamente uma vez em qualquer máquina de um conjunto de máquinas não-relacionadas, sem preempção. Cada tarefa tem uma data de entrega, um peso e, para cada máquina, além de um tempo de processamento, um tempo de preparação dependente da sequência. Em todo este trabalho, o objetivo é minimizar a soma dos atrasos ponderados das tarefas, mas outros objetivos, como a minimização do makespan e da soma das folgas também são discutidos.Inicialmente, este trabalho propõe e analisa implementações eficientes de diversas heurísticas baseadas em buscas locais para abordar o problema. Fatores como o desenho e detalhes de implementação dos algoritmos são discutidos. As heurísticas propostas são então comparadas com outrasimplementações bem sucedidas, para mostrar suas vantagens em termos de qualidade e tempo de computação, principalmente para instâncias de grande porte.Para medir a qualidade das soluções, os valores de função objetivo das soluções obtidas são comparados com limites inferiores do problema. Para obter tais limites, um algoritmo Non-Delayed Relax-and-Cut é desenvolvido a partir de uma relaxação lagrangeana de uma formulação indexada no tempo. Para obter-se soluções aproximadas para o problema, a relaxação lagrangeana apresentada também é utilizada para

ASSUNTO(S)

processamento paralelo (computadores) teses. processamento eletronico de dados teses. algoritmos de computador teses. computação teses.

Documentos Relacionados

• Estudo de meta-heuristicas populacionais para a programação de maquinas paralelas com tempos de preparação dependentes da sequencia e datas de entrega
• Um problema de sequenciamento em máquinas paralelas não-relacionadas com tempos de preparação dependentes de máquina e da sequência:: modelos e algoritmos exato.
• Evolutionary Algorithms for Parallel Machine Scheduling Problems with Sequence Dependent Setup Times
• Sequenciamento de plantas multiproposito com tempos de preparação dependentes da sequencia utilizando a representação STN
• Otimização bi-objetivo para o problema de sequenciamento de tarefas em uma maquina com tempos de preparação dependentes da sequencia