Utilize este identificador para referenciar este registo:
https://hdl.handle.net/1822/23220
Título: | Aplicação de um algoritmo de pesquisa meta-heurística por geração de colunas (SearchCol) ao problema de máquinas paralelas |
Autor(es): | Lopes, Henrique Daniel Oliveira |
Orientador(es): | Alvelos, Filipe Pereira e |
Data: | 2012 |
Resumo(s): | Neste trabalho é apresentada a aplicação de um algoritmo de pesquisa meta-heurística
por geração de colunas (SearchCol) ao problema de máquinas paralelas não idênticas,
com tempos de preparação dependentes da sequência, com o objetivo de minimizar a
soma ponderada dos atrasos.
O SearchCol é um método híbrido que combina a geração de colunas com meta-heurísticas com o objetivo de obter boas soluções para problemas de otimização combinatória em tempos aceitáveis. A ideia chave é que a solução de um problema é vista
como uma combinação de soluções de problemas de menor dimensão (subproblemas). As
soluções dos subproblemas são obtidas pela geração de colunas e sua combinação é feita
por uma meta-heurística.
Neste trabalho, são testadas diferentes políticas de inserção de colunas no problema
mestre restrito juntamente com os diferentes algoritmos de resolução do subproblema,
nomeadamente o algoritmo de programação dinâmica que resolve o subproblema de forma
exata e duas heurísticas. São apresentados resultados de testes computacionais para
afinação dos parâmetros do SearchCol. Os resultados do SearchCol são comparados com
os resultados de um algoritmo de partição e geração de colunas (Branch-and-Price) e uma
heurística baseada em geração de colunas e programação inteira mista. This work presents the application of a metaheuristic search by column generation (SearchCol) algorithm to an unrelated parallel machines problem, with sequence-dependent setup times and the objective of minimizing the total weighted tardiness. The SearchCol method consists in a hybridization of column generation with metaheuristics to obtain good solutions for combinatorial optimization problems in acceptable times. The central idea is that the solution of a problem can be seen as a combination of solutions of smaller problems (subproblems). The solutions of subproblems are obtained by column generation and their combination is done by a meta-heuristics. In this work, di erent policies insertion of columns in the restricted master problem, are tested, along with different subproblem solving algorithms, namely the dynamic programming algorithm that solves the subproblem accurately and two heuristics. We present the results of computational tests that lead to tuning of SearchCol parameters. The results of SearchCol are compared with the results of a Branch-and-Price algiritm and a heuristic based on column generation and mixed integer programming. |
Tipo: | Dissertação de mestrado |
Descrição: | Dissertação de mestrado em Engenharia de Sistemas |
URI: | https://hdl.handle.net/1822/23220 |
Acesso: | Acesso aberto |
Aparece nas coleções: | BUM - Dissertações de Mestrado DPS - Dissertações de Mestrado |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
Henrique Daniel Oliveira Lopes.pdf | 1,9 MB | Adobe PDF | Ver/Abrir |