İki boyutlu kesme problemi için sezgisel yaklaşım ile bir uygulama

Abstract

Pek çok değişik endüstride farklı koşullar ve amaçlarla karşımıza çıkan kesme problemlerinin her biri birer eniyileme problemidir. Bu problemler NP-tam sınıfında olduğundan çözümü bulmak için kombinasyonel eniyileme yapılır. Kesme problemlerinin zorluğu, büyük parça üzerine yerleştirilecek parçaların geometrisine ve problemin doğasından gelen kısıtlamalarına (çok farklı çözümlerin varlığına) bağlıdır. Problemlerin çözüm yaklaşımları çeşitli sayıdaki bu kısıtlamalara bağlı olarak geliştirilir.İlk sığan algoritmasının en kötü durumda %22 optimal sonuca yaklaştığı bilinmektedir. Bu sebepten ötürü, optimal çözümlere yaklaşmak için çeşitli sezgisel yöntemler kullanılmıştır.Bu çalışmada iki boyutlu kesme problemi için genetik algoritma ve dinamik programlama yardımı ile oluşturulmuş sezgisel bir yerleştirme algoritması geliştirilmiştir. Ayrıca seçim ve yerleşim algoritmaları olarak çalışma iki bölüme ayrılmış ve yerleşim algoritması olarak ilk sığan (first fit) ve dinamik programlama, seçim algoritması olarak genetik algoritma kullanılmıştır. Yerleşim algoritmalarının problem çözümüne etkisi incelenmiştir.

Each cutting problem is an optimization problem where it occures in many different industries with different conditions and objectives. This problem is member of NP-complete class so solution needs to be found with combinational optimization. Difficulty of cutting problems are related with geometry of the small parts which will be placed on major part and limitations (the existence of different solutions). A variety of approaches to the solution of problems are developed depending on the number of these restrictions.It is known that the first-fit algorithm may reach to 22% optimal results in the worst case. For this reason, various heuristic methods are used to find more optimal solutions.In this tesis, placement algorithm has been devoloped with genetic algorithms and dynamic programming for two-dimensional cutting problem. In addition, selection and placement algorithms work as divided into two parts: the first fit algorithm and dynamic programming as placement algorithm, genetic algorithms are used as the selection algorithm. The effect of placement algorithms to the problem solutions were examined.