COMPLEXITY OF FRAGMENTABLE OBJECT BIN PACKING AND AN APPLICATION

We examine in this paper a variant of the bin packing problem, where i t is permissible to fragment the objects while packing them into bins of fixed capacity. We call this the Fragmentable Object Bin Packing pr oblem (FOBP). Fragmentation is associated with a cost, leading to the consumption of additional bin capacity. We show that the problem and i ts absolute approximation are both NP-complete. This is an interesting problem because if the cost of fragmentation is nullified then the pr oblem can be easily solved optimally. If fragmentation is not permitte d, then we get the usual bin packing problem. The application comes fr om a problem in data path synthesis where it is some times necessary t o schedule data transfers, subject to restrictions arising from the un derlying hardware. We show that FOBP reduces to a simplified version o f this problem, thereby proving that it is also a similar hard problem . (C) 1998 Elsevier Science Ltd. All rights reserved.