%0 Thesis
%@documentstage not transferred
%@holdercode {isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S}
%@nexthigherunit 8JMKD3MGPCW/3F2PHGS
%@usergroup administrator
%@usergroup jefferson
%@usergroup simone
%3 publicacao.pdf
%J Some contributions to the solution of the cutting stock and pattern sequencing integrated problem
%@secondarytype TDI
%2 sid.inpe.br/jeferson/2004/07.02.13.58.52
%A Pinto, Maria José,
%P 194
%@dissemination NTRSNASA; BNDEPOSITOLEGAL.
%@secondarydate 20040621
%@group CAP-SPG-INPE-MCT-BR
%K corte, modelos matemáticos, método de relaxação (matemática), pesquisa operacional, cutting, mathematical models, relaxation method (mathematics), operation research.
%I Instituto Nacional de Pesquisas Espaciais (INPE)
%@copyholder SID/SCD
%@secondarykey INPE-11826-TDI/964
%9 Tese (Doutorado em Computação Aplicada)
%@area COMP
%8 2004-06-21
%X Os problemas de corte de estoque e de sequenciamento de padrões são oriundos de importantes aplicações práticas. A literatura existente geralmente os aborda de forma independente. Neste trabalho, apresentamos uma formulação matemática para o problema integrado e buscamos explorar a estrutura desta formulação para o desenvolvimento de um método de resolução eficiente. Devido à complexidade do modelo apresentado, propomos um esquema de decomposição para resolvê-lo que, para obter sucesso, necessita de uma resolução eficiente de ambos os problemas, o de corte e o de sequenciamento. Aperfeiçoamos e desenvolvemos métodos de resolução do problema de sequenciamento contribuindo com novas formulações para o MTSP e para o MOSP, que parecem promissoras para a resolução destes problemas em um menor tempo computacional. Apesar das melhoras nos tempos computacionais, os avanços conseguidos com as abordagens propostas não foram suficientes para que se possa utilizá-las rotineiramente para se resolver instâncias do problema integrado, de tamanhos encontrados na prática. Um procedimento heurístico para o problema integrado foi também desenvolvido para fornecer um limitante superior de boa qualidade para o problema. Com este trabalho, esperamos ter contribuído com o avanço no estado da arte com respeito à resolução de problemas de corte e seqüenciamento de forma integrada. ABSTRACT: The cutting stock problem and the pattern sequencing problem arise in important practical applications. In the existing literature these problems are generally treated independently. In this work, we developed a mathematical formulation for the integrated problem and we investigated the structure of this formulation in order to develop an efficient method for its solution. Due to the complexity of the integrated model, we propose a decomposition procedure to solve it. For the success of this procedure, both problems, the cutting stock problem and the pattern sequencing problems, have to be solved in an efficient way. We improved and developed methods to solve the pattern sequencing problem contributing with news formulations for the MTSP and the MOSP, that seem to be promising for solving these problems in a reduced computational time. Although the computational times were reduced with the proposed approaches, the advances obtained were not sufficient to be regularly used to solve instances of the problem with sizes found in practice. We also developed a heuristic to solve the integrated problem in order to provide a better upper bound to the problem. With this study, we expected to have contributed to the state of the art with respect to solving cutting and sequencing problems in an integrated way.
%@project CAP-SPG-INPE-MCT-BR
%E Becceneri, José Carlos (presidente),
%E Yanasse, Horácio Hideki (orientador),
%E Lorena, Luiz Antônio Nogueira,
%E Soma, Nei Yoshihiro,
%E Morabito Neto, Reinaldo,
%T Algumas contribuições à resolução do problema de corte integrado ao problema de sequenciamento dos padrões
%4 sid.inpe.br/jeferson/2004/07.02.13.58
%D 2004
%C São José dos Campos