No presente trabalho estudamos duas variações do problema de empacotamento de itens retangulares idênticos, permitindo rotações de 90 graus, em um poliedro. Uma variação consiste em encontrar a maior quantidade de itens retangulares idênticos que podem ser empacotados em um poliedro. A outra consiste em encontrar o poliedro de um determinado tipo com menor área para empacotar uma quantidade fixa de itens retangulares idênticos. Desenvolvemos restrições de eliminação de simetrias para estes problemas, o que tornou a resolução dos mesmos mais eficiente, por métodos do tipo branch-&-bound. Estudamos também o problema de corte no qual há uma determinada demanda (de itens) a ser cortada e um conjunto de objetos disponíveis. Desejamos satisfazer a demanda minimizando o custo dos objetos utilizados e, dentre as diferentes possibilidades de se fazer isso, desejamos aquela que maximize as sobras aproveitáveis. De forma geral, sobras aproveitáveis podem ser entendidas como regiões retangulares de um objeto que possuem altura e largura iguais ou superiores a de um item de referência e representam sobras do processo de corte que podem se tornar objetos e serem reaproveitadas em um novo procedimento de corte. Apresentamos modelos de otimização em dois níveis para duas variações do problema de corte com sobras aproveitáveis a saber: o problema de corte de itens retangulares em dois estágios e o problema de corte de itens retangulares não guilhotinado. Como formas de resolver os modelos propostos, apresentamos reformulações destes modelos de programação em dois níveis em modelos de programação inteira mista. Lidamos também com uma variação do problema de corte com sobras aproveitáveis considerando a minimização da quantidade de sobras. Aplicamos restrições de eliminação de simetrias aos modelos desenvolvidos para o problema de corte de itens retangulares com sobras aproveitáveis, a fim de resolver instâncias maiores, e desenvolvemos uma estratégia de solução alternativa para os modelos. Os modelos desenvolvidos foram implementados computacionalmente e fomos capazes de resolver instâncias pequenas dos problemas em questão. / In this work we study two variations of the packing problem where identical rectangular items must be packed into a polyhedron. One of the variations consists in finding the largest amount of rectangular items that can fit in a polyhedron. The other one consists in finding a minimal area polyhedron of a certain type that packs a set of rectangular identical items. We present some symmetry-breaking constraints that reduce the computational effort in solving those problems through a branch-&-bound method. We also studied the cutting stock problem where there are some items to be cut from a set of rectangular objects and we need to satisfy the demand of items to be cut minimizing the cost of the used objects and, among the different ways of doing this, we want that which maximize the usable leftovers. Loosely speaking,usable leftovers can be understood as rectangular regions in an object that has the width and the height greater than or equal to the ones of a reference item. These leftovers can be seen as leftovers from a cutting process that will become items in a new cutting process. We present bilevel programming models to two variations of this problem with usable leftovers: the two-stage cutting stock problem of rectangular items and the non-guillotine cutting stock problem of rectangular items. In order to solve the proposed models we present also MIP reformulations of these bilevel programming problem models. We also developed some symmetry breaking constraints in order to accelerate the solving process of those models. The developed models were computationally programmed and we were able to solve small instances of the proposed problems

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-17T07:58:08Z (GMT). No. of bitstreams: 1 Porto_ClaudiaAkemiFurushima_M.pdf: 1805902 bytes, checksum: 15341772d15a37d8642fa403d27fbd6a (MD5) Previous issue date: 2010 / Resumo: O resumo poderá ser visualizado no texto completo da tese digital / Abstract: The abstract is available with the full electronic digital document / Mestrado / Teoria da Computação / Mestre em Ciência da Computação

Os problemas de empacotamento de itens irregulares são problemas de corte e empacotamento, nos quais peças irregulares de menor tamanho (que chamamos de itens) devem ser empacotados inteiramente em uma peça grande (que chamamos de placa), obedecendo a restrições de nãosobreposição e minimizando as dimensões da placa. Para garantir a não-sobreposição, fazemos uso de retas separadoras, quer dizer, retas que separam um item de outro. Apresentamos modelos de programação não-linear para problemas de empacotamentos de itens regulares e irregulares que rotacionam livremente. Os itens podem ser círculos, polígonos convexos e não-convexos. A principal vantagem dos modelos é a simplicidade, já que estes utilizam somente conceitos básicos de geometria. Usamos o algoritmo de programação não-linear IPOPT (um algoritmo de tipo de pontos interiores), que faz parte da COIN-OR, para a resolução dos problemas. Testes computacionais foram executados usando instâncias conhecidas da literatura e os resultados foram comparados com resultados apresentados na literatura, obtidos com outras metodologias que também usam rotações livre, mostrando que nossos modelos são competitivos. Propomos também o uso de parábolas separadoras para a verificação de não-sobreposição na modelagem do problema, o que pode trazer ganhos computacionais e melhor qualidade de soluções. / The irregular packing problems are cutting and packing problems, in which smaller irregular pieces (which we call items) should be packaged entirely in one large piece (which we call a plate), obeying non-overlapping constraints and minimizing the dimensions of the plate. To ensure non-overlapping, we make use of separation lines, that is, lines that separate one item from another. We present nonlinear programming models for problems of packing regular and irregular items that rotate freely. The items can be circles, convex and nonconvex polygons. The main advantage of the models is their simplicity, because they use only basic geometry concepts. We use the nonlinear programming algorithm IPOPT (an algorithm of interior points type), which is part of COIN-OR, to solve the problems. Computational tests were performed using known instances of the literature and the results were compared with results presented in the literature, obtained with other methodologies that also use free rotations, showing that our models are competitive. We also propose the use of separating parabola to avoid items overlaping in the models, which could provide greater computational eficiency as well as solutions with better quality.

Orientador: Eduardo Candido Xavier / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-23T15:26:56Z (GMT). No. of bitstreams: 1 Silveira_Tiago_M.pdf: 2498154 bytes, checksum: 4bbdff83ad5a399e1c436ffdbeb89a92 (MD5) Previous issue date: 2013 / Resumo: O resumo poderá ser visualizado no texto completo da tese digital / Abstract: The complete abstract is available with the full electronic document / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Eduardo Candido Xavier / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-24T00:15:42Z (GMT). No. of bitstreams: 1 Silveira_JeffersonLuizMoisesda_D.pdf: 2236708 bytes, checksum: 8e569408c2f068347058e36031689c3a (MD5) Previous issue date: 2013 / Resumo: Neste trabalho estamos interessados em problemas de empacotamento e roteamento. Assumindo a hipótese de que P ? NP, sabemos que não existem algoritmos eficientes para resolver tais problemas. Além de algoritmos exatos, duas das abordagens para resolver tais problemas são Algoritmos Aproximados e Heurísticas. Nesta tese mostramos algoritmos baseados nestas três abordagens para ambos os problemas, de empacotamento e roteamento. Os dois primeiros problemas atacados foram generalizações de problemas clássicos de empacotamento: O problema da mochila bidimensional e o problema de empacotamento em faixas. Estes foram generalizados adicionando restrições na forma de carregamento e descarregamento dos itens no recipiente (restrições estas, que aparecem no contexto de problemas de roteamento). O terceiro problema é uma combinação de problemas de empacotamento e roteamento. Neste caso, atacamos uma generalização do clássico Pickup and Delivery Problem. Propomos os primeiros resultados de aproximação para algumas versões dos problemas de empacotamento supracitados. Além disto, apresentamos algumas abordagens práticas para o terceiro problema. As heurísticas foram avaliadas através de experimentos computacionais comparando os seus resultados com algoritmos exatos / Abstract: In this work we are interested in packing and routing problems. Assuming P ? NP, we have that there are no efficient algorithms to deal with such problems. Besides exact algorithms, two approaches to solve such problems are Approximation Algorithms and Heuristics. In this thesis we show algorithms using these three approaches for both packing and routing problems. The first two addressed problems are generalizations of classical packing problems: The Two Dimensional Knapsack problem and the Strip Packing problem. These problems were generalized by adding constraints on the way the items can be inserted/removed into/from the bin (These constraints appear in the context of routing problems). The third problem is combination of packing and routing problems. It is a generalization of the classical Pickup and Delivery problem. We propose the first approximation results for some packing problems. Besides that, we present some practical algorithms for the third problem. The heuristics were assessed through computational experiments by comparing their results with exact algorithms / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

No presente trabalho estudamos duas variações do problema de empacotamento de itens retangulares idênticos, permitindo rotações de 90 graus, em um poliedro. Uma variação consiste em encontrar a maior quantidade de itens retangulares idênticos que podem ser empacotados em um poliedro. A outra consiste em encontrar o poliedro de um determinado tipo com menor área para empacotar uma quantidade fixa de itens retangulares idênticos. Desenvolvemos restrições de eliminação de simetrias para estes problemas, o que tornou a resolução dos mesmos mais eficiente, por métodos do tipo branch-&-bound. Estudamos também o problema de corte no qual há uma determinada demanda (de itens) a ser cortada e um conjunto de objetos disponíveis. Desejamos satisfazer a demanda minimizando o custo dos objetos utilizados e, dentre as diferentes possibilidades de se fazer isso, desejamos aquela que maximize as sobras aproveitáveis. De forma geral, sobras aproveitáveis podem ser entendidas como regiões retangulares de um objeto que possuem altura e largura iguais ou superiores a de um item de referência e representam sobras do processo de corte que podem se tornar objetos e serem reaproveitadas em um novo procedimento de corte. Apresentamos modelos de otimização em dois níveis para duas variações do problema de corte com sobras aproveitáveis a saber: o problema de corte de itens retangulares em dois estágios e o problema de corte de itens retangulares não guilhotinado. Como formas de resolver os modelos propostos, apresentamos reformulações destes modelos de programação em dois níveis em modelos de programação inteira mista. Lidamos também com uma variação do problema de corte com sobras aproveitáveis considerando a minimização da quantidade de sobras. Aplicamos restrições de eliminação de simetrias aos modelos desenvolvidos para o problema de corte de itens retangulares com sobras aproveitáveis, a fim de resolver instâncias maiores, e desenvolvemos uma estratégia de solução alternativa para os modelos. Os modelos desenvolvidos foram implementados computacionalmente e fomos capazes de resolver instâncias pequenas dos problemas em questão. / In this work we study two variations of the packing problem where identical rectangular items must be packed into a polyhedron. One of the variations consists in finding the largest amount of rectangular items that can fit in a polyhedron. The other one consists in finding a minimal area polyhedron of a certain type that packs a set of rectangular identical items. We present some symmetry-breaking constraints that reduce the computational effort in solving those problems through a branch-&-bound method. We also studied the cutting stock problem where there are some items to be cut from a set of rectangular objects and we need to satisfy the demand of items to be cut minimizing the cost of the used objects and, among the different ways of doing this, we want that which maximize the usable leftovers. Loosely speaking,usable leftovers can be understood as rectangular regions in an object that has the width and the height greater than or equal to the ones of a reference item. These leftovers can be seen as leftovers from a cutting process that will become items in a new cutting process. We present bilevel programming models to two variations of this problem with usable leftovers: the two-stage cutting stock problem of rectangular items and the non-guillotine cutting stock problem of rectangular items. In order to solve the proposed models we present also MIP reformulations of these bilevel programming problem models. We also developed some symmetry breaking constraints in order to accelerate the solving process of those models. The developed models were computationally programmed and we were able to solve small instances of the proposed problems

O problema de empacotamento de cilindros em níveis é comumente encontrado nas indústrias de cerâmica. Solucionar este problema significa encontrar o posicionamento ideal dos itens cerâmicos cilíndricos dentro do forno de modo que o menor número de fornos seja utilizado e os itens não se sobreponham e obedeçam aos limites do recipiente. Também é considerado o uso de prateleiras para que haja uma melhor ocupação do espaço do forno. Propomos uma formulação matemática não-linear inteira mista e métodos de resolução heurísticos e exato para o problema. Os métodos heurísticos consistem em escolher uma estratégia de ordenação, posicionar os itens em cada nível por meio da heurística Bottom-Left e posicionar os níveis no recipiente utilizando as estratégias Best-Fit, First-Fit ou Worst-Fit. Ao total, propomos seis variações heurísticas para resolução do problema. O método exato consiste em estimar o número de níveis e recipientes necessários e resolver o problema por meio de um solver de otimização global. Os experimentos computacionais foram realizados para um conjunto de instâncias que criamos. Os resultados mostraram que o método exato é capaz de encontrar a solução ótima em um curto período de tempo para instâncias de pequeno porte e que as heurísticas são capazes de resolver o problema em um tempo computacional baixo, para instâncias de pequeno, médio e grande porte, sendo que algumas heurísticas apresentam melhor desempenho que outras. / The cylinder packing problem in levels is commonly found in ceramic industries. Solving this problem consists in finding the ideal position of items inside furnaces so that the minimum number of furnaces is used and the items do not overlap and obeying furnaces size. In this case, it is possible to add levels to the furnace. We proposed a non-linear integer mixed mathematical model for the problem and heuristic and exact resolution methods. Heuristic methods consist of choosing a sorting strategy, packing the items at each level by a Bottom-Left heuristic, and positioning the levels in the furnace using Best-Fit, First- Fit or Worst-Fit strategy. In total, it is proposed six heuristic variations to solve the problem. The exact method consists in solving the problem by a global optimization solver. The computational experiments were run over a set of new proposed instances. The results have shown that the exact method is able to find an optimal solution in a short period of time for small instances and that the proposed heuristics are capable of solving the problem in a low computational time for small, medium and large instances. Furthermore, some of them have performed better than others.

Problemas de corte e empacotamento de itens irregulares são problemas que visam determinar um leiaute ótimo de objetos pequenos dentro de objetos maiores, a fim de atender a uma demanda. Estes problemas têm grande importância prática, já que surgem em vários tipos de indústria (como a têxtil, a de móveis e a de calçados). O problema estudado neste trabalho é o problema de corte de itens irregulares em recipientes. Os recipientes são delimitados e o objetivo é encontrar um leiaute dos objetos menores, sem sobreposição, dentro dos objetos maiores utilizando a menor quantidade de recipientes. Propomos um novo método de resolução para o problema. Nosso método é um algoritmo que gerencia um conjunto de heurísticas, de baixo nível, específicas para a resolução do problema com recipientes retangulares e irregulares. Recipientes irregulares são polígonos convexos e não convexos, que podem ser furados. As heurísticas desenvolvidas utilizam uma malha de pontos sobre a técnica de no-fit polygon para evitar a sobreposição dos itens e encontrar posições viáveis no recipiente retangular ou irregular. Os experimentos computacionais foram feitos para um grande conjunto de instâncias, de recipientes retangulares e irregulares. Os resultados demonstram a competitividade do método, que obtêm resultados bons e algumas soluções ótimas, em um tempo computacional aceitável. / Cutting and packing of irregular items are problems that aim to determine the optimum layout of small objects within larger objects (that we call bins), in order to meet a demand. These problems have great practical importance, since they emerge in various types of industry (such as textile, furniture and shoemaking). The problem studied in this work is the irregular bin packing problem. The bins are enclosed and the goal is to find a layout of items, without overlap, within the bins by using the minimum quantity of them. We propose a new method of resolution to this problem. Our method is an algorithm that manages a set of low-level heuristics, specific to solve the problem with rectangular bins and irregular bins. Irregular bins are convex and non-convex polygons, which may contain holes. The developed heuristics uses a mesh of points and the technique of no-fit polygon to avoid the overlapping of items and find feasible positions in rectangular or irregular bins. The computational experiments were performed for a large set of instances, using both rectangular and irregular bins. The results demonstrate the competitiveness of the method, which can get good results and some optimal solutions within an acceptable computational time.

O problema de empacotamento de cilindros em níveis é comumente encontrado nas indústrias de cerâmica. Solucionar este problema significa encontrar o posicionamento ideal dos itens cerâmicos cilíndricos dentro do forno de modo que o menor número de fornos seja utilizado e os itens não se sobreponham e obedeçam aos limites do recipiente. Também é considerado o uso de prateleiras para que haja uma melhor ocupação do espaço do forno. Propomos uma formulação matemática não-linear inteira mista e métodos de resolução heurísticos e exato para o problema. Os métodos heurísticos consistem em escolher uma estratégia de ordenação, posicionar os itens em cada nível por meio da heurística Bottom-Left e posicionar os níveis no recipiente utilizando as estratégias Best-Fit, First-Fit ou Worst-Fit. Ao total, propomos seis variações heurísticas para resolução do problema. O método exato consiste em estimar o número de níveis e recipientes necessários e resolver o problema por meio de um solver de otimização global. Os experimentos computacionais foram realizados para um conjunto de instâncias que criamos. Os resultados mostraram que o método exato é capaz de encontrar a solução ótima em um curto período de tempo para instâncias de pequeno porte e que as heurísticas são capazes de resolver o problema em um tempo computacional baixo, para instâncias de pequeno, médio e grande porte, sendo que algumas heurísticas apresentam melhor desempenho que outras. / The cylinder packing problem in levels is commonly found in ceramic industries. Solving this problem consists in finding the ideal position of items inside furnaces so that the minimum number of furnaces is used and the items do not overlap and obeying furnaces size. In this case, it is possible to add levels to the furnace. We proposed a non-linear integer mixed mathematical model for the problem and heuristic and exact resolution methods. Heuristic methods consist of choosing a sorting strategy, packing the items at each level by a Bottom-Left heuristic, and positioning the levels in the furnace using Best-Fit, First- Fit or Worst-Fit strategy. In total, it is proposed six heuristic variations to solve the problem. The exact method consists in solving the problem by a global optimization solver. The computational experiments were run over a set of new proposed instances. The results have shown that the exact method is able to find an optimal solution in a short period of time for small instances and that the proposed heuristics are capable of solving the problem in a low computational time for small, medium and large instances. Furthermore, some of them have performed better than others.

Problemas de corte e empacotamento de itens irregulares são problemas que visam determinar um leiaute ótimo de objetos pequenos dentro de objetos maiores, a fim de atender a uma demanda. Estes problemas têm grande importância prática, já que surgem em vários tipos de indústria (como a têxtil, a de móveis e a de calçados). O problema estudado neste trabalho é o problema de corte de itens irregulares em recipientes. Os recipientes são delimitados e o objetivo é encontrar um leiaute dos objetos menores, sem sobreposição, dentro dos objetos maiores utilizando a menor quantidade de recipientes. Propomos um novo método de resolução para o problema. Nosso método é um algoritmo que gerencia um conjunto de heurísticas, de baixo nível, específicas para a resolução do problema com recipientes retangulares e irregulares. Recipientes irregulares são polígonos convexos e não convexos, que podem ser furados. As heurísticas desenvolvidas utilizam uma malha de pontos sobre a técnica de no-fit polygon para evitar a sobreposição dos itens e encontrar posições viáveis no recipiente retangular ou irregular. Os experimentos computacionais foram feitos para um grande conjunto de instâncias, de recipientes retangulares e irregulares. Os resultados demonstram a competitividade do método, que obtêm resultados bons e algumas soluções ótimas, em um tempo computacional aceitável. / Cutting and packing of irregular items are problems that aim to determine the optimum layout of small objects within larger objects (that we call bins), in order to meet a demand. These problems have great practical importance, since they emerge in various types of industry (such as textile, furniture and shoemaking). The problem studied in this work is the irregular bin packing problem. The bins are enclosed and the goal is to find a layout of items, without overlap, within the bins by using the minimum quantity of them. We propose a new method of resolution to this problem. Our method is an algorithm that manages a set of low-level heuristics, specific to solve the problem with rectangular bins and irregular bins. Irregular bins are convex and non-convex polygons, which may contain holes. The developed heuristics uses a mesh of points and the technique of no-fit polygon to avoid the overlapping of items and find feasible positions in rectangular or irregular bins. The computational experiments were performed for a large set of instances, using both rectangular and irregular bins. The results demonstrate the competitiveness of the method, which can get good results and some optimal solutions within an acceptable computational time.