An Adaptive Jellyfish Search Algorithm for Packing Items with Conflict

Walaa H. El-Ashmawi, Ahmad Salah (), Mahmoud Bekhit, Guoqing Xiao, Khalil Al Ruqeishi and Ahmed Fathalla ()
Additional contact information
Walaa H. El-Ashmawi: Faculty of Computers and Informatics, Suez Canal University, Ismailia 41522, Egypt
Ahmad Salah: Faculty of Computers and Informatics, Zagazig University, Sharkia 44519, Egypt
Mahmoud Bekhit: University of Technology Sydney (UTS), Sydney, NSW 2007, Australia
Guoqing Xiao: College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082, China
Khalil Al Ruqeishi: Mathematical and Physical Sciences Department, College of Arts and Sciences, University of Nizwa, Nizwa P.O. Box 33, Oman
Ahmed Fathalla: Department of Mathematics, Faculty of Science, Suez Canal University, Ismailia 41522, Egypt

Mathematics, 2023, vol. 11, issue 14, 1-28

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 (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/14/3219/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/14/3219/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:14:p:3219-:d:1199859

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().