%0 Thesis
%@documentstage not transferred
%@holdercode {isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S}
%@nexthigherunit 8JMKD3MGPCW/3F2PHGS
%@usergroup administrator
%@usergroup simone
%3 paginadeacesso.html
%J Pattern reduction in cutting stock problem
%@secondarytype TDI
%2 sid.inpe.br/jeferson/2003/12.17.16.01.35
%A Limeira, Marcelo Saraiva,
%P 176
%@dissemination NTRSNASA; BNDEPOSITOLEGAL.
%@secondarydate 20031017
%@group CAP-SPG-INPE-MCT-BR
%K Corte, otimização, métodos heurísticos, padrões, computer science, cutting, optimization, heuristic methods, patterns.
%I Instituto Nacional de Pesquisas Espaciais (INPE)
%@copyholder SID/SCD
%@secondarykey INPE-11896-TDI/966
%9 Tese (Doutorado em Computação Aplicada)
%@area COMP
%8 2003-10-17
%X Neste trabalho de tese focaliza-se o problema de redução do número mínimo de padrões distintos em problemas de corte de estoque. É feita uma revisão da literatura encontrada sobre este problema e novas heurísticas para este problema são propostas. A primeira heurística proposta compõe-se de três fases. Na primeira fase, padrões são gerados e selecionados se satisfizerem níveis de aspiração pré-estabelecidos. O problema é reduzido e resolvido na segunda fase. Na terceira fase, alguma técnica de redução de padrões é aplicada. Na segunda heurística proposta escalona-se as demandas dos itens por um fator constante e resolve-se o problema resultante. A terceira heurística proposta é uma variante da Heurística 1 com uma pequena mudança na fase 1. A quarta heurística proposta é uma variante do método de redução apresentado por Foerster e Wäscher (1999). Alguns limitantes inferiores para o número mínimo de padrões distintos em uma solução ótima para o problema de corte de estoque também foram propostos. As heurísticas 1, 2 e 3 foram implementadas e testes computacionais foram realizados. Os resultados obtidos dos testes computacionais indicam que as heurísticas implementadas têm bom desempenho em comparação com outras propostas anteriormente na literatura. ABSTRACT: In this thesis we focus on the problem of reducing the number of patterns in cutting stock problems. A review of the literature found on this subject is made and new heuristics for this problem are proposed. The first heuristic proposed is composed of three phases. In the first phase, patterns are generated and chosen if they satisfy some pre-established aspiration levels. The problem is reduced and solved in the second phase. In the third phase, some pattern reduction technique is applied. In the second heuristic proposed we scale the demands of the items by a constant factor and we solve the resulting problem. The third heuristic proposed is a variant of Heuristic 1 with a small modification in phase 1. The fourth heuristic proposed is a variant of the methods of reduction presented by Foerster and Wäscher (1999). Some lower bounds for the minimum possible number of different patterns in an optimal solution for the cutting stock problem were also introduced. Heuristics 1, 2 and 3 were implemented and computational tests were performed. The results obtained from the computational tests indicate that the proposed heuristics have good performance in comparison with previous procedures suggested in the literature.
%@project CAP-SPG-INPE-MCT-BR
%E Becceneri, José Carlos (presidente),
%E Yanasse, Horácio Hideki (orientador),
%E Lorena, Luiz Antonio Nogueira,
%E Soma, Nei Yoshihiro,
%E Morabito Neto, Reinaldo,
%T Redução do número de padrões em problemas de corte de estoque
%4 sid.inpe.br/jeferson/2003/12.17.16.01
%D 2003
%C São José dos Campos