Carina Maria Oliveira Pimentel
Centro Algoritmi - Universidade do Minho

Filipe Pereira e Alvelos
Dep. Produção e Sistemas - Universidade do Minho

José Manuel Valério de Carvalho
Dep. Produção e Sistemas - Universidade do Minho

Abstract: In this paper, we present two algorithms for the multi-item capacitated lot-sizing problem with setup times. In this problem we aim at finding a production plan for several items over a number of time periods that minimizes the production, inventory and setup costs and satisfies all demand requirements without exceeding capacity limits. Both of the algorithms are based on the application of the Dantzig-Wolfe principle to a classical model of Mixed Integer Programming. In one case, we apply item decomposition and in the other case we apply a period decomposition. In both cases the reformulated models are stronger than the original one. These reformulated models are solved by branch-and-price, which is a combination of column generation and branch-and-bound methods. We present computational results for a set of instances with different characteristics, to establish comparisons between the two decomposition models. These results are then compared with the classic Mixed Integer Programming formulation solved by the commercial solver Cplex 8.1.

Resumo: Neste artigo apresentam-se dois algoritmos para o problema de lotes de produção multi-artigo capacitado com tempos de preparação. Neste problema pretende-se 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 e respeite restrições de procura e de capacidade. Os algoritmos baseiam-se na aplicação do princípio de decomposição de Dantzig-Wolfe a um modelo clássico de Programação Inteira Mista. Num dos casos é efectuada uma decomposição por artigo e no outro uma decomposição por período. Em ambos os casos os modelos reformulados são mais fortes do que o modelo original. Os modelos reformulados são resolvidos através do método de partição e geração de colunas, que resulta da combinação do método de geração de colunas com o método de partição e avaliação ("branch-and-bound"). 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 clássica resolvida através do Cplex 8.1, um software comercial para Programação Inteira Mista.

Keywords: Production Planning, Mixed Integer Programming, Branch and Price.