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 offered 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.

Farklı genişlik ve uzunluktaki nesnelerin mümkün olan en az sayıda sabit kapasiteli kutu kullanılarak yerleştirilmesini amaçlayan tek boyutlu kutu paketleme problemi, çözümü polinom zamanlı olmayan (NP) ve endüstri mühendisliği alanında popüler olan kombinatoriyal bir en iyileme problemdir. Çok bilinen bu endüstri probleminin çok amaçlı versiyonlarıyla gündelik hayatta sıkça karşılaşılmaktadır. 20 kutuya kadar olan küçük ölçekli problemler karmaşık olmayan basit algoritmalar kullanılarak çözülebilse de, büyük ölçekli problemlere optimal çözüm üretmek problemin kolay takip edilemeyen doğası sebebiyle mümkün olmayabilir. Kesin çözüm bulmanın mümkün olmadığı büyük ölçekli söz konusu problemlere en iyi çözümü bulabilmek amacı ile şimdiye kadar En Az Boşluk Algoritması, Tabu Araması, Parçacık Sürü Optimizasyonu benzeri sezgisel yontemler yaygın olarak kullanılmıştır. Ancak, problemin çözümüne yönelik geliştirilen bu sezgisel yöntemler performansı artıran son nesil paralel bilgisayar teknolojisi kullanılmaksızın tek bir işlemci kullanilarak çözülmüştür. Bu çalışma ile literatürde ilk defa CUDA (Compute Unified Device Architecture) kullanılarak grafik islemci birimi (GPU) katkısı ile Gruplama Genetik Algoritması (GGA)'nın performansı artırılmıştır. Heterojen bir mimari üzerinde koşturulan program ile GGA'nin islem süresini uzatan çarprazlama ve mutasyon algoritmalari GPU uzerinde çalıştırılmış, sonuçlar ise ekran kartı üzerinde bulunan global bellek üzerinde tutulmuştur. 1.238 farkli problem seti uzerinde koşturulan problem ve sonuçlari, Tek Boyutlu Kutulama CUDA GPU algoritmasının literatürde yer alan en iyi algoritmalar arasında yer alabileceğini ve CPU karşılığına göre de 60 kat daha hızlı olabileceğini göstermiştir.