Loading...
An adaptive jellyfish search algorithm for packing items with conflict
El-Ashmawi, Walaa H. Salah, Ahmed Bekhit, Mahmoud Xiao, Guoqing Al Ruqeishi, Khalil Fathalla, Ahmed
El-Ashmawi, Walaa H.
Salah, Ahmed
Bekhit, Mahmoud
Xiao, Guoqing
Al Ruqeishi, Khalil
Fathalla, Ahmed
Abstract
The bin packing problem (BPP) is a classic combinatorial optimization problem with several variations. The BPP with conflicts (BPPCs) is not a well-investigated variation. In the BPPC, there are conditions that prevent packing some items together in the same bin. There are very limited efforts utilizing metaheuristic methods to address the BPPC. The current methods only pack the conflict items only and then start a new normal BPP for the non-conflict items; thus, there are two stages to address the BPPC. In this work, an adaption of the jellyfish metaheuristic has been proposed to solve the BPPC in one stage (i.e., packing the conflict and non-conflict items together) by defining the jellyfish operations in the context of the BPPC by proposing two solution representations. These representations frame the BPPC problem on two different levels: item-wise and bin-wise. In the item-wise solution representation, the adapted jellyfish metaheuristic updates the solutions through a set of item swaps without any preference for the bins. In the bin-wise solution representation, the metaheuristic method selects a set of bins, and then it performs the item swaps from these selected bins only. The proposed method was thoroughly benchmarked on a standard dataset and compared against the well-known PSO, Jaya, and heuristics. The obtained results revealed that the proposed methods outperformed the other comparison methods in terms of the number of bins and the average bin utilization. In addition, the proposed method achieved the lowest deviation rate from the lowest bound of the standard dataset relative to the other methods of comparison.
Keywords
metaheuristic algorithms, artificial jellyfish optimizer, bin packing problem, any-fit algorithm
Date
2023
Type
Journal article
Journal
Book
Volume
11
Issue
14
Page Range
1-28
Article Number
ACU Department
Peter Faber Business School
Faculty of Law and Business
Faculty of Law and Business
Collections
Relation URI
Source URL
Event URL
Open Access Status
Published as ‘gold’ (paid) open access
License
CC BY 4.0
File Access
Open
Notes
Copyright: © 2023 by the authors. Licensee MDPI, Basel, Switzerland.
This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https:// creativecommons.org/licenses/by/ 4.0/).
This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https:// creativecommons.org/licenses/by/ 4.0/).