Dissertação

{en_GB=Efficient meta-heuristics for multi-and-many objective Bin Packing Problems} {} EVALUATED

{pt=O problema do empacotamento é um otimização combinatória que faz parte da família de corte e empacotamento. Este problema tem aplicação em vários campos, desde o empacotamento em caixas até à alocação de recursos em diferentes áreas. O principal objectivo deste problema é minimizar o número de entidades necessárias para inserir todos os itens. Hoje em dia, devido aos avanços tecnológicos, todas as indústrias começam-se a focar na recolha e análise de dados, direcionando as suas ações de modo a otimizar todas as suas operações e consequentemente a rentabilidade. O Problema do Empacotamento, que começou a ser estudado nos anos 60, recentemente começou a ser aplicado em problemas com multi-and-many objectivos. Isto permitiu a resolução de combinações de várias funções objectivo, tentando encontrar o equilíbrio entre as diversas soluções, e aumentando assim as possibilidades em áreas relacionadas com cargas ou alocações em memórias virtuais, sendo esta ultima aplicação um bom exemplo do impacto dos avanços tecnológicos na Indústria 4.0. Este paper explora o cenário de várias otimizações combinatórias, contextualizando o problema do empacotamento dentro da investigação operacional. Igualmente, a plataforma PlatEMO é introduzida, e o seu conjunto de problemas combinatórios utilizado como paralelismo para a construção de um problema de empacotamento com multi-and-many objectivos. Por último, a introdução das metaheurísticas estudadas e a sua comparação é apresentada ao leitor, baseando o estudo em métricas para avaliar a sua eficiência e eficácia, bem como a sua influencia no problema de empacotamento., en=The Bin Packing Problem (BPP) is a specific combinatorial problem inside Cutting and Packing Problems (C&P), having a large impact in several industries with practical applications from packing boxes, to scheduling and resource allocation. The main goal of BPP is to minimize the number of entities where the items will be placed, finding the best way of storing them. Today, as computing capacity and processing speed increases, all industries are moving towards data collection and optimization. Therefore, more data can be analysed and better results achieved. The BPP has been studied since the 60s, but, just recently started to appear in papers focusing on its multi-and-many objective formulations, balancing different combinations and trade-offs of minimizing other goals important to areas such as cargo loading or virtual memory allocations, being a good example of the computational advances impact in the different industries. This paper describes the background of several Combinatorial Problems, contextualizing the BPP inside the Operations Research (OR) field, providing knowledge about other C&P and their usage. Furthermore, it introduces the PlatEMO framework together with its combinatorial multi-and-many objective problems suite, that are used as a parallelism to study and introduce: the 3D-BPP with many-and-multi objectives; the meta-heuristics selected to be studied and to solve the problem; and the metrics used to evaluate its solutions. Lastly, the reader is presented with the comparison of the different metaheuristics studied during this paper and their application in the multi-and-many objective Bin Packing Problem (mBPP) developed.}
{pt=Otimização Combinatória, Corte e Empacotamento, Problema do Empacotamento, Meta-heuristicas, Algoritmos Evolucionários., en=Combinatorial Optimization, Cutting and Packing, Bin Packing Problem, Meta-heuristics, Evolutionary Algorithms}

Maio 22, 2020, 0:0

Orientação

ORIENTADOR

Susana Margarida da Silva Vieira

Departamento de Engenharia Mecânica (DEM)

Professor Auxiliar

ORIENTADOR

José Rui De Matos Figueira

Departamento de Engenharia e Gestão (DEG)

Professor Associado