Problema do empacotamento

Origem: Wikipédia, a enciclopédia livre.
(Redirecionado de First fit)
Saltar para a navegação Saltar para a pesquisa
Wikitext.svg
Esta página ou seção precisa ser wikificada (desde junho de 2017).
Por favor ajude a formatar esta página de acordo com as diretrizes estabelecidas.

No problema de bin packing (ou problema do empacotamento), objetos de diferentes volumes devem ser embalados em um número finito de bandejas ou recipientes de volume V de uma forma que minimize o número de recipientes utilizados. Na teoria da complexidade computacional, este é um problema de combinatória NP-difícil.[1] O problema de decisão (decidir se um determinado número de pacotes é o ideal) é NP-completo.[2]

Existem muitas variações deste problema, tais como empacotamento 2D (2D packing), empacotamento linear (linear packing), empacotamento por peso (packing by weight), empacotamento por custo (packing by cost), e assim por diante. Eles têm muitas aplicações, tais como o enchimento de recipientes, carregamento de caminhões com peso com capacidade restrita, criação de arquivo de backup (cópias de segurança) em mídia.

O problema  do empacotamento também pode ser visto como um caso especial do problema de corte de estoque (cutting stock problem). Quando o número de pacotes é restrito a 1 e cada item é caracterizado por um volume e um valor, o problema de maximização do valor dos itens que podem caber na lixeira é conhecida como a problema da mochila.

Apesar do fato de que o problema do empacotamento tem uma complexidade computacional uma NP-difícil, as melhores soluções para grandes instâncias do problema pode ser produzido com algoritmos sofisticados. Além disso, muitas heurísticas foram desenvolvidas: por exemplo, o algoritmo de first fit fornece uma solução rápida, mas muitas vezes não ideal, envolvendo colocar-se cada item para a primeira posição que couber. Ele requer custo de tempo Θ(n log n), onde n é o número de elementos a ser empacotados. O algoritmo pode ser tornado mais eficaz se primeiramente  ordenar a lista de elementos em ordem decrescente (às vezes conhecida como o algoritmo first-fit decrescente), embora isso ainda não garante uma solução ótima, e para longas listas pode aumentar o tempo de execução do algoritmo. Sabe-se, contudo, que existe sempre pelo menos um ordenamento de itens que o first-fit produzir uma solução ótima.[3]

Um variante do bin packing que ocorre na prática é quando os itens podem compartilhar o espaço quando empacotados em uma caixa. Especificamente, um conjunto de itens pode ocupar menos espaço quando embaladas em conjunto do que a soma de seus tamanhos individuais. Esta variante é conhecida como VM packing[4] desde quando máquinas virtuais (VMs) são embaladas em um servidor, o total de sua memória gerenciada pode diminuir devido às páginas compartilhadas pelas VMs as quais precisam ser armazenados apenas uma vez. Se os itens podem dividir o espaço de maneiras arbitrárias, o problema do empacotamento é difícil, mesmo de forma aproximada. No entanto, se o compartilhamento de espaço se encaixa em uma hierarquia, como é o caso de compartilhamento de memória em máquinas virtuais, o problema do empacotamento pode ser eficientemente aproximado.

Declaração Formal[editar | editar código-fonte]

Dado um conjunto de pacotes (bins)  de um mesmo tamanho e uma lista de  itens com tamanhos  para empacotar, encontre um numero inteiro de bins  e uma -partição  do conjunto  tal que   A solução é ótimo se possui um . O valor de para uma solução ótima é denotado como OPT abaixo. Uma possível formula mesclada de programação linear com inteiros é:

minimize
subject to

onde se pacote  for usado e e então  é colocado no pacote .[5]

Algoritmo de first-fit[editar | editar código-fonte]

Este é um algoritmo de aproximação muito simples, o algoritmo guloso. O algoritmo processa os itens em ordem arbitrária. Para cada item, ele tenta colocar o item no primeiro pacote que pode acomodá-lo. Se nenhum pacote é encontrado, ele abre um novo pacote e coloca o item dentro deste novo pacote.

É bastante simples para mostrar este algoritmo, obtém-se um fator de aproximação de 2, isto é, o número de pacotes utilizados por este algoritmo não é mais do que duas vezes o número ideal. Em outras palavras, é impossível para 2 pacotes estarem preenchidos no máximo pela metade, pois tal possibilidade implica que em algum ponto, exatamente um pacote foi no máximo cheio até a metade e um nov foi aberto para acomodar um item de tamanho de no máximo V/2. Mas desde que o primeiro tem, pelo menos, um espaço de V / 2, o algoritmo não abrirá um novo pacote para qualquer item cujo tamanho é de, no máximo, V / 2. Só depois de o pacote encher-se com mais do que o V / 2, ou se um item com um tamanho maior do que o V / 2 chega, o algoritmo pode abrir uma nova posição.

Assim, se temos B bandejas, pelo menos B − 1 bandejas estão cheias mais que a metade do total. Portanto, . Porque é um limite inferior do valor ideal OPT, temos que B − 1 < 2OPT e, portanto, B ≤ 2OPT.[6] Veja a análise abaixo para uma melhor aproximação dos resultados.

Prova alternativa:

Suponha que o algoritmo guloso retorna mais de 2 OPT pacotes. Se tomarmos quaisquer dois pacotes sucessivos, juntos, eles devem conter, pelo menos, V de itens (caso contrário, apenas um pacote seria o suficiente para estes itens). Desde que nós temos, no mínimo, OPT pares mais pacotes extra, nós, em conjunto, teríamos mais do que OPT V itens, que seria uma contradição.

Análise de algoritmos aproximados[editar | editar código-fonte]

As estratégias best fit e o first fit estão entre os mais simples algoritmos heurísticos para resolver o problema do empacotamento. Eles foram provados que não utilizam mais de 11/9 OPT + 1 pacotes (onde OPT é o número de posições dadas pela solução ótima).[7] O mais simples destes, a estratégia First Fit Decrescente(FFD), onde opera primeiramente ordenando os itens a serem inseridos em ordem decrescente por seus tamanhos e, em seguida, inserir cada item para o primeiro pacote na lista com espaço suficiente restante. Às vezes, no entanto, não se tem a opção de classificar a entrada, por exemplo, quando nos deparamos com um problema online de empacotamento. Em 2007, foi comprovado que o limite 11/9 OPT + 6/9 para a FFD é Grande-O.[8] MFFD[9] (uma variante do FFD) não usa mais do que 71/60 OPT + 1 pacotes[10] (i.e. delimitada por cerca de 1.18 OPT, em comparação com cerca de 1,22 OPT por FFD). Em 2013, Sgall e Dósa deu um limitante superior para a estratégia first-fit (FF), mostrando que ele nunca precisa mais do que 17/10 OPT posições, para qualquer entrada.

É NP-difícil para distinguir se OPT é 2 ou 3, assim, para todo ε > 0, problema do empacotamento é difícil de aproximar cerca de 3/2 − ε. (Se tal aproximação, existe, pode determinar se n inteiros não negativos pode ser particionado em dois conjuntos com a mesma soma em tempo polinomial. No entanto, esse problema é conhecido por ser NP-difícil.) Consequentemente, o problema do empacotamento não tem um esquema de tempo polinomial de aproximação (APMS), a menos que P = NP. Por outro lado, para qualquer 0 < ε ≤ 1, é possível encontrar uma solução usando não mais do que (1 + ε)OPT + 1 pacote em tempo polinomial. Este tipo de aproximação é conhecida como assintótico PTAS.[11][12]

Algoritmo exato[editar | editar código-fonte]

Martello e Toth[13] desenvolveram um algoritmo exato para o 1-D problema do empacotamento, chamado de MTP. Uma alternativa mais rápida é a algoritmo Conclusão de Pacotes (Bin Completion) proposto por Korf, em 2002,[14] e, mais tarde, melhorado;[15] este segundo livro relata o tempo médio para resolver um milhão de ocorrências, com 80 itens em um 440 MHz Sun Ultra com 10 workstation foi de 31 ms.

Outra melhoria foi apresentada por Schreiber e Korf em 2013.[16] A novo e melhorado algoritmo Conclusão de Pacotes é mostrado para ser de até cinco ordens de magnitude mais rápido que Conclusão de Pacotes antigo sobre problemas não-triviais com 100 itens, e supera o BCP (branch-and-cut-and-price) algoritmo por Belov e Scheithauer em problemas que têm menos de 20 pacotes como a solução ideal. Qual o algoritmo tem o melhor desempenho depende das propriedades do problema, como o número de itens, o número ideal de pacotes, o espaço não utilizado na solução ótima e precisão de valores.

Veja também[editar | editar código-fonte]

  • Se o número de caixas é para ser fixo ou restrito, e o tamanho das caixas é para ser o mínimo, este é um problema diferente, que é equivalente ao problema de programação com múltiplos processadores
  • Guilhotina problema
  • Subconjunto soma problema

Referencias[editar | editar código-fonte]

  1. Korte, Bernhard; Vygen, Jens (2006). «Bin-Packing». Combinatorial Optimization: Theory and Algorithms. Col: Algorithms and Combinatorics 21. [S.l.]: Springer. pp. 426–441. ISBN 978-3-540-25684-7. doi:10.1007/3-540-29297-7_18 
  2. Barrington, David Mix (2006). «Bin Packing» 
  3. Lewis 2009
  4. Sindelar, Sitaraman & Shenoy 2011, pp. 367–378
  5. Martello & Toth 1990, p. 221
  6. Vazirani 2003, p. 74.
  7. Yue 1991, pp. 321–331.
  8. Dósa 2007, pp. 1–11.
  9. Garey & Johnson 1985, pp. 65–106.
  10. Yue & Zhang 1995, pp. 318–330.
  11. Vazirani 2003, pp. 74–76.
  12. Fernandez de la Vega & Lueker 1981, pp. 349–355
  13. Martello & Toth 1990, pp. 237–240.
  14. Korf 2002
  15. R. E. Korf (2003), An improved algorithm for optimal bin packing.
  16. Schreiber & Korf 2013

Bibliografia

  1. Korf, Richard E. (2002), A new algorithm for optimal bin packing. (PDF) 
  2. Vazirani, Vijay V. (2003), Approximation Algorithms, ISBN 3-540-65367-8, Berlin: Springer 
  3. Yue, Minyi (October 1991), «A simple proof of the inequality FFD (L) ≤ 11/9 OPT (L) + 1, ∀L for the FFD bin-packing algorithm», Acta Mathematicae Applicatae Sinica, ISSN 0168-9673, 7 (4): 321–331, doi:10.1007/BF02009683  Verifique data em: |data= (ajuda)
  4. Dósa, György (2007), «The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I)≤(11/9)OPT(I)+6/9», in: Chen, Bo; Paterson, Mike; Zhang, Guochuan, Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, ISBN 978-3-540-74449-8, Springer Berlin / Heidelberg, ISSN 0302-9743, 4614/2007, pp. 1–11, doi:10.1007/978-3-540-74450-4 
  5. Xia, Binzhou; Tan, Zhiyi (2010), «Tighter bounds of the First Fit algorithm for the bin-packing problem», Discrete Applied Mathematics, ISSN 0166-218X, 158 (15): 1668–1675, doi:10.1016/j.dam.2010.05.026 
  6. Garey, Michael R.; Johnson, David S. (1985), «A 71/60 theorem for bin packing*1», Journal of Complexity, 1: 65–106, doi:10.1016/0885-064X(85)90022-6 
  7. Yue, Minyi; Zhang, Lei (July 1995), «A simple proof of the inequality MFFD(L)≤71/60 OPT(L) + 1,L for the MFFD bin-packing algorithm», Acta Mathematicae Applicatae Sinica, ISSN 0168-9673, 11 (3): 318–330, doi:10.1007/BF02011198  Verifique data em: |data= (ajuda)
  8. Fernandez de la Vega, W.; Lueker, G. S. (December 1981), «Bin packing can be solved within 1 + ε in linear time», Springer Berlin / Heidelberg, Combinatorica, ISSN 0209-9683, 1 (4): 349–355, doi:10.1007/BF02579456  Verifique data em: |data= (ajuda)
  9. Lewis, R. (2009), «A General-Purpose Hill-Climbing Method for Order Independent Minimum Grouping Problems: A Case Study in Graph Colouring and Bin Packing», Computers and Operations Research, 36 (7): 2295–2310, doi:10.1016/j.cor.2008.09.004 
  10. Martello, Silvano; Toth, Paolo (1990), «Bin-packing problem» (PDF), Knapsack Problems: Algorithms and Computer Implementations, ISBN 0471924202, Chichester, UK: John Wiley and Sons 
  11. Michael R. Garey and David S. Johnson (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A4.1: SR1, p. 226.
  12. David S. Johnson, Alan J. Demers, Jeffrey D. Ullman, M. R. Garey, Ronald L. Graham. Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms. SICOMP, Volume 3, Issue 4. 1974.
  13. Lodi A., Martello S., Monaci, M., Vigo, D. (2010) "Two-Dimensional Bin Packing Problems". In V.Th. Paschos (Ed.), Paradigms of Combinatorial Optimization, Wiley/ISTE, p. 107-129
  14. Dósa G., Sgall J. (2013) First Fit bin packing: A tight analysis. To appear in STACS 2013.
  15. Benkő A., Dósa G., Tuza Z. (2010) Bin Packing/Covering with Delivery, Solved with the Evolution of Algorithms, Proceedings 2010 IEEE 5th International Conference on Bio-Inspired Computing: Theories and Applications, BIC-TA 2010, art. no. 5645312, Pages 298-302.
  16. Sindelar, Michael; Sitaraman, Ramesh; Shenoy, Prashant (2011), «Sharing-Aware Algorithms for Virtual Machine Colocation», Proceedings of 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), San Jose, CA, June 2011: 367–378 
  17. Schreiber, Ethan L.; Korf, Richard E. (2013), Improved Bin Completion for Optimal Bin Packing and Number Partitioning (PDF), ISBN 978-1-57735-633-2, IJCAI '13, Beijing, China: AAAI Press, pp. 651–658 

Links externos[editar | editar código-fonte]