Modelos e métodos de otimização para problemas de corte e empacotamento a duas dimensões

Abstract

Nesta tese, propõem-se modelos e métodos de otimização para problemas de corte e empacotamento a duas dimensões. Os problemas de corte e empacotamento são problemas com os quais muitas indústrias têm de lidar no decorrer do seu processo produtivo. De um modo genérico estes problemas consistem na divisão de um recurso, materiais sólidos no caso do corte e espaço utilizável no caso do empacotamento, em partes mais pequenas otimizando um determinado objetivo. Diferentes variantes e objetivos podem ser considerados dependendo das aplicações onde o problema tem origem. Devido a sua vasta aplicabilidade estes problemas têm sido muito estudados nas últimas décadas. Nesta tese, são propostos novos modelos de programação inteira com tamanho pseudo-polinomial para diferentes variantes do problema de corte bidimensional e para o problema integrado de corte bidimensional e dimensionamento de lotes. É também proposta uma aplicação de um algoritmo SearchCol (pesquisa meta-heurística por geração de colunas), que combina geração de colunas com meta-heurísticas ao problema de empacotamento bidimensional. O primeiro problema de corte estudado tem restrições de guilhotina e limitação no número de cortes (estágios) possíveis. Para este problema apresenta-se um modelo de programação inteira cujo tamanho, como se prova, e pseudo-polinomial. Neste modelo cada variável de decisão está associada com o corte de um item de uma placa ou de parte de uma placa, que resulte de cortes anteriores (placas residuais). Além das restrições de guilhotina e do número de estágios foram estudadas outras variantes do problema. O modelo de programação inteira proposto foi estendido para o problema de corte bidimensional também estagiado em que se permite a rotação dos itens, para o problema de corte em que os itens podem ser cortados de placas com tamanhos diferentes, para o problema de minimizar o tempo despendido no corte dos itens das placas, para o problema de minimizar os desperdícios e ainda para o problema de corte bidimensional onde se atribuem valores as placas residuais de sobra. O estudo dos problemas de corte não pode ser analisado de uma forma isolada no processo produtivo, al em disso resolver um problema de corte em cada período de planeamento, pode resultar em soluções de fraca qualidade, isto é, com desperdício excessivo, quando considerado um conjunto de períodos de planeamento. Com o objetivo de abordar esta característica e estudado também o problema integrado de corte bidimensional e dimensionamento de lotes. Para este problema são apresentados dois modelos de programação inteira. O problema de empacotamento bidimensional foi também estudado e para a sua resolução foi utilizado um algoritmo SearchCol, que tem por base um novo modelo de decomposição para o problema de empacotamento bidimensional. Testes computacionais foram realizados para todos os modelos de programação inteira propostos e para a aplicação do SearchCol ao problema de empacotamento bidimensional, para tal foram utilizadas instâncias reais provenientes da indústria do mobiliário e instâncias da literatura. De um modo geral, os resultados computacionais comprovam a e ciência dos modelos e métodos propostos.

In this thesis, optimization models and methods are proposed for the two dimensional cutting stock and bin packing problems. The cutting and packing problems are problems that many industries have to deal during the production process. Generally these problems consist in a division of a resource in small parts, solid materials in the case of cutting and usable space in the case of packaging, in order to optimize a certain objective. Different variants and objectives may be considered depending on the applications where the problem appeared. Due to the wide applicability of these problems, they have been very studied in recent decades. In this thesis, new models of integer programming pseudo-polynomial in size are proposed for different variants of the two-dimensional cutting stock problem and for the integrated two-dimensional cutting stock and lot sizing problems. It is also proposed an application of an algorithm SearchCol (metaheuristic search by column generation), which combines column generation with meta-heuristics, to the two-dimensional bin packing problem. Firstly it is studied the two-dimensional cutting stock problem with guillotine constraints and with a limitation in the number of possible cuts (stages). For this problem, it is proposed an integer programming model, which size is proved to be pseudo-polynomial. In this model each decision variable is associated with cutting an item from a plate or from a part of a plate, resulting from previous cuts (residual plate). Besides the guillotine and the number of stages constraints, other variants of the problem have been studied. The proposed integer programming model was extended to the two-dimensional cutting stock problem also staged, which allows items rotation, for the cutting stock problem in which the items can be cut form plates with different sizes, for the problem of minimizing the time spent in the cutting process of the items from the plates, for the problem of minimizing the wastage and also for the cutting stock problem in which values are assigned to the residual plates. The study of the cutting stock problems cannot be analysed in isolated way in the production process, also solving a cutting stock problem in each planning period, can result in poor quality solutions, i.e., with excessive waste, when considered a set of planning periods. In order to address this feature, it is also studied the integrated two-dimensional cutting stock and lot-sizing problem. For this problem are proposed two integer programming models. The two-dimensional bin packing problem has also been studied and for solving it a SearchCol algorithm was used, which is based on a new decomposition model for the two-dimensional bin packing problem. Computational tests were conducted for all the proposed integer programming models and for the application of the SearchCol to the two-dimensional bin packing problem, real instances from furniture companies and instances from the literature are used. Generally, the computational results prove the efficiency of the proposed models and methods.