Journals / Avrupa Bilim ve Teknoloji Dergisi / 2019 / Cilt: 0 - Sayı: 17
Solution of Two Dimensional Rectangular Strip Packing Problem Using Heuristic Algorithms
- Pages
- 315–322
- DOI
- —
Abstract
In this study, a method is proposed for the solution of two-dimensional rectangular strip-packing problem by using bottom-left fill, first-fit decreasing and no-fit polygon heuristic algorithms. The two-dimensional rectangular strip-packing problem (2D-SPP) is the placement of a series of rectangular pieces on a strip with a constant width and infinite height. The goal is to minimize the height required to completely place all the rectangles onto the strip. In order to solve this problem, the bottom-left fill algorithm is used for the placement process and the no-fit polygon method is used to prevent the overlap between the rectangular parts. In addition, after the parts are sorted in descending order by areas, the first-fit decreasing heuristic algorithm is used as the selection algorithm for the placement process. The study has been carried out on 21 different data sets and performance evaluation has been done. As a result of conducted experimental studies, near to optimal solutions were obtained. The experimental results show the effectiveness of the proposed heuristic methods for 2D-SPP.
Özet
Bu çalışmada, alt sol dolgu, ilk uygun azalan ve uygun olmayan çokgen sezgisel algoritmaları kullanılarak iki boyutlu dikdörtgen şeritpaketleme probleminin çözümü üzerine bir yöntem önerilmektedir. İki boyutlu dikdörtgen şerit paketleme problemi (2D-SPP), sabitgenişlik ve sonsuz yüksekliğe sahip bir şerit üzerine bir dizi dikdörtgen parçanın yerleştirilmesidir. Amaç, tüm dikdörtgenleritamamen şeridin içine yerleştirmek için gereken yüksekliği en aza indirgemektir. Bu problemin çözümünde, yerleştirme işlemi için altsol dolgu algoritması, dikdörtgen parçalar arasında oluşabilecek çakışmayı önlemek için uygun olmayan çokgen yöntemikullanılmıştır. Ayrıca, parçalar alanlarına göre azalan sırada sıralandıktan sonra yerleştirme işlemi için kullanılacak olan seçimalgoritması olarak da ilk uygun azalan sezgisel algoritması kullanılmıştır. 21 farklı veri seti üzerinde çalışmalar gerçekleştirilmiş veperformans değerlendirilmesi yapılmıştır. Gerçekleştirilen deneysel çalışmalar sonucunda optimal çözüme yakın sonuçlar eldeedilmiştir. Deneysel sonuçlar, 2D-SPP için önerilen sezgisel yöntemlerin etkinliğini göstermektedir.