Um problema de corte com padrões compartimentados
1. Introdução
Padrões de corte compartimentados são comuns em empresas do ramo da metalurgia
que necessitam efetuar laminação a frio do aço que é acondicionado em bobinas.
Estas bobinas do estoque são identificadas pelo seu "peso" (varia de
12.000 Kg a 13.500 Kg), sua largura (varia de 1000 mm a 1300 mm), espessura do
aço (varia de 0,90 mm a 6,30 mm) e pelo teor de carbono na liga, que
determinará a dureza do aço. A demanda é composta por fitas de especificações
determinadas (largura, espessura e tipo de aço) que devem ser cortadas de uma
bobina do estoque e, devido a razões técnicas, a maioria destas fitas precisam
ter a espessura do aço reduzida por meio de laminação. A laminação é feita com
"cilindros de laminação" que efetuam pressão sobre a lâmina de aço em
temperatura ambiente (laminação a frio, figura_1). Devido a limitações
técnicas, a máquina de laminação não pode processar a largura total de uma
bobina do estoque, além do mais, existem vários conjuntos de fitas com reduções
de espessura de aço distintas, de modo que, devem ser definidas bobinas
intermediárias com larguras admissíveis pelo laminador e compostas de fitas
compatíveis entre si. Estas bobinas intermediárias são cortadas de uma bobina
em estoque e, delas são recortadas as fitas, de modo que, os padrões de corte
devem ser estruturados em compartimentos, cujos tamanhos devem ser
determinados.
Na figura_2 ilustramos o processo de corte com um padrão compartimentado.
Suponha que o aço da bobina tenha 1,20 mm de espessura e que as fitas da
primeira bobina intermediária precisem ser laminadas a uma espessura de 1,00
mm, enquanto, as da segunda bobina intermediária devem ser laminadas a uma
espessura de 0,90 mm, ou numa outra situação não serem laminadas.
Por razões técnicas, o número de cortes numa bobina do estoque e de recortes
numa bobina intermediária é limitado, além do mais, nas bobinas do estoque e
nas bobinas intermediárias existem perdas técnicas intrínsecas.
Em síntese, os aspectos peculiares aqui citados apontam para um problema
complexo e que foge do contexto clássico, até porque, o esquema de corte se dá
em duas fases. Além disto, a necessidade do processo de laminação induz padrões
de corte nada evidentes, visto que, nem todas as fitas são compatíveis entre
si.
2. Padrões de Corte Compartimentados
Um padrão de corte é denominado compartimentado quando é necessário definir
compartimentos (objetos intermediários) a serem cortados dos objetos, dos quais
posteriormente serão recortados os itens. Este tipo de padrão ocorre quando os
itens necessitam sofrer processos técnicos distintos, ou máquinas da linha de
produção não comportam as dimensões dos objetos em estoque.
Um exemplo é o da indústria de móveis, onde os itens devem passar por processos
técnicos distintos e as máquinas da linha de produção não comportam as
dimensões originais das placas de madeira. Assim, há a necessidade de construir
padrões compartimentos (figura_3), onde cada um deles corresponde a uma placa
intermediária de dimensões menores que a da placa original.
O corte de bobinas de aço é um exemplo onde aparecem padrões compartimentados
unidimensionais, pois, alguns itens devem sofrer laminações distintas, neste
caso é preciso definir compartimentos que são denominados bobinas
intermediárias (figura_2).
A grande dificuldade na construção de um padrão compartimentado, unidimensional
ou bibdimensional, está no fato de não conhecermos as dimensões dos
compartimentos que devem compor o padrão, ao mesmo tempo, é preciso determinar
quais compartimentos e em quais quantidades constituirão o padrão. Hoto (2001)
e Hoto et al.(1996, 1996, 1998) descrevem padrões compartimentados
unidimensionais por meio de um Problema da Mochila Compartimentada (PMC) (Hoto
et al., 1999, 2002), que é uma nova variação do clássico Problema da Mochila.
Marques (2000) e Marques & Arenales (2000) estudaram o caso restrito do PMC
e apresentaram alguns procedimentos heurísticos. Na próxima seção
apresentaremos o modelo de geração de colunas que escrevemos para o corte de
bobinas de aço, bem como uma formulação matemática da mochila compartimentada
para gerar padrões compartimentados unidimensionais.
3. Uma abordagem de Geração de Colunas no Corte de Bobinas de Aço
Na resolução do Problema de Corte de Bobinas de Aço (PCBA) sujeitas a laminação
adotamos a Técnica de Geração de Colunas de Gilmore-Gomory (1961, 1963). Nosso
objetivo consiste em minimizar os custos associados às perdas lineares de aço
numa bobina, e custos por utilização de compartimentos, além de examinar as
limitações do estoque. Considere as definições dadas a seguir:
Dados das Bobinas
* m total de tipos de bobinas em estoque;
* Pr "peso" (a massa) da bobina (objeto) r=1,...,m (Kg);
* Lr largura da bobina (objeto) r=1,...,m (mm);
* er disponibilidade da bobina (objeto) r=1...,m (unidades de bobinas);
* custo linear do aço da bobina
(objeto) r=1,...,m ($/mm);
* <formula/> perda linear de aço na bobina
(objeto) r=1,...,m, segundo o padrão compartimentado j (mm);
* S1 perda intrínseca na borda de uma bobina (mm);
Dados das Fitas
* n total de tipos de itens;
* <formula/>1 largura da fita (item)
i=1,....,n (mm);
* di demanda solicitada da fita (item) i=1,....,n (Kg);
* <formula/> número de fitas (itens) tipo i na
bobina r, segundo o padrão compartimentado j (unidades de fitas);
Dados das Bobinas Intermediárias
* <formula/> custo operacional da bobina
intermediária (compartimento) h na bobina r, segundo o padrão
compartimentado j ($/unidade do compartimento h);
* Hjr total de tipos de bobinas intermediárias (compartimentos) na bobina
r, segundo o padrão compartimentado j (unidades de compartimentos);
* <formula/> número de bobinas intermediárias
(compartimentos) h na bobina r, segundo o padrão compartimentado j
(unidades de compartimentos);
* Lmin largura mínima de uma bobina intermediária (mm);
* Lmax largura máxima de uma bobina intermediária (mm);
* S2 perda intrínseca na borda de uma bobina intermediária (mm);
Padrões
* pr total de padrões compartimentados viáveis para bobinas do tipo r;
Variável
* <formula/> número de bobinas utilizadas do
tipo r, segundo o padrão compartimentado j (unidades de bobinas);
O modelo matemático que formulamos para resolver o PCBA é escrito como:
Modelo do PCBA
sujeito a:
Para facilitar cálculos e notações, sejam 
. Na figura_4 ilustramos a estrutura matricial do modelo, onde
está representada a matriz A e os vetores c e d, e onde Ar ([/img/revistas/
pope/v23n1/a13img08.gif])<formula/>, r=1,...,m.
Observe que uma coluna do modelo do PCBA (1.1 ' 1.4) possui (n + m) componentes
e tem o seguinte aspecto <formula/>, onde o valor
unitário ocupa a posição (n + r) da coluna.
Devido a grandeza da matriz A, na prática ela pode atingir milhões ou bilhões
de colunas, a utilização do SIMPLEX fica prejudicada, pois, decidir qual coluna
deverá compor a nova base dentre as milhões ou bilhões existentes é
computacionalmente inviável. Para contornar este entrave, Gilmore-Gomory (1961,
1963) introduziram a idéia de determinar esta coluna (no caso do PCBA uma
coluna do tipo <formula/>) por meio de um problema
otimização que depende das características das colunas. Para escrevermos este
problema, iremos investigar a natureza dos custos relativos para cada tipo de
bobina r=1,...,m do estoque. Seja o vetor de multiplicadores SIMPLEX dado por p
= cBB-1=(p1,..., pn,pn+1,..., pn+r,...pn+m) onde B é uma matriz básica obtida
de A e cB o vetor de custos associado às colunas de B, então:
Substituindo <formula/> por [/img/revistas/pope/
v23n1/a13img12.gif]<formula/>i[/img/revistas/pope/
v23n1/a13img03.gif] e reorganizando o cálculo obtemos:
Escrevendo <formula/>, onde [/img/revistas/pope/
v23n1/a13img15.gif] é o número de itens tipo i que aparecem no compartimento h,
do padrão j que é usado para cortar bobinas do tipo r, a expressão do custo
relativo pode ser rescrita como:
Finalmente a expressão do custo relativo é escrita da seguinte forma:
Onde,
Note que para cada bobina do tipo r, a parcela [/img/revistas/pope/v23n1/
a13img17.gif] (Lr- S1) - p n+r de (2.1) é uma constante, além do mais, os itens
do PCBA (as fitas) podem ser indexados pelo conjunto N={1,...,n}, e eles devem
ser agrupados em subconjuntos N1,...,Nk, onde cada um deles contém os índices
das fitas que são compatíveis entre si devido o processo de laminação, de forma
que {N1,...,Nk} constitua uma partição de N.
Para cada subconjunto Ns, s=1,...k, seja o conjunto Vs dos índices dos
compartimentos viáveis construídos a partir dos itens de Ns, de forma que
{V1,...,Vk} constitua uma partição de V=V1 È ...ÈVk . Tendo em vista que
devemos obter o mínimo { <formula/> é uma coluna
não básica}, o problema gerador de colunas do modelo (1.1 ' 1.4) pode ser
escrito como:
Modelo do Gerador de Padrões Compartimentados do PCBA
O modelo (3.1 ' 3.4) descreve o que denominamos Problema da Mochila
Compartimentada (PMC). Observe que (3.2) é a restrição física da mochila e
(3.3) são chamadas de "restrições de compartimentação". O PMC pode
ser resolvido otimamente pelo seguinte procedimento:
Procedimento_COMPEX
1. Para s=1,...,k, seja o agrupamento Ns e o subconjunto Vs associado;
1.1 Para cada h Î Vs, considere whÎ {(Lmin - S2), (Lmin - S2) + 1,...,(Lmax -
S2)} a capacidade do compartimento viável de índice h, e resolva a seguinte
mochila para obter a utilidade vh do compartimento:
maximizar <formula/>
sujeito a:
2. Seja V=V1 È ...ÈVk e resolva a seguinte mochila:
maximizar <formula/>
sujeito a:
yh > 0 e inteiro, h Î V
Propriedade
O algoritmo COMPEX encontra uma solução ótima do Problema da Mochila
Compartimentada (PMC), quando todas as mochilas do procedimento forem
resolvidas otimamente.
ProvaPara cada compartimento de índice h Î V, existe um único sÎ {1,...,k} que
depende de h, tal que h Î Vs, visto que os conjuntos Vs, s=1,..., k, foram
construídos como uma partição de V.
Seja wh a capacidade deste compartimento e considere Wh = [/img/revistas/pope/
v23n1/a13img23.gif] o conjunto de todos os vetores que representam uma
combinação linear dos pesos dos itens com índices em Ns, igual a wh.
A cardinalidade de Wh é finita, assim suponha que Wh tenha mh vetores e
considere <formula/> ,t=1,...,mh os possíveis
valores de utilidades para o compartimento de capacidade wh.
Observe que ao escolhermos vh = max{ <formula/>}
(mochila do passo 1 do COMPEX) a utilidade vh é dominante sob todas as
possíveis utilidades do compartimento de capacidade wh, e este mesmo raciocínio
se aplica ao custo ch por utilização do compartimento.
Supondo que a mochila do passo 2 do COMPEX é resolvida otimamente podemos
concluir que o COMPEX encontra um ótimo para o PMC.
Um procedimento alternativo, baseado no cálculo de limitantes, pode ser usado
para obter uma solução viável do PMC. Neste caso, a alteração é feita no passo
1.1 do COMPEX, vejamos:
Procedimento_COMPMT
1. Para s = 1,..., k, seja o agrupamento Ns e o subconjunto Vs associado;
1.1 Para cada h Î V, considere wh Î {(Lmin - S2),(Lmin - S2) +1,...,
(Lmax - S2)} a capacidade do compartimento viável de índice h, e
calcule um Limitante Superior [/img/revistas/pope/v23n1/
a13img26.gif]h para a utilidade vh do compartimento (por exemplo, o
Limitante de Martello-Toth);
2. Seja V=V1 È ...ÈVk e resolva a seguinte mochila:
maximizar <formula/>
sujeito a:
yh > 0 e inteiro, h Î V
Na tabela_1 resumimos os resultados que obtivemos para 900 exemplos de mochilas
compartimentadas, geradas aleatoriamente. A capacidade de todas as mochilas é
1200, as larguras <formula/>i e as utilidades ui
foram geradas aleatoriamente, respeitando as condições reais do PCBA. O custo
por utilizar um compartimento foi considerado como nulo.
Os algoritmos foram implementados em Delphi e executados num pentium II, 450
Mhz e com 160 Mb de RAM. Os exemplos foram agrupados em 3 grandes categorias,
segundo o número de compartimentos, e cada uma foi dividida em duas outras,
segundo o número de agrupamentos. A menor compartimentação é composta por 30
compartimentos e 3 agrupamentos com 5 itens em cada. A maior compartimentação é
formada por 6000 compartimentos e 20 agrupamentos com 100 itens em cada. As
colunas da tabela_1 são:
<formula/> e [/img/revistas/pope/v23n1/
a13img30.gif]: respectivamente, o limite mínimo e máximo das capacidades dos
compartimentos;
Agrup:número de agrupamentos da compartimentação;
Itens: número de itens num agrupamento da compartimentação;
Igualdade: percentual de exemplos em que as soluções doCOMPEXeCOMPMTforam
iguais;
Tempo: tempo médio de execução de um exemplo;
Perda: percentual de perda (espaço ocioso) na mochila;
Dif: percentual de diferença entre o valor da solução doCOMPEXe
doCOMPMTcalculado pela expressão100.<formula/>,
ondeValCOMPEXé o valor do objetivo obtido pela solução doCOMPEX, eValCOMPMTo
valor do objetivo obtido pela solução doCOMPMT.
Os resultados obtidos indicam que o procedimento COMPMT é competitivo em
relação ao COMPEX para problemas em que o número de compartimentos é alto,
porém, ressaltamos que o desempenho deste procedimento pode não ser
satisfatório para alguma classe de problemas, visto que, trata-se de uma
heurística. Nos problemas maiores, o COMPMT obteve menos soluções ótimas,
entretanto, a diferença dos objetivos não se mostrou significativa.
4. Arredondamento de uma Solução do PCBA e Fracionamento do Estoque
O procedimento consiste em resolver o modelo (1.1 ' 1.4) relaxando a condição
de integralidade da variável <formula/>. A seguir,
truncamos (arredondamos para baixo) a solução obtida. Um problema residual é
formulado a partir da demanda remanescente e resolvido, de modo que, este
processo é repetido até que o arredondamento forneça uma solução residual nula.
Ao final, é bem possível que uma pequena demanda ainda deva ser atendida, isto
é feito por meio de uma heurística que gera padrões restritos, que também é
utilizada nos problemas residuais.
Seja xr= (<formula/>) T, r = 1,...,m. Observe que
A1x1 + A2x2 +,...,Amxm =d, e que 1.xr < er, onde Ar = ([/img/revistas/pope/
v23n1/a13img08.gif]) nxpr e 1 = (1,...,1)pr , r = 1,...,m.
Sejam <formula/> a solução contínua do problema
(1.1 ' 1.4) e <formula/> o arredondamento para
baixo desta solução (maior inteiro menor ou igual a [/img/revistas/pope/v23n1/
a13img34.gif]), r = 1,...,m . Considere d0 = d a demanda inicial e [/img/
revistas/pope/v23n1/a13img36.gif] = er, r = 1,...,m, a disponibilidade inicial
do estoque. Para q =1,...,Q, os Problemas Residuais, com soluções contínuas [/
img/revistas/pope/v23n1/a13img37.gif], são definidos como:
No objetivo do modelo (4.1 ' 4.4) cr = ([/img/revistas/pope/v23n1/
a13img38.gif]) e <formula/>, j = 1,...,pr, r =
1,...,m. Na inequação 4.3 <formula/> é a norma 1
do vetor <formula/>. O total Q de Problemas
Residuais a serem resolvidos é determinado quando [/img/revistas/pope/v23n1/
a13img42.gif] = 0.
Ressaltamos que a medida que os Problemas Residuais são resolvidos as demandas
di das fitas vão diminuindo, por conseqüência, os padrões compartimentados
destes problemas devem ser restritos. O modelo do PMC restrito que adotamos é o
seguinte:
Modelo do Gerador de Padrões Compartimentados Restritos do PCBA
No modelo anterior as restrições adicionais são as (5.4) que limitam o total de
itens a serem compartimentados na mochila, conforme a demanda de cada fita.
O procedimento COMPEX pode ser adaptado para gerar padrões compartimentados
restritos. Isto é feito substituindo as mochilas do passo 1.1 por mochilas
canalizadas, cuja restrição de canalização sob as variáveis é baseada nas
restrições (5.4). Por fim, a mochila do passo 2 do COMPEX deve ser substituída
por uma mochila de variáveis binárias. Com estas modificações temos um
procedimento heurístico que denominamos COMPREST para obter uma solução viável
do PMC restrito. Se neste novo procedimento, substituirmos o cálculo das
mochilas canalizadas pelo simples cálculo de Limitantes Superiores, teremos um
novo procedimento heurístico que denominamos COMPRESTMT.
Após a resolução de todos os Problemas Residuais, ainda poderá existir uma
demanda residual que é atendida por uma heurística de repetição exaustiva
(Hinxman, 1980) com padrões compartimentados restritos.
Em visita a uma empresa do setor descobrimos que as bobinas em estoque poderiam
ser fracionadas em duas outras bobinas, cujos "pesos" são exatamente
a metade do "peso" da bobina original. Por exemplo, uma bobina do
estoque que tenha 12.000 Kg poderia ser fracionada em duas de 6.000 Kg.
Assim, o arredondamento das soluções contínuas dos Programas de Programação
Linear, usados no Corte de Bobinas de Aço sujeitas a Laminação, pode ser feito
por meio da seguinte função:
Observe que ao utilizarmos a função de arredondamento [/img/revistas/pope/
v23n1/a13img44.gif], surgirão em estoque bobinas fracionadas, de modo que, ao
arredondarmos uma solução torna-se necessário identificarmos se o tipo de
bobina em questão já sofreu fracionamento. Caso a bobina em questão tenha
sofrido o fracionamento ela não poderá ser novamente fracionada, e o
arredondamento deverá ser feito pela função [/img/revistas/pope/v23n1/
a13img45.gif] (maior inteiro menor ou igual a x).
5. Resultados Computacionais da aplicação do PMC no PCBA
As implementações foram feitas em Delphi e executadas num pentium II, 450 Mhz
com 160 Mb de RAM. Para construir um padrão compartimentado irrestrito
implementamos os procedimentos COMPEX e COMPMT (Hoto, 2001) e (Hoto et al.,
2002) que resolvem o Problema da Mochila Compartimentada Irrestrito. Para os
padrões compartimentados restritos implementamos os procedimentos COMPREST e
COMPRESTMT (Hoto, 2001). Cada exemplo do PCBA foi resolvido de quatro maneiras
distintas, obtidas pelas seguintes combinações:
* combinação 1 * combinação 2
COMPMT para padrões irrestritos COMPMT para padrões irrestritos
COMPRESTMT para padrões restritos COMPREST para padrões restritos
* combinação 3 * combinação 4
COMPEX para padrões irrestritos COMPEX para padrões irrestritos
COMPRESTMT para padrões restritos COMPREST para padrões restritos
Na tabela_2 apresentamos os resultados numéricos que obtivemos na resolução de
21 exemplos gerados aleatoriamente, cujos dados foram baseados nas condições
práticas do problema. As larguras foram geradas com valores distribuídos entre
55 mm e 250 mm.
Como estoque utilizamos três tipos de bobinas: com largura de 900 mm, de 1100
mm e de 1200 mm, todas elas com 12.000 Kg. A capacidade do laminador está
compreendida entre os valores 154 mm e 456 mm. O custo de bobinas
intermediárias sujeitas à laminação foi considerado 50% maior que o de bobinas
intermediárias isentas deste processo.
Nas colunas Agrup, Comp e Iens estão registrados respectivamente o número de
agrupamentos, o número total de compartimentos e o número de itens de cada
exemplo. Cada exemplo foi examinado segundo as quatro combinações possíveis, de
forma que, foi medido o tempo de execução em minutos, segundos e milisegundos
(coluna Tempo), a perda de material (coluna Perda) e o número de bobinas
intermediárias no processo (coluna Bobint).
Observe pelo gráfico da figura_5 que as combinações 1 e 2 são praticamente
equivalentes quanto ao número de bobinas intermediárias, ocorrendo o mesmo com
as combinações 3 e 4.
No gráfico da figura_6 podemos observar que a combinação que requer menor tempo
de execução na maioria dos exemplos é a combinação 1, porém, o número de
bobinas intermediárias é bem superior se comparados com os obtidos pela
combinação 4, que requer um tempo de execução mais elevado.
Para finalizar, apresentamos os resultados obtidos para um conjunto de 20 itens
extraídos de dados reais. Os agrupamentos dos itens são: N1={1,2,3}, N2={4},
N3={5}, N4={6,7,8}, N5={9,10,11,12}, N6={13,14,15,16,17} e N4={18,19,20}. Na
tabela_3 estão os resumidos os dados do problema e na tabela_4 os resultados
obtidos.
6. Conclusões
Neste artigo abordamos o Problema de Corte de Bobinas de Aço (PCBA), que é um
problema de corte unidimensional, cujos padrões devem ser estruturados em
compartimentos. Para construir um padrão de corte do PCBA é preciso resolver um
especial problema da mochila que denominamos Problema da Mochila
Compartimentada (PMC).
Para o PMC irrestrito desenvolvemos dois procedimentos o COMPEX e o COMPMT, que
foram descritos e comparados numericamente. No caso do COMPEX mostramos que o
procedimento encontra uma solução ótima do PMC, já o COMPMT consiste de uma
heurística baseada no cálculo de limitantes superiores.
Para o PMC restrito desenvolvemos um procedimento heurístico derivado do COMPEX
que denominamos COMPREST. A abordagem do cálculo de limitantes superiores no
lugar das mochilas canalizadas, foi aplicada no COMPREST, fornecendo um
procedimento que denominamos COMPRESTMT.
Utilizamos a Técnica de Geração de Colunas de Gilmore-Gomory para resolver o
PCBA e, baseado nos resultados computacionais obtidos, os algoritmos COMPEX
(para gerar padrões do caso irrestrito) e COMPRESTMT (para gerar padrões do
caso restrito) resultam numa boa estratégia para problema.
