New algorithms for the bin packing problem

Abstract

ÖZET Tek Boyutlu Yerleştirme problemi geniş bir uygulama alanı olan tanınmış bir NP-kapsar problemdir. Bu çalışmada, bir literatür taraması yapılmış ve problemin NP-kapsar olmasından dolayı öncelikle bazı sezgisel algoritmalar üzerinde durulmuş ve bunun yanı sıra sıf ır-bir tam sayı problemleri çözebilen bir prosedür kullanılarak, iyi çözülebilir ve en iyi çözümü bulan bir algoritma geliştirilmeye çalışılmıştır. Ayrıca, Tek Boyutlu Yerleştirme probleminin yeni bir özel durumu olarak yerleştirmenin dengeli yapılması problemi tanımlanmış ve gene bu problemi çözmek için bazi algoritmalar üzerinde çalışılmış ve bu algoritmalar denenmiştir.

iv ABSTRACT Bin Facking is a well-known NP-complete problem which has many real-life applications. In this study, an extensive literature survey is followed by a number of new heuristic and optimal algorithms developed using a new general procedure called ` Similar Tree Search Algorithm ` to solve zero-one integer programming problems. Besides, a new special case of the bin packing problem, smooth packing, is defined and algorithms to solve this new problem are generated and tested.