Algoritmos de aproximação para o problema do empacotamento de soma mínima bidimensional [recurso eletrônico]
Rachel Vanucchi Saraiva
DISSERTAÇÃO
Português
T/UNICAMP Sa71a
[Approximation algorithms for the two-dimensional min-sum bin packing problem]
Campinas, SP : [s.n.], 2023.
1 recurso online ( p.) : il., digital, arquivo PDF.
Orientador: Rafael Crivellari Saliba Schouery
Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
Resumo: Este trabalho trata da variante de soma mínima do problema do empacotamento para itens quadrados, em que uma lista de itens quadrados deve ser empacotada em recipientes quadrados indexados de dimensões 1 x 1. O custo de empacotar cada item é igual ao índice do recipiente em que é empacotado...
Ver mais
Resumo: Este trabalho trata da variante de soma mínima do problema do empacotamento para itens quadrados, em que uma lista de itens quadrados deve ser empacotada em recipientes quadrados indexados de dimensões 1 x 1. O custo de empacotar cada item é igual ao índice do recipiente em que é empacotado e o objetivo é minimizar o custo total de empacotar todos os itens. O problema tem aplicações na minimização do tempo médio de operações logísticas como corte e entrega de produtos. Neste trabalho provamos que algoritmos clássicos para empacotamento bidimensional que ordenam os itens em ordem não-crescente de tamanho, como Hybrid First Fit, têm desempenho arbitrariamente ruim quando aplicados a esse problema. Apresentamos, então, uma 5/2-aproximação e um PTAS
Ver menos
Abstract: This work addresses the min-sum variant of the bin packing problem for square items, where a list of square items has to be packed into indexed square bins of dimension 1 x 1. The cost of packing each item is equal to the index of the bin in which it is placed and the objective is to...
Ver mais
Abstract: This work addresses the min-sum variant of the bin packing problem for square items, where a list of square items has to be packed into indexed square bins of dimension 1 x 1. The cost of packing each item is equal to the index of the bin in which it is placed and the objective is to minimize the total cost of packing all items. The problem has applications in minimizing the average time of logistic operations such as cutting stock and delivery of products. We prove that classic algorithms for two-dimensional bin packing that order items in non-increasing order of size, such as Hybrid First Fit, can have an arbitrarily bad performance for this variant. We, then, present a 5/2-approximation and a PTAS for the problem
Ver menos
Requisitos do sistema: Software para leitura de arquivo em PDF
Algoritmos de aproximação para o problema do empacotamento de soma mínima bidimensional [recurso eletrônico]
Rachel Vanucchi Saraiva
Algoritmos de aproximação para o problema do empacotamento de soma mínima bidimensional [recurso eletrônico]
Rachel Vanucchi Saraiva