Um esquema de aproximação para um problema de empacotamento com cenários
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.
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
Como Citar
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.
