JUCS - Journal of Universal Computer Science 30(8): 1008-1022, doi: 10.3897/jucs.102470
A Plant Propagation Algorithm for the Bin Packing Problem
Rewayda Razaq Abo-Alsabeh‡, Meryem Cheraitia§, Abdellah Salhi|‡ University of Kufa, Najaf, Iraq§ 8 Mai 1945 University, Guelma, Algeria| University of Essex, Colchester, United Kingdom
Corresponding author: Rewayda Razaq Abo-Alsabeh ( ruwaida.mohsin@uokufa.edu.iq ) Corresponding author: Meryem Cheraitia ( meryem.cheraitia@hotmail.fr ) © Rewayda Razaq Abo-Alsabeh, Meryem Cheraitia, Abdellah Salhi. This is an open access article distributed under the terms of the Creative Commons Attribution License (CC BY-ND 4.0). This license allows reusers to copy and distribute the material in any medium or format in unadapted form only, and only so long as attribution is given to the creator. The license allows for commercial use. Citation:
Abo Alsabeh RRM, Cheraitia M, Salhi A (2024) A Plant Propagation Algorithm for the Bin Packing Problem. JUCS - Journal of Universal Computer Science 30(8): 1008-1022. https://doi.org/10.3897/jucs.102470 |  |
Abstract
We consider the one-dimensional Bin Packing Problem (BPP) and its solution using a novel heuristic approach namely the Plant Propagation Algorithm (PPA). The problem can be stated as follows: given a set of objects of various weights, sizes, or any measure, and a set of bins each with fixed capacity, find the minimum number of bins needed to pack all the items such that the sum of the elements packed inside each bin does not exceed its capacity. BPP is a well-studied problem, however, being NP-Hard, the search for a computationally viable solution approach for it continues. In this paper, we report on our implementation of PPA for BPP and its performance against other algorithms on number of non-trivial instances. Computational results and their discussion are included.
Keywords
Algorithms, Approximate Solution, Bin Packing, Heuristic, Plant Propagation Algorithm