Author
Ekici, Ali
Publication Date
2021-02
Publication Place
-
Elsevier
Subject
Bin packing problem with conflicts, Item fragmentation, Heuristic, Lower bound, Oversized items
Type
Periodical
Language
English
Digital
Yes
Manuscript
No
Library
Özyeğin University
Library Asset ID
0305-0548
Record ID
e971c668-9c74-4d52-a310-57d08aaa427e
Library Location
Industrial Engineering
Date
2021-02
Sample Text
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.
DOI
10.1016/j.cor.2020.105113
Cilt
126
