Akademik Veri Yönetim Sistemi
Tezin Türü: Yüksek Lisans
Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Türkiye
Tezin Onay Tarihi: 2015
Tezin Dili: İngilizce
Öğrenci: Şükrü Özer Özcan
Eş Danışman: YUSUF SAHİLLİOĞLU, AHMET COŞAR
Özet: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.