Técnicas para minimização do número de padrões de corte no problema de corte de estoque

Técnicas para minimização do número de padrões de corte no problema de corte de estoque

Author Kobersztajn, Henrique Augusto Autor UNIFESP Google Scholar
Advisor Poldi, Kelly Cristina Poldi Autor UNIFESP Google Scholar
Institution Universidade Federal de São Paulo (UNIFESP)
Graduate program Ciência da Computação
Abstract In this work, we present an approach to the one-dimensional cutting stock problem with one type of object and also with multiple types of objects. We consider two objectives in order to obtain the final solution: minimize the total length of cut objects and the number of different cutting patterns. Both objectives, generally conflicting, are dealt independently on the proposed methods. Initially, an exact solution to the cutting stock problem is obtained and, upon this solution, procedures are applied aiming different cutting patterns reduction. The minimizing pattern reduction process does not necessarily keep the initial minimum length of cut objects, however the increase of the length is allowed in a controlled way if it implies in more pattern reduction at the final solution. Computational tests are performed with random data to evaluate empirically this approach, and good results are obtained comparing to other methods presented in literature.

Neste trabalho é apresentada uma abordagem para a resolução do problema de corte de estoque unidimensional inteiro para o caso em que temos um único tipo de objeto em estoque e também para o caso em que temos múltiplos tipos de objetos. Dois objetivos são levados em consideração na obtenção da solução final: a minimização do comprimento total de objetos cortados e a redução da quantidade de padrões de corte distintos. Estes dois objetivos, geralmente conflitantes, são tratados de forma independente nos métodos propostos neste trabalho. Inicialmente, uma solução exata para o problema de corte de estoque é obtida e então, sobre esta solução, é aplicado um conjunto de procedimentos visando a redução da quantidade de padrões de corte distintos. Tais procedimentos não necessariamente mantêm o comprimento mínimo de objetos cortados inicialmente, de forma que o aumento no comprimento cortado é permitido de forma controlada se implicar em uma maior redução dos padrões distintos presentes na solução final. Testes computacionais são realizados com um conjunto de dados gerados aleatoriamente de forma a avaliar empiricamente esta abordagem e mostram bons resultados comparados a outros métodos encontrados na literatura.
Keywords integer optimization
cutting stock problem
cutting pattern
pattern minimizing
linear programming
otimização inteira
problema de corte de estoque
padrões de corte
redução de padrões
programação linear
Language Portuguese
Date 2015-10-27
Published in KOBERSZTAJN, Henrique Augusto. Técnicas para minimização do número de padrões de corte no problema de corte de estoque. 2015. 94 f. Dissertação (Mestrado) - Instituto de Ciência e Tecnologia, Universidade Federal de São Paulo (UNIFESP), São José dos Campos, 2015.
Research area Ciência da computação
Knowledge area Ciências exatas e da terra
Publisher Universidade Federal de São Paulo (UNIFESP)
Extent 94 p.
Origin https://sucupira.capes.gov.br/sucupira/public/consultas/coleta/trabalhoConclusao/viewTrabalhoConclusao.jsf?popup=true&id_trabalho=2666925
Access rights Closed access
Type Dissertation
URI http://repositorio.unifesp.br/handle/11600/47075

Show full item record




File

File Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Search


Browse

Statistics

My Account