| Texto completo | |
| Autor(es): |
Borges, Yulle G. F.
;
de Lima, Vinicius L.
;
Miyazawa, Flavio K.
;
Pedrosa, Lehilton L. C.
;
de Queiroz, Thiago A.
;
Schouery, Rafael C. S.
Número total de Autores: 6
|
| Tipo de documento: | Artigo Científico |
| Fonte: | JOURNAL OF COMBINATORIAL OPTIMIZATION; v. 48, n. 4, p. 28-pg., 2024-11-01. |
| Resumo | |
This paper presents theoretical and practical results for the bin packing problem with scenarios, a generalization of the classical bin packing problem which considers the presence of uncertain scenarios, of which only one is realized. For this problem, we propose approximation algorithms whose ratios are bounded by the square root of the number of scenarios times the approximation ratio for an algorithm for the vector bin packing problem. We also show how an asymptotic polynomial-time approximation scheme is derived when the number of scenarios is constant, that is, not a part of the input. As a practical study of the problem, we present a branch-and-price algorithm to solve an exponential set-cover model and a variable neighborhood search heuristic. Experiments show the competence of the branch-and-price in obtaining optimal solutions for about 59% of the instances considered, while the combined heuristic and branch-and-price optimally solved 62% of the instances considered. (AU) | |
| Processo FAPESP: | 22/05803-3 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento e localização e suas integrações em contextos industriais e logísticos |
| Beneficiário: | Reinaldo Morabito Neto |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |
| Processo FAPESP: | 17/11831-1 - Algoritmos e modelos para problemas de corte e empacotamento |
| Beneficiário: | Vinícius Loti de Lima |
| Modalidade de apoio: | Bolsas no Brasil - Doutorado Direto |