Algoritmos de partição e geração de colunas para dimensionamento de lotes de produção

Abstract

Nesta tese, apresentam-se duas aplicações do método de partição e geração de colunas ao problema de lotes de produção multi-artigo capacitado com tempos de preparação. O problema de lotes de produção multi-artigo capacitado com tempos de preparação pode ser descrito como um modelo no qual se procura determinar um plano de produção para vários artigos ao longo de um determinado horizonte temporal, que minimize os custos de produção, de armazenagem e de preparação dos artigos e respeite restrições de procura e de capacidade. A abordagem seguida é a de reformular a formulação de programação inteira mista do problema, utilizando o princípio da decomposição de Dantzig-Wolfe, e combinar o método de geração de colunas com o método de partição e avaliação (método de partição e geração de colunas) para obter soluções óptimas. Na definição da regra de partição utiliza-se uma abordagem baseada nas variáveis binárias do modelo original, que garante a preservação da estrutura do subproblema. A partir da formulação de programação inteira mista do problema, definem-se dois modelos de decomposição: a decomposição por artigo e a decomposição por período e resolvem-se os problemas reformulados através do método de geração de colunas. Para determinar a solução óptima inteira dos problemas reformulados aplica-se o método de partição e geração de colunas. São apresentados resultados de testes computacionais para um conjunto de instâncias com diferentes características, que permitem estabelecer comparações entre os dois modelos de decomposição. Esses resultados computacionais são ainda comparados com a formulação de programação inteira mista que se resolve através de um “solver” de problemas de programação inteira mista, o CPLEX.

In this thesis, we present two branch-and-price algorithms to solve the multi-item capacitated lot-sizing problem with setup times. The multi-item capacitated lot-sizing problem with setup times can be seen as a model in which we want to find a production plan for several items over a number of time periods, that minimize the labour costs, inventory costs and setup costs and satisfies all demand requirements without exceeding capacity limits. The approach taken consists in reformulating the mixed integer problem, using the Dantzig-Wolfe decomposition principle, and then combining the column generation method with the branch-and-bound method (branch-and-price method) in order to obtain optimal solutions. In the definition of the branch rule we use an approach based on the binary variables of the original model that assure the conservation of the structure of the subproblem. Based on the mixed integer formulation of the problem, we develop two decomposition models: the item decomposition and the period decomposition and solve the reformulated problems with the column generation method. In order to obtain the integer optimal solution of the reformulated problems we use the branch-and-price method. We present results of the computational tests for a set of instances with different characteristics, to establish comparisons between the two decomposition models. These results are then compared with the mixed integer formulation that we solve by CPLEX, a mixed integer problems solver.