An Adaptive Jellyfish Search Algorithm for Packing Items with Conflict
Open Access
- 22 July 2023
- journal article
- research article
- Published by MDPI AG in Mathematics
- Vol. 11 (14) , 3219
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
This publication has 52 references indexed in Scilit:
- Average-weight-controlled bin-oriented heuristics for the one-dimensional bin-packing problemEuropean Journal of Operational Research, 2011
- On conflict and cooperation in a two-echelon inventory model for deteriorating itemsComputers & Industrial Engineering, 2010
- New lower bounds for bin packing problems with conflictsEuropean Journal of Operational Research, 2010
- Jellyfish blooms in China: Dominant species, causes and consequencesMarine Pollution Bulletin, 2010
- Mediterranean Jellyfish Venoms: A Review on ScyphomedusaeMarine Drugs, 2010
- An improved multi-staged algorithmic process for the solution of the examination timetabling problemAnnals of Operations Research, 2010
- An analysis of lower bound procedures for the bin packing problemComputers & Operations Research, 2005
- Heuristics and lower bounds for the bin packing problem with conflictsComputers & Operations Research, 2004
- Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problemsArtificial Intelligence, 1992
- Examination timetabling by computerComputers & Operations Research, 1984