Algoritmos de partição e geração de colunas
para dimensionamento de lotes de produção
1 Introdução
Neste artigo aborda-se o problema de lotes de produção multi-artigo capacitado com
tempos de preparação (LPMAC). Este problema ocorre no âmbito do planeamento da
produção de médio prazo, e tem como objectivo a determinação de um plano de produção
para vários artigos, habitualmente produtos acabados, ao longo de um determinado
horizonte temporal. O plano resultante deverá satisfazer a procura dos clientes e respeitar
os limites de capacidade e por outro lado minimizar os custos envolvidos. Visto na
perspectiva dos sistemas de planeamento da produção, este problema corresponde ao
plano mestre de produção (Pochet, 2001) e pertence à classe de problemas de lotes de
produção de nível único, multi-artigo, capacitado e com procura determinística e
dinâmica.
Neste trabalho apresentam-se dois métodos de resolução exacta do problema LPMAC
baseados em duas decomposições. Em ambas, parte-se de um modelo clássico de
Programação Inteira Mista (PIM) e aplica-se o princípio de decomposição de Dantzig-Wolfe
(Dantzig and Wolfe, 1960), definindo de diferentes formas os subproblemas. Na primeira
decomposição as restrições de capacidade são mantidas no problema mestre, estando
cada subproblema associado a um artigo. Para esta decomposição foi já desenvolvido um
algoritmo de partição e geração de colunas (Jans, 2002). O nosso trabalho difere na forma
como as regras de partição são compatibilizadas com o subproblema. Na segunda
decomposição as restrições de equilíbrio de stocks são mantidas no problema mestre,
estando cada subproblema associado a um período. Uma contribuição fundamental deste
trabalho é o desenvolvimento de um algoritmo de partição e geração de colunas baseado
nesta decomposição.
Para resolver a relaxação linear dos modelos reformulados utiliza-se o método de
geração de colunas (“column generation”) e para resolver o problema inteiro aplica-se o
método de partição e geração de colunas (“branch and price”).
A motivação para a utilização de métodos de decomposição neste trabalho está
relacionada com a potencial vantagem destes métodos em termos da qualidade dos limites
inferiores que produzem, comparativamente com os limites que se obtêm resolvendo
directamente a formulação clássica de PIM para o LPMAC. Do aumento da qualidade das
soluções, resulta potencialmente a redução dos tempos de resolução do problema. Uma
outra contribuição deste trabalho está associada à comparação experimental entre dois
modelos de decomposição alternativos e entre estes e a formulação clássica resolvida pelo
software comercial Cplex 8.1 (ILOG, 2002).
No que respeita à organização do artigo, na Secção 2 apresenta-se uma revisão de
bibliografia relativa aos modelos e métodos de resolução para o problema. Na Secção 3
descreve-se o problema LPMAC e apresenta-se uma formulação clássica de PIM para este
problema. Na Secção 4 aplicam-se duas decomposições de Dantzig-Wolfe ao problema e
definem-se os problemas mestres e subproblemas associados, bem como a estratégia
usada para a obtenção de soluções inteiras. Na Secção 5 apresentam-se resultados
computacionais para um conjunto de instâncias com diferentes características, que
permitem estabelecer comparações entre os dois modelos de decomposição e um software
comercial de PIM e por último, na Secção 6 apresentam-se as conclusões deste trabalho.
2 Revisão Bibliográfica
O primeiro modelo de Programação Inteira para problemas de lotes de produção deve-se a
Wagner e Whitin (Wagner and Whitin, 1958), que apresentaram para o problema de lotes
de produção de artigo único não capacitado, conhecido na literatura por “ULS Uncapacitated Lot Sizing Problem”, uma formulação de programação matemática e um
algoritmo de programação dinâmica, conhecido como algoritmo de Wagner-Whitin.
Existem na literatura (ver, por exemplo, (Drexl and Kimms, 1997) e (Kuik et al., 1994))
quatro modelos principais de PIM para a classe de problemas de lotes de produção de
nível único, multi-artigo, com procura determinística e dinâmica e capacitado: o modelo
“CLSP – Capacitated Lot Sizing Problem”, o modelo “DLSP – Discrete Lot Sizing and
Scheduling Problem”, o modelo “CSLP – Continuous Setup Lot Sizing Problem” e o modelo
“PLSP – Proportional Lot Sizing and Scheduling Problem”.
Nos problemas de lotes de produção multi-artigo capacitados é habitual estabelecer-se
a distinção entre “small bucket problems“ (SBP) e “big bucket problems” (BBP). Nos BBP
permite-se a produção de vários artigos em cada período de planeamento enquanto que
nos SBP considera-se que em cada período de planeamento apenas um artigo pode ser
produzido. Os SBP permitem modelar as decisões de escalonamento e são adequados
para situações em que existe a necessidade de controlar com rigor a capacidade
consumida na preparação enquanto que os BBP utilizam-se ao nível do dimensionamento
de lotes, onde normalmente se tomam decisões com base em recursos agregados.
O problema CLSP é uma extensão do problema ULS para o caso capacitado e
consequentemente multi-artigo e é um BBP. Os modelos DLSP e CSLP são ambos SBP e
integram as decisões de dimensionamento de lotes com as decisões de escalonamento.
Enquanto que no CSLP, a produção realizada em cada período pode variar, mas é
limitada pela restrição de capacidade, no DLSP, a quantidade produzida em cada período
ou é nula, ou tem de ser igual à capacidade total desse período. O PLSP é também um
SBP e surgiu na sequência do CSLP. Neste modelo permite-se a produção de dois artigos
em cada período com o objectivo de se utilizar toda a capacidade disponível em cada
período.
O problema abordado neste artigo (LPMAC) é um CLSP com tempos de preparação. Os
trabalhos pioneiros, sobre métodos de resolução para o problema LPMAC devem-se a
Manne (Manne, 1958), a Dzielinski e Gomory (Dzielinski and Gomory, 1965) e a Lasdon e
Terjung (Lasdon and Terjung, 1971). Em (Manne, 1958) apresenta-se um modelo
aproximado de programação linear para o problema. Em (Dzielinski and Gomory, 1965) é
aplicada a decomposição de Dantzig-Wolfe ao problema e determina-se o limite inferior do
problema reformulado pelo método de geração de colunas. Em (Lasdon and Terjung,
1971) reformula-se o modelo de programação linear proposto por (Manne, 1958) e resolvese esse novo problema pelo método de geração de colunas. Estas abordagens estão
directamente relacionadas com a decomposição por artigo a apresentar na subsecção 4.1,
sendo de salientar que, tal como a generalidade das abordagens baseadas em relaxação
Lagrangeana ((Chen and Thizy, 1990), (Diaby et al., 1992b), (Merle et al., 1999), (Thizy
and Wassenhove, 1985) e (Trigeiro et al., 1989)), apenas conduzem à obtenção de limites
inferiores e não a uma solução óptima inteira. Uma excepção é o trabalho de (Jans, 2002)
que aplica a decomposição de Dantzig-Wolfe e o método de geração de colunas para
resolver a relaxação linear do problema LPMAC e aplica o método de partição e geração de
colunas para determinar a sua solução óptima inteira. Este trabalho está relacionado com
o trabalho aqui apresentado no âmbito da decomposição por artigo. Aquilo que o
distingue do algoritmo baseado na decomposição por artigo aqui desenvolvido é a
utilização de regras de partição diferentes.
Diaby et al. (Diaby et al., 1992a) abordam o problema LPMAC através de uma
relaxação Lagrangeana alternativa, baseada na relaxação das restrições de equilíbrio de
stocks. Essa abordagem está relacionada com a decomposição por período apresentada
na subsecção 4.2. Embora aqui também se aborde uma decomposição em que os
subproblemas estão associados a períodos, os métodos aplicados na resolução do
problema reformulado, são diferentes. Neste trabalho utiliza-se a decomposição de
Dantzig-Wolfe e técnicas de partição e geração de colunas.
Outros métodos específicos, não directamente relacionados com os apresentados
neste artigo, têm sido aplicados no LPMAC, sendo de salientar métodos de planos de corte
((Barany et al., 1984), (Belvaux and Wolsey, 2000), (Miller et al., 2000) e (Pochet and
Wolsey, 1991)), redefinição de variáveis (Eppen and Martin, 1987) e métodos heurísticos
(Karimi et al., 2003).
3 O problema de lotes de produção multi-artigo capacitado
com tempos de preparação
O planeamento da produção é uma importante área em qualquer organização industrial,
pois permite-lhe lidar de uma forma mais eficiente com as decisões associadas ao fluxo de
materiais e com a utilização de pessoas e equipamentos, entre outros. Em qualquer
sistema de produção existe normalmente um número extremamente elevado de artigos
(ou encomendas) a produzir num conjunto limitado de recursos, aos quais estão
associadas datas de entrega acordadas com os clientes que se podem sobrepor e que
devem ser cumpridas. O planeamento da produção encarrega-se de planear os recursos e
actividades necessárias de modo a permitir a entrega atempada daquilo que é pedido. É
neste contexto que o problema LPMAC se torna relevante. Este problema diz respeito às
decisões tomadas ao nível do plano mestre de produção, no sistema de planeamento da
produção. Em linhas gerais, neste problema procura-se determinar um plano de
produção para um conjunto de artigos finais, faseado no tempo, através da consideração
de um conjunto de períodos de planeamento. Esse plano indica para cada artigo final as
quantidades a produzir desse artigo (que definem um lote) e os períodos em que essas
quantidades devem ser produzidas, atendendo a um conjunto de restrições.
Associado a cada plano de produção, existe um custo que engloba três componentes:
custos de produção, custos de armazenagem e custos de preparação. O custo de
produção pode variar com o artigo e com o período e representa o custo incorrido por
cada unidade produzida. O custo de armazenagem representa o custo que se incorre por
unidade armazenada e por período de armazenagem, sempre que a decisão é a de
produzir antecipadamente para satisfazer procuras de períodos posteriores. Por último, o
custo de preparação representa um custo fixo do lote.
No modelo mais estudado do problema de lotes de produção multi-artigo capacitado
apenas se consideram os custos de preparação, sendo a preparação contabilizada apenas
na função objectivo. Como o tempo de preparação (de máquinas, pessoas, materiais, etc.)
consome parte da capacidade de produção disponível, nesse modelo a capacidade
realmente utilizada é necessariamente subestimada. Para muitos dos autores que
consideram na formulação do problema apenas o custo de preparação, a inclusão deste
tempo no modelo é vista como uma extensão simples. Esta posição é contrariada em
(Trigeiro et al., 1989), onde se mostra que o problema com a consideração dos tempos de
preparação se torna num problema muito mais difícil de resolver. Com vista à modelação
mais precisa do problema, é este último modelo que é abordado neste artigo,
considerando-se directamente no modelo a capacidade gasta com a preparação, ao invés
de esta ser considerada implicitamente no custo de preparação.
Nos parágrafos que se seguem, apresenta-se a formulação clássica de PIM para o
problema LPMAC.
Considerem-se os seguintes conjuntos e parâmetros: I que representa o conjunto de
artigos, indexados por i=1,...,n; J que representa o conjunto de períodos de produção,
indexados por j=1,...,m; pij que representa o custo unitário de produção do artigo i no
período j; qij que representa o custo fixo de preparação do artigo i no período j; hij que
representa o custo unitário de armazenagem do artigo i no final do período j; dij que
representa a procura do artigo i no período j; cj que representa a capacidade de produção
no período j; aij que representa a capacidade consumida na produção de uma unidade do
artigo i no período j e bij que representa a capacidade consumida na preparação do artigo i
no período j.
Considerem-se ainda as seguintes variáveis de decisão: xij que representa a
quantidade a produzir do artigo i no período j; yij que é uma variável binária que assume o
valor 1 se o artigo i é produzido no período j, e assume o valor 0 caso contrário e sij que
representa o nível de inventário do artigo i no final do período j.
Para um determinado horizonte temporal o objectivo é o de determinar as quantidades
a produzir de cada artigo em cada período e as quantidades a armazenar de cada artigo
para períodos posteriores, que minimizam os custos de produção, de preparação e de
armazenagem e que garantem a entrega atempada dos artigos, a ocorrência de uma
preparação sempre que se produza e que a capacidade disponível não é ultrapassada.
Matematicamente podemos concretizar este objectivo através da formulação de PIM que
se apresenta de seguida, que se designa por formulação clássica.
n
m
n
m
n
m
Z C = Min ∑ ∑ p ij x ij + ∑ ∑ q ij y ij + ∑ ∑ h ij s ij
i =1 j =1
i =1 j =1
(C)
i =1 j =1
sujeito a:
x1i = d1i + s1i ,
s
i
j −1
i
j
∀i ∈ I
i
j
i
j
+x =d +s ,
n
n
i =1
i =1
(1)
∀i ∈ I, ∀j ∈ J \ {1}
∑ a ij x ij + ∑ b ij y ij ≤ c j , ∀j ∈ J
⎧⎪c j − b ij m i ⎫⎪ i
x ij ≤ min ⎨
, ∑ dt ⎬y j ,
i
t= j
⎪⎭
⎪⎩ a j
s ij ≥ 0 , ∀i ∈ I, ∀j ∈ J
i
j
x ≥ 0,
∀i ∈ I, ∀j ∈ J
y ij ∈ {0 ,1},
∀i ∈ I, ∀j ∈ J .
(2)
(3)
∀i ∈ I, ∀j ∈ J
(4)
(5)
(6)
(7)
A função objectivo minimiza o custo total. As restrições (1) e (2) são as restrições de
equilíbrio de stocks, que garantem que a procura dos clientes em cada período é satisfeita
e que relacionam os níveis de inventário de um determinado período com os níveis de
inventário do período imediatamente anterior. As restrições (3) são as restrições de
capacidade, que forçam o consumo do recurso com a produção e a preparação a não
exceder a capacidade disponível no período j. As restrições (4) garantem que uma
preparação ocorre se o artigo i for produzido no período j. Estas restrições poderiam ser
substituídas por xij≤Myij, sendo M um valor constante elevado. Deste modo garantir-se-ia
que, sempre que se decidisse produzir o artigo i no período j, deveria ocorrer uma
preparação. Para tornar a formulação mais forte, o coeficiente M pode ser substituído por
c j − b ij
, ou seja, pela quantidade máxima que é possível produzir do artigo i
um lado por
a ij
m
no período j, e por outro lado por ∑ dti , ou seja, pela soma da procura desde o período em
t=j
análise (período j) até ao último período de planeamento. Entre os dois coeficientes
referidos, deve escolher-se aquele que tiver menor valor, uma vez que a quantidade a
produzir do artigo i no período j será limitada por esse valor. As restrições (5) e (6) impõem
a condição de não negatividade das variáveis e as restrições (7) forçam as variáveis de
preparação a assumir valores binários.
A formulação clássica é constituída por 2nm variáveis contínuas, nm variáveis
binárias e m+2nm restrições, sem considerar as condições de integralidade e de não
negatividade. Relembra-se que n representa o número de artigos e m o número de
períodos de planeamento.
4 Decomposições para o problema LPMAC
A qualidade dos limites inferiores de um modelo é um aspecto crucial na resolução de
modelos de PIM. É nesse sentido que se aplica aqui a decomposição de Dantzig-Wolfe
(Dantzig and Wolfe, 1960), já que esta permite a obtenção de formulações mais fortes para
o problema. Do aumento da qualidade do modelo podem resultar melhores intervalos de
integralidade e melhores tempos de resolução dos problemas.
A um problema de PIM podem aplicar-se diferentes decomposições de Dantzig-Wolfe,
de acordo com as restrições que se considerem na definição do subproblema e do
problema mestre. Após a análise da estrutura da formulação clássica do problema
LPMAC, identificaram-se duas decomposições de Dantzig-Wolfe alternativas, que se
estudaram com o objectivo de aferir a sua eficiência e de estabelecer algumas
comparações entre ambas, bem como compará-las com a formulação clássica resolvida
através de um software comercial de PIM. Nas subsecções seguintes apresentam-se as
duas decomposições.
4.1 Decomposição por Artigo
Na formulação clássica do problema LPMAC apresentada na secção anterior, apenas as
restrições de capacidade (3) interligam os artigos a produzir. Se se deixar de considerar
estas restrições, o problema decompõe-se num conjunto de (sub)problemas
independentes, cada um correspondendo a um problema de lotes de produção de artigo
único não capacitado (ULS). Para tirar partido desta estrutura, nesta decomposição, as
restrições (3) definem as restrições de ligação, que ficam no problema mestre. O
subproblema é composto pelas restrições (1)-(2) e (4)-(7) e cada subproblema está
associado ao problema ULS, existindo n subproblemas diferentes.
4.1.1 Problema Mestre
Para a definição do problema mestre, considere-se o conjunto H que representa o
conjunto de planos de produção indexados por k=1,...,t e os parâmetros: β ijk, α ijk e δ ijk. β ijk
assume o valor 1 caso exista uma preparação do artigo i no período j no plano de
produção k, e assume o valor 0 caso contrário; i=1,...,n ; j=1,...,m ; k=1,...t. αijk representa
a quantidade a produzir do artigo i no período j, no plano de produção k; i=1,...,n ;
j=1,...,m ; k=1,...t e δ ijk representa o nível de inventário do artigo i no final do período j, no
plano de produção k; i=1,...,n ; j=1,...,m ; k=1,...t. Considere-se ainda a variável zik que
representa o peso do plano de produção k do artigo i; i=1,...,n ; k=1,...t e os parâmetros e
variáveis de decisão definidas na Secção 3, relativas à formulação clássica.
Da aplicação da decomposição de Dantzig-Wolfe à formulação clássica, resulta um
novo problema, que se designa por problema mestre, que tem associadas variáveis de
decisão que representam o peso dos pontos extremos dos subproblemas (como o poliedro
definido pelas restrições que definem o subproblema é limitado, no problema mestre
existirão apenas pontos extremos). Qualquer solução do problema mestre pode então ser
expressa através de uma combinação convexa e não negativa dos pontos extremos dos
subproblemas. O problema mestre, da decomposição por artigo é do tipo:
n t
⎡m
⎤
Z PMI = Min∑∑ ⎢∑ (q ij β ijk + p ijα ijk + hijδ ijk )zki ⎥
i =1 k =1 ⎣ j =1
⎦
(PMI)
sujeito a:
t
∑ z ki = 1, ∀i ∈ I
(π i )
(8)
k =1
n
t
∑ ∑ ( b ij β ijk + a ij α ijk ) z ki ≤ c j , ∀j ∈ J
i =1 k =1
i
z k ≥ 0 , ∀i ∈ I , ∀k ∈ H .
( μj )
(9)
(10)
Nesta decomposição, a solução dos subproblemas (variáveis de decisão do problema
mestre) correspondem a planos de produção. Para um determinado artigo, cada plano de
produção indica em que períodos se deve produzir e em que quantidades. As variáveis de
decisão zik representam assim a proporção da procura do artigo i que é satisfeita através
do plano de produção k. A função objectivo minimiza a soma dos custos totais. As
restrições (8) são as restrições de convexidade. Existe uma restrição de convexidade para
cada artigo, na qual se força a escolha de uma combinação de planos de produção.
Associada a cada restrição de convexidade está uma variável dual π i. O segundo conjunto
de restrições, conjunto (9), diz respeito às restrições de capacidade. Neste conjunto forçase a que a combinação de planos de produção escolhida respeite a capacidade disponível
em cada período. Este segundo conjunto tem associadas as variáveis duais μj. As
restrições (10) forçam as variáveis de decisão a tomarem valores não negativos.
Em termos de dimensão, o problema PMI, comparativamente com o problema C, tem
um número mais reduzido de restrições. Enquanto que na formulação clássica existem
como vimos anteriormente m+2nm restrições, no problema mestre PMI, este número
reduz-se para n+m. Já em termos de variáveis, o problema PMI, comparativamente com o
problema C, tem um número gigantesco de variáveis, pelo que se utiliza o método de
geração de colunas para o resolver. A ideia subjacente à geração de colunas pode definirse do seguinte modo: em vez de considerarmos todos os planos de produção dos
subproblemas no problema mestre PMI, vamos considerar apenas um conjunto restrito
desses planos, definindo um problema mestre restrito (PMR) e avaliar se existem planos
que não estão actualmente no problema PMI, que caso fossem incluídos no problema
poderiam melhorar o valor da função objectivo. Os planos de produção que se revelarem
atractivos devem ser adicionados ao problema mestre.
Para iniciar o processo iterativo de geração de colunas, o PMR tem de ser um
problema válido, visto ter de fornecer variáveis duais aos subproblemas, para fazer a
avaliação dos planos de produção atractivos. Para garantir a admissibilidade do PMR
incluiu-se nas restrições (8) um conjunto de variáveis artificiais, vi, associadas a cada
n
artigo e na função objectivo o termo ∑ f iv i , onde f i representa uma penalidade elevada,
i =1
que torna qualquer solução com variáveis artificiais positivas de pior qualidade que uma
solução óptima em termos das variáveis zik. Foram ainda incluídos no primeiro PMR um
subconjunto de planos de produção do conjunto de todos os planos de produção dos n
subproblemas.
Para recuperar a solução do problema C, a partir de uma solução do problema PMI
basta aplicar as expressões:
x ij =
y ij =
t
∑ α ijk z ki
(11)
k =1
t
∑ β ijk z ki
(12)
k =1
Conhecido o valor das variáveis xij, através das equações (1) e (2), é imediata a
determinação do valor das variáveis de decisão auxiliares sij.
4.1.2 Subproblemas
Se μj representar o vector de variáveis duais associado ao conjunto de restrições de
capacidade (9) e π i a variável dual associada à restrição i do conjunto de restrições de
convexidade (8), os n subproblemas a resolver são definidos por:
m
Z SPI = Min ∑ p ij x ij +
j =1
m
m
m
m
j =1
j =1
j =1
j =1
∑ q ij y ij + ∑ h ij s ij − ∑ ( b ij y ij ) μ j − ∑ ( a ij x ij ) μ j − π i (SPI)
sujeito a:
x1i = d1i + s1i ,
s ij −1 + x ij = d ij + s ij ,
(13)
∀j ∈ J \ {1}
⎧⎪c j − b ij m i ⎫⎪ i
x ij ≤ min ⎨
, ∑ dt ⎬y j ,
i
t=j
⎪⎭
⎪⎩ a j
x ij ≥ 0 ,
∀j ∈ J
∀j ∈ J
(14)
(15)
(16)
y ij ∈ {0 ,1}, ∀j ∈ J
(17)
s ij ≥ 0 ,
(18)
∀j ∈ J .
Para resolver os subproblemas da decomposição por artigo, pode utilizar-se o
algoritmo de programação dinâmica proposto por (Wagner and Whitin, 1958), que resolve
em tempo polinomial o problema. Cada subproblema tem associados 2m-1 planos de
produção e a solução óptima de cada um dos n subproblemas representa um plano de
produção relativo ao artigo i. Como no subproblema não existem restrições de capacidade,
em todos os planos de produção, quando se toma a decisão de produzir num determinado
período, produz-se para satisfazer a procura de um número inteiro de períodos. Estes
planos são conhecidos por planos de Wagner-Whitin.
Durante o processo de geração de colunas, enquanto o valor óptimo da função
objectivo do subproblema (custo reduzido associado a um plano de produção) for menor
do que zero, deverá adicionar-se ao problema mestre uma nova coluna ou variável, que
corresponde à solução do subproblema (plano de produção). Em cada iteração, podem
portanto ser adicionadas ao problema mestre n novas colunas, caso cada subproblema
contribua com uma coluna atractiva.
4.2 Decomposição por Período
Nesta subsecção aborda-se uma decomposição alternativa à decomposição por artigo, que
consiste em deixar no problema mestre as restrições de equilíbrio de stocks (1) e (2) e em
passar para o subproblema as restrições (3), (4), (6) e (7). Com esta decomposição os
subproblemas passam a estar associados aos períodos de planeamento. No nosso melhor
conhecimento, esta decomposição foi apenas estudada por (Diaby et al., 1992a), que
utilizaram a relaxação Lagrangeana e resolveram o problema reformulado pelo método do
subgradiente. Neste trabalho, aplica-se a decomposição de Dantzig-Wolfe e a resolução do
problema reformulado é feita pelo método de geração de colunas, que quando combinado
com o método de partição e avaliação, permite ainda a obtenção de soluções óptimas
inteiras.
4.2.1 Problema Mestre
Para definir o problema mestre da decomposição por período, considerem-se os
parâmetros e variáveis da formulação clássica apresentada na Secção 3, o conjunto H que
representa o conjunto de padrões de produção indexados por k=1,...,t e os parâmetros:
β ijk e α ijk. β ijk assume o valor 1 caso exista uma preparação no período j do artigo i, no
padrão de produção k e assume o valor 0 caso contrário; i=1,...,n ; j=1,...,m ; k=1,...t e αijk
representa a quantidade a produzir no período j do artigo i, no padrão de produção k;
i=1,...,n ; j=1,...,m ; k=1,...t. Considere-se também a variável de decisão zjk que representa o
peso do padrão de produção k do período j; j=1,...,m ; k=1,...t.
O problema mestre que na decomposição por período resulta da aplicação da
decomposição de Dantzig-Wolfe, é tal como o da decomposição por artigo constituído por
variáveis de decisão que representam pesos de pontos extremos dos subproblemas, pois
neste caso o poliedro definido pelas restrições do subproblema é também um conjunto
limitado . A diferença é que agora as variáveis representam padrões de produção que
estão associados a um período. Cada padrão de produção indica para um determinado
período a quantidade que deve ser produzida do “mix” de artigos a processar.
A solução da relaxação linear do problema LPMAC, quando se aplica a decomposição
por período, pode ser obtida resolvendo o seguinte problema mestre, aqui designado por
PMJ:
n m
m t
n
Z PMJ = Min ∑ ∑ h ij s ij + ∑ ∑ ⎡⎢∑ (q ij β ijk + p ijα ijk )z jk ⎤⎥
i =1 j =1
j =1 k =1 ⎣ i =1
⎦
(PMJ)
sujeito a:
t
∑ z jk ≤ 1, ∀j ∈ J
k =1
(π j )
t
∑ α1ik z1k = d1i + s1i , ∀i ∈ I
k =1
s ij −1 +
(19)
( μ1i )
(20)
t
∑ α ijk z jk = d ij + s ij , ∀i ∈ I, ∀j ∈ J \ {1} ( μ ij )
(21)
k =1
s ij ≥ 0 ,
z jk ≥ 0 ,
∀i ∈ I, ∀j ∈ J
(22)
∀j ∈ J, ∀k ∈ H .
(23)
As variáveis de decisão zjk podem ser vistas como a proporção da procura do período j
que é satisfeita pelo padrão de produção k. A função objectivo do problema mestre
minimiza a soma dos custos totais. As restrições (19) representam as restrições de
convexidade. Existe uma restrição de convexidade associada a cada período na qual se
força a escolha de uma combinação de padrões de produção. Associada a cada restrição
de convexidade está uma variável dual πj. No caso da decomposição por período, as
restrições de convexidade podem ser escritas como uma desigualdade do tipo ≤, em vez da
sua forma habitual, na qual estas restrições são escritas como uma igualdade. Esta
alteração é possível, devido ao espaço de soluções admissíveis do subproblema SPJ (que
será definido na subsecção seguinte) incluir a origem. Com esta modificação, excluem-se
do problema mestre os padrões de produção que indiquem que para um determinado
período nada deve ser produzido. O conjunto de restrições (20) e (21), são as restrições de
equilíbrio de stocks. Neste conjunto força-se a que a combinação de padrões de produção
escolhida respeite a procura de cada artigo em cada período. Este conjunto tem
associadas as variáveis duais μ ij . As restrições (22) e (23) impõem a condição de não
negatividade das variáveis de inventário e das variáveis de peso, respectivamente.
Quanto à dimensão, o problema PMJ tem m+nm restrições. Nesta decomposição o
número de variáveis do problema mestre é extremamente elevado, pelo que também se
recorre ao método de geração de colunas para resolver o problema PMJ.
Devido ao conjunto de restrições de equilíbrio de stocks do primeiro período de
planeamento, restrições (20), o primeiro PMR pode não ser válido. Para o validar,
associou-se uma variável artificial, vi, a cada restrição deste conjunto. Estas variáveis
podem ser interpretadas como sendo o inventário existente no início do primeiro período
n
de planeamento. À função objectivo, adicionou-se o termo ∑ f iv i , onde f
i
é um escalar
i =1
com um valor muito elevado, para garantir que qualquer solução com variáveis artificiais
positivas é pior que uma solução óptima em termos das variáveis de peso zjk.
A solução do problema C, pode ser obtida por aplicação das seguintes expressões:
x ij =
y ij =
t
∑ α ijk z jk
(24)
k =1
t
∑ β ijk z jk
(25)
k =1
4.2.2 Subproblemas
Cada um dos m subproblemas da decomposição por período é definido por:
n
n
n
i =1
i =1
i =1
Z SPJ = Min ∑ p ij x ij + ∑ q ij y ij − ∑ x ij μ ij − π j
(SPJ)
sujeito a:
n
n
i =1
i =1
∑ a ij x ij + ∑ b ij y ij ≤ c j ,
⎧⎪c j − b ij m i ⎫⎪ i
x ij ≤ min ⎨
, ∑ dt ⎬y j ,
i
t=j
⎪⎩ a j
⎪⎭
x ij ≥ 0 ,
∀i ∈ I
y ij , ∈ {0 , 1} ∀i ∈ I ,
(26)
∀i ∈ I
(27)
(28)
(29)
onde πj representa a variável dual associada à restrição j do conjunto de restrições de
convexidade (19) e μ ij representa o vector de variáveis duais associado ao conjunto de
restrições de equilíbrio de stocks (conjunto de restrições (20) e (21)).
A função objectivo de cada subproblema representa o custo reduzido associado ao
padrão de produção j. No processo de geração de colunas, enquanto os custos reduzidos
dos subproblemas forem menores do que zero, deverão adicionar-se ao problema mestre
restrito os padrões de produção correspondentes.
Os subproblemas da decomposição por período estão associados ao problema da
mochila contínuo com preparações (“continuous knapsack problem with setups”). Este
problema foi recentemente abordado em (Perrot and Vanderbeck, 2004), onde é
apresentado um algoritmo de programação dinâmica e um algoritmo de partição e
avaliação para o problema.
4.3 Pesquisa de Soluções Inteiras
Ao resolver os problemas mestres definidos nas subsecções 4.1.1 e 4.2.1 por geração de
colunas, estamos a determinar a solução óptima da relaxação linear dos modelos de
decomposição. O valor da solução que se obtém representa portanto um limite inferior
para o valor do óptimo inteiro. Como os subproblemas que resultam de ambos os modelos
de decomposição não possuem a propriedade da integralidade (Geoffrion, 1974), o limite
inferior que se obtém na resolução dos problemas mestres é melhor ou igual que o obtido
pela solução da relaxação linear da formulação clássica.
Para recuperarmos uma solução expressa em termos das variáveis de peso para uma
solução em termos das variáveis originais da formulação clássica, basta aplicarmos as
expressões (11) e (12) no caso da decomposição por artigo e as expressões (24) e (25) caso
se trate da decomposição por período. Se, nessa solução, existirem variáveis de
preparação, as variáveis yij, que não sejam binárias, esta solução não corresponde à
solução óptima do problema C. Para determinar a solução óptima inteira do problema
deverá então recorrer-se ao método de partição e geração de colunas. Este método
combina o método de partição e avaliação com o método de geração de colunas (Barnhart
et al., 1998) e assenta na resolução de um problema mestre em cada nodo da árvore de
pesquisa através do método de geração de colunas.
A estratégia de partição usada neste trabalho, consiste em adicionar ao problema
mestre restrições de partição que forçam as variáveis originais de preparação a assumir
valores binários. Esta estratégia tem a vantagem de ser geral, podendo ser aplicada a
qualquer tipo de problema, garantindo a preservação da estrutura do subproblema nos
nodos da árvore de pesquisa.
Quando a solução da raiz da árvore de pesquisa, ou a solução de um determinado
nodo não é inteira, e existe interesse em explorá-lo, devem adicionar-se dois novos nodos
ao problema. Cada um destes nodos passa a definir um “novo” problema, no qual para
além de se considerar o problema mestre actual, se considera também uma das restrições
de partição, a seguir apresentadas:
∑ β ijk z ki = 0 ou ∑ β ijk z ki = 1
se decomposição por artigo
∑ β ijk z jk = 0 ou ∑ β ijk z jk = 1
se decomposição por período
k ∈H
k ∈H
k ∈H
k ∈H
onde H representa o conjunto de planos de produção (se decomposição por artigo) ou de
padrões de produção (se decomposição por período) que fazem parte desse problema
mestre actual.
Após a adição da restrição de partição, para que os custos reduzidos dos
subproblemas a resolver no processo de geração de colunas sejam correctamente
determinados, deve alterar-se a função objectivo desses subproblemas, na qual se deve
passar a considerar a variável dual associada à restrição de partição que foi adicionada.
No caso da decomposição por artigo, se ηij representar a variável dual associada à
restrição de partição que foi adicionada ao nodo, na função objectivo de cada um dos n
subproblemas, apresentada na subsecção 4.1.2, deve subtrair-se o termo seguinte:
m
∑ y ijη ij . Se se tratar da decomposição por período e se for τ ij a variável dual associada à
j =1
restrição de partição, na função objectivo de cada um dos m subproblemas apresentados
n
na subsecção 4.2.2 deve subtrair-se o termo: ∑ y ijτ ij .
i =1
5 Resultados Computacionais
Com o objectivo de avaliar e comparar o desempenho de ambos os algoritmos de partição
e geração de colunas e de os comparar com a formulação clássica resolvida pelo software
Cplex 8.1 realizaram-se testes computacionais, cujos resultados se apresentam neste
capítulo. Para medir o desempenho de cada um dos três métodos, utilizaram-se os
seguintes critérios: qualidade dos limites inferiores (medida através do cálculo dos
intervalos de integralidade) e eficiência. Os resultados computacionais
foram obtidos através da resolução de um conjunto de 180 instâncias usadas por (Trigeiro
et al., 1989), as quais foram geradas com base na variação de quatro características:
variabilidade da procura, capacidade utilizada, periodicidade de encomenda (“time
between orders”) e tempo de preparação. Na mesma referência podem encontrar-se
informações pormenorizadas acerca da forma como estas instâncias foram obtidas. Todas
as instâncias consideram 10 artigos e 20 períodos de planeamento.
Em ambos os modelos de decomposição, os problemas mestres quer da raiz da árvore
de pesquisa quer de qualquer nodo da árvore, são resolvidos até à optimalidade pelo
algoritmo dual do simplex, através do Cplex. Os subproblemas da decomposição por
artigo e da decomposição por período são também resolvidos até à optimalidade, usando o
Cplex. Os primeiros problemas mestres restritos são definidos através de um conjunto de
variáveis artificiais que asseguram a admissibilidade dos mesmos e de um subconjunto
de planos de produção no caso da decomposição por artigo e em cada iteração do método
de geração de colunas resolvem-se todos os subproblemas até optimalidade e todas as
colunas atractivas são adicionadas ao problema mestre restrito.
No método de partição e geração de colunas, quer na decomposição por artigo, quer
na decomposição por período, fizeram-se alguns testes preliminares onde se testaram
duas estratégias de pesquisa da árvore. Na primeira estratégia utilizou-se a pesquisa
primeiro em profundidade e deu-se prioridade ao nodo que tem associado a restrição de
partição do tipo ≥ e na regra de partição utilizou-se uma estratégia baseada na escolha da
variável com parte fraccionária mais próxima de 1. Na segunda estratégia de pesquisa da
árvore, também se utilizou a pesquisa primeiro em profundidade, mas deu-se prioridade
ao nodo de pesquisa que tem associada a restrição de partição do tipo ≤ e na regra de
partição utilizou-se uma estratégia baseada na escolha da variável com parte fraccionária
mais próxima de 0. Como a primeira estratégia foi a que produziu melhores resultados,
na realização dos testes que aqui se apresentam foi esta a estratégia seguida.
Os algoritmos de partição e geração de colunas foram implementados em C++
utilizando a ferramenta ADDing − Automatic Dantzig-Wolfe Decomposition for INteger
column Generation (Alvelos, 2005). Os testes foram realizados num computador pessoal
com um processador Pentium 4 a 2 GHz e com 1 GB de memória.
Na tabela 1 apresentam-se os tempos de resolução da relaxação linear dos dois
modelos de decomposição e da formulação clássica resolvida pelo Cplex. Esses tempos
estão expressos em segundos e referem-se aos tempos médios de resolução do conjunto
de 180 instâncias.
Na resolução do problema inteiro, limitou-se o tempo de resolução a 3600 segundos.
Usando a decomposição por período, não se consegue atingir a solução óptima em
nenhuma das 180 instâncias no tempo limite estabelecido, encontrando-se apenas
soluções incumbentes. Em 109 das 180 instâncias testadas não se consegue determinar
a solução óptima usando quer a decomposição por artigo, quer o Cplex. Existem portanto
71 instâncias que são resolvidas até à optimalidade, considerando o Cplex e/ou a
decomposição por artigo. Desta análise concluí-se que em cerca de 40% das instâncias
testadas se consegue determinar a solução óptima do problema em menos de uma hora.
Com o Cplex consegue-se determinar a solução óptima de 61 instâncias num tempo
médio de 307.90 segundos enquanto que com a decomposição por artigo se consegue
determinar a solução óptima de 59 instâncias, num tempo médio de 381.90 segundos.
Já em termos de soluções incumbentes, em 49 das 109 instâncias em que não se
consegue determinar a solução óptima o Cplex apresenta melhores incumbentes que os
modelos de decomposição. Nas restantes 60 instâncias, é a decomposição por artigo que
apresenta as melhores soluções incumbentes. As soluções incumbentes da decomposição
por período são sempre piores que as soluções incumbentes da decomposição por artigo e
do Cplex. Na tabela 2 sumariam-se estes resultados. A segunda coluna da tabela refere-se
ao número de instâncias que são resolvidas até à optimalidade por cada um dos métodos
e na terceira coluna apresentam-se os tempos médios de resolução dessas instâncias. Na
quarta coluna apresentam-se os intervalos médios de integralidade ou GAP’s médios de
integralidade em percentagem. Os GAP’s foram determinados através da seguinte
Z − Z LI
, representando ZPI o valor da solução óptima inteira e ZLI o valor do
expressão: PI
Z PI
limite inferior (o valor da solução óptima do nodo da raiz da árvore) de cada um dos três
métodos. Nesta análise consideraram-se as 71 instâncias para as quais se obteve a
solução óptima inteira. Por último, na quinta coluna quantifica-se o número de
instâncias, do conjunto das 109 que não são resolvidas até à optimalidade, em que cada
método apresenta melhores soluções incumbentes.
Analisando os resultados da tabela 1, conclui-se que na decomposição por artigo os
tempos médios de resolução da relaxação linear são bastante inferiores aos obtidos com a
decomposição por período. Entre a decomposição por artigo e o Cplex, a diferença não é
tão significativa, mas o Cplex consegue resolver a relaxação mais rapidamente. A
diferença de tempos médios entre a decomposição por artigo e a decomposição por
período ronda os 19.50 segundos e entre a decomposição por artigo e o Cplex ronda os 2
segundos. Da análise da tabela 2 depreende-se que em termos do número de instâncias
resolvidas até à optimalidade, a diferença entre a decomposição por artigo e a
decomposição por período é enorme. Entre a decomposição por artigo e o Cplex considerase que essa diferença não é significativa. Quanto aos tempos médios de resolução do
problema inteiro, como na decomposição por período não se obtém nenhuma solução
óptima, nesta análise apenas se consideraram os tempos médios de resolução do
conjunto de 59 instâncias da decomposição por artigo e do conjunto de 61 instâncias da
decomposição por período. O Cplex é o método que em média apresenta melhores tempos
de resolução, não sendo contudo significativa a diferença entre os tempos médios deste
método e os tempos médios da decomposição por artigo. Essa diferença é de 74 segundos.
Quanto aos GAP’s de integralidade, esta é para nós uma medida de desempenho
fundamental, pois permite-nos aferir acerca da qualidade dos modelos desenvolvidos,
independentemente da implementação utilizada para os resolver. O modelo da
decomposição por artigo é claramente mais forte que o modelo da decomposição por
período e que a formulação clássica. Comparando o GAP da decomposição por período
com o do Cplex, concluí-se que são ambos semelhantes, embora o GAP da decomposição
por período seja um pouco melhor. Para além da análise dos GAP’s, a análise das
melhores soluções incumbentes, permite-nos também atestar a qualidade das soluções.
Quanto mais baixo for o valor da solução incumbente mais próximo estamos do valor da
solução óptima inteira. Para o conjunto das 109 instâncias, para as quais não se obtém a
solução óptima inteira em 3600 segundos, compararam-se as soluções incumbentes
obtidas pelos três métodos na altura em que o tempo limite foi atingido. Dessa análise
verificou-se que a decomposição por artigo é a que apresenta para um maior número de
instâncias as melhores soluções incumbentes.
Depois de efectuada a análise geral dos resultados obtidos na resolução do conjunto
das 180 instâncias, fez-se a análise dos resultados atendendo à variação dos quatro
parâmetros das instâncias de teste. Nesta fase consideraram-se como medidas de
desempenho os tempos médios de resolução do problema inteiro e os GAP’s médios de
integralidade. Para o cálculo dos GAP’s de integralidade consideraram-se as 71 instâncias
para as quais se obteve a solução óptima e consideraram-se os três métodos de resolução.
Para o cálculo dos tempos médios de resolução apenas se considerou a decomposição por
artigo e o Cplex, já que na decomposição por período não se obteve a solução óptima
inteira de nenhuma das instâncias. No caso da decomposição por artigo utilizaram-se as
59 instâncias para as quais se obteve a solução óptima e para o Cplex, utilizaram-se as
61 instâncias que são resolvidas até à optimalidade com este método. Os resultados que
se apresentam na tabela 3 e na tabela 4 referem-se a esta análise.
Da análise da tabela 3 verifica-se que quando a utilização de capacidade é alta, há
poucas instâncias que são resolvidas e que à medida que aumenta a utilização de
capacidade o GAP quer da decomposição por período quer do Cplex baixa, sendo que em
relação à decomposição por artigo à medida que aumenta a utilização de capacidade,
também aumenta o GAP. O efeito no GAP, quando se varia a procura e quando se varia o
tempo de preparação, não é significativo se se considerar a decomposição por período e o
Cplex. Na decomposição por artigo as diferenças são mais acentuadas, verificando-se que
a passagem de um nível para o nível imediatamente superior, leva a um aumento do GAP.
Em relação à variação na periodicidade de encomenda, pode dizer-se que à medida que
aumenta a periodicidade de encomenda aumenta significativamente a dificuldade do
problema, sendo esse aumento mais acentuado para a decomposição por período e para o
Cplex. Esta análise só pode ser baseada nas instâncias com periodicidade baixa e média,
já que em nenhuma das instâncias com periodicidade alta se conseguiu obter resultados.
Por último, salienta-se que relativamente aos GAP’s de integralidade em termos gerais o
comportamento da decomposição por período e do Cplex é muito idêntico, face às
variações nos parâmetros.
Na análise dos tempos de resolução do problema inteiro, deverá notar-se que os
resultados apresentados na tabela 4 não dizem respeito exactamente às mesmas
instâncias, pelo que as comparações que se apresentam de seguida poderão estar
enviesadas. Idealmente deveriam considerar-se as mesmas instâncias, mas nesse caso a
amostra seria relativamente baixa.
Quando a utilização de capacidade é alta, há poucas instâncias que são resolvidas até
à optimalidade e quando a periodicidade de encomenda é alta nenhum dos métodos
consegue encontrar soluções óptimas inteiras. Verifica-se que os tempos médios de
resolução aumentam significativamente quando se passa de uma utilização de capacidade
baixa para média, assim como quando se passa da variabilidade da procura média para a
alta e quando se passa da periodicidade de encomenda baixa para a média. Em termos
gerais o desempenho da decomposição por artigo é idêntico ao do Cplex, sendo de realçar
que nas instâncias com variabilidade da procura média e com periodicidade de
encomenda média, os tempos médios de resolução são mais baixos na decomposição por
artigo comparativamente com os tempos do Cplex.
6 Conclusões
Neste artigo apresentaram-se e compararam-se dois algoritmos de partição e geração de
colunas para a obtenção de soluções óptimas inteiras do problema de lotes de produção
multi-artigo capacitado com tempos de preparação. Ambos os algoritmos baseiam-se na
aplicação da decomposição de Dantzig-Wolfe a uma formulação de Programação Inteira
Mista clássica para o problema. Num deles, os subproblemas estão associados a períodos
e, no outro, os subproblemas estão associados aos artigos.
O modelo de decomposição por artigo permite obter intervalos de integralidade muito
baixos, o que nos leva a considerar que existiriam vantagens em investir-se no aumento
da eficiência deste modelo em abordagens futuras, nomeadamente ao nível do algoritmo
de partição e geração de colunas. Certamente os tempos de resolução poderiam ser
reduzidos através da implementação do algoritmo de programação dinâmica proposto por
Wagner-Whitin, para resolver os subproblemas e através da implementação de heurísticas
para a obtenção de soluções admissíveis de melhor qualidade, quer na raiz da árvore de
pesquisa quer nos nodos da árvore.
Para a pesquisa de soluções inteiras propôs-se um esquema de partição baseado nas
variáveis originais de preparação, no qual se adicionam restrições de partição ao
problema mestre, garantindo-se deste modo a preservação da estrutura do subproblema.
Este esquema tem a vantagem de ser geral e de poder ser aplicado a qualquer tipo de
problema de Programação Inteira ou de Programação Inteira Mista.
Os testes computacionais realizados mostraram que a decomposição por artigo tem
um desempenho claramente superior ao da decomposição por período e que entre a
decomposição por artigo e a formulação clássica resolvida pelo Cplex a vantagem da
decomposição por artigo em termos de intervalos de integralidade é significativa. Já em
termos de tempos de resolução ambos os métodos têm um desempenho similar, embora
com o Cplex 8.1 se obtenham em média resultados um pouco melhores.
