Bin packing problem with conflicts and item fragmentation
Author
Type :
Article
Publication Status :
Published
Access :
restrictedAccess
Abstract
In this paper, we study the Bin Packing Problem with Conflicts and Item Fragmentation (BPPC-IF) which has applications in the delivery and storage of items that cannot be packed together. Given a set of items each with a certain size, the goal in BPPC-IF is to pack these items into a minimum number of fixed-capacity bins while not packing fragments of conflicting items into the same bin. We assume a size-preserving fragmentation, i.e., the total size of fragments of an item packed into the bins has to be equal to the item's original size. We first prove that BPPC-IF is still NP-hard even though items can be fragmented. Unlike the Bin Packing Problem with Item Fragmentation (BPPIF), we show that BPPC-IF does not necessarily admit optimal solutions with a special structure. Moreover, we show that preprocessing an instance with oversized items (items with size greater than bin capacity) by packing a fragment of such items with size equal to bin capacity to a single bin does not necessarily yield an optimal solution. Using this observation, we develop a lower bounding procedure. Finally, we propose a heuristic algorithm which sequentially packs items into the bins using the observation about the oversized items. Through an extensive computational study, we demonstrate the superior performance of the proposed solution approach over the existing algorithms in the literature.
Source :
Computers & Operations Research
Date :
2021-02
Volume :
126
Publisher :
Elsevier
URI
http://hdl.handle.net/10679/7797https://www.sciencedirect.com/science/article/pii/S0305054820302306
Collections
Share this page