.png){kind=icon}
.png){kind=icon}
Return
Variable-sized bin packing problem with conflicts and item fragmentation
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cie.2021.107844.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Variable-sized bin packing
Conflicts
Fragmentation
Heuristic
Lower bound
Journal
IF:
6.5
Papers:
1.0W
Citations:
3.8W