Corte linear. Problema de corte unidimensional
Corte unidimensional de barras com tipos de perfil, estoque limitado e largura de corte. Plano para cada barra, sobras, aproveitamento do material e dois objetivos de otimização.
Corte linear é a distribuição de peças por barras, armaduras, tubos ou outros materiais de comprimento determinado. As peças podem mudar de lugar: o que importa não é a posição inicial na lista, mas quais delas devem ser cortadas da mesma barra.
A calculadora abaixo cria um plano para vários tipos de perfil, considera as quantidades disponíveis e a largura de corte e depois mostra a sobra de cada barra. Os valores padrão podem ser apagados; servem apenas como exemplo. As fórmulas e um pouco de teoria estão abaixo da calculadora.
Material de partida
| Tipo de perfil | Comprimento | Quantidade | ||
|---|---|---|---|---|
Peças
| Tipo de perfil | Comprimento | Quantidade | ||
|---|---|---|---|---|
Material de partida, peças e perfis
Material de partida é a barra original, e uma peça é o pedaço que se pretende obter. As tabelas usam os seguintes campos:
- Tipo de perfil identifica o material ou produto laminado, por exemplo «Armadura A500C». Uma peça só pode ser colocada em material com o mesmo tipo de perfil. Uma armadura de aço e um tubo de alumínio não devem ser misturados no mesmo plano, mesmo que seus comprimentos combinem convenientemente.
- Comprimento é o comprimento do material ou da peça. Todos os comprimentos devem usar as mesmas unidades: se forem escolhidos metros, 80 centímetros são escritos como 0,8.
- Quantidade é o número de posições idênticas. A calculadora expande esse número em peças ou barras individuais, portanto uma linha «comprimento 3, quantidade 2» significa duas peças de comprimento 3.
A sobra é a parte de uma barra utilizada que não se transformou em peça nem foi consumida pelo corte. Ela ainda pode ser aproveitada, por isso nem sempre é correto chamá-la de perda irrecuperável. As barras não utilizadas não entram nas sobras.
Um exemplo com duas barras
Suponhamos que temos uma barra de 12 metros e outra de 9 metros. Precisamos de quatro peças: 8, 7, 4 e 2 metros.
Um plano completo tem o seguinte aspecto:
| Material | Peças | Sobra |
|---|---|---|
| 12 m | 8 + 4 m | 0 m |
| 9 m | 7 + 2 m | 0 m |
O comprimento total das peças é 21 metros, exatamente igual ao comprimento do material utilizado. O aproveitamento do material é de 100%. Este é o exemplo padrão da calculadora, mas, naturalmente, uma sobra nula não é prometida para outros dados.
Por que considerar a largura de corte
Ao serrar, uma pequena parte do material se transforma em aparas. Essa medida chama-se largura de corte (kerf). Se ela for ignorada, um belo plano na tela pode não caber numa barra real.
A calculadora usa uma regra conservadora: uma largura de corte é reservada para cada peça. Se peças de comprimento forem colocadas numa barra e a largura de corte for
, o comprimento ocupado será
em que é o número de peças na barra. O plano só é admissível quando
, onde
é o comprimento do material. A sobra é calculada como
Por que e não
? A regra
serve quando uma barra é dividida completamente em
partes. Mas se restar uma sobra depois da última peça, ainda é preciso separá-la dela. Para não criar uma exceção oculta no caso de coincidência exata dos comprimentos, a calculadora sempre reserva um corte por peça.
Por exemplo, duas peças de 5 metros com largura de corte de 1 metro precisam de 12 metros, e não de uma barra de 10 metros. Esse plano requer duas barras, se estiverem disponíveis.
O que exatamente é otimizado
«Otimização» tem aqui dois sentidos diferentes. É possível gastar menos barras ou deixar menos material nas barras utilizadas. Esses objetivos nem sempre coincidem.
Suponhamos que exista uma barra de 12 metros e duas de 5 metros, e sejam necessárias duas peças de 3 metros:
- Número mínimo de barras. As duas peças cabem numa barra de 12 metros. A sobra é de 6 metros, mas as duas barras curtas permanecem intactas.
- Mínimo de sobras totais. Cada peça é colocada na sua própria barra de 5 metros. Duas barras são usadas, mas as sobras totais são de apenas 4 metros.
Por isso a calculadora permite escolher o objetivo. Por padrão, o mínimo de sobras está selecionado. Quando o critério principal empata, usa-se o secundário: primeiro compara-se a sobra total ou o número de barras e depois o inverso.
Para avaliar o resultado, é útil o aproveitamento do material — a proporção do comprimento das peças acabadas no comprimento do material utilizado:
em que é o comprimento da
-ésima peça e
é o comprimento da
-ésima barra utilizada. A largura de corte não entra no numerador. Portanto, aproveitamento do material, parcela de corte e parcela de sobra somam 100%.
Por que não se pode simplesmente prometer o melhor plano
Este é um problema de corte unidimensional (one-dimensional cutting-stock problem), próximo do problema de empacotamento em contêineres (bin packing problem). Na formulação clássica, é preciso colocar um conjunto dado de objetos no número mínimo de contêineres idênticos. O nosso problema considera ainda materiais de diferentes comprimentos, quantidades limitadas e compatibilidade de perfis.
Mesmo o empacotamento clássico é NP-difícil.1 Isso não significa que seja impossível obter uma resposta exata. Para um conjunto pequeno, podem-se enumerar as variantes; problemas grandes são resolvidos com programação inteira e geração de padrões de corte.2 Mas um solucionador exato desse tipo exigiria limites próprios e uma implementação muito mais complexa.
A calculadora usa heurísticas — regras que constroem rapidamente um bom plano, mas não demonstram sua otimalidade. Por isso, o resultado deve ser lido como «melhor plano encontrado», e não «melhor de todos os planos possíveis».
Como o algoritmo funciona
Primeiro, o problema é separado por tipo de perfil. Isso não é uma aproximação: uma peça não pode passar para material de outro perfil de qualquer forma. Em seguida, quatro variantes de construção são executadas para cada perfil:
- peças por comprimento decrescente ou crescente;
- ao abrir uma nova barra, primeiro a mais curta adequada ou primeiro a mais longa adequada.
Para a peça seguinte, a regra do melhor ajuste (best fit) escolhe a barra já aberta onde restará menos espaço após a alocação. Se nenhuma servir, outra barra não utilizada é aberta.
Os planos obtidos são melhorados localmente:3
- Remoção de uma barra. O algoritmo tenta transferir suas peças para outras barras já utilizadas. Se conseguir, a barra é liberada.
- Trocas. Se uma transferência simples não ajudar, o algoritmo tenta um número limitado de trocas de peças e repete a remoção.
- Substituição do material. Se o mesmo grupo de peças couber numa barra não utilizada mais curta e do mesmo perfil, a substituição é feita.
Resta apenas comparar as variantes pelo objetivo escolhido. Não há tentativas aleatórias: repetir o cálculo com os mesmos dados produz o mesmo plano.
Limite inferior do número de barras
Para um perfil, o comprimento total das peças pode ser dividido pelo maior comprimento de material disponível e arredondado para cima:
em que é o limite inferior do número de barras e
é o comprimento máximo disponível para este perfil. Os limites dos perfis são somados.
O limite é propositalmente simples: não considera a largura de corte, os limites de quantidade nem combinações inconvenientes de comprimentos. Se o plano encontrado usar exatamente barras, está demonstrado que seu número é mínimo. Disso não decorre que as sobras sejam mínimas.
Como ler o resultado
O plano de corte contém uma linha por barra utilizada. A entrada «8 + 4» significa duas peças dos comprimentos correspondentes; sua ordem de corte não influencia o consumo de material. Cada linha repete o comprimento das peças, a reserva de corte, a sobra e o aproveitamento do material.
O resumo por perfil ajuda a verificar a distribuição entre os tipos de material. Material não utilizado mostra o estoque restante. Se nenhum plano completo for encontrado, a tabela Peças não alocadas enumera o que o algoritmo não conseguiu alocar.
O que isso significa na prática? Talvez realmente não haja material suficiente ou uma peça seja mais comprida que qualquer barra adequada. Mas também é possível que a heurística não tenha encontrado um plano existente. Portanto, «não foi encontrado um plano completo» não prova que o corte seja impossível.
Limitações
- A otimalidade não é garantida. A admissibilidade do plano e todo o balanço de comprimentos são verificados, mas não se verifica se o resultado é mínimo entre todos os planos possíveis.
- Os perfis não são misturados. Seus nomes são comparados exatamente, incluindo maiúsculas e minúsculas. Substituir um material por outro exige uma decisão de engenharia separada, não uma regra de empacotamento.
- As peças não são divididas. Cada peça deve caber inteiramente numa única barra.
- Novas sobras não se transformam automaticamente em material de partida. Se precisar usá-las num trabalho posterior, adicione manualmente as sobras adequadas à tabela de material.
- Limites de entrada. São suportadas até 100 barras e 100 peças depois de expandir as quantidades, com até seis casas decimais. Este é um limite do cálculo no navegador, não uma propriedade do problema.
- Somente o comprimento é considerado. Custo de compra, cortes das extremidades, dispositivos de fixação, sobra útil mínima, ordem de operação da máquina e tempo de corte não fazem parte do modelo.
Se, em vez de comprimento, forem fornecidas largura e altura de retângulos, trata-se de outro problema. Para isso existe a calculadora de empacotamento bidimensional. Para contêineres idênticos sem perfis e sem plano por barra, podem ser úteis as calculadoras Problema de empacotamento e Problema de empacotamento 2.
-
Richard E. Korf. A New Algorithm for Optimal Bin Packing. AAAI 2002. Definições do problema, heurísticas e complexidade. Artigo. ↩
-
P. C. Gilmore, R. E. Gomory. A Linear Programming Approach to the Cutting-Stock Problem. Operations Research, 1961. Padrões de corte e geração de colunas. Artigo. ↩
-
A. C. F. Alvim, C. C. Ribeiro, F. Glover, D. J. Aloise. A hybrid improvement heuristic for the one-dimensional bin packing problem. Journal of Heuristics, 2004. Um exemplo de combinação de construção e melhoria local dos planos. Artigo. ↩
Comentários