Problemas de Corte e Empacotamento: Uma abordagem em Grafo E/OU
O problema de corte consiste no corte de objetos maiores para produção de peças menores, de modo que uma certa função objetivo seja otimizada, por exemplo, a perda seja minimizada. O problema de empacotamento pode também ser visto como um problema de corte, onde as peças menores são arranjadas dentr...
| Autor: | |
|---|---|
| Tipo de documento: | Tesis doctoral |
| Estado: | Published version |
| Fecha de publicación: | 2000 |
| País: | Brasil |
| Institución: | USP |
| Repositorio: | Biblioteca Digital de Teses e Dissertações da USP |
| Lenguaje: | Portugués |
| OAI Identifier: | oai:teses.usp.br:tde-12042016-153927 |
| Acceso en línea: | http://www.teses.usp.br/teses/disponiveis/55/55134/tde-12042016-153927/ |
| Nivel de acceso: | Acceso abierto |
| Palabra clave: | AND/OR-graph search Busca em grafo E/OU Combinatorial optimization Cutting and packing problems Heurísticas. Heuristics. Otimização combinatória Problemas de corte e empacotamento |
| _version_ | 1878750526913380352 |
|---|---|
| author | Vianna, Andréa Carla Gonçalves |
| author_browse | Vianna, Andréa Carla Gonçalves |
| author_facet | Vianna, Andréa Carla Gonçalves |
| author_role | author |
| collection | Biblioteca Digital de Teses e Dissertações da USP |
| description | O problema de corte consiste no corte de objetos maiores para produção de peças menores, de modo que uma certa função objetivo seja otimizada, por exemplo, a perda seja minimizada. O problema de empacotamento pode também ser visto como um problema de corte, onde as peças menores são arranjadas dentro dos objetos. Uma abordagem em grafo E/OU para a resolução de problemas de corte e empacotamento foi proposta inicialmente por Morabito (1989) para problemas de corte bidimensionais e, mais tarde, estendida para problemas tridimensionais (Morabito, 1992). Nesta abordagem foi utilizada uma técnica de busca híbrida, onde se combinou a busca em profundidade primeiro com limite de profundidade e a busca hill-climbing, utilizando-se heurísticas baseadas nos limitantes superiores e inferiores. Experiências computacionais mostraram a viabilidade de uso na prática desta abordagem. Mais tarde, Arenales (1993) generalizou esta a abordagem em grafo E/OU mostrando como diferentes problemas de corte poderiam ser resolvidos, independentemente da dimensão, formas dos objetos e itens, baseado em simples hipóteses, sem realizar, entretanto, estudos computacionais. O presente trabalho tem por objetivo estender a abordagem em grafo E/OU para tratar outros casos não analisados pelos trabalhos anteriores, tais como situações envolvendo diferentes processos de corte, bem como a implementação computacional de métodos baseados na abordagem em grafo E/OU, mostrando, assim, a versatilidade da abordagem para tratar diversas situações práticas de problemas de corte e sua viabilidade computacional. |
| eu_rights_str_mv | openAccess |
| format | doctoralThesis |
| id | BR_0f97fc91c05a779fb64cf3f11c8a7dcf |
| institution | USP |
| instname_str | Universidade de São Paulo (USP) |
| language | por |
| network_acronym_str | BR |
| network_name_str | Brasil |
| oai_identifier_str | oai:teses.usp.br:tde-12042016-153927 |
| publishDate | 2000 |
| publishDateSort | 2000 |
| publisher | Biblioteca Digitais de Teses e Dissertações da USP |
| publisherStr | Biblioteca Digitais de Teses e Dissertações da USP |
| reponame_str | Biblioteca Digital de Teses e Dissertações da USP |
| spelling | Problemas de Corte e Empacotamento: Uma abordagem em Grafo E/OU Cutting and packing problems: an AND/OR-Graph approach Vianna, Andréa Carla Gonçalves AND/OR-graph search Busca em grafo E/OU Combinatorial optimization Cutting and packing problems Heurísticas. Heuristics. Otimização combinatória Problemas de corte e empacotamento O problema de corte consiste no corte de objetos maiores para produção de peças menores, de modo que uma certa função objetivo seja otimizada, por exemplo, a perda seja minimizada. O problema de empacotamento pode também ser visto como um problema de corte, onde as peças menores são arranjadas dentro dos objetos. Uma abordagem em grafo E/OU para a resolução de problemas de corte e empacotamento foi proposta inicialmente por Morabito (1989) para problemas de corte bidimensionais e, mais tarde, estendida para problemas tridimensionais (Morabito, 1992). Nesta abordagem foi utilizada uma técnica de busca híbrida, onde se combinou a busca em profundidade primeiro com limite de profundidade e a busca hill-climbing, utilizando-se heurísticas baseadas nos limitantes superiores e inferiores. Experiências computacionais mostraram a viabilidade de uso na prática desta abordagem. Mais tarde, Arenales (1993) generalizou esta a abordagem em grafo E/OU mostrando como diferentes problemas de corte poderiam ser resolvidos, independentemente da dimensão, formas dos objetos e itens, baseado em simples hipóteses, sem realizar, entretanto, estudos computacionais. O presente trabalho tem por objetivo estender a abordagem em grafo E/OU para tratar outros casos não analisados pelos trabalhos anteriores, tais como situações envolvendo diferentes processos de corte, bem como a implementação computacional de métodos baseados na abordagem em grafo E/OU, mostrando, assim, a versatilidade da abordagem para tratar diversas situações práticas de problemas de corte e sua viabilidade computacional. The cutting problem consists of cutting larger objects in order to produce smaller pieces, in such a way as to optimizing a given objective function, for example, minimizing the waste. The packing problem can also be seen as a cutting problem, where the position that each smaller piece is arranged inside of the objects can be seen as the place it was cut from. An AND/OR-graph approach to solve cutting and packing problems was initially proposed by Morabito (1989) for two-dimensional cutting problem and, later, extended to threedimensional problems (Morabito, 1992). That approach uses a hybrid search, which combines depth-first search under depth bound and hill-climbing strategy. Heuristics were devised based on upper and lower bounds. Computational experiences demonstrated its practical feasibility. The AND/OR-graph approach was later generalized by Arenales (1993) based on simple hypothesis. He showed that different cutting problems Gould be solved using the AND/ORgraph approach, independently of the dimension and shapes. The main objective of this thesis is the practical extension of the AND/OR-graph approach to handle other cases not considered by previous works. It was considered different cutting processes, as well as the analysis of computational implementation, showing how can it be adapted to many classes of practical cutting and packing problems. Biblioteca Digitais de Teses e Dissertações da USP http://www.teses.usp.br/teses/disponiveis/55/55134/tde-12042016-153927/ |
| spellingShingle | Problemas de Corte e Empacotamento: Uma abordagem em Grafo E/OU Vianna, Andréa Carla Gonçalves AND/OR-graph search Busca em grafo E/OU Combinatorial optimization Cutting and packing problems Heurísticas. Heuristics. Otimização combinatória Problemas de corte e empacotamento |
| status_str | publishedVersion |
| title | Problemas de Corte e Empacotamento: Uma abordagem em Grafo E/OU |
| title_full | Problemas de Corte e Empacotamento: Uma abordagem em Grafo E/OU |
| title_fullStr | Problemas de Corte e Empacotamento: Uma abordagem em Grafo E/OU |
| title_full_unstemmed | Problemas de Corte e Empacotamento: Uma abordagem em Grafo E/OU |
| title_short | Problemas de Corte e Empacotamento: Uma abordagem em Grafo E/OU |
| title_sort | Problemas de Corte e Empacotamento: Uma abordagem em Grafo E/OU |
| topic | AND/OR-graph search Busca em grafo E/OU Combinatorial optimization Cutting and packing problems Heurísticas. Heuristics. Otimização combinatória Problemas de corte e empacotamento |
| topic_facet | AND/OR-graph search Busca em grafo E/OU Combinatorial optimization Cutting and packing problems Heurísticas. Heuristics. Otimização combinatória Problemas de corte e empacotamento |
| url | http://www.teses.usp.br/teses/disponiveis/55/55134/tde-12042016-153927/ |