Bir boyutlu kutulama probleminin eniyilenmesi için hiper-sezgisel paralel bir algoritma

Abstract

Bir boyutlu kutulama problemi (1BKP), endüstri mühendisliğinin üzerinde en çok çalışılan NP-Zor kombinatoriyal problemlerinden bir tanesidir. Büyük sayıda (elliden fazla) parça içeren problem kümeleri için en iyi çözümün bulunması klasik kaba kuvvet algoritmaları ile yüz yıllarca sürebilmektedir. Bu yüzden (yaklaşık)-optimal çözümleri ile eniyilemeyi tam olarak ya da düşük performans kayıpları ile kısa sürelerde bulabilen sezgisel algoritmalar sıklıkla kullanılmaktadır. Bu çalışma ile birlikte, Gruplama Genetik Algoritmalarında (GGA) kullanılan sezgisel kutulama tekniklerinden sadece bir tanesini kullanan klasik yaklaşımlar yerine, aynı anda birçok sezgisel kutulama tekniğini kullanan hiper-sezgisel paralel bir algoritma (HPGG-1BKP) geliştirildi. En Uygun Boşluğu Doldur (EUBD), İlk Bulduğun Boşluğu Doldur (İBBD) ve En Küçük Boşluğu Bırakarak Doldur (EKBBD) sezgisel kutu doldurma algoritmaları bu algoritmada aynı anda paralel olarak kullanıldı. 1228 bençmark problemi üzerinde yapılan deneyler sonucunda %88.1 başarı ile 1070 optimal sonuç elde edildi. Geri kalan problemler için de sadece bir kutu daha fazla kullanan çözümler üretilerek sonuçlar eniyilendi. Önerilen algoritma Falkenauer GGA ile karşılaştırıldığında %9'a varan iyileşmeler elde edildi