Resolução de problemas de programação de máquinas paralelas pelo método de partição e geração de colunas

Abstract

O problema de programação de máquinas paralelas não-idênticas com tempos de preparação dependentes da sequência é uma generalização do problema de programação de máquinas paralelas que envolve a determinação da melhor afectação e sequenciamento de n trabalhos a m máquinas, com tempos de preparação dependentes da sequência de trabalhos processados, de forma a minimizar uma função de custo. Neste trabalho, apresentamos 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 que designamos 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.

We consider a class of scheduling problems of unrelated parallel machines with sequence-dependent setup times which involves finding the best assignment and sequencing of n jobs to m machines, with sequence-dependent setup times, to minimize a cost function. In this work, we develop a new optimization algorithm for the solution of the unrelated parallel machines with sequence-dependent setup times and release dates for the machines and the jobs. First we give a mathematical formulation for the problem where the cost function is non-linear. By applying the Dantzig-Wolfe decomposition to this formulation we obtain an equivalent integer programming formulation where each decision variable (column) represents a single machine schedule. The linear programming relaxation of the integer programming formulation is solved by column generation, where columns are generated on m subproblems which are single-machine scheduling problems. Feasible columns are added as needed by solving a shortest path problem with release dates for the jobs and machines, using dynamic programming. Several dynamic programming models are studied and a method to increase the efficiency of the model chosen is proposed The linear programming solution obtained generally provides a strong lower bound that is used in a branch-and-bound algorithm to solve the integer formulation. A specific branching rule that reduces significantly the number of nodes explored is presented. Column generation stabilization and accelerating methods are presented and a new method designated by “primal boxstep” is proposed. A heuristic was developed to find an initial solution for the problem. The computational results show that the approach is capable of solving problems of large size to optimality within reasonable computational time for a wide variety of problems with different characteristics and levels of congestion of the system.