Optıcut: Desen minimizasyonlu tek boyutlu stok kesme problemi için yeni bir sezgisel yaklaşım
Opticut: A new heuristic algorithm for the one-dimensional cutting stock problem with pattern minimisation
- Tez No: 965313
- Danışmanlar: DOÇ. DR. ESRA TEKEZ
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2025
- Dil: Türkçe
- Üniversite: Sakarya Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Endüstri Mühendisliği Bilim Dalı
- Sayfa Sayısı: 103
Özet
Tek boyutlu stok kesme problemi (1DCSP), kâğıt, çelik, ambalaj ve plastik film gibi endüstriyel sektörlerde sıkça karşılaşılan bir kombinatoryal optimizasyon problemidir. Bu problemin temel amacı, büyük stok malzemelerini belirli talepleri karşılayacak şekilde daha küçük parçalara keserek fire miktarını ve üretim maliyetlerini en aza indirmektir. Gerçek dünya uygulamalarında, fire miktarının yanı sıra kesim desenleri arasındaki geçişlerden kaynaklanan kurulum maliyetleri gibi ek faktörler problemi karmaşık hale getirir. Tek boyutlu stok kesme probleminin desen minimizasyonlu varyantı, fire miktarını azaltırken aynı zamanda oluşturulan kesim desenlerinin sayısını en aza indirmeyi hedefler. Bu, malzeme kullanımını optimize ederken üretim süreçlerinde karmaşıklığı ve maliyeti düşürmek için bir denge kurmayı amaçlar. Daha az desen kullanımı, genellikle kurulum maliyetlerini azaltır ve operasyonel verimliliği artırır. NP-tam olarak sınıflandırılan bu problem, boyut arttıkça hesaplama karmaşıklığı üstel olarak yükseldiğinden, kabul edilebilir sürelerde pratik çözümler üretmek için sezgisel yaklaşımlara gereksinim duyar. Bu tezde, tek boyutlu stok kesme probleminin desen minimizasyonlu varyantını çözmek için OPTICUT adında yeni bir sezgisel algoritma geliştirilmiştir. OPTICUT, toplam maliyeti ve desen sayısını azaltmada mevcut en gelişmiş yöntemleri geride bırakarak, akademik araştırmalar ve endüstriyel uygulamalar için güçlü bir çözüm sunmaktadır. Bu tez, kapsamlı literatür taraması, detaylı hesaplama deneyleri ve duyarlılık analizleriyle algoritmanın etkinliğini kanıtlamaktadır. Bu tezde, 1DCSP alanındaki literatür, Web of Science veri tabanında 1983-2025 yılları arasında yayımlanan 169 çalışma incelenerek detaylı olarak analiz edilmiştir. Bu çalışmalar toplam 2,695 atıf almış olup, malzeme fire minimizasyonunun (%42,28) en yaygın araştırma hedefi olduğu belirlenmiştir. Maliyet optimizasyonu (%12.08) ikinci sırada yer alırken, desen minimizasyonu daha az çalışılmış ancak pratik açıdan kritik bir konu olarak öne çıkmaktadır. Mevcut çözüm yöntemleri arasında sezgisel yaklaşımlar (örneğin, sıralı sezgisel prosedür), meta-sezgisel yöntemler (örneğin, genetik algoritmalar) ve kesin yöntemler (örneğin, tamsayılı doğrusal programlama) bulunmaktadır. Ancak bu yöntemler, genellikle fire ve desen kullanımını aynı anda optimize etmekte zorlanmakta ve özellikle büyük ölçekli veya karmaşık problemlerde yetersiz kalmaktadır. Bu durum, OPTICUT'ın gidermeyi hedeflediği bir açıktır.OPTICUT, 1DCSP'yi desen minimizasyonuyla çözmek için üç aşamalı bir hibrit yaklaşım benimsemektedir: Başlangıç çözüm üretimi (sütun üretimi yaklaşımı ile): Gilmore ve Gomory'nin (1963) yönteminden esinlenerek, bu aşamada sütun üretimiyle başlangıçta uygulanabilir bir çözüm oluşturulur. Bu yöntem, fire minimizasyonunda genellikle etkili olsa da çok sayıda kesim deseni üretebildiğinden sonraki aşamalarda iyileştirme gerektirir. Alternatif çözümler üretimi (desen üretimi yaklaşımı ile): İki farklı algoritma, Algoritma A ve Algoritma B, alternatif kesim desenleri havuzunu oluşturur. Algoritma A, siparişleri uzunluk ve artık değerlerine göre önceliklendirerek 20 yineleme boyunca değişen öncelik katsayılarıyla çalışır. Algoritma B ise 50 yineleme boyunca izin verilen fire miktarını kademeli olarak artırarak desen çeşitliliğini sağlar. Bu mekanizmalar, çözüm uzayını kapsamlı bir şekilde keşfetmeyi ve yüksek kaliteli desenler üretmeyi mümkün kılar. Nihai optimizasyon (tamsayılı doğrusal programlama yaklaşımı ile): Önceki aşamalardan elde edilen desen havuzu, 45 saniyelik bir süre sınırı içinde tamsayılı doğrusal programlama (ILP) ile optimize edilir ve stok maliyetleri ile kurulum maliyetlerini içeren toplam maliyeti en düşük olan çözüm seçilir. Algoritma sipariş değeri (Vi), sipariş önceliği (Pri) ve izin verilen fire artışı gibi dinamik parametreleri kullanarak, zorlu problem örneklerine uygun yüksek kaliteli kesim desenleri üretir. Uygulamanın ayrıntıları, sözde kod ve akış şemalarıyla sunulmuş, böylece şeffaflık ve tekrarlanabilirlik sağlanmıştır. OPTICUT'ın performansı, CUTGEN1 (Gau & Wäscher, 1995) ve Umetani (2003, 2018) veri setlerinden alınan 1.840 benchmark örneğiyle test edilmiştir. Deneyler, Intel Core i7-1165G7 işlemci ve 16 GB RAM'e sahip bir bilgisayarda, Python ile PULP-CBC-CMD çözücüsü kullanılarak gerçekleştirilmiş olup örnek başına ortalama hesaplama süresi 165 saniye olarak kaydedilmiştir. CUTGEN1 sonuçları: Sipariş çeşitliliği ve stok uzunluk oranlarına göre 18 problem sınıfında gruplandırılan 1.800 test örneğinde, OPTICUT toplam maliyeti %0.0013 ve desen sayısını %0.6 oranında azaltmıştır. En iyi mevcut algoritmalarla (CUI, MSHP, YL) karşılaştırıldığında, stok kullanımında %83, desen sayısında %50 ve toplam maliyette %67 oranında baskınlık elde ederek genel verimlilikte üstünlük sağlamıştır. Umetani sonuçları: Kimyasal elyaf endüstrisinden alınan 40 gerçek dünya örneğinde, OPTICUT üstün performans göstermiştir. Stok maliyetinin stok uzunluğuna bağlı olduğu ve kurulum maliyetinin 100 olarak sabitlendiği varsayımında, MSHP ve CUI'ye kıyasla maliyette %0.51'e, desen sayısında ise %0.82'ye varan azalmalar elde edilmiştir. 'Fiber29_9080' örneği: OPTICUT, 35 stok rulosunu 6 desen ve 550 mm fire ile kullanırken, CUI aynı fire seviyesinde 7 desen kullanmıştır. Bu sonuç da OPTICUT'ın desen minimizasyon yetkinliğini açıkça ortaya koymaktadır. 150 CUTGEN1 örneği üzerinde gerçekleştirilen duyarlılık analizi, OPTICUT'ın parametre değişimlerine (Vi, Pri, fire artışı) karşı duyarlılığını incelemiştir. Sonuçlar, stok kullanımının tüm denemelerde sabit kaldığını, desen sayısının ise parametre aralıkları genişledikçe azaldığını ortaya koymuş; ancak bu etkinin minimal düzeyde olduğu belirlenmiştir. Bu tutarlılık, OPTICUT'ın farklı problem koşullarında güvenilirliğini artırmaktadır. Her ek deneme, hesaplama süresine yaklaşık 0,5 saniye eklemektedir. OPTICUT, literatüre aşağıdaki temel katkıları sunmaktadır: • Üstün performans: Stok uzunluğuna göre küçük ve büyük sipariş türlerini içeren çeşitli senaryolarda (CUTGEN1 grup 1 ve grup 3) ile gerçek dünya örneklerinde, mevcut yöntemlerden daha iyi sonuçlar elde etmiştir. • Maliyet ve desen azaltımı: Malzeme maliyetinin yanı sıra toplam maliyeti ve desen sayısını ölçülebilir oranda azaltarak operasyonel verimliliği artırmaktadır. • Esneklik: Kullanıcıların malzeme ve kurulum maliyetlerini ile deneme sayısını ayarlayarak ihtiyaçlarına göre optimize edilmiş farklı sonuçlar elde etmelerine olanak tanımaktadır. • Yenilikçi özellikler: Dinamik değişkenlerin kullanımı ve hibrit yaklaşımıyla, literatürdeki çözümleri aşan yüksek kaliteli çözümler üretmektedir. • Pratik uygulanabilirlik: Makul hesaplama süreleriyle gerçek dünya kesim operasyonlarında kullanılabilir bir çözüm sunmaktadır. OPTICUT için aşağıdaki geliştirmeler önerilmektedir: • Ticari çözücü entegrasyonu: Gurobi gibi bir çözücünün entegrasyonu, ILP çözüm süresini ve kalitesini iyileştirebilir. • Paralel hesaplama: Sütün üretme Algoritması, Algoritma A ve B'nin eşzamanlı çalışması, işlem süresini %50'ye kadar azaltabilir. • Çözüm sonrası desen azaltma: Çözüm sonrası uygulanacak ek algoritmalar, fire seviyesini koruyarak desen sayısını daha da düşürebilir. • Çoklu stok uzunlukları: Algoritmanın farklı stok uzunluklarını işleyebilmesi, uygulanabilirliğini artıracaktır. OPTICUT, desen minimizasyon varyantlı 1DCSP'yi çözmek için yenilikçi ve etkili bir yöntem sunmaktadır. Ampirik veriler, algoritmanın farklı senaryolarda mevcut yöntemlerden üstün performans sergilediğini göstermektedir. Sonuç olarak OPTICUT, maliyet ve desen minimizasyonunu birleştirerek kaynak verimliliği ve maliyet tasarrufu açısından önemli bir ilerleme sağlamaktadır.
Özet (Çeviri)
The one-dimensional cutting stock problem (1DCSP) is a well-known combinatorial optimization challenge encountered across various industrial sectors, including paper, steel, and plastic film production. The primary objective of 1DCSP is to efficiently cut larger stock materials into smaller pieces to meet specific demands while minimizing waste and production costs. In real-world applications, additional considerations such as setup costs—arising from transitions between cutting patterns—further complicate the problem. The variant addressed in this dissertation, known as the 1DCSP with pattern minimization, seeks to balance waste reduction with the minimization of the number of distinct cutting patterns, as fewer patterns typically reduce setup costs and improve operational efficiency. Classified as NP-hard, this problem exhibits exponential computational complexity as its size increases, necessitating heuristic approaches to achieve practical solutions within acceptable timeframes. This dissertation introduces OPTICUT, a novel heuristic algorithm designed to address the 1DCSP with pattern minimization. OPTICUT aims to outperform existing state-of-the-art methods by reducing both total costs and the number of cutting patterns, offering a robust and efficient solution for both academic research and industrial applications. The study builds on an extensive literature review, comprehensive computational experiments, and sensitivity analyses to validate the algorithm's effectiveness. The dissertation provides a thorough review of the 1DCSP literature, analyzing 169 publications from the Web of Science database spanning 1983 to 2025, with a total of 2,695 citations. The analysis reveals that material waste minimization is the most common research objective (42.28%), followed by cost optimization (12.08%). Pattern minimization, though less frequently studied, is critical in practical settings due to its impact on setup costs. Existing solution methods include heuristic approaches (e.g., Haessler's Sequential Heuristic Procedure, 1975), metaheuristics (e.g., genetic algorithms), and exact methods (e.g., integer linear programming, ILP). However, these approaches often struggle to simultaneously optimize waste and pattern usage, particularly in large-scale or complex scenarios, highlighting a gap that OPTICUT seeks to address. OPTICUT employs a three-stage hybrid methodology to tackle the 1DCSP with pattern minimization: Initial solution generation (using column generation approach): Drawing from Gilmore and Gomory (1963), this stage uses column generation to produce an initial feasible solution. While mostly effective at minimizing waste, it often generates a large number of patterns, necessitating further refinement. Alternative solutions generation (using pattern generation approach): Two distinct algorithms, Algorithm A and Algorithm B, create a pool of alternative cutting patterns. Algorithm A prioritizes items based on their length and residual value, iterating over 20 generations with varying priority coefficients. Algorithm B adjusts allowable waste incrementally across 50 iterations, ensuring diversity in pattern selection. These mechanisms enhance the exploration of the solution space. Final optimization (using integer linear programming approach): The pattern pool from the previous stages is optimized using ILP within a 45-second time limit, selecting the solution with the lowest total cost, which includes stock costs, setup costs, and waste-related expenses. The algorithm incorporates dynamic parameters—such as item value V(i), priority Pr(i), and allowable waste increase to generate high-quality cutting patterns tailored to challenging problem instances. pseudocode and flowcharts detail the implementation, ensuring transparency and reproducibility. OPTICUT's performance was rigorously evaluated using 1,840 benchmark instances from two datasets: CUTGEN1 (Gau & Wäscher, 1995) and Umetani (2003, 2018). Experiments were conducted on an Intel Core i7-1165G7 processor with 16 GB RAM, implemented in Python using the PULP-CBC-CMD solver, with an average computation time of 165 seconds per instance. CUTGEN1 results: Across 18 problem classes grouped by order variety and stock length ratios, OPTICUT reduced total costs by 0.0013% and pattern usage by 0.6% compared to state-of-the-art algorithms (e.g., CUI, MSHP, YL). It achieved dominance in 83% of classes for stock usage, 50% for pattern count, and 67% for total cost, outperforming competitors in overall efficiency. Umetani results: In 40 real-world fiber cutting instances, OPTICUT demonstrated superior performance, particularly with large stock lengths (e.g., 9080 mm). For stock cost = stock length and setup cost = 100, it achieved up to 0.51% cost reduction and 0.82% pattern reduction compared to MSHP and CUI, excelling in scenarios with diverse item sizes. An illustrative example,“Fiber29_9080,”showed OPTICUT utilizing 35 stock rolls with 6 patterns and 550 mm waste, compared to CUI's 7 patterns for the same waste level, underscoring its pattern minimization capability. A sensitivity analysis on 150 CUTGEN1 instances assessed OPTICUT's robustness against parameter variations (Vi, Pri, and waste increase). Results indicated consistent stock usage across trials, with pattern count decreasing as parameter ranges widened, albeit with minimal impact. This stability enhances OPTICUT's reliability across diverse problem configurations, with computation time increasing by approximately 0.5 seconds per additional trial. OPTICUT offers several key contributions: Superior performance: It outperforms existing methods in diverse scenarios, including small and large item types relative to stock length, as evidenced by CUTGEN1 groups 1 and 3, and real-world fiber examples. Cost and pattern reduction: The algorithm achieves measurable reductions in total cost and pattern count, enhancing operational efficiency. Flexibility: Users can adjust stock and setup costs, as well as trial numbers, for tailored optimization. Innovative features: Dynamic variables and a hybrid approach enable high-quality pattern generation, surpassing documented solutions in the literature. Practical applicability: With reasonable computation times, OPTICUT is viable for real-world cutting operations. Future enhancements could include: Commercial solver integration: Incorporating solvers like Gurobi could reduce ILP computation time and improve solution quality. Parallel computing: Simultaneous execution of Algorithm A and B could cut processing time by up to 50%. Post-Pattern reduction: Additional algorithms could further minimize patterns without increasing waste. Multiple stock lengths: Extending OPTICUT to handle varied stock lengths would broaden its applicability. This dissertation demonstrates that OPTICUT is an effective and innovative solution for the 1DCSP with pattern minimization, validated by empirical results showing significant advantages over existing methodologies. OPTICUT represents a significant advancement in the field of 1DCSP, bridging theoretical insights with practical utility. By addressing both cost and pattern minimization, it offers a promising framework for future research and industrial adoption, contributing to resource efficiency and cost savings in cutting stock operations.
Benzer Tezler
- Canalis opticus'ta Nervus opticus ve Arteria opthalmica ilişkisi: Endonazal endoskopik yaklaşım ile anatomik bir bakış
The relationship of the optic nerve and the opthlamic artery in the optic canal: An anatomical view with an endonasal endoscopical approach
TUĞBA MORALI GÜLER
- Nervus optıcusta yaşa bağlı yapısal değişikliklerin morfometrik, immünohistokimyasal ve ince yapı düzeyinde incelenmesi.
Morphometric, immunohistochemical and ultrastructural examination of age-related structural alterations in optic nerve.
SERPİL ÇİLİNGİROĞLU
Doktora
Türkçe
2007
AnatomiGazi ÜniversitesiAnatomi Ana Bilim Dalı
PROF. DR. ENGİN ÇALGÜNER
DOÇ. DR. MELTEM BAHÇELİOĞLU
- Canalis opticus ve sella turcica'nın bilgisayarlı tomografi görüntülerinde morfolojik analizi ve klinik önemi
Morphological analysis and clinical implication of the optic canaland sella turcica using computed tomography
FATMANUR İLGİN
Yüksek Lisans
Türkçe
2021
AnatomiNecmettin Erbakan ÜniversitesiAnatomi Ana Bilim Dalı
DR. ÖĞR. ÜYESİ GÜLAY AÇAR
- Nervus opticus'un intrakraniyal seyrinin incelenmesi ve histolojik analizi
The investigation of intracranial part and histology of the optic nerve
SÜLEYMAN HİLMİ TUNAHAN
Yüksek Lisans
Türkçe
2006
Adli TıpAfyon Kocatepe ÜniversitesiAnatomi Ana Bilim Dalı
DOÇ. DR. AHMET SONGUR
YRD. DOÇ. DR. ORHAN BAŞ
- Arteria centralis retinae'nin nervus opticus'a giriş yeri, orjin ve seyir varyasyonlarının araştırılması
Başlık çevirisi yok
NECDET KOCABIYIK