Kesme problemine sezgisel bir yaklaşım
A heuristic approach to the cutting stock problem
Yazar: FIRAT BAYIR
Danışman: PROF. DR. ERHAN ÖZDEMİR
İstanbul Üniversitesi / Sosyal Bilimler Enstitüsü / İşletme Ana Bilim Dalı / Sayısal Yöntemler Bilim Dalı
Derece: Doktora, 2013
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control ; Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering ; İşletme = Business Administration
Dizin: Algoritmalar = Algorithms ; Ambalajlama = Packaging ; Gezgin satıcı problemi = Travelling salesman problem ; Kesme problemleri = Cutting problems ; Malzeme kesme problemleri = Material cutting problem ; Optimizasyon = Optimization ; Stok kesme problemi = Stock cutting problem ; İki boyutlu kesme = Two dimensional cutting

Özet:
Kesme ve yerleştirme problemi gerek akademisyenler için gerekse cam, metal, kağıt, tekstil deri gibi endüstriler için en önemli araştırma konularından biridir. Kesilecek küçük parçaların büyük hammaddelere atanması veya 3 boyutlu konteynırların yüklenmeleri bu tarz problemlerdendir. Bu tez çalışması, kesme ve yerleştirme sınıfındaki Stok Kesim Problemi?nin 1,5 boyutlu versiyonu olan Açık Boyut Problemidir. Problemin amacı, bir boyutu sabit diğer boyutu açık olan dikdörtgen şeklindeki bir stok malzemesine kesilecek parça kümesindeki tüm parçaları, fireyi minimize edecek şekilde atamaktır. Atanacak küçük parçaların konveks olma şartı aranmamaktadır. Probleme Gezgin Satıcı probleminin bir varyantı olarak yaklaşılmış, parçaların eklenme sıraları ve parçaların duruş açıları optimizasyon kriteri olarak ele alınmıştır. Problem, Genetik Algoritmalar yardımıyla çözülmüştür. Yeni bir çaprazlama operatörü önerilmiş, alanı büyük olan parçaya öncelik tanınması prensibi eklenmiştir. Paketleme algoritması olarak aşağı sol dolgu algoritması, döndürme özelliği eklenerek geliştirilmiştir. Uygulamaya konu olan kesilecek parçalar Anand, McCord ve Sharma?nın (1999) yayınladıkları makaleden alınmış, sonuçlar makalede önerilen metot ile karşılaştırılmıştır.



Anahtar Kelimeler: Kesme ve Yerleştirme Problemi, Stok Kesim Problemi, Açık Boyut Problemi, Genetik Algoritma, Gezgin Satıcı Problemi, Optimizasyon, Düzensiz Şekiller, Konveks Olmayan Çokgen, Konkav, Kumaş Kesimi, Metal Kesimi, Deri Kesimi, Döndürmeli Aşağı Sol Dolgu Algoritması

Abstract:
Cutting and Packing Problem is one of the most important research areas among both academicians and Industries such as glass, metal, paper and apparel. Assignments of small parts to the raw material sheets or three dimensional bin-packing problems are such problems. This work deals with Open Dimension Problem, that is 1,5 dimensional version of Cutting Stock Problem. Objective of the problem is assigning all of the parts from bill of manufacturing to a rectangular sheet which is one dimension is fixed but the other dimension is open by means of minimizing the waste of material. There is no restriction about the convexity of the parts. Approached to the problem as a variant of the Travelling Salesman Problem, order of the parts and angles was handled as optimization criteria. Problem was solved by using Genetic Algorithms. A new crossover operator was proposed; the principal of choosing the larger part was added. For packaging, bottom-left-fill algorithm was used by adding rotation feature. Parts which are subject to this study is taken from the published article of Anand, McCord and Sharma (1999), the results were compared with the proposed method in article



Keywords: Cutting and Packing Problem, Cutting Stock Problem, Open Dimension Problem, Genetic Algorithm, Travelling Salesman Problem, Optimisation, irregular Shapes, Non-Convex, Concave, Fabric Cut, Metal Cut, Leather Cut, Rotating 
Bottom-Left Algorithm