- Tytuł:
- Bin packing with restricted item fragmentation
- Autorzy:
- Pieńkosz, K.
- Powiązania:
- https://bibliotekanauki.pl/articles/205659.pdf
- Data publikacji:
- 2014
- Wydawca:
- Polska Akademia Nauk. Instytut Badań Systemowych PAN
- Tematy:
-
bin packing
fragmentable items
approximation algorithms - Opis:
- In this paper we consider a generalization of the bin packing problem, in which it is permitted to fragment the items while packing them into bins. There is, however, a restriction that the size of each piece of the fragmented item cannot be smaller than a given parameter β An interesting aspect of such a model is that if β= 0, then the problem can be easily solved optimally. If β is large enough, meaning, in fact, that the fragmentation is not allowed, we get the classical bin packing problem, which is NP-hard in the strong sense. We present approximation algorithms for solving the problem and analyse their properties. The results of computational experiments and conclusions relating to the effectiveness of the algorithms are also presented.
- Źródło:
-
Control and Cybernetics; 2014, 43, 4; 547-556
0324-8569 - Pojawia się w:
- Control and Cybernetics
- Dostawca treści:
- Biblioteka Nauki
Artykuł