Bin packing problem with conflicts and item fragmentation

Name: Bin packing problem with conflicts and item fragmentation
Author: Ekici, Ali

İsim	Bin packing problem with conflicts and item fragmentation
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

Kaynağa git Özyeğin Üniversitesi

Aramaya Dön

Özyeğin Üniversitesi

Kaynağa git

Bin packing problem with conflicts and item fragmentation

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