Pesquisa Operacional e o Desenvolvimento Sustentável
27 a 30/09/05, Gramado, RS
RESOLVENDO MOCHILAS COMPARTIMENTADAS RESTRITAS Robinson Hoto Universidade Estadual de Londrina, CCE, Departamento de Matemática CEP 86051-970, CP 6001, fone (43) 3371 4150,
[email protected] Campus Universitário, Londrina, PR, Brasil Fernando Spolador Universidade Estadual de Londrina, CCE, Departamento de Computação CEP 86051-970, CP 6001, fone (43) 3371 4150,
[email protected] Campus Universitário, Londrina, PR, Brasil Fabiano Marques Universidade Anhembi Morumbi
[email protected] Campus Centro, São Paulo, SP, Brasil
Resumo O Problema da Mochila Compartimentada (PMC) irrestrita tem sido relatado na literatura para construir padrões de problemas de corte em duas fases. Um procedimento que envolve a resolução de várias mochilas, e uma heurística baseada em limitantes superiores já foi desenvolvida para o problema irrestrito. Existe ainda o caso restrito de uma mochila compartimentada, onde são considerados limites no número de compartimentos e de itens da mochila. Neste trabalho nós sugerimos resolver o problema da mochila compartimentada restrita por meio de uma decomposição e avaliamos um procedimento heurístico. Palavras-chave: mochilas compartimentadas, heurística de decomposição, programação matemática.
Abstract The unbounded Compartmentalized Knapsack Problem (CKP) appears in the literature to build patterns of two phases cut problems. A procedure to the resolution of several knapsacks, and a heuristics based on upper bounds were developed for the unbounded problem. Also, there is the bounded case of the CKP, where limits in the number of compartments and of items of the knapsack are considered. In this work, we suggested solving the bounded compartmentalized knapsack problem with decomposition and we evaluated a heuristic procedure. Keywords: knapsack, compartments, heurístic.
1. Introdução O caso irrestrito de uma mochila compartimentada [03, 04, 09, 10] consiste em construir compartimentos (aqui indexados por k) de capacidades Lk desconhecidas, porém, limitadas entre um valor mínimo e um valor máximo ( Lmin ≤ Lk ≤ Lmax ), no interior de uma mochila de capacidade L conhecida, cujo objetivo é o de maximizar a utilidade. Salienta-se que os itens, de utilidades ui e pesos l i , são separados em agrupamentos N s , s = 1, K , q , e itens de agrupamentos distintos não devem ser alocados num mesmo compartimento. Mochilas compartimentadas são comuns em problemas de corte em duas fases [03, 05, 06], destacamos: corte de bobinas de papel, bobinas de filme plástico e bobinas de aço. Estas mochilas são úteis para construir os particulares padrões destes problemas de corte, veja figura 1.
27 a 30/09/05, Gramado, RS
Pesquisa Operacional e o Desenvolvimento Sustentável
As abordagens formais de mochilas compartimentadas foram apresentadas pela primeira vez por Hoto [03], onde o caso irrestrito foi estudo em detalhes. Atualmente, as pesquisas se concentram no caso restrito e os resultados mais recentes foram obtidos por Marques [10]. Os estudos atuais indicam que os trabalhos futuros abordarão o caso bidimensional, onde serão modelados padrões compartimentados bidimensionais (ver figura 2), que podem ocorrer no corte de placas de madeira, placas de circuito eletrônico, etc. Numa mochila compartimentada, sua capacidade L, as capacidades Lk dos compartimentos e os pesos l i , representam respectivamente no problema do corte de bobinas, o comprimento de uma bobina do estoque, os comprimentos de uma bobina intermediária e os comprimentos dos itens, que em geral são denominados fitas. 3 facas - 2 bobinas intermediárias
bobina
Padrão de Corte Compartimentado corte
3 facas - 2 itens
5 facas - 4 itens
bobinas intermediárias recorte
itens
categoria 1
categoria 2
Figura 1. Padrão compartimentado num problema de corte em duas fases. 4
4
4
4
2
Compartimento 1 4
4
4
4
2
3
1
Padrão Compartimentado Bidimensional
3
1
1
Compartimento 2 3
1
3
1
1
Figura 2. Padrão de corte compartimentado bidimensional. Considere aik o número de itens do tipo i no compartimento k ∈ Vs , onde Vs é o conjunto de índices de compartimentos construídos a partir de itens indexados por N s . Dada a capacidade Lk do
1757
27 a 30/09/05, Gramado, RS
Pesquisa Operacional e o Desenvolvimento Sustentável
compartimento, pode não existir uma combinação linear inteira dos pesos l i que seja exatamente igual a Lk , contudo, caso existam aik ∈ + , tais que ∑ l i aik = Lk denominaremos o compartimento i∈N s
k de viável. Seja ck um custo pelo uso do compartimento k, e yk a variável que informa o número de compartimentos do tipo k ∈ Vs que devem ocorrer na mochila. O modelo de uma mochila compartimentada irrestrita pode ser escrito como: Mochila Compartimentada Irrestrita
⎛ ⎞ ⎛ ⎞ maximizar ∑ ⎜⎜ ( ∑ ui aik ) − ck ⎟⎟ yk + L + ∑ ⎜ ( ∑ ui aik ) − ck ⎟ yk ⎟ k∈V1 ⎝ i∈N1 k∈Vq ⎜ ⎠ ⎝ i∈N q ⎠ sujeito a: ∑ ( ∑ l i aik ) yk + L + ∑ ( ∑ l i aik ) yk ≤ L k∈V1 i∈N1
k∈Vq i∈N q
⎡ yk ⎤ ⎡ yk ⎤ ⎢ ⎥ Lmin ≤ ∑ l i aik ≤ ⎢ ⎥ Lmax , k ∈ Vs , s = 1, ..., q i∈N s ⎢ yk + 1 ⎥ ⎢ yk + 1 ⎥ aik , yk ≥ 0 e inteiros, i ∈ N = N1 ∪ L ∪ N q , k ∈ V = V1 ∪ L ∪ Vq
No modelo anterior ⎡⎢ . ⎤⎥ representa a função teto. Na próxima seção discutiremos restrições adicionais e apresentaremos o modelo de uma mochila compartimentada restrita. 2. Mochilas Compartimentadas Restritas por meio de Decomposição Em algumas aplicações é preciso considerar restrições adicionais [01, 02, 03, 05] na compartimentação de uma mochila, dentre as quais destacamos: 1. a quantidade de cada item i que compõe a mochila deve ser limitada por di : q
∑ ∑ aik yk ≤ di , i ∈ N = N1 ∪ L ∪ N q ;
s =1 k∈Vs
2. a quantidade de itens em cada compartimento k deve ser limitada por F2 − 1 : ∑ aik ≤ F2 − 1 , k ∈V = V1 ∪ L ∪ Vq , s = 1, ..., q; i∈N s
3. a quantidade de compartimentos na mochila deve ser limitada por F1 − 1 : q
∑ ∑ yk ≤ F1 − 1 ;
s =1 k∈Vs
Assim, o caso restrito de uma mochila compartimentada é escrito como: Mochila Compartimentada Restrita
⎛ ⎞ ⎛ ⎞ maximizar ∑ ⎜⎜ ( ∑ ui aik ) − ck ⎟⎟ yk + L + ∑ ⎜ ( ∑ ui aik ) − ck ⎟ yk ⎟ k∈V1 ⎝ i∈N1 k∈Vq ⎜ ⎠ ⎝ i∈N q ⎠ sujeito a: ∑ ( ∑ l i aik ) yk + L + ∑ ( ∑ l i aik ) yk ≤ L k∈V1 i∈N1
k∈Vq i∈N q
∑ yk + L + ∑ yk ≤ F1 − 1
k∈V1
k∈Vq
⎡ yk ⎤ ⎡ yk ⎤ ⎢ ⎥ Lmin ≤ ∑ l i aik ≤ ⎢ ⎥ Lmax , k ∈Vs , s = 1, ..., q i∈N s ⎢ yk + 1 ⎥ ⎢ yk + 1 ⎥
1758
27 a 30/09/05, Gramado, RS
Pesquisa Operacional e o Desenvolvimento Sustentável
∑ aik ≤ F2 − 1 , k ∈V = V1 ∪ L ∪ Vq , s = 1, ..., q
i∈N s
∑ aik yk + L + ∑ aik yk ≤ di , i ∈ N = N1 ∪ L ∪ N q
k∈V1
k∈Vq
aik , yk ≥ 0 e inteiros, i ∈ N = N1 ∪ L ∪ N q , k ∈V = V1 ∪ L ∪ Vq A restrição adicional 1 surge em problemas práticos onde deve ser considerada uma demanda di para cada item i, por exemplo, no corte de bobinas de aço [03], neste caso, para atender a demanda, mais de uma mochila deverá ser resolvida. A restrição adicional 2 decorre de necessidades técnicas como a limitação no número de facas para recortes a serem feitos em bobinas intermediárias de aço [03] (dentre F2 facas, duas são usadas para aparar as bordas das bobinas intermediárias, veja figura 1). A restrição adicional 3 também aparece em virtude de limitações no número de facas, neste caso, para cortes a serem feitos numa bobina de aço do estoque [03] (dentre F1 facas, duas são usadas para aparar as bordas das bobinas, veja figura 1). Digamos que o número total de compartimentos que envolvem a resolução de uma mochila compartimentada seja computável. Neste caso, sugerimos decompor o problema em duas etapas: na primeira são resolvidas várias mochilas que irão construir os compartimentos viáveis, na segunda um Programa Linear Inteiro se encarregará de escolher os compartimentos que deverão compor a mochila. Vejamos o algoritmo proposto: Heurística de Decomposição para Compartimentação Restrita
1. Para s = 1, ..., q, e cada compartimento viável de capacidade Lk ∈{Lmin , Lmin + 1, K, Lmax } com k ∈Vs , resolva a seguinte mochila de variáveis canalizadas, com a restrição adicional ∑ aik ≤ F2 − 1 , i∈N s
que fornecerá o melhor valor de utilidade do compartimento: maximizar vk = ∑ ui aik i∈N s
sujeito a: ∑ l i aik = Lk i∈N s
∑ aik ≤ F2 − 1
i∈N s
0 ≤ aik ≤ di , e inteiros, i ∈ N s 2. Resolva o seguinte Programa Linear Inteiro, obtendo uma solução da compartimentação restrita: maximizar ∑ ( vk − ck ) yk + L + ∑ ( vk − ck ) yk k∈V1
k∈Vq
sujeito a: ∑ aik yk + L + ∑ aik yk ≤ di , i ∈ N = N1 ∪ L ∪ N q k∈V1
k∈Vq
∑ Lk yk + L + ∑ Lk yk ≤ L
k∈V1
k∈Vq
∑ yk + L + ∑ yk ≤ F1 − 1
k∈V1
k∈Vq
yk ≥ 0 e inteiros, k ∈V = V1 ∪ L ∪ Vq
1759
Pesquisa Operacional e o Desenvolvimento Sustentável
27 a 30/09/05, Gramado, RS
A próxima seção traz uma heurística que também é baseada em decomposição, mas, que prevê uma relaxação no modelo. 3. Heurística do Melhor Compartimento Uma alternativa proposta por Marques [09, 10] consiste em reduzir o espaço de busca, construindo o melhor compartimento para “w” capacidades distintas de cada Vs , s = 1, ..., q. Vejamos: Heurística do Melhor Compartimento para w-Capacidades
1. Para s = 1, ..., q, selecionar o melhor compartimento para as “w” capacidades da seguinte forma: 1.1 Faça Lk = Lmax e j = 1 1.2 Enquanto Lk > Lmin e j ≤ w faça 1.2.1 Resolva o seguinte problema da mochila: maximizar vk = ∑ ui aik i∈N s
sujeito a: ∑ l i aik ≤ Lk i∈N s
∑ aik ≤ F2 − 1
i∈N s
0 ≤ aik ≤ di e inteiros, i ∈ N s ⎛ ⎞ 1.2.2 Faça Lk = ⎜ ∑ l i aik ⎟ − 1 ⎜ i∈N ⎟ ⎝ s ⎠ 1.2.3 Faça j = j + 1 2. Seja W o conjunto dos índices dos compartimentos construídos no passo 1, e resolva o seguinte Programa Linear Inteiro: maximizar ∑ ( vk − ck ) yk k∈W
sujeito a: ∑ aik yk ≤ di , i ∈ N k∈W
∑ Lk yk ≤ L
k∈W
∑ yk ≤ F1 − 1
k∈W
yk ≥ 0 e inteiros, k ∈W Em seu trabalho, Marques [10] considerou a existência de uma classe especial V0 de compartimentos, sob os quais não se exige que a respectiva capacidade esteja limitada entre um mínimo ( Lmin ) e um máximo ( Lmax ). Esta postura facilita a tarefa de compartimentar a mochila, além de descaracterizar o problema restrito em seu formato mais geral. Adicionalmente, em algumas situações práticas esta classe de compartimentos pode não existir, de fato, a concepção de uma heurística capaz de compartimentar uma mochila restrita no seu contexto mais amplo é desejável. 4. Mochilas Compartimentadas Restritas com Geração de Colunas No passo 1 do algoritmo de decomposição, no pior caso serão calculadas q( Lmax − Lmin + 1) mochilas, que é o número total de compartimentos a serem considerados, que pode ser excessivamente alto. O cálculo destas mochilas é necessário para obtermos as utilidades vk dos compartimentos para alimentar o objetivo do PLI do passo 2, porém, um limitante superior vk poderia ser calculado
1760
27 a 30/09/05, Gramado, RS
Pesquisa Operacional e o Desenvolvimento Sustentável
rapidamente, entretanto, é preciso conhecer os valores de aik para resolver o PLI. Sugerimos, neste caso, resolver o PLI por meio de geração de colunas [01, 02], onde cada uma delas apresenta a seguinte configuração:
⎡ a1k ⎤ ⎢ M ⎥ ⎢ ⎥ ak = ⎢ ank ⎥ ⎢ ⎥ ⎢ Lk ⎥ ⎢⎣ 1 ⎥⎦
A coluna ak ao lado refere-se ao compartimento k ∈Vs para algum s. Ela informa o quanto de cada um dos n tipos de itens (N = N1 ∪ L ∪ N q = {1, 2, ..., n} ) ocorrem no compartimento ao qual ela faz referência, além de trazer a capacidade do compartimento e a contribuição que será dada no preenchimento da mochila compartimentada, de fato, i ∈ N s e para os itens i ∈ N − N s , aik = 0 .
Temos agora uma nova heurística para a compartimentação restrita de uma mochila: Heurística para Compartimentação Restrita com Geração de Colunas
1. Para s = 1, ..., q, e cada compartimento viável de capacidade Lk ∈{Lmin , Lmin + 1, K, Lmax } com k ∈Vs , calcule um limitante superior vk para o valor da utilidade vk = ∑ ui aik da mochila do passo i∈N s
1 do Algoritmo de Decomposição. 2. Resolva o seguinte Programa Linear Inteiro com Geração de Colunas, obtendo uma solução viável da compartimentação restrita:
maximizar ∑ ( vk − ck ) yk + L + ∑ ( vk − ck ) yk k∈V1
k∈Vq
sujeito a: ∑ aik yk + L + ∑ aik yk ≤ di , i ∈ N = N1 ∪ L ∪ N q k∈V1
k∈Vq
∑ Lk yk + L + ∑ Lk yk ≤ L
k∈V1
k∈Vq
∑ yk + L + ∑ yk ≤ F1 − 1
k∈V1
k∈Vq
yk ≥ 0 e inteiros, k ∈V = V1 ∪ L ∪ Vq No intuito de escrever o problema secundário que gerará colunas, consideraremos π = (π1 , π2 , K, πn , πn+1 , πn + 2 ) o vetor dos multiplicadores Simplex, e wk = vk − ck a utilidade do compartimento de índice k ∈Vs . Ressaltamos que o custo ck é função da coluna ak a ser gerada, além disto, no cálculo do custo relativo da coluna utilizaremos vk , e não vk , vejamos: n
πak − wk = πak − vk + ck = ∑ πi aik + πn +1Lk + πn + 2 − vk + ck = n
i =1 n
i =1
i =1
= ∑ πi aik + πn +1 ( ∑ l i aik ) + πn + 2 − vk + ck n
Seja cik o custo por alocar um item do tipo i no compartimento k, tal que, ck = ∑ cik aik . Uma i =1
n
vez que vk = ∑ ui aik , podemos escrever o custo relativo como: i =1
⎛n ⎞ πak − wk = ⎜ ∑ (πi + πn +1l i − ui + cik )aik ⎟ + πn + 2 = ⎝ i =1 ⎠
1761
27 a 30/09/05, Gramado, RS
Pesquisa Operacional e o Desenvolvimento Sustentável
⎛ ⎞ ⎛ ⎞ = ⎜ ∑ (πi + πn +1l i − ui + cik )aik ⎟ + ⎜ ∑ (πi + πn +1l i − ui + cik )aik ⎟ + πn+ 2 = ⎜ i∈N ⎟ ⎜ i∈N − N ⎟ s ⎝ s ⎠ ⎝ ⎠ ⎛ ⎞ = ⎜ ∑ (πi + πn +1l i − ui + cik )aik ⎟ + πn+ 2 ⎜ i∈N ⎟ ⎝ s ⎠ Considerando que o programa linear do passo 2 é de maximização, sabemos que se πak − wk ≥ 0 para toda coluna k da partição não-básica, então a corrente solução é ótima. Assim, caso ⎞ ⎪⎧⎛ ⎪⎫ o min {πak − wk } = min ⎨⎜ ∑ (πi + πn +1l i − ui + cik )aik ⎟ + πn + 2 ⎬ ≥ 0, então a corrente solução será ⎜ ⎟ k k ⎪ i∈N ⎪⎭ ⎠ ⎩⎝ s ótima. O problema secundário encarregado de gerar uma coluna ak pode ser escrito como: ⎛ ⎞ minimizar ⎜ ∑ (πi + πn +1l i − ui + cik )aik ⎟ + πn + 2 ⎜ i∈N ⎟ ⎝ s ⎠ sujeito a:
ak = [ a1k L ank
Lk 1] ser uma coluna T
que modela o compartimento k ∈ Vs O compartimento k ∈ Vs deve ser tal que: ∑ l i aik = Lk , i∈N s
∑ aik ≤ F2 − 1 e aik ∈
i∈N s
+
para
i ∈ N s . Uma vez que πn + 2 é constante, o gerador de colunas do PLI do passo 2 é mochila com o seguinte formato: maximizar ∑ ( ui − (πi + πn +1l i + cik ) ) aik i∈N s
sujeito a: ∑ l i aik = Lk i∈N s
∑ aik ≤ F2 − 1
i∈N s
aik ≥ 0 e inteiros, i ∈ N s Na próxima seção apresentaremos os resultados numéricos que simulamos entre a heurística de decomposição e a heurística do melhor compartimento para w-capacidades, no caso, efetuamos testes para w = 5, 10, 15, 25 e 50. A compartimentação com geração de colunas encontra-se em fase de testes e não iremos apresentar seus resultados numéricos. 5. Simulações Nesta seção apresentamos um resumo das simulações feitas com o auxílio do pacote Xpress (www.dashoptimization.com), onde comparamos o desempenho da heurística do melhor compartimento para w-capacidades (seção 3) em relação à heurística de decomposição (seção 2). Os dados das simulações foram gerados uniformemente em três categorias da seguinte maneira:
categoria A: l i ∈ [5, 0.25 Lmax ] e ui ∈ [1, l i + 100] categoria B: l i ∈ [5, 0.50 Lmax ] e ui ∈ [1, l i + 100] categoria C: l i ∈ [5, 0.75 Lmax ] e ui ∈ [1, l i + 100] No total foram executadas 1440 mochilas, de modo que, para cada categoria considerou-se Lmin = 100 , Lmax = 300 e L = 900, 1100 e 1200, nas restrições adicionais foram utilizados F1 = 6 , F1 = 12 e di = 5 para cada item i. Os valores escolhidos para cada parâmetro é por se assemelharem aos valores encontrados na prática.
1762
27 a 30/09/05, Gramado, RS
Pesquisa Operacional e o Desenvolvimento Sustentável
As tabelas 1, 2 e 3 apresentam, respectivamente, os dados das simulações das categorias A, B e C. Em cada uma delas a coluna Agrup indica o número de agrupamentos da mochila, a coluna Itens indica o número de itens em cada agrupamento. Em todos os exemplos, a heurística de decomposição obteve soluções de qualidade melhor que a de w-capacidades, desta forma, nas colunas Gap(5), Gap(10), Gap(15), Gap(25) e Gap(50) estão registradas as seguintes diferenças percentuais:
Gap ( w) = 1 −
objetivo(heurística de w − capacidades ) ; w = 5, 10, 15, 25 e 50 objetivo(heurística de decomposição)
Tabela 1. Resultados das simulações para a categoria A. Agrup Itens Gap(5) Gap(10) Gap(25) 5 9,232% 8,6513% 8,1675% 10 3,991% 2,1799% 1,0932% 5 20 10,242% 5,8095% 1,8896% 50 20,920% 12,8510% 3,6386% 5 3,352% 2,6809% 2,2785% 10 2,978% 1,0317% 0,1919% 10 20 6,174% 2,0395% 0,4892% 50 18,167% 7,6631% 0,8696% 5 1,324% 1,0501% 1,0000% 10 1,828% 0,4791% 0,0753% 20 20 5,431% 1,6693% 0,2310% 50 14,392% 5,5631% 0,8462% 5 0,659% 0,5417% 0,5105% 10 1,261% 0,3678% 0,0417% 50 20 2,073% 0,5739% 0,1636% 50 8,621% 3,3660% 0,3359%
Gap(50) 8,1650% 0,6437% 0,8414% 0,3890% 2,1996% 0,0721% 0,0699% 0,0420% 0,9545% 0,0272% 0,0076% 0,0482% 0,5105% 0,0011% 0,0074% 0,0344%
A figura a seguir ilustra o comportamento das heurísticas em relação ao número de agrupamentos e itens, segundo a categoria A. (b) (a)
Gap Gap
Agrup
Agrup
Itens Itens
(c) Gap
Itens
Agrup
Figura 3. (a) Gap para w = 5, (b) Gap para w = 25, (c) Gap para w = 50.
1763
27 a 30/09/05, Gramado, RS
Pesquisa Operacional e o Desenvolvimento Sustentável
Tabela 2. Resultados das simulações para a categoria B. Agrup Itens Gap(5) Gap(10) Gap(25) 5 14,529% 14,0236% 13,9641% 10 6,054% 5,0885% 4,6752% 5 20 5,594% 3,5131% 2,5278% 50 15,122% 6,1509% 1,8288% 5 9,679% 9,1250% 8,9456% 10 2,916% 2,0069% 1,6083% 10 20 4,611% 1,6617% 0,4354% 50 10,507% 3,4737% 0,8324% 5 6,605% 6,2065% 6,1862% 10 1,304% 0,5291% 0,2418% 20 20 2,806% 0,5473% 0,1223% 50 8,643% 2,7751% 0,3536% 5 4,177% 4,0024% 3,9033% 10 0,849% 0,3661% 0,1095% 50 20 1,294% 0,4000% 0,0951% 50 4,706% 1,3052% 0,1921%
Gap(50) 13,9641% 4,6027% 1,4117% 0,6249% 8,8825% 1,6002% 0,0837% 0,1593% 6,1780% 0,2418% 0,0127% 0,0037% 3,8835% 0,0542% 0,0126% 0,0193%
A figura a seguir ilustra o comportamento das heurísticas em relação ao número de agrupamentos e itens, segundo a categoria B.
(b)
(a)
Gap
Gap
Agrup Itens
Agrup Itens
(c) Gap
Agrup Itens
Figura 4. (a) Gap para w = 5, (b) Gap para w = 25, (c) Gap para w = 50.
1764
27 a 30/09/05, Gramado, RS
Pesquisa Operacional e o Desenvolvimento Sustentável
Tabela 3. Resultados das simulações para a categoria C. Agrup Itens Gap(5) Gap(10) Gap(25) 5 16,833% 16,5842% 16,5436% 10 10,227% 9,8850% 9,3569% 5 20 6,210% 4,2583% 3,2364% 50 10,245% 4,5166% 1,4875% 5 11,397% 11,1296% 10,9978% 10 4,359% 3,8747% 3,5617% 10 20 3,696% 1,3455% 0,6975% 50 5,652% 2,1613% 0,4206% 5 7,125% 6,8793% 6,8395% 10 2,785% 2,2621% 2,1327% 20 20 2,820% 1,0535% 0,4157% 50 5,200% 1,2280% 0,1388% 5 5,825% 5,6884% 5,6158% 10 0,723% 0,6435% 0,6258% 50 20 1,117% 0,3854% 0,1302% 50 2,711% 0,8784% 0,1615%
Gap(50) 16,5436% 9,2425% 2,9578% 0,7863% 10,9978% 3,4999% 0,5786% 0,1385% 6,7764% 2,1327% 0,2012% 0,0279% 5,6158% 0,6055% 0,0523% 0,0148%
A figura a seguir ilustra o comportamento das heurísticas em relação ao número de agrupamentos e itens, segundo a categoria C.
(b)
(a)
Gap
Gap
Agrup Itens
Agrup
Itens
(c) Gap
Itens
Agrup
Figura 5. (a) Gap para w = 5, (b) Gap para w = 25, (c) Gap para w = 50.
1765
Pesquisa Operacional e o Desenvolvimento Sustentável
27 a 30/09/05, Gramado, RS
6. Conclusões Pelo que podemos observar, a heurística de decomposição proposta apresenta melhores resultados para os problemas tratados em relação à heurística de w-capacidades. Em particular, esta última exibe um desempenho inferior para mochilas com um número pequeno de agrupamentos e de itens, que melhora sensivelmente à medida que estas variáveis aumentam. Aparentemente, a qualidade das soluções não apresenta melhoria significativa crescendo w de 25 para 50, indicando que o aumento excessivo de w não é recomendável. Para w = 5 os resultados em todas as categorias não foram muito satisfatórios, embora, Marques [10] afirme que o desempenho da heurística seja muito bom. Nós acreditamos que os bons resultados relatados por Marques [10] devem-se pela consideração de uma classe V0 de compartimentos, sob os quais não existe qualquer tipo de restrição. De fato, Marques [10] admite a existência de um agrupamento N 0 , cujos itens podem ser combinados para formar compartimentos de capacidade Lk , k ∈ V0 , sem que seja necessário cumprir a restrição Lmin ≤ Lk ≤ Lmax . Em problemas práticos específicos, como no corte de bobinas de aço sujeitas à laminação a frio, poderíamos efetuar este tipo de relaxação, porém, com respeito ao aspecto teórico do problema, nos parece ser altamente desejável o desenvolvimento de métodos capazes de compartimentar uma mochila restrita no seu contexto mais amplo. Finalizando, a heurística de decomposição parece ser uma alternativa razoável para compartimentações restritas, e em casos onde o problema é intratável o uso de geração de colunas pode ser uma abordagem promissora. Agradecimentos Os autores agradecem ao revisor deste trabalho pelas valiosas sugestões, ao CNPq pelo apoio financeiro e a Dash Optimization que cedeu o pacote Xpress para as simulações. Bibliografia [01] Gilmore, P. C., R. E. Gomory. 1961. A linear programming approach to the cutting stock problem. Operations Research, 9(6), 849-859. [02] Gilmore, P. C., R. E. Gomory. 1963. A Linear Programming Approach to the cutting stock problem, parth II, Operations Research, 11(6), 863-888. [03] Hoto, R. 2001. O problema da mochila compartimentada aplicado no corte de bobinas de aço. Tese de Doutoramento, COPPE/UFRJ, Engenharia de Sistemas e Computação, Rio de Janeiro, RJ, Brasil. [04] Hoto, R., N. Maculan, M. N. Arenales, F. P. Marques. 2002. Um novo procedimento para o cálculo de mochilas compartimentadas. Investigação Operacional - APDIO, 22, 213-234. [05] Hoto, R., N. Maculan, F. P. Marques, M. N. Arenales. 2003. Um problema de corte com padrões compartimentados. Pesquisa Operacional - SOBRAPO, 23, 169-187. [06] Hoto, R., M. N. Arenales, N. Maculan. 2004. The Compartmentalised Knapsack Problem: a case study. Technical Report n. 81, ICMC-USP. [07] Hoto, R., M. N. Arenales, N. Maculan. 2005. The Compartmentalised Knapsack Problem: a case study. European Journal of Operational Research (review). [08] Hoto, R., F. Spolador, N. Maculan. 2005. Rollcut: A System to Plan Cuts of Steel Rolls. Production and Operations Management (submitted). [09] Marques, F. P., M. N. Arenales. 2002. O problema da mochila compartimentada e aplicações. Pesquisa Operacional, 22(3), 285-304. [10] Marques, F. P. 2004. O problema da mochila compartimentada e aplicações. Tese de Doutoramento, ICMC-USP, São Carlos, SP, Brasil. [11] Martello S., P. Toth. 1990. Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons, Chichester, England.
1766
