Complexity of fragmentable object bin packing and an application

We examine in this paper a variant of the bin packing problem, where it is permissible to fragment the objects while packing them into bins of fixed capacity. We call this the Fragmentable Object Bin Packing problem (FOBP). Fragmentation is associated with a cost, leading to the consumption of additional bin capacity. We show that the problem and its absolute approximation are both NP-complete. This is an interesting problem because if the cost of fragmentation is nullified then the problem can be easily solved optimally. If fragmentation is not permitted, then we get the usual bin packing problem. The application comes from a problem in data path synthesis where it is sometimes necessary to schedule data transfers, subject to restrictions arising from the underlying hardware. We show that FOBP reduces to a simplified version of this problem, thereby proving that it is also a similar hard problem.