Variable-sized bin packing problem with conflicts and item fragmentation

Name: Variable-sized bin packing problem with conflicts and item fragmentation
Author: Ekici, Ali

İsim	Variable-sized bin packing problem with conflicts and item fragmentation
Yazar	Ekici, Ali
Basım Tarihi:	2022-01
Basım Yeri	- Elsevier
Konu	Variable-sized bin packing, Conflicts, Fragmentation, Heuristic, Lower bound
Tür	Süreli Yayın
Dil	İngilizce
Dijital	Evet
Yazma	Hayır
Kütüphane:	Özyeğin Üniversitesi
Demirbaş Numarası	0360-8352
Kayıt Numarası	2deb9797-d397-47ac-b313-68d2bcade555
Lokasyon	Industrial Engineering
Tarih	2022-01
Örnek Metin	In this paper, we study the Variable-Sized Bin Packing Problem with Conflicts and Item Fragmentation (VSBPPC-IF) that has applications such as (i) the delivery planning of incompatible items using a fleet of heterogenous vehicles where split delivery is allowed, and (ii) load balancing and memory allocation in parallel processing. In VSBPPC-IF, a set of items has to be packed into the bins with different capacities and costs. Items can be fragmented, and each fragment can be packed into a separate bin. However, the fragments of conflicting items cannot be packed into the same bin. The goal in VSBPPC-IF is to find a packing of the items into the bins with minimum total cost. We propose a lower bounding mechanism for the problem and compare it against the trivial continuous lower bound. We develop a novel heuristic algorithm based on the idea of generating subsets of compatible items and determining the types of the bins used by solving a mathematical model. We compare the performance of the proposed solution approach both against a lower bound and a set of benchmark algorithms from the literature. The proposed heuristic not only outperforms the benchmark algorithms but also provides solutions with quite low (0.25% on average) optimality gaps.
DOI	10.1016/j.cie.2021.107844
Cilt	163

Kaynağa git Özyeğin Üniversitesi

Aramaya Dön

Özyeğin Üniversitesi

Kaynağa git

Variable-sized bin packing problem with conflicts and item fragmentation

Yazar Ekici, Ali

Basım Tarihi 2022-01

Basım Yeri - Elsevier

Konu Variable-sized bin packing, Conflicts, Fragmentation, Heuristic, Lower bound

Tür Süreli Yayın

Dil İngilizce

Dijital Evet

Yazma Hayır

Kütüphane Özyeğin Üniversitesi

Demirbaş Numarası 0360-8352

Kayıt Numarası 2deb9797-d397-47ac-b313-68d2bcade555

Lokasyon Industrial Engineering

Tarih 2022-01

Örnek Metin In this paper, we study the Variable-Sized Bin Packing Problem with Conflicts and Item Fragmentation (VSBPPC-IF) that has applications such as (i) the delivery planning of incompatible items using a fleet of heterogenous vehicles where split delivery is allowed, and (ii) load balancing and memory allocation in parallel processing. In VSBPPC-IF, a set of items has to be packed into the bins with different capacities and costs. Items can be fragmented, and each fragment can be packed into a separate bin. However, the fragments of conflicting items cannot be packed into the same bin. The goal in VSBPPC-IF is to find a packing of the items into the bins with minimum total cost. We propose a lower bounding mechanism for the problem and compare it against the trivial continuous lower bound. We develop a novel heuristic algorithm based on the idea of generating subsets of compatible items and determining the types of the bins used by solving a mathematical model. We compare the performance of the proposed solution approach both against a lower bound and a set of benchmark algorithms from the literature. The proposed heuristic not only outperforms the benchmark algorithms but also provides solutions with quite low (0.25% on average) optimality gaps.

DOI 10.1016/j.cie.2021.107844

Cilt 163