Apresentações
Resolução de problemas de programação de máquinas paralelas pelo método de partição e geração de colunas
Manuel Joaquim Pereira Lopes
— ISEP
O problema de programação de máquinas paralelas envolve a determinação da melhor afectação e sequenciamento de n trabalhos a m máquinas de forma a minimizar uma função de custo.
Neste trabalho, apresento um novo algoritmo de optimização para a solução de problemas de máquinas paralelas não-idênticas com tempos de preparação dependentes da sequência e datas de disponibilidade para as máquinas e para os trabalhos, de forma a minimizar a soma ponderada dos desvios positivos (atrasos) às datas de entrega dos trabalhos.
É apresentada uma primeira formulação matemática em que a função de custo é não-linear. Pela aplicação do método de decomposição de Dantzig-Wolfe obtemos uma formulação de programação inteira equivalente em que cada variável de decisão (coluna) representa uma sequência de afectação numa máquina. A relaxação linear desta formulação é resolvida pelo método de geração de colunas, onde as colunas são geradas em m subproblemas, em que cada um deles representa um problema de programação de máquina única. Colunas válidas são adicionadas à solução inicial admissível pela resolução de um problema de caminho mais curto com datas de disponibilidade das máquinas e dos trabalhos, usando programação dinâmica. São estudados vários modelos de programação dinâmica e é proposto um método para melhorar a eficiência do modelo adoptado.
A solução da relaxação linear obtida fornece geralmente um bom limite inferior, que é usado num algoritmo de partição e avaliação para resolver a formulação de programação inteira. É desenvolvida uma regra específica de partição que reduz significativamente o número de nodos explorados na árvore de pesquisa. É ainda desenvolvida uma heurística para determinar uma solução inicial para o problema.
São apresentados métodos de aceleração e estabilização do algoritmo de geração de colunas e é proposto um novo método designado por “primal boxstep”.
Por último, são apresentados resultados de testes computacionais para uma gama alargada de problemas com diferentes características e diferentes níveis de congestionamento do sistema, que mostram que esta aproximação é capaz de resolver problemas de dimensão significativa em tempo computacional considerado razoável.