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

Download

index.pdf

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

206
views

103
downloads

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

DOI

https://doi.org/10.1007/978-3-319-47217-1_6

Collections

Graduate School of Natural and Applied Sciences, Conference / Seminar

Suggestions

OpenMETU
Core

A Scalable evolutionary algorithm for solving the one-dimensional bin packing problem on GPU using CUDA Özcan, Şükrü Özer; Coşar, Ahmet; Sahillioğlu, Yusuf; Department of Computer Engineering (2015) One-dimensional Bin Packing Problem (1DBPP) is a challenging NP-Hard combinatorial industrial engineering problem which is used to pack finite number of items into minimum number of fixed size bins. Different versions of 1DBPP can be faced in real life. Although the problems that have small number of items up to 20 can be solved with brute-force algorithms, large problem instances of the 1DBPP cannot be solved exactly due to its intractable nature. Therefore, heuristic approaches such as Genetic, Particle S...
Robust hyper-heuristic algorithms for the offline oriented/non-oriented 2D bin packing problems Beyaz, Muhammed; Dokeroglu, Tansel; Coşar, Ahmet (2015-11-01) The offline 2D bin packing problem (2DBPP) is an NP-hard combinatorial optimization problem in which objects with various width and length sizes are packed into minimized number of 2D bins. Various versions of this well-known industrial engineering problem can be faced frequently. Several heuristics have been proposed for the solution of 2DBPP but it has not been possible to find the exact solutions for large problem instances. Next fit, first fit, best fit, unified tabu search, genetic and memetic algorith...
Hybrid heuristic algorithms for the multi objective load balancing of 2D bin packing problems Muhammet, Beyaz; Dökeroğlu, Tansel; Coşar, Ahmet (null; 2015-09-23) 2D Bin packing problem (2DBPP) is an NP-hard combinatorial optimization problem. Multiobjective versions of this well-known industrial engineering problem can occur frequently in real world application. Recently, Hybrid Evolutionary Algorithms have appear as a new area of research with their ability to combine alternative heuristics and local search mechanisms together for higher quality solutions. In this study, we propose a set of novel multiobjective hybrid genetic and memetic algorithms that make use of...
Optimization of one-dimensional Bin Packing Problem with island parallel grouping genetic algorithms Dokeroglu, Tansel; Coşar, Ahmet (2014-09-01) The well-known one-dimensional Bin Packing Problem (BPP) of whose variants arise in many real life situations is a challenging NP-Hard combinatorial optimization problem. Metaheuristics are widely used optimization tools to find (near-) optimal solutions for solving large problem instances of BPP in reasonable running times. With this study, we propose a set of robust and scalable hybrid parallel algorithms that take advantage of parallel computation techniques, evolutionary grouping genetic metaheuristics,...
Hybrid metaheuristic algorithms for single and multi-objective 2d bin packing problem Beyaz, Muhammed; Coşar, Ahmet; Dökeroğlu, Tansel; Department of Computer Engineering (2015) 2D Bin packing problem (2DBPP) is an NP-hard combinatorial optimization problem. Objects with di erent width and length sizes are packed in order to minimize the number of unit-capacity bins according to an objective function. Single or multiobjective versions of this well-known industrial engineering problem can be faced frequently in real life situations. There have been several heuristics proposed for the solution of 2DBPP until now where it is not possible to find the exact solutions for large problem i...

Citation Formats

S. O. Ozcan, T. Dokeroglu, A. Coşar, and A. Yazıcı, “A Novel Grouping Genetic Algorithm for the One-Dimensional Bin Packing Problem on GPU,” 2016, vol. 659, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/32590.