Back to Search

Variable-sized bin packing problem with conflicts and item fragmentation

Title	Variable-sized bin packing problem with conflicts and item fragmentation
Author	Ekici, Ali
Publication Date:	2022-01
Publication Place	- Elsevier
Subject	Variable-sized bin packing, Conflicts, Fragmentation, Heuristic, Lower bound
Type	Periodical
Language	English
Digital	Yes
Manuscript	No
Library:	Özyeğin University
Library Asset ID	0360-8352
Record ID	2deb9797-d397-47ac-b313-68d2bcade555
Library Location	Industrial Engineering
Date	2022-01
Sample Text	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

View in source Özyeğin University Özyeğin University - Historical works, archives, and periodicals search engine

Özyeğin University

Variable-sized bin packing problem with conflicts and item fragmentation

Author Ekici, Ali

Publication Date 2022-01

Publication Place - Elsevier

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

Type Periodical

Language English

Digital Yes

Manuscript No

Library Özyeğin University

Library Asset ID 0360-8352

Record ID 2deb9797-d397-47ac-b313-68d2bcade555

Library Location Industrial Engineering

Date 2022-01

Sample Text 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