O uso de K soluções para o problema de corte de estoque com sobras aproveitáveis

Abstract

Este trabalho propõe diferentes estratégias de solução para a técnica de geração de colunas utilizada para resolver o problema de corte de estoque com sobras aproveitáveis (PCESA). Este problema consiste em atender a demanda de produção de itens solicitados por clientes a partir do corte de objetos comprados de fornecedores ou de sobras resultantes de cortes anteriores. O objetivo é de cunho econômico e visa, por exemplo, a minimização da perda gerada com o corte dos objetos. Neste problema, durante o processo de corte, sobras podem ser geradas para o estoque e não são contabilizadas como perdas. Uma técnica bastante utilizada para resolver este problema, assim como o clássico problema de corte de estoque, é o método de geração de colunas, que é um método iterativo no qual a cada iteração novas colunas (padrões de corte) são geradas a fim de encontrar a melhor solução para a relaxação linear do problema. A geração de colunas utiliza o problema da mochila para gerar as colunas que serão inseridas a cada iteração no problema de corte. Desta forma, o objetivo deste trabalho é estudar o impacto da inserção de K soluções, obtidas pelo problema da mochila em instâncias do PCESA unidimensional, a cada iteração do método de geração de colunas. Para as estratégias propostas, testes computacionais foram realizados utilizando classes de instâncias que variaram o valor de K. Os resultados mostraram que as estratégias reduzem o número de iterações e podem reduzir o tempo computacional em relação a geração de colunas padrão, quando apenas uma coluna é inserida a cada iteração .

This work proposes different solution strategies to the column generation method used to solve the cutting stock problem with usable leftovers (CSPUL). This problem consists in meeting client demands cutting objects bought from the market or leftovers resulted from previous cuts. The objective is economic and aims, for example, to minimize the total waste generated by cutting objects. In this problem, during the cutting process, leftovers can be generated for the stock and are not counted as wastes. A very useful technique to solve this problem, as well as the classic cutting stock problems, is the column generation method that is an iterative method. In each iteration of the method, new columns (cutting patterns) are generated in order to find the best solution for the linear relaxation of the problem. The column generation uses the knapsack problem to generate the columns that will be inserted at each iteration in the cutting problem. Thus, the objective of this work is to study the impact of the insertion of K solutions obtained in the knapsack problem in instances of the one-dimensional CSPUL in each iteration of the column generation method. For the proposed strategies, computational tests were performed using classes of instances that varied the k value. The results showed that the strategies reduce the number of iterations and can reduce computational time in relation to the standard column generation, when only one column is inserted at each iteration.