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

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

Author Costa, Calvin Rodrigues Da Autor UNIFESP Google Scholar
Advisor Nascimento, Maria Cristina Vasconcelos Autor UNIFESP Google Scholar
Institution Universidade Federal de São Paulo (UNIFESP)
Graduate program Ciência da computação
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.
Keywords Mosp
Lower Bounds
Graph Clustering Algorithms
Mosp
Limitantes Inferiores
Algoritmos De Agrupamento Em Grafos
Language Portuguese
Date 2017-02-21
Research area Otimização
Knowledge area Ciência Da Computação
Publisher Universidade Federal de São Paulo (UNIFESP)
Extent 170p.
Origin https://sucupira.capes.gov.br/sucupira/public/consultas/coleta/trabalhoConclusao/viewTrabalhoConclusao.jsf?popup=true&id_trabalho=4995855
Access rights Closed access
Type Dissertation
URI http://repositorio.unifesp.br/handle/11600/50878

Show full item record




File

File Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Search


Browse

Statistics

My Account