Variable-sized bin packing problem with conflicts and item fragmentation. (January 2022)

• Record Type: Journal Article
• Authors: Ekici, Ali
• Is Part Of: Computers & industrial engineering. Volume 163(2022)
• Publication Date: 2022-01
• Subjects: Variable-sized bin packing -- Conflicts -- Fragmentation -- Heuristic -- Lower bound; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2021.107844
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: Proposed lower bound provides better bounds for dense conflict graph instances. Proposed heuristic algorithm outperforms the benchmark algorithms. Proposed heuristic algorithm finds solutions with 0.25% optimality gap on average. Abstract: 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.