İmalat sektöründe parça yerleştirme ve kesme probleminin optimizasyonu
Optimization of part placement and cutting problem in the manufacturing sector
Yazar: HÜSEYİN FIRAT
Danışman: DOÇ. DR. DAVUT HANBAY
İnönü Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2018
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Kesme ve paketleme problemi, bir yüzeyin veya nesnenin içine çok sayıda düzenli veya düzensiz şeklin örtüşme olmadan düzenli bir şekilde yerleştirilmesidir. Birleştirici optimizasyon yöntemleri içinde yer alan bu problem, matematiksel modelle çözümün zor olduğu, NP-Complete problemi olarak bilinmektedir. Bu problemin amacı, elde bulunan malzemeyi verimli bir şekilde kullanarak elde edilecek atık miktarının en aza indirilmesidir.
Bu tezde, çok çeşitli endüstriyel ve imalat sektöründe yaygın olarak görülen problemlerden biri olan iki boyutlu kesme ve paketleme problemi incelenmiş ve çeşitli uygulamalar geliştirilmiştir. Bu kapsamda, kesme ve paketleme problemi için, alt-sol, uygun olmayan çokgen, alt-sol dolgu gibi sezgisel yöntemler ve benzetimli tavlama (BT) ve tabu arama (TA) gibi metasezgisel yöntemler kullanılarak çözüm yaklaşımları geliştirilmiştir. Deneysel çalışmalarda, yerleştirme işlemleri için alt-sol ve alt-sol dolgu yöntemleri, yerleştirilen parçalar arasında çakışma olmaması için uygun olmayan çokgen yöntemi ve daha hızlı ve verimli paketleme işlemleri için de metasezgisel yöntemlerden BT ve TA algoritmaları kullanılmaktadır.
Sezgisel yöntemlerle gerçekleştirilen deneyler sonucunda, fire oranının %11,2 ile %15,26 arasında değiştiği görülmektedir. Metasezgisel yöntemler kullanılarak gerçekleştirilen deneyler sonucunda ise, elde edilen fire oranları %2 ile %7,2 arasında değişkenlik göstermektedir ve bu fire oranları ise, çoğu endüstriler için oldukça iyi bir orandır. Deneysel sonuçlar, metasezgisel yöntemlerle yapılan paketleme işlemlerinin daha verimli olduğunu göstermektedir.

ANAHTAR KELİMELER: Kesme Stok Problemi, Paketleme Problemi, Uygun Olmayan Çokgenler, Alt-Sol Yerleştirme Teoremi, Optimizasyon, Minimum Fire

Abstract:
Cutting and packing problem is the placement of a large number of regular or irregular shapes into a surface or object without overlapping regularly. This problem, which takes part in combining optimization methods, is known as NP-Complete problem, which is difficult to solve with mathematical model. The purpose of this problem is to minimize the amount of waste that will be produced by using the available material efficiently.
In this thesis, two dimensional cutting and packing problem which is one of the problems which is widely seen in various industrial and manufacturing sectors has been investigated and various applications have been developed. In this manner, solution approaches have been developed for cutting and packing problem using heuristic methods such as bottom-left, no-fit polygon and bottom-left fill and metaheuristic methods such as Simulated Annealing (SA) and Tabu Search (TA). In experimental studies, bottom-left and bottom-left fill methods are used for placement process, no-fit polygon method is used for no overlap between placed parts and metaheuristic methods such as SA and TA algorithms are used for faster and efficient packing process.
As a result of experiments conducted with heuristic methods, it seen that, the waste rate varies between 11.2% and 15.26%. As a result of experiments carried out with metaheuristic methods, the waste rate varies between 2% and 7.2%, and these waste rate is pretty good for most industries. Experimental results show that the packing process using metaheuristics methods is more efficient.

KEYWORDS: Cutting Stock Problem, Packing Problem, No-Fit Polygon, Bottom-Left Placement Theorem, Optimization, Minimum Waste