Made available in DSpace on 2014-12-02T11:16:56Z (GMT). No. of bitstreams: 0 Previous issue date: 2014-05-13Bitstream added on 2014-12-02T11:20:50Z : No. of bitstreams: 1 000796058.pdf: 2888477 bytes, checksum: aeb48d13f2d71aae91a21d050cd51b93 (MD5) / O presente trabalho propõe uma análise sobre os problemas de corte e empacotamento com restrições práticas que representam cenários reais na indústria. Em síntese o problema de corte consiste em cortar um conjunto de peças de um determinado objeto, e o problema de empacotamento consiste em alocar um conjunto de peças dentro de um objeto. No mundo real se apresenta uma grande quantidade de variações destes problemas. Neste estudo limitamo-nos a estudar os problemas com peças e objetos com formas regulares, restringindo assim os problemas de duas dimensões ao uso de retângulos e aos problemas de três dimensões ao uso de paralelepípedos. De forma específica os problemas de corte estudados neste trabalho são o problema da mochila bidimensional (2D-SLOPP, do inglês Two-Dimensional Single Large Object Placement Problem) com restrições de padrão de corte; valores associados às peças; limites de exemplares por peça e orientação das peças. O segundo problema a ser estudado, é o problema da embalagem (2D-SBSBPP, do inglês Two-Dimensional Single Bin Size Bin Packing Problem) com restrições de padrões de corte tipo guilhotina e restrições de orientação das peças. Finalmente, o problema de empacotamento estudado no presente trabalho é o problema do carregamento de um único contêiner (3D-SKP ou 3D-SLOPP, do inglês Three-Dimensional Single Knapsack Problem e Three-Dimensional Single Large Object Placement Problem, respectivamente) com restrições de orientação das caixas; limites de resistência das caixas ao empilhamento; limite de peso do carregamento suportado pelo contêiner; estabilidade do padrão de carregamento e carga divida em múltiplos destinos. Estes três problemas apresentados são de grande interesse para a indústria, graças a isto, atualmente existe uma ampla literatura especializada de trabalhos referentes a esta temática. Logo, diferentes tipos de ... / In this work we study the cutting and packing problems with practical constraints that represent real world scenarios of the industry. The cutting problem consists in to cut a set of pieces from an object, and the packing problem consists in to pack a set of items in an object. In the real world there are a big number of variations of this problem. In this study we only carry out the problems where the pieces and the objects have a regular shape, bounding of that way the two-dimensional problems to use just rectangular items and the three-dimensional problems to use just parallelepiped pieces. Specifically, the cutting problems studied in this work are: the Two-Dimensional Single Knapsack Problem, taking into account cutting pattern constraints (guillotine and non-guillotine patterns), orientation of the pieces constraints, associated costs to the pieces constraints and demanding types of pieces constraints. The second problem that we work on is the Two-Dimensional Single Bin Size Packing Problem, taking into account cutting pattern constraints (only guillotine patterns) and orientation pieces constraints. The last problem is the Container Loading Problem (Three- Dimensional Single Large Object Placement Problem) taking into account: orientation box constraints, load-bearing strength constraints, cargo stability constraints (full support) and multi-drop constraints. All the previous problems have a big spectrum of application on the Industry, because of this; there is a big amount of previous work on it. Different methodologies, exact and approximate algorithms have been proposed as solution strategies. Due to the mathematical and computational complexity of these problems, the exact algorithms cannot solve real world instances of the problem. The approach of this study consists on presenting and/or adapting different encodings and optimization algorithms. Among the proposed approach solutions is ...

Made available in DSpace on 2016-06-02T19:51:24Z (GMT). No. of bitstreams: 1 DissAA_2.pdf: 2467441 bytes, checksum: 3618b64c429e59e38fbf9929c981ad63 (MD5) Previous issue date: 2006-12-07 / Financiadora de Estudos e Projetos / The Cutting Stock Problem consists of determining the best form to cut units of material (objects in supply), producing a set of lesser units (demanded item), with specific dimensions, that are ordered through an order wallet. To minimize the loss of material this study described a method of evaluation and optimization of the process planning of the cutting of metallic structural tubes used in the manufacturing of small aircrafts for the agricultural aeronautic industry. In order, to support the decisions in the cutting process it was developed an optimization approach based on mathematical mixed integer programming models. The mathematic models are resolved in GAMS/CPLEX, using the production data of Neiva, an aeronautical company subsidiary of Embraer. The results showed that it is possible obtain significant profits in the production in with the application of mathematical models in the process of cut in the aeronautic industry. Mathematical models have a potential to generate beneficial solutions in the production process reducing the costs of production with the re-use of the leftovers. / O objetivo deste estudo foi avaliar e otimizar o planejamento do processo de corte de tubos estruturais metálicos utilizados na fabricação de aeronaves leves voltadas ao segmento de mercado agrícola. Através do enfoque sistêmico da Pesquisa Operacional, buscamos a possibilidade de minimizar as perdas de material e gerar retalhos cujas dimensões permitam sua posterior utilização. Foi desenvolvida uma abordagem de otimização baseada em programação matemática linear inteira mista, para apoiar as decisões no processo de corte. Os modelos estudados abrangem os objetivos propostos, incluindo o critério de minimizar os custos com as perdas do material e a possibilidade de gerar sobras com tamanho suficiente para reaproveitamento. Utilizando-se a linguagem de modelagem GAMS e o solver CPLEX, os modelos resolveram exemplos destacados da prática da empresa Neiva, localizada em Botucatu/SP, subsidiária da empresa aeronáutica Embraer. Inclusive com uma abordagem multi-períodos, esses exemplos mostram o potencial dos modelos para gerar soluções melhores que as atualmente utilizadas pela empresa, em um tempo computacional admissível.

Orientador: Ruben Augusto Romero Lazaro / Banca: José Roberto Sanches Mantovani / Banca: Silvio Alexandre de Araujo / Banca: José Elias Claudio Arroyo / Banca: Ramón Álvarez-Valdés / Resumo: O presente trabalho propõe uma análise sobre os problemas de corte e empacotamento com restrições práticas que representam cenários reais na indústria. Em síntese o problema de corte consiste em cortar um conjunto de peças de um determinado objeto, e o problema de empacotamento consiste em alocar um conjunto de peças dentro de um objeto. No mundo real se apresenta uma grande quantidade de variações destes problemas. Neste estudo limitamo-nos a estudar os problemas com peças e objetos com formas regulares, restringindo assim os problemas de duas dimensões ao uso de retângulos e aos problemas de três dimensões ao uso de paralelepípedos. De forma específica os problemas de corte estudados neste trabalho são o problema da mochila bidimensional (2D-SLOPP, do inglês Two-Dimensional Single Large Object Placement Problem) com restrições de padrão de corte; valores associados às peças; limites de exemplares por peça e orientação das peças. O segundo problema a ser estudado, é o problema da embalagem (2D-SBSBPP, do inglês Two-Dimensional Single Bin Size Bin Packing Problem) com restrições de padrões de corte tipo guilhotina e restrições de orientação das peças. Finalmente, o problema de empacotamento estudado no presente trabalho é o problema do carregamento de um único contêiner (3D-SKP ou 3D-SLOPP, do inglês Three-Dimensional Single Knapsack Problem e Three-Dimensional Single Large Object Placement Problem, respectivamente) com restrições de orientação das caixas; limites de resistência das caixas ao empilhamento; limite de peso do carregamento suportado pelo contêiner; estabilidade do padrão de carregamento e carga divida em múltiplos destinos. Estes três problemas apresentados são de grande interesse para a indústria, graças a isto, atualmente existe uma ampla literatura especializada de trabalhos referentes a esta temática. Logo, diferentes tipos de ... / Abstract: In this work we study the cutting and packing problems with practical constraints that represent real world scenarios of the industry. The cutting problem consists in to cut a set of pieces from an object, and the packing problem consists in to pack a set of items in an object. In the real world there are a big number of variations of this problem. In this study we only carry out the problems where the pieces and the objects have a regular shape, bounding of that way the two-dimensional problems to use just rectangular items and the three-dimensional problems to use just parallelepiped pieces. Specifically, the cutting problems studied in this work are: the Two-Dimensional Single Knapsack Problem, taking into account cutting pattern constraints (guillotine and non-guillotine patterns), orientation of the pieces constraints, associated costs to the pieces constraints and demanding types of pieces constraints. The second problem that we work on is the Two-Dimensional Single Bin Size Packing Problem, taking into account cutting pattern constraints (only guillotine patterns) and orientation pieces constraints. The last problem is the Container Loading Problem (Three- Dimensional Single Large Object Placement Problem) taking into account: orientation box constraints, load-bearing strength constraints, cargo stability constraints (full support) and multi-drop constraints. All the previous problems have a big spectrum of application on the Industry, because of this; there is a big amount of previous work on it. Different methodologies, exact and approximate algorithms have been proposed as solution strategies. Due to the mathematical and computational complexity of these problems, the exact algorithms cannot solve real world instances of the problem. The approach of this study consists on presenting and/or adapting different encodings and optimization algorithms. Among the proposed approach solutions is ... / Doutor

Orientador: Flávio Keidi Miyazawa / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-18T01:07:44Z (GMT). No. of bitstreams: 1 Queiroz_ThiagoAlvesde_D.pdf: 1460601 bytes, checksum: 0d83e25259c427329e25174c2e729e77 (MD5) Previous issue date: 2010 / Resumo: Problemas de Corte e Empacotamento são, em sua maioria, NP-difíceis e não existem algoritmos exatos de tempo polinomial para tais se for considerado P ¿ NP. Aplicações práticas envolvendo estes problemas incluem a alocação de recursos para computadores; o corte de chapas de ferro, de madeira, de vidro, de alumínio, peças em couro, etc.; a estocagem de objetos; e, o carregamento de objetos dentro de contêineres ou caminhões-baú. Nesta tese investigamos problemas de Corte e Empacotamento NP-difíceis, nas suas versões bi- e tridimensionais, considerando diversas restrições práticas impostas a tais, a saber: que permitem a rotação ortogonal dos itens; cujos cortes sejam feitos por uma guilhotina; cujos cortes sejam feitos por uma guilhotina respeitando um número máximo de estágios de corte; cujos cortes sejam não-guilhotinados; cujos itens tenham demanda (não) unitária; cujos recipientes tenham tamanhos diferentes; cujos itens sejam representados por polígonos convexos e não-convexos (formas irregulares); cujo empacotamento respeite critérios de estabilidade para corpos rígidos; cujo empacotamento satisfaça uma dada ordem de descarregamento; e, cujos empacotamentos intermediários e final tenham seu centro de gravidade dentro de uma região considerada "segura". Para estes problemas foram propostos algoritmos baseados em programação dinâmica; modelos de programação inteira; técnicas do tipo branch-and-cut; heurísticas, incluindo as baseadas na técnica de geração de colunas; e, meta-heurísticas como o GRASP. Resultados teóricos também foram obtidos. Provamos uma questão em aberto levantada na literatura sobre cortes não-guilhotinados restritos a um conjunto de pontos. Uma extensiva série de testes computacionais considerando instâncias reais e várias outras geradas de forma aleatória foram realizados com os algoritmos desenvolvidos. Os resultados computacionais, sendo alguns deles comparados com a literatura, comprovam a validade dos algoritmos propostos e a sua aplicabilidade prática para resolver os problemas investigados / Abstract: Several versions of Cutting and Packing problems are considered NP-hard and, if we consider that P ¿ NP, we do not have any exact polynomial algorithm for solve them. Practical applications arises for such problems and include: resources allocation for computers; cut of steel, wood, glass, aluminum, etc.; packing of objects; and, loading objects into containers and trucks. In this thesis we investigate Cutting and Packing problems that are NP-hard considering theirs two- and three-dimensional versions, and subject to several practical constraints, that are: that allows the items to be orthogonally rotated; whose cuts are guillotine type; whose cuts are guillotine type and performed in at most k stages; whose cuts are non-guillotine type; whose items have varying and unit demand; whose bins are of variable sizes; whose items are represented by convex and non-convex polygons (irregular shapes); whose packing must satisfy the conditions for static equilibrium of rigid bodies; whose packing must satisfy an order to unloading; and, whose intermediaries and resultant packing have theirs center of gravity inside a safety region; Such cutting and packing problems were solved by dynamic programming algorithms; integer linear programming models; branch-and-cut algorithms; several heuristics, including those ones based on column generation approaches, and metaheuristics like GRASP. Theoretical results were also provided, so a recent open question arised by literature about non-guillotine patterns restricted to a set of points was demonstrated. We performed an extensive series of computational experiments for algorithms developed considering several instances presented in literature and others generated at random. These results, some of them compared with the literature, validate the approaches proposed and suggest their applicability to deal with practical situations involving the problems here investigated / Doutorado / Doutor em Ciência da Computação

Orientadores: Marcia Aparecida Gomes Ruggiero, Antonio Carlos Moretti / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-11T07:33:43Z (GMT). No. of bitstreams: 1 Sakamori_Momoe_M.pdf: 494316 bytes, checksum: ffa8a12071e05ab6083c917588e53797 (MD5) Previous issue date: 2008 / Resumo: Neste trabalho resolvemos um problema de corte unidimensional não-linear para minimizar o número de objetos processados, setup e desperdício. O termo não-linear representa o setup da máquina de corte. Resolvemos o problema utilizando o pacote MINOS e obtemos a solução inteira através de um procedimento heurístico. Como o número de padrões de corte pode ser muito grande, propomos uma geração de colunas modificada, que usa os multiplicadores de Lagrange do problema não-linear ao invés das variáveis duais do problema de programação linear padrão. Além disso, propomos um novo processo de geração de colunas utilizando um problema da mochila não-linear como subproblema para gerar colunas promissoras / Abstract: In this work we solve a nonlinear unidimensional cutting-stock problem to minimize the number of objects processed, setup and trim loss. The nonlinear term represents the setup of the cutting machine. We solve the problem using the MINOS package and obtain the integer solution through a heuristic procedure. Since the number of cutting patterns can be very high, we propose a modified column generation that uses the Lagrange multipliers of the nonlinear problem instead the dual variables of the standard linear programming problem. Also, we propose a new column generation process using a nonlinear knapsack problem as the subproblem to generate pro_table columns / Mestrado / Pesquisa Operacional / Mestre em Matemática Aplicada

O problema de corte de estoque consiste em cortar objetos maiores, disponíveis em estoque, para produzir uma quantidade especificada de peças menores, de modo que uma certa função objetivo seja otimizada. Um modelo de otimização linear tem sido amplamente utilizado na solução deste problema desde os anos 60, que incorpora parte da estrutura combinatória inerente ao problema na construção das colunas da matriz de restrições. As colunas são construídas a cada iteração do Método Simplex, chamando-se geração de colunas. Apesar do método Simplex ser largamente utilizado para este tipo de problema, apresenta baixa convergência quando próximo da otimalidade, pouco melhorando a função objetivo. Assim, estratégias para aceleração do Método Simplex faz-se necessário, uma maneira consiste na redução do espaço dual, com a introdução de restrições (colunas no primal) que evite grandes variações nas variáveis duais, chamadas cortes duais. Neste trabalho, generalizamos duas famílias de cortes duais recentemente publicadas e analisamos o impacto computacional desses cortes duais sobre a convergência do Método Simplex / The cutting stock problem consists of cutting large available objects in stock to produce a quantity of ordered smaller itens, in such a way as to optimize a given objective function. A linear optmizatim model has been widely used to solve this problem since the 60s, in which part of a combinatorial structure of the problem is embedded. The columns of the constraint matrix are generated in each iteration of the Simplex Method, called the column generation technique. Although, the Simplex Method is widely used, it has a low convergence near to optimality. In this way, strategies to accelerate the Simplex Method are welcome which can be obtained by adding dual cuts (primal columns). The goal of this work is to study published dual cuts and to proposed others. In this book us extend two families of dual cuts, which were recently published, and analyse the computational impact of these dual cuts on the converge of the Simplex Method

Orientador: Antonio Carlos Moretti / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-19T18:37:54Z (GMT). No. of bitstreams: 1 Souza_JulianodaSilvade_M.pdf: 2798780 bytes, checksum: b977e17cdf141668422f1dd2f3ef4eb0 (MD5) Previous issue date: 2012 / Resumo: Neste trabalho é apresentada uma nova abordagem da heurística Simulated Annealing, no que se refere a geração de soluções na vizinhança de uma solução factível, para encontrar a solução ótima de uma formulação de programação linear inteira para o Problema de Corte de Estoque Unidimensional. O desempenho do novo algoritmo é comparado à metodologia publicada em A simulated annealing heuristic for the one-dimensional cutting stock problem apresentada em [2]. Os resultados dos experimentos computacionais indicam que essa nova abordagem, fornece soluções muito melhores em relação ao valor objetivo em tempo equivalente de execução. Além disso, uma comparação qualitativa é feita com o solver CPLEX. Para os experimentos numéricos utiliza-se o gerador de problemas CUTGEN1: A problem generator for the Standard One-dimensional Cutting Stock Problem, proposto em [6], o qual fornece um gerador de classes de problemas de acordo com os critérios de tamanho dos itens finais e demandas. Finalmente, são reportados resultados dos experimentos computacionais baseados na metodologia apresentada em [1] no artigo Guidelines for Designing and Reporting on Computational Experiments with Heuristic Methods / Abstract: This work presents a new approach to heuristic Simulated Annealing, in refers to the generation of solutions in the neighborhood of a feasible solution, to _nd the solution an optimal integer linear programming formulation for the Cutting Stock Problem One-dimensional. The performance of the new algorithm is compared to the methodology published in A simulated annealing heuristic for the one-dimensional cutting stock problem presented in [2]. The results of computational experiments indicate that this new approach provides much better solutions in relation to the objective value time equivalent execution. In addition, a qualitative comparison is made to the CPLEX solver. For the numerical experiments we use the generator of problems CUTGEN1: A problem generator for the Standard One-dimensional Cutting Stock Problem, in [6], which provides a generator classes of problems according to criteria size and demands of end items. Finally, results of experiments are reported computer-based method presented in [1] by article Guidelines for Designing and Reporting on Computational Experiments with Heuristic Methods / Mestrado / Matematica Aplicada / Mestre em Matemática Aplicada

Orientador: Antonio Carlos Moretti / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatística e Computação Cientifica / Made available in DSpace on 2018-08-04T09:51:10Z (GMT). No. of bitstreams: 1 SallesNeto_LuizLeduinode_D.pdf: 2686631 bytes, checksum: 6929a985654c561695159e4b4fc6ebb7 (MD5) Previous issue date: 2005 / Resumo: Neste trabalho apresentamos um novo método para minimizar o número de objetos processados e o número de padrões distintos (setup) num problema de corte unidimen-sional. Suavizamos a função objetiva, inteira e não linear proposta por Haessler em 1975. Para gerar os padrões de corte utilizamos inicialmente uma heurística (SHP de-senvolvida por Haessler), e posteriormente adaptamos o método de geração de colunas de Gilmore e Gomory para este modelo não-linear. Palavras-Chaves: Problema de corte de estoque; Geração de colunas; Setup; Heurística; Programação Não-Linear / Abstract: In this work we introduce a new method to minimize both the number of processed objects and the number of nonzeros cutting patterns (Le., setup) in an one-dimensional cutting stock problem. To do so, we smooth the discontinuous nonlinear function used in Haessler(1975) to represent both objectives: the number of objects and setup number. To generate the cutting patterns we use the Gilmore&Gomory strategy with a starting basis given by the method SHP (Sequential Heuristic Procedure) developed by Haessler. Keywords: Cutting stock problem; Column generation; Heuristic; Setup; Nonlinear programming / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

Orientador: Sônia Cristina Poltroniere Silva / Resumo: A Matemática está constantemente presente em nosso cotidiano, sendo ferramenta importante para uma melhor compreensão do mundo e facilitadora dos processos de tomada de decisão. Neste sentido, o trabalho com resolução de problemas ao longo da formação escolar básica faz-se extremamente necessário. Inserida neste contexto, a modelagem matemática é uma ferramenta que permite uma melhor leitura e um tratamento mais adequado do problema. Essa dissertação aborda, inicialmente, conceitos básicos relativos ao Problema de Corte de Estoque e a sua modelagem matemática, com ênfase na definição dos padrões de corte. Posteriormente, é discutido o método branch-and-bound, utilizado na resolução de problemas de otimização linear inteira, como é o caso do problema de corte. Por m, são propostas duas situações-problema, que consideram aplicações do Problema de Corte, para serem trabalhados com alunos do Ensino Médio, considerando os conceitos matemáticos assimilados previamente. / Abstract: Mathematics is constantly present in our daily lives, being an important tool for a bet ter understanding of the world and facilitating decision making processes. In this sense, problem-solving work throughout basic school education is extremely necessary. In this context, mathematical modeling is a tool that allows a better reading and a better treat ment of the problem. This dissertation initially addresses the basic concepts related to the Cutting Stock Problem and the mathematical modeling for the one-dimensional case, with emphasis on the de nition of the cutting patterns. Subsequently, the Branch-and-bound method, used in solving Integer Linear Programming Problems, such as the cutting pro blem, is discussed. Finally, problem situations are proposed, which consider applications of the Cutting Stock Problem, to be worked with high school students, emphasizing the previously assimilated mathematical concepts. / Mestre

Os problemas de corte de estoque consistem em cortar um conjunto de objetos dispon´veis em estoque para produzir um conjunto de itens em quantidades e tamanhos especificados, de modo a otimizar uma fun¸cao objetivo. Tais problemas tem in´umeras aplica¸coes industriais e tem sido bastante estudados na literatura. Tipicamente, problemas de corte tem como principal objetivo a minimiza¸cao das sobras. Entretanto, como a qualidade dos padroes de corte depende diretamente dos tamanhos e quantidades dos itens a serem produzidos, nesta tese, consideramos que se a demanda presente gerar sobras indesej´aveis (nem tao grandes para serem aproveit´aveis, nem tao pequenas para serem perdas aceit´aveis), entao conv´em gerar retalhos (nao comput´aveis como perda) que serao utilizados para produzir itens de demandas futuras. Desta forma, algumas caracter´sticas desej´aveis para uma boa solu¸cao sao definidas e altera¸coes em m´etodos heur´sticos cl´assicos sao apresentadas, de modo que os padroes de corte com sobras indesej´aveis sao alterados. Para os problemas de corte unidimensionais, desenvolvemos procedimentos heur´sticos que consideram o aproveitamento de sobras, mantendo como o principal objetivo a minimiza ¸cao das perdas. Outra abordagem para este problema, considera o caso em que al´em da minimiza¸cao das perdas, os retalhos dispon´veis em estoque devem ter prioridade de uso em rela¸cao aos demais objetos durante o processo de corte. A an´alise do desempenho dos procedimentos heur´sticos propostos quando somente a minimiza¸cao das perdas ´e considerada, ´e realizada com base em exemplos da literatura, exemplos pr´aticos e exemplares gerados aleatoriamente. Para os procedimentos heur´sticos que priorizam o corte dos retalhos do estoque, al´em de exemplares da literatura, simulamos uma situa¸cao em m´ultiplos per´odos na qual problemas de corte de estoque em sucessivos per´odos sao resolvidos. A cada per´odo, um problema para o per´odo seguinte ´e gerado considerando atualiza¸coes do estoque, os retalhos gerados nos per´odos anteriores e uma nova demanda de itens que ´e v gerada aleatoriamente. No caso bidimensional, tamb´em consideramos problemas em que, al´em da perda m´nima, os retalhos dispon´veis em estoque devem ter prioridade de corte em rela¸cao aos demais objetos. Para resolver este problema, altera¸coes foram realizadas na abordagem grafo E/OU e em procedimentos heur´sticos da literatura. A an´alise do desempenho dos procedimentos heur´sticos propostos considera problemas pr´aticos retirados da carteira de pedidos de uma pequena empresa de esquadrias met´alicas. Devido `a dificuldade na an´alise dos procedimentos heur´sticos desenvolvidos que consideram o aproveitamento de sobras (as solu¸coes apresentam caracter´sticas importantes e conflitantes), tamb´em apresentamos neste trabalho uma estrat´egia fuzzy para facilitar a analise das solu¸coes obtidas. Os testes computacionais sao realizados considerando os procedimentos heur´sticos desenvolvidos para os problemas de corte unidimensionais com sobras aproveit´aveis e problemas gerados aleatoriamente / Cutting stock problems consist of cutting a set of available objects in order to produce ordered items in specified amounts and sizes, in such way to optimize an objective function. Such problems have a great number of industrial applications and are widely studied in the literature. Typically, cutting problems have as main objective the minimization of the leftovers. However, since the cutting patterns quality depends directly of the sizes and amounts of the items that will be produced, in this tesis, we consider that if the present demand to generate undesirable waste (not large enough to be used, nor too small to be acceptable waste), then it is better to generate retails (not computed as waste) that will be used to produce items to meet future demands. In this way, some desirable characteristics for a good solution are defined and alterations in classical heuristic methods are presented, such that the cutting patterns with undesirable waste are altered. To the one-dimensional cutting stock problems, we developed heuristic procedures that consider the usable leftovers and preserve as main objective the minimization of the waste. Other approach for this problem considers the case in witch, beside minimal waste, the available retails in stock must be used with priority in relation to the other objects during the cutting process. The performance of the modified heuristics procedures, when only the minimal waste is considered, is observed by solving instances from the literature, practical instances and randomly generated instances. For heuristic procedures that prioritize the cut of retails of the stock, beside the instances from the literature, we simulated a situation in multiple periods in that cutting stock problems in successive periods are solved. In each period, a problem to the next period is generated considering updating of the stock, the retails generated in previous periods and a new demand of items that is randomly generated. For the two-dimensional cutting problems, we also consider problems in that, beside minimization of the waste, the available retails in stock must be used with priority vii in relation to the other objects. To solve this problem, alterations were realized in an AND/OR graph approach and in heuristic procedures of the literature. The performance of the proposed heuristics procedures is observed by solving practical instances provided by a small metallic frameworks industry. Due to difficulty in analyze the heuristic procedures developed for the cutting stock problem with usable leftover (the solutions present important and conflicting characteristics), we also present a fuzzy strategy to facilitate the analysis of the obtained solutions. The computational results are realized considering the developed heuristic procedures to the one-dimensional cutting stock problem with usable leftover and randomly generated instances