A Novel Grouping Genetic Algorithm for the One-Dimensional Bin Packing Problem on GPU

Date

2016-10-28

Author

Ozcan, Sukru Ozer
Dokeroglu, Tansel
Coşar, Ahmet
Yazıcı, Adnan

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

16
views

35
downloads

Cite This

One-dimensional Bin Packing Problem (1D-BPP) is a challenging NP-Hard combinatorial problem which is used to pack finite number of items into minimum number of bins. Large problem instances of the 1D-BPP cannot be solved exactly due to the intractable nature of the problem. In this study, we propose an efficient Grouping Genetic Algorithm (GGA) by harnessing the power of the Graphics Processing Unit (GPU) using CUDA. The time consuming crossover and mutation processes of the GGA are executed on the GPU by increasing the evaluation times significantly. The obtained experimental results on 1,238 benchmark 1D-BPP instances show that our proposed algorithm has a high performance and is a scalable algorithm with its high speed fitness evaluation ability. Our proposed algorithm can be considered as one of the best performing algorithms with its 66 times faster computation speed that enables to explore the search space more effectively than any of its counterparts.

Subject Keywords

1D Bin packing, Grouping genetic, CUDA, GPU

URI

https://hdl.handle.net/11511/32590

Collections

Graduate School of Natural and Applied Sciences, Conference / Seminar