Orientador: Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T17:20:46Z (GMT). No. of bitstreams: 1
Silva_FabricioLuisSantosda_M.pdf: 657410 bytes, checksum: 65ac7a297f6547a9ac70dfa42604f1ce (MD5)
Previous issue date: 2010 / Resumo: Neste trabalho lidamos com o problema de Empacotamento em Faixa Bidimensional considerando o caso em que os itens devem ser dispostos de forma a manter o empacotamento estável e satisfazer uma ordem de descarregamento imposta. Consideramos o caso em que a orientação dos itens é fixa. Definimos uma metodologia para analisar a estabilidade do empacotamento observando as condições de equilíbrio estático para corpos rígidos. Desenvolvemos heurísticas e formulamos um programa linear inteiro para o problema de Empacotamento em Faixa sujeito a tais restrições. A resolução da formulação inteira ocorre através de uma estratégia do tipo branch-and-cut. As restrições de estabilidade foram inseridas como planos de corte de maneira a remover empacotamentos que não são estáveis. Em nossos experimentos computacionais, vemos que o modelo proposto é adequado para lidar com instâncias de pequeno até médio porte, dentro de um tempo computacional razoável / Abstract: This paper investigates the Two-Dimensional Strip Packing Problem considering the case in which the items should be arranged to form a stable packing and satisfy an order of unloading, so that after unloading, the packing is still stable. We consider the case where the items are oriented and rotations are not allowed. We present a methodology to analyze the stability of the packing observing the conditions for static equilibrium of rigid bodies. We present heuristics and formulate an integer linear programming model for the Strip Packing problem considering such constraints. To solve the integer formulation, we develop a branch-and-cut approach. For each integer solution obtained during the branch-and-cut algorithm, corresponding to a non-stable packing, we insert a cutting plane for which this integer solution is not satisfied. In our computational experiments, we see that the proposed model is suitable to deal with small and mid-sized instances. Some optimal solutions were obtained after few hours of CPU processing / Mestrado / Mestre em Ciência da Computação
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.unicamp.br:REPOSIP/275720 |
| Date | 19 August 2018 |
| Creators | Silva, Fabrício Luis Santos da |
| Contributors | UNIVERSIDADE ESTADUAL DE CAMPINAS, Miyazawa, Flávio Keidi, 1970-, Neto, Reinaldo Morabito, Xavier, Eduardo Candido |
| Publisher | [s.n.], Universidade Estadual de Campinas. Instituto de Computação, Programa de Pós-Graduação em Ciência da Computação |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | 76 f. : il., application/octet-stream |
| Source | reponame:Repositório Institucional da Unicamp, instname:Universidade Estadual de Campinas, instacron:UNICAMP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0024 seconds