İki Boyutlu Giyotinsiz Kesme Problemlerinin Benzetilmiş Tavlama Algoritması ile Çözümlerinin İncelenmesi

Year 2005, Volume: 8 Issue: 1 - Volume: 8 Issue: 1, 25 - 36, 01.03.2005

Alev Söke Zafer Bingül

Abstract

Bu çalışmada, benzetilmiş tavlama (BT) algoritması ve geliştirilmiş aşağı sol (AS) algoritmasının ortak kullanımıyla iki boyutlu giyotinsiz kesme problemlerinin çözümü için melez bir yaklaşım geliştirilmiştir. 17 adet birbirinden farklı dikdörtgen parçadan oluşan beş ayrı test problemi ve 29 adet birbirinden farklı dikdörtgen parçadan oluşan bir test problemi üzerinde çalışılmıştır. Bu test problemlerinde, 200x200 birimlik alan ile sınırlandırılmış bir büyük parça üzerinde sıfır fire değerini verecek şekilde parçaların yerleştirilmesi istenmektedir. Bu çalışmada BT algoritmasında kullanılan farklı parametrelerin, kesme problemlerinin çözümleri üzerindeki etkileri incelenmiştir. Elde edilen en iyi sonuca ait parametre grubu: Lundy ve Mees soğutma çizelgesi, yer değiştirme komşuluk hareketi ve iç döngü sayısı:3 olarak bulunmuştur. Ayrıca 17 ve 29 parçalı test problemleri için elde edilen çözümlerin fire değerlerinin sırasıyla %4 - %21 ve %10 - %17 arasında değiştiği görülmüştür.

Keywords

Benzetilmiş tavlama algoritması, Geliştirilmiş aşağı sol algoritması, Kesme problemleri.

A Study of Simulated Annealing Algorithm for Solutions of Two Dimensional Non-Guillotine Cutting Problems

Abstract

In this study, a hybrid approach using both simulated annealing (SA) algorithm and improved bottom left (BL) algorithm for solution of the two dimensional non-guillotine cutting problems were developed. Five different test problems consisting of 17 individual rectangular pieces and a test problem consisting of 29 individual rectangular pieces were studied. In test problems, it is desired to place the pieces on a main piece limited with 200x200 unit field which has zero trim loss value. In this work, the influences of different parameters using in SA algorithm on solutions of cutting problems were investigated. Parameter group obtained from best result (Lundy and Mees cooling schedule, swap neighborhood move and number of inner loop:3) was found. Also trim loss values obtained from results of 17 and 29 pieces test problems were seen to change between 4% - 21% and 10% 17% respectively

Keywords

Simulated annealing algorithm, Improved bottom left algorithm, Cutting problems