Publication
Heuristicas para a minimização dos atrasos em sequenciamento de maquinas paralelas com tempos de preparação dependentes da sequência
| Summary: | 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 |
|---|---|
| Main Authors: | Mateus Rocha de Paula |
| Subject: | Processamento eletronico de dado Processamento paralelo Processamento eletronico de dados Processamento paralelo (Computadores) Algoritmos de computador Computação |
| Year: | 2019 |
| Country: | Brazil |
| Document type: | master thesis |
| Access type: | open access |
| Associated institution: | IBICT |
| Language: | Portuguese |
| Origin: | Oasisbr |
| Summary: | 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 |
|---|
Funded activities
No funded projects found.