A pesquisa Operacional e os Recursos Renováveis
4 a 7 de novembro de 2003, Natal-RN
MINIMIZANDO O NÚMERO DE DIFERENTES PADRÕES DE CORTE UMA ABORDAGEM DE CAMINHO MÍNIMO
Maria Cristina N. Gramani
Universidade Presbiteriana Mackenzie - Escola de Engenharia
Departamento de Engenharia de Produção
Rua da Consolação, 930 - Prédio 06
Cep: 01302-907 - São Paulo- SP - Brasil
[email protected]
Resumo
Neste artigo consideramos o problema de corte de estoque unidimensional minimizando
o número de diferentes padrões de corte. Propomos um novo método de resolução consistindo
na representação do problema em um grafo, onde os nós denotam os itens demandados e os
arcos representam o número de diferentes padrões de corte a serem processados. Após a
construção do grafo, resta apenas resolver um problema de caminho mínimo.
Palavras-Chave: corte de estoque, caminho mínimo, heurística.
Abstract
In this paper we consider the one dimensional cutting stock problem minimizing the
number of different cutting patterns. We propose a new resolution method consisting in the
representation of the problem in a graph, where the nodes denote the items demanded and the
arcs represent the number of different cutting patterns to be processed. After the construction of
this graph, it only remains to solve a minimum path problem.
Keywords: cutting stock, minimum path, heuristics.
Introdução
Considere uma linha de produção, por exemplo, em uma indústria de papel, aço,
móveis, vidros, etc, onde objetos são cortados em peças menores a fim de atender as
quantidades e dimensões especificadas pelos clientes.
Consideremos para este artigo o processo de uma indústria de papel, onde devemos
cortar bobinas grandes em bobinas menores. Este é o bem conhecido problema de corte de
estoque. Este módulo de cortagem, por sua vez, tem um subproblema fundamental que exige a
definição de como os itens (bobinas menores) devem ser arranjados dentro de cada bobina
grande. A esta definição chamamos de padrão de corte.
Figura 1: Um padrão de corte
Considere um processo onde temos em estoque uma quantidade ilimitada de barras e
desejamos atender a uma certa demanda. O problema surge quando se faz a troca de um padrão
de corte para outro, este procedimento pode ter um alto custo e tempo de preparação de
máquina. Mas se objetivarmos a mínima quantidade de trocas de padrões de corte, minimizando
estes custos, nos depararemos com um problema de difícil resolução.
Logo, surge a
necessidade de desenvolver metodologias a fim de minimizar a quantidade de diferentes tipos
de padrões de corte, mesmo que para isso, seja necessário abrir mão da perda mínima ocorrida
no processo de corte. Embora o potencial de aplicações de otimização nos processos de corte no
Brasil seja enorme, são poucos ainda os exemplos de utilização de metodologias específicas.
Obviamente, a otimização baseada no conhecimento e habilidade humana é largamente
utilizada.
A literatura apresenta alguns artigos referentes a este problema. Haessler (1975),
propôs uma formulação para o problema de corte de estoque unidimensional com custos de
setup para troca de padrões. Haessler (1988), discutiu algumas abordagens para resolver tal
problema. LeFrançois and Gascon (1995), apresentaram uma comparação de quatro diferentes
abordagens para o problema de corte de estoque onde a perda ocorrida e a troca de padrões eram
relevantes. Poldi (2002),
estudou o mesmo problema tratando de heurísticas de
arredondamento.
Método Proposto
Propomos resolver o problema de forma parcial, ou seja, resolvendo problemas menores
ao invés de resolver o problema global. Inicialmente, arranjamos os itens em ordem crescente
de comprimento, e, a partir de então, representamos o problema em um grafo, onde os nós
representam os itens demandados, e cada arco corresponde a um problema associado de corte de
estoque minimizando a quantidade de diferentes tipos de padrões de corte. Suponha, que o arco
(k,l) corresponda aos itens k e l. Nesse problema estamos procurando por uma solução de corte
de estoque que utilize a menor quantidade de padrões de corte satisfazendo a soma das
demandas dos itens dos tipos k, k+1, ..., l-1. A Figura 1 corresponde à rede constituída por 4
tipos de itens e seus respectivos arcos.
1511
1
2
3
5
4
Figura 1: Rede de Caminho Mínimo
Por exemplo, o Arco 1-4 na Figura 1, corresponde à produção da demanda dos itens dos
tipos 1, 2 e 3. O Arco 2-4 corresponde à produção da demanda dos itens dos tipos 2 e 3, e assim
por diante.
Associado com cada arco (k,l) existe um problema de corte de estoque minimizando a
quantidade de diferentes tipos de padrões de corte a ser resolvido, que segue o algoritmo de
Poldi (2002). O valor da função objetivo obtido dessa resolução é então definido como o custo
associado ao arco (k,l).
Resolvendo então cada arco, ou seja, obtendo a quantidade de padrões de corte obtidos
considerando determinados tipos de peças, resta-nos finalmente, resolver apenas um simples
problema de caminho mínimo.
Tomemos um exemplo com 6 tipos de diferentes itens, com tamanhos e demandas
fornecidas pela Tabela 1 a seguir. Consideramos as barras a serem cortadas de um único
tamanho L=40, disponíveis nas quantidades necessárias.
item comprimento demanda
1
3
120
2
4
100
3
18
72
4
19
115
5
22
70
6
26
112
Tabela 1: Dados do exemplo
Ao resolvermos o problema de forma global, ou seja, resolvendo o arco (1,7), utilizando
o algoritmo de Poldi (2002) que minimiza a quantidade de diferentes tipos de padrões de corte,
obtemos a seguinte solução:
Padrão
1
Padrão
2
Padrão
3
Padrão
4
Padrão
5
Padrão
6
Item 1
Item 2
Item 3
Item 4
Item 5
Item 6
0
Quantidade
de bobinas
cortadas no
padrão
26
3
3
0
1
0
2
3
0
0
1
0
1
0
1
0
0
Perda
no
padrão
0
1
0
7
0
1
0
0
28
0
0
1
0
0
1
17
0
1
0
1
0
44
0
0
0
2
0
0
30
2
1512
Padrão
7
Padrão
8
0
0
0
0
1
0
19
18
0
0
0
0
0
1
112
14
Tabela 2: Solução utilizando o problema de forma global – arco (1,7)
Resolvendo de forma parcial, ou seja, representando o problema em um grafo e para
cada arco solucionando o problema utilizando o algoritmo de Poldi (2002), e finalmente
resolvendo o problema do caminho mínimo, obtemos como solução a necessidade de cortar 7
diferentes tipos de padrões de corte, a fim de atender a demanda solicitada, da seguinte forma:
Padrão
1
Padrão
2
Padrão
3
Padrão
4
Padrão
5
Padrão
6
Padrão
7
Item 1
Item 2
Item 3
Item 4
Item 5
Item 6
0
Quantidade
de bobinas
cortadas no
padrão
10
12
1
0
0
0
0
10
0
0
0
0
1
0
0
0
Perda
no
padrão
0
0
0
9
0
1
0
0
2
3
1
0
1
0
70
0
0
0
2
0
0
56
2
0
0
0
1
0
0
1
21
0
0
0
0
0
1
112
14
Tabela 3: Solução utilizando a rede de caminho mínimo.
A solução obtida acima corresponde a resolver inicialmente o problema considerando
apenas os dois primeiros tipos de itens, ou seja, o arco (1,3) e depois resolver o problema
considerando o restante dos itens, ou seja, o arco (3, 7).
Logo, como mostra a Figura abaixo, tratando o problema de forma global, a perda total
ocorrida para atender a demanda desejada foi de 1.987 unidades, e foram necessárias 267 barras
disponíveis em estoque, e, tratando o problema de forma parcial, a perda total ocorrida para
atender a demanda desejada foi de 1.707 unidades, e foram necessárias 250 barras disponíveis
em estoque.
1513
2500
2000
1500
Solução global
1000
Solução Caminho Mínimo
500
0
Perda Total
Qde padrões de corte
Um simples exemplo nos mostra que resolvendo problemas menores, existe a
possibilidade de obter melhores soluções do que quando resolvendo o problema de forma
global. Neste caso especificamente, notamos que além de minimizar a quantidade de diferentes
tipos de padrões de corte utilizados, também houve uma significativa diferença de 14%, em
relação à perda total no processo.
Obviamente não podemos tirar conclusões baseadas em uma única instância, porém esta
instância nos sugere um possível caminho promissor a ser analisado.
Conclusões e Trabalhos Futuros
Mostramos nesse artigo uma nova abordagem de resolução para o Problema de Corte de
Estoque quando minimizando a quantidade de diferentes tipos de padrões de corte. Esta
abordagem consistiu em resolver problemas menores ao invés de resolver o problema global,
para isso, representamos o problema em um grafo e depois utilizando o problema do caminho
mínimo para sua resolução. Finalmente, mostramos com um simples exemplo a vantagem que
pode ser obtida quando utilizamos a rede de caminho mínimo quando comparando-a com a
solução global.
Os próximos passos consistem em analisar computacionalmente um conjunto maior de
instâncias, verificando assim a eficácia da abordagem proposta.
Agradecimentos
Ao Instituto Presbiteriano Mackenzie pelo suporte financeiro à pesquisa.
À Kelly Cristina Poldi e ao Prof. Dr. Marcos N. Arenales pelo código do programa que
minimiza os diferentes tipos de padrões de corte.
Bibliografia
Christofides, N. E Whitlock, C. (1977), “An Algorithm for Two-Dimensional Cutting
Problems”, Op. Res. 25, pp. 30-44.
Gilmore, P. e Gomory, R. (1963), “A Linear Programming Approach to the Cutting Stock
Problem - Part II”, Op. Res. 11, pp. 863-888.
1514
Gilmore, P. e Gomory, R. (1965), “MultiStage Cutting Sotck Problems of Two and more
Dimensions”, Op. Op. Es. 14, pp. 1045-1074.
Haessler RW (1971), “A heuristic programming solution to a nonlinear cutting stock problem”,
Management Science, 17, B793-B802.
Haessler, R.W., (1975), “Controlling cutting pattern changes in one-dimensional trim
problems”, Operations Research 23(3), 483-493.
Haessler, R.W., (1988), “Selection and design of heuristic procedures for solving roll trim loss
problems”, Management Science 34 (12), 1460-1471.
Hinxman, A. (1980), “The Trim-Loss and Assortment Problems: A Survey”, European J. Opr.
Res. 5, pp. 8-18.
LeFrançois, P. e Gascon, A., (1995), “Solving a one-dimensional cutting-stock problem in a
small manufacturing firm: a case study”, IIE Transactions 27, 483-496.
Morábito R., Arenales, M. E Arcaro, V. (1991), “An And-Or-Graph Approach for TwoDimentional Cutting Problems”, European J. Op. Res. 58.
Limeira, M.S.; Yanasse, H.H.(2001), “Uma heurística para o problema de redução de padrões
de corte”, Anais da V Oficina Nacional de Problemas de Corte e Empacotamento, São José dos
Campos, 137-145.
Poldi, K.C., Arenales, M.N. (2002), “Heurísticas para o Problema de Corte de Estoque
Unidimensional Inteiro”, Anais do XXXIV SBPO, Rio de Janeiro, RJ.
1515