ProblemadoEmpacotamento

Universidade Federal de Minas Gerais
Departamento de Ciência da Computação

P
ROBLEMA DO
EMPACOTAMENTO
(
BIN PACKING
)

Bruno Fonseca [e-mail] Giuliene Gomes [e-mail] Vinicius Morais [e-mail] Belo Horizonte
23 de junho de 2015

Sumário

Introdução ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 2 Definição do problema ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 2 Bin Packing unidimensional ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 3 Aplicação ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 4 Alocação em canais de TV ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 4 Alocação de programas em discos e fitas magnéticas ­­­­­­­­­­­­­ 4 Problema de programação em veículos ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 4 Metodologia ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 5

Heurística
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­
5 First­Fit­Decrasing ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 5 Ótimo ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 6 Testes ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 6 Conclusão ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 8 Bibliografia ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 8

1

Introdução

Atualmente, diversas indústrias se deparam com o problema do empacotamento no decorrer de seu processo produtivo. Este problema tem grande aplicabilidade no carregamento de caminhões e aviões, onde o ideal é que caiba o máximo possível de produtos e a utilização do mínimo possível de meios de transporte.
Em síntese, o problema do empacotamento consiste em empacotar itens de diferentes volumes em um número finito