A Scalable evolutionary algorithm for solving the one-dimensional bin packing problem on GPU using CUDA

Download

index.pdf

Date

2015

Author

Özcan, Şükrü Özer

Metadata

Show full item record

Item Usage Stats

265
views

110
downloads

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 Swarm, Tabu Search, and Minimum Bin Slack have been widely used to solve this important problem (near-) optimally. Most of the the state-of-the art algorithms that have been proposed to solve the 1DBPP are executed on a single processor and do not make use of the high performance opportunities that are ordered by the recent parallel computation technologies. In this study, we increase the performance of a Grouping Genetic Algorithm (GGA) by harnessing the power of the graphics processing unit (GPU) using Compute Unified Device Architecture (CUDA) for the first time in literature. The time consuming crossover and mutation processes of the GGA are executed on the GPU and the population of solutions is kept on the global memory of GPU while running the whole algorithm in a heterogeneous computing environment. The obtained experimental results on 1,238 benchmark problem instances show that the proposed algorithm, CUDA GGA for 1DBPP (CUDA-GGA-1DBPP), is a high performance and scalable algorithm that can be counted among the best performing algorithms in literature and it is about 60 times faster than its CPU counterpart.

Subject Keywords

Graphics processing units., CUDA (Computer architecture)., Evolutionary computation., Genetic algorithms.

URI

http://etd.lib.metu.edu.tr/upload/12619383/index.pdf
https://hdl.handle.net/11511/25005

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

A Novel Grouping Genetic Algorithm for the One-Dimensional Bin Packing Problem on GPU Ozcan, Sukru Ozer; Dokeroglu, Tansel; Coşar, Ahmet; Yazıcı, Adnan (SPRINGER INT PUBLISHING AG, GEWERBESTRASSE 11, CHAM, CH-6330, SWITZERLAND; 2016-10-28) 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 i...
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...
A Hybrid Nonlinear Method for Array Thinning Epcacan, Erdal; Çiloğlu, Tolga (2018-05-01) A nonlinear method for array thinning is proposed. The method is based on hybrid usage of genetic algorithm (GA) and nonlinear apodization. The method proposes a special layout, which consists of two subarrays. Layout and weights for the subarray having larger aperture are designed by GA. Layout and weights for the second subarray are determined according to results of the aforementioned design. Dual apodization is applied to the outputs of the subarrays to obtain the output. Results show that there is an i...
A Distributed Heuristic Algorithm for the Rectilinear Steiner Minimal Tree Problem Cinel, Sertac; Bazlamaçcı, Cüneyt Fehmi (Institute of Electrical and Electronics Engineers (IEEE), 2008-11-01) Rectilinear Steiner minimal tree (RSMT) problem finds a minimum length tree that interconnects a given set of points by only horizontal and vertical line segments and by using extra points if necessary. In this paper, to speedup the RSMT construction, two recently developed successful heuristic algorithms, namely rectilinear steiner tree (RST) by Zhou and hatched greedy algorithm (BGA) by Kahng et al., have been used as the basis. Following a slight modification on RST, which led to a nonrecursive and a con...
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...

Citation Formats

Ş. Ö. Özcan, “A Scalable evolutionary algorithm for solving the one-dimensional bin packing problem on GPU using CUDA,” M.S. - Master of Science, Middle East Technical University, 2015.