Agrupamento Em Grafos Para A Decomposição Do Problema De Minimização De Pilhas Abertas

Abstract

The Minimization of Open Stacks Problem (MOSP) consists on determining a se- quence of cut patterns to meet the demands of items in a cutting industry. This ope- rational planning problem is NP-hard and empirical tests on the behavior of exact methods to solve it indicates that to proof the optimality of the solutions for certain instances is very time-consuming. This difficulty is perhaps due to the existence of several alternative solutions with the same objective function value. This Dissertation refers to this phenomenon as degeneration. To avoid or reduce the influence of the ob- served degeneration and, consequently, to reduce the computational time of proving the optimality of the solutions, we proposed to decompose the problem represented in a graph by clustering strategies. Each of the components of the decomposition defines a smaller MOSP subproblem and, by solving these subproblems, it is possi- ble to infer faster, from the computational point of view, regarding lower limits and, eventually, to obtain optimal solutions for the original problem. In addition, lower bounds are generated by proposing strategies to collapse edges of the MOSP graph. In computational experiments, benchmark instances were used to evaluate the results obtained by the proposed strategies. The method that performs edge collapses in the MOSP graph and identifies its lower bound by assessing the degrees of the nodes of the resulting graph provided the best results, although it has presented weak bounds for sparse instances. The HSMY method, which employs a graph clustering heuristic from the literature to decompose the problem, has presented the best lower bounds for sparse instances.

O problema de minimização de pilhas abertas (MOSP), do inglês, Minimization of Open Stacks Problem consiste na determinação de uma sequência de padrões de corte para atender as demandas dos itens em uma indústria de corte. Este problema de planejamento operacional é da classe NP-difícil e testes empíricos sobre o compor- tamento de algoritmos exatos para resolvê-lo apontam uma demora na prova da otimalidade das soluções para determinadas instâncias. Atribui-se a essa dificuldade, a existência de diversas soluções alternativas com mesmo valor de função objetivo. Nesta Dissertação, refere-se a esse fenômeno como degeneração. Para evitar ou dimi- nuir a influência das degenerações observadas e, consequentemente, tornar menos custosa computacionalmente a prova de otimalidade das soluções, propõe-se decom- por o problema representado em um grafo, por estratégias de agrupamento em gra- fos. Cada uma das componentes da decomposição define um subproblema MOSP de menor tamanho e, resolvendo estes subproblemas, pode-se inferir mais rapidamente, do ponto de vista computacional, a respeito de limitantes inferiores e, eventualmente, obter soluções ótimas para o problema original. Além disso, geram-se limitantes in- feriores propondo estratégias para colapsar arestas do grafo MOSP. Nos experimen- tos computacionais, empregaram-se instâncias benchmark da literatura para avaliar os resultados obtidos pelas estratégias propostas. O método que realiza colapsos de arestas no grafo MOSP e identifica o limitante pelos graus dos nós do grafo resul- tante forneceu melhores resultados, embora tenha apresentado limitantes fracos para instâncias pouco densas. O método HSMY, que emprega uma heurística de agrupa- mento em grafos da literatura para decompor o problema, foi o que apresentou os melhores limitantes para as instâncias menos densas.