Um esquema de aproximação para um problema de empacotamento com cenários

  • Yulle Borges UNICAMP
  • Thiago de Queiroz UFG
  • Vinícius Lima UNICAMP
  • Flavio Miyazawa UNICAMP
  • Lehilton Pedrosa UNICAMP

Resumo


Investigamos um problema de empacotamento onde cada item possui um peso e está associado a um ou mais cenários e todos os recipientes têm uma capacidade fixa. Um empacotamento é uma atribuição de itens a recipientes de maneira que o peso total dos itens alocados a um recipiente para um mesmo cenário não ultrapasse a capacidade do recipiente. O objetivo do problema é encontrar um empacotamento de todos os itens em recipientes, de maneira a minimizar o número máximo de recipientes usados em qualquer cenário. Apre- sentamos um esquema de aproximação assintótico quando o número de cenários é limitado por uma constante.

Palavras-chave: Bin packing, Incerteza, Algoritmo de aproximação, Esquema de aproximação

Referências

Bódis, A. e Balogh, J. (2018). Bin packing problem with scenarios. Central European Journal of Operations Research, pages 1–19.

Christensen, H. I., Khan, A., Pokutta, S., e Tetali, P. (2017). Approximation and online algorithms for multidimensional bin packing: A survey. Computer Science Review, 24:63 – 79.

Coffman, E. G., Csirik, J., Galambos, G., Martello, S., e Vigo, D. (2013). Bin packing approximation algorithms: survey and classification. In Handbook of combinatorial optimization, pages 455–531. Springer.

Coffman, E. G., Garey, M. R., e Johnson, D. S. (1984). Approximation algorithms for bin-packing-an updated survey. In Algorithm design for computer system design, pages 49–106. Springer.

Delorme, M., Iori, M., e Martello, S. (2016). Bin packing and cutting stock problems: Mathematical models and exact algorithms. European Journal of Operational Rese- arch, 255(1):1 – 20.

Dyckhoff, H. (1990). A typology of cutting and packing problems. European J. Operati- onal Research, 44:145–159.

Fernandez de la Vega, W. e Lueker, G. S. (1981). Bin packing can be solved within 1 + ? in linear time. Combinatorica, 1(4):349–355.

Feuerstein, E., Marchetti-Spaccamela, A., Schalekamp, F., Sitters, R., van der Ster, S., Stougie, L., e van Zuylen, A. (2017). Minimizing worst-case and average-case makes- pan over scenarios. Journal ofScheduling, 20(6):545–555.

Wascher, G., Haussner, H., e Schumann, H. (2007). An improved typology of cutting and packing problems. European Journal ofOperational Research, 183(3):1109–1130.
Publicado
02/07/2019
BORGES, Yulle; DE QUEIROZ, Thiago; LIMA, Vinícius ; MIYAZAWA, Flavio; PEDROSA, Lehilton . Um esquema de aproximação para um problema de empacotamento com cenários. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 4. , 2019, Belém. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2019 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2019.6400.