Author(s): Pereira, José Miguel Ribeiro Pinhão
Date: 2013
Persistent ID: http://hdl.handle.net/1822/28509
Origin: RepositóriUM - Universidade do Minho
Project/scholarship: info:eu-repo/grantAgreement/FCT/5876-PPCDTI/100645/PT ;
Subject(s): Problemas de empacotamento a duas dimensões; Heurística de melhor encaixe; Two-dimensional bin packing problems; Best-fit heuristic; 519.863
Dissertação de mestrado em Engenharia de Sistemas
Nesta dissertação é apresentada uma heurística de melhor encaixe para um problema de empacotamento a duas dimensões. Este problema faz parte de um conjunto mais vasto de problemas de corte e empacotamento que são estudados em Investigação Operacional, e têm aplicação prática nas mais diversas áreas industriais. São analisados diferentes modelos de empacotamento a duas dimensões. A heurística foi desenhada com base no modelo de melhor encaixe, e deu origem a uma ferramenta de software de optimização do planeamento de corte de matéria-prima. O desenvolvimento desta ferramenta foi inspirado por um caso real de uma empresa portuguesa de instalação de revestimentos, tendo como objectivo a optimização do processo de planeamento de corte de matéria-prima. Foram realizados testes computacionais sobre a ferramenta desenvolvida tendo como referência um conjunto de instâncias reais, que permitiram aferir o nível qualitativo das soluções obtidas pela heurística face à qualidade das soluções reais existentes.
In this work, a best-fit heuristic for a two-dimensional bin packing problem is presented. This problem is part of a wider set of cutting and packing problems studied in the field of Operations Research, having multiple applications in various industrial environments. A series of two-dimensional cutting and packing problems is analysed. Namely, level packing models, level and stack packing models and free cutting models. Furthermore, several resolution models are studied for the problems mentioned above. The best-fit heuristic for two-dimensional bin packing problems was designed having the best-fit model as a starting point, and was integrated in the development of an industrial software tool for raw material cutting optimization. The development of the industrial tool was inspired by the real case of a portuguese surface industry. The heuristic implemented was submitted to several software tests based on a set of real instances, that permitted to generate a benchmark capable of traducing the quality of the solutions obtained by the heuristic versus the initial existing results.
Fundação para a Ciência e a Tecnologia (FCT) - (PIDDAC).
Fundo Europeu de Desenvolvimento Regional (FEDER) atrav és do COMPETE - Programa Operacional Factores de Competitividade (POFC).
Projeto "SearchCol - Metaheuristic search by column generation" (PTDC/EIA-EIA/100645/2008).
