Aplicação de um algoritmo de pesquisa meta-heurística por geração de colunas (SearchCol) ao problema de máquinas paralelas

Abstract

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.