Yazar
Ekici, Ali
Basım Tarihi
2021-02
Basım Yeri
-
Elsevier
Konu
Bin packing problem with conflicts, Item fragmentation, Heuristic, Lower bound, Oversized items
Tür
Süreli Yayın
Dil
İngilizce
Dijital
Evet
Yazma
Hayır
Kütüphane
Özyeğin Üniversitesi
Demirbaş Numarası
0305-0548
Kayıt Numarası
e971c668-9c74-4d52-a310-57d08aaa427e
Lokasyon
Industrial Engineering
Tarih
2021-02
Örnek Metin
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
