Stokta kesme sorunu - Cutting stock problem

Gelen işlemler araştırma , kesme stok problemi standart boyutlu parçaların kesilmesi sorunudur stok kağıt ruloları ya da malzeme, metal levha minimize malzemenin israf ise, belirtilen boyutlardaki parçalara. Bu bir olan optimizasyon problemi de matematik sektöründe uygulamalardan kaynaklanmaktadır. Hesaplama karmaşıklığı açısından , sorun, sırt çantası sorununa indirgenebilen NP-zor bir sorundur . Problem bir tamsayı doğrusal programlama problemi olarak formüle edilebilir .

Tek boyutlu kesim stoğu probleminin gösterimi

Bir kağıt makinesi, her biri 5600 mm genişliğinde sınırsız sayıda ana (jumbo) rulo üretebilir. Aşağıdaki tabloda aşağıdaki 13 öğe kesilmelidir.

Bu tür bir problemle ilgili önemli olan şey, birçok farklı ürün biriminin aynı ana rulodan yapılabilmesidir ve olası kombinasyonların sayısı genel olarak çok fazladır ve numaralandırmak önemsiz değildir.

Bu nedenle sorun, talebin karşılanması ve israfın en aza indirilmesi için ana merdaneden ürün merdaneleri yapmak için optimum bir model seti bulmaktır.

Genişlik	# Öğeler
1380	22
1520	25
1560	12
1710	14
1820	18
1880	18
1930	20
2000	10
2050	12
2100	14
2140	16
2150	18
2200	20

Sınırlar ve çekler

Toplam ürün miktarını her bir ana silindirin boyutuna bölerek basit bir alt sınır elde edilir. Gerekli toplam ürün 1380 x 22 + 1520 x 25 + ... + 2200 x 20 = 407160 mm'dir. Her bir ana rulo 5600 mm'dir ve minimum 72,7 rulo gerektirir, bu da 73 veya daha fazla rulo gerektiği anlamına gelir.

Çözüm

Bıçak değişikliklerini en aza indirgeyen, küçük beyaz dairelerle gösterilen minimum atık çözümü

Bu küçük örnek için 308 olası desen vardır. En uygun cevap, 73 ana silindir gerektirir ve% 0.401 atık içerir; Bu durumda, bu atık düzeyine sahip minimum model sayısının 10 olduğu sayısal olarak gösterilebilir. Ayrıca, her biri 10 model ve% 0.401'lik bir israfa sahip olan bu tür 19 farklı çözümün mevcut olduğu hesaplanabilir. aşağıda ve resimde gösterilmiştir:

Tekrarlama	İçindekiler
2	1820 + 1820 + 1820
3	1380 + 2150 + 1930
12	1380 + 2150 + 2050
7	1380 + 2100 + 2100
12	2200 + 1820 + 1560
8	2200 + 1520 + 1880
1	1520 + 1930 + 2150
16	1520 + 1930 + 2140
10	1710 + 2000 + 1880
2	1710 + 1710 + 2150
73

Sınıflandırma

Stok kesme problemleri birkaç şekilde sınıflandırılabilir. Bir yol, kesimin boyutluluğudur: yukarıdaki örnek, tek boyutlu (1D) bir problemi göstermektedir; 1D'nin diğer endüstriyel uygulamaları boruları, kabloları ve çelik çubukları keserken ortaya çıkar. Mobilya, giyim ve cam üretiminde iki boyutlu (2D) problemlerle karşılaşılmaktadır. Ana öğe veya gerekli parçalar düzensiz şekilli olduğunda (deri, tekstil, metal endüstrilerinde sıklıkla karşılaşılan bir durum) bu, yuvalama sorunu olarak adlandırılır .

Kesmeyi içeren pek çok üç boyutlu (3D) uygulama bilinmemektedir; ancak yakından ilişkili 3B paketleme problemi , nesneleri nakliye konteynırlarına paketlemek gibi birçok endüstriyel uygulamaya sahiptir (bkz. örneğin konteynerleştirme : ilgili küre paketleme problemi 17. yüzyıldan beri incelenmiştir ( Kepler varsayımı )).

Başvurular

Yüksek üretim hacimleri için stok kesme problemlerinin endüstriyel uygulamaları, özellikle daha küçük birimler halinde kesilen büyük rulolarda temel malzeme üretildiğinde ortaya çıkar (bkz. Rulo dilimleme ). Bu, örneğin kağıt ve plastik film endüstrilerinde ve aynı zamanda çelik veya pirinç gibi yassı metallerin üretiminde de yapılır. Makine ve süreç sınırları, müşteri gereksinimleri ve kalite sorunları nedeniyle özel üretim kısıtlamalarından kaynaklanan birçok değişken ve ek kısıtlamalar vardır; bazı örnekler:

• İlk aşamada üretilen merdanelerin daha sonra ikinci kez işlendiği iki aşamalı. Örneğin, tüm ofis kırtasiye malzemeleri (örn . Avrupa'da A4 boyutu, ABD'de Letter boyutu ) böyle bir süreçte üretilir. Karmaşıklık, ikinci aşamadaki makinelerin birincilden daha dar olması nedeniyle ortaya çıkıyor. Üretimin her iki aşamasının da verimli kullanımı önemlidir (enerji veya malzeme kullanımı açısından) ve birincil aşama için verimli olan, ikincil aşamada verimsiz olabilir ve bu da ödünleşmelere yol açabilir. Metalize film (atıştırmalıkların paketlenmesinde kullanılır) ve kağıt üzerinde plastik ekstrüzyon ( sıvı paketlemede , örneğin meyve suyu kartonlarında kullanılır) bu tür bir işlemin diğer örnekleridir.
• Dilme işleminin fiziksel veya mantıksal kısıtlamalara sahip olduğu sarıcı kısıtlamaları: çok yaygın bir kısıtlama, yalnızca belirli sayıda dilimleme bıçağının mevcut olmasıdır, bu nedenle uygulanabilir modellerin maksimum sayıda rulodan fazlasını içermemesi gerekir. Sarma makineleri standartlaştırılmadığından, birçok başka kısıtla karşılaşılmaktadır.
• Müşteri gereksiniminin bir örneği, belirli bir siparişin iki kenar pozisyonunun herhangi birinden karşılanamadığı zamandır: bunun nedeni, tabakanın kenarlarının kalınlıkta daha büyük varyasyonlara sahip olma eğiliminde olmasıdır ve bazı uygulamalar bunlara karşı çok hassas olabilir.
• Kalite sorununa bir örnek, ana rulonun etrafından kesilmesi gereken kusurlar içermesidir. Fotoğraf kağıdı veya Tyvek gibi zorlu kalite özelliklerine sahip pahalı malzemeler , boşa harcanan alanın en aza indirilmesi için dikkatlice optimize edilmelidir.
• Birden fazla makinede sipariş üretilebildiği ve bu makinelerin farklı genişliklere sahip olduğu durumlarda çok makineli problemler ortaya çıkmaktadır. Genel olarak birden fazla ana silindir genişliğinin bulunması, israfı önemli ölçüde artırır; ancak pratikte ek sipariş bölme kısıtlamalarının hesaba katılması gerekebilir.
• Ayrıca, üretilen merdanelerin aynı çapta olması gerekmediği, ancak bir aralık içinde değişebildiği yarı sürekli bir problem de vardır. Bu genellikle sayfa siparişlerinde gerçekleşir. Bu bazen 1½ boyutlu problem olarak bilinir . Bu varyant , biraz kafa karıştırıcı bir şekilde oluklu mukavva programlama problemi olarak adlandırılan oluklu mukavva üretiminde de ortaya çıkar .
• Bazı kağıt makineleri, talep edilen ürünlere kıyasla nispeten dar olduğundan, bazı şirketler , iki makaranın (ilk jumbo makaraların kesilmesiyle üretilen) yan yana birleştirildiği bir sıyırma ( ağ-kaynak olarak da bilinir ) ikincil işlemine yatırım yaptı. daha geniş bir rulo oluşturmak için yan taraf (biraz üst üste binme ile). Birincil işlemde daha dar makaraların üretilmesi, toplam atığın azalmasına neden olur.
• Metal endüstrisinde önemli bir fark, tipik olarak ana silindirlerin daha erken üretilmesi ve genellikle birbirinden farklı olmasıdır (hem genişlik hem de uzunluk açısından). Bu nedenle, yukarıda bahsedilen çoklu makine problemi ile benzerlikler vardır. Uzunluk varyasyonlarının varlığı 2 boyutlu bir sorun yaratır, çünkü israf hem genişlik hem de uzunluk açısından ortaya çıkabilir.
• Giyotin sorun ancak tüm yolu, her bir tabaka boyunca devam sadece kesimler izin verilir, belirtilen boyutlardaki dikdörtgenler halinde kesilmesi başka bir 2-D sorundur. Bu sorunun endüstriyel uygulamaları cam endüstrisinde bulunabilir.

Giyotin kesim örneği

Giyotin içermeyen kesim örneği

• Tek boyutlu durum için, verilen talebi karşılayacak en iyi ana boyutu belirleme problemi , çeşitlendirme problemi olarak bilinir .

Tarih

Kesme stoğu sorunu ilk olarak 1939'da Kantorovich tarafından formüle edildi . 1951'de bilgisayarlar yaygın olarak bulunmadan önce, LV Kantorovich ve VA Zalgaller , kesme aşamasında malzemenin ekonomik kullanımı sorununu doğrusal programlama yardımıyla çözmeyi önerdi. Önerilen teknik daha sonra sütun oluşturma yöntemi olarak adlandırıldı .

Matematiksel formülasyon ve çözüm yaklaşımları

Kesme stoğu problemi için standart formülasyon (ancak tek değil) , her biri parça gerektiren m sipariş listesiyle başlar , burada . Daha sonra olası tüm kesim kombinasyonlarının bir listesini oluştururuz (genellikle "desenler" olarak adlandırılır). Bu kalıpların sayısı olsun . Her modelle , desenin kaç kez kullanılacağını, nerede kullanılacağını temsil eden pozitif bir tamsayı değişkeni ilişkilendiririz . Doğrusal tamsayı programı daha sonra: ${\ displaystyle q_ {j}}$${\ displaystyle j = 1, \ ldots, m}$${\ displaystyle n}$${\ displaystyle x_ {i}}$${\ displaystyle i}$${\ displaystyle i = 1, \ ldots, n}$

${\ displaystyle \ min \ toplam _ {i = 1} ^ {n} c_ {i} x_ {i}}$

${\ displaystyle {\ text {st}} \ sum _ {i = 1} ^ {n} a_ {ij} x_ {i} \ geq q_ {j}, \ quad \ quad \ forall j = 1, \ noktalar, m}$

${\ displaystyle x_ {i} \ geq 0}$ , tamsayı

nerede kere sipariş sayısıdır desende göründüğünü ve desen maliyeti (genellikle atık) 'dir . Miktar kısıtlamalarının kesin doğası, incelikle farklı matematiksel özelliklere yol açabilir. Yukarıdaki formülasyonun miktar kısıtlamaları minimum kısıtlamalardır (en azından her bir siparişin belirli bir miktarı üretilmelidir, ancak muhtemelen daha fazlası). Ne zaman objektif aza indirir kullanılan ana öğe sayısı ve üretilecek miktar için kısıt eşitlik değiştirilirse, denir bin ambalaj sorunu . En genel formülasyonun iki taraflı kısıtlamaları vardır (ve bu durumda minimum atık çözümü, minimum ana öğe sayısından fazlasını tüketebilir): ${\ displaystyle a_ {ij}}$${\ displaystyle j}$${\ displaystyle i}$${\ displaystyle c_ {i}}$${\ displaystyle i}$${\ displaystyle c_ {i} = 1}$

${\ displaystyle q_ {j} \ leq \ sum _ {i = 1} ^ {n} a_ {ij} x_ {i} \ leq Q_ {j}, \ quad \ quad \ forall j = 1, \ noktalar, m }$

Bu formülasyon sadece tek boyutlu problemler için geçerli değildir. Hedefin israfı en aza indirmek değil, üretilen ürünlerin toplam değerini maksimize etmek ve her siparişin farklı bir değere sahip olmasını sağlamak olduğu bir çok varyasyon mümkündür.

Genel olarak, olası örüntülerin sayısı, m'nin bir fonksiyonu olan mertebelerinin sayısı olarak üssel olarak artar . Sipariş sayısı arttıkça, olası kesme modellerini saymak pratik olmayabilmektedir.

Alternatif bir yaklaşım, gecikmeli sütun oluşturma kullanır . Bu yöntem, stokta kesme sorununu sadece birkaç kalıpla başlayarak çözer. Gerektiğinde ek kalıplar üretir. Tek boyutlu durum için, yeni modeller , lineer programdan çift ​​değişkenli bilgi kullanılarak sırt çantası problemi adı verilen yardımcı bir optimizasyon problemi çözülerek tanıtıldı . Sırt çantası problemi, onu çözmek için dal ve sınır ve dinamik programlama gibi iyi bilinen yöntemlere sahiptir . Gecikmeli Sütun Oluşturma yöntemi, özellikle sorunun boyutu büyüdükçe, orijinal yaklaşımdan çok daha verimli olabilir. Sütun nesil kesme stok sorunu uygulanan yaklaşım 1960'larda yayınlanan bildiri bir dizi Gilmore ve Gomory öncülük ettiler. Gilmore ve Gomory, bu yaklaşımın, tüm olası kalıpları önceden numaralandırmaya gerek kalmadan (kesirli) optimal çözüme yakınsamanın garantili olduğunu gösterdi.

Orijinal Gilmore ve Gomory yönteminin bir sınırlaması, integralliği ele almamasıdır, bu nedenle çözüm kesirler içerebilir, örneğin belirli bir model 3.67 kez üretilmelidir. En yakın tam sayıya yuvarlama, optimal olmayan bir çözüme ve / veya bazı siparişlerin eksik veya fazla üretilmesine yol açabileceği (ve iki taraflı talep kısıtlamaları varlığında olası fizibilite) genellikle işe yaramaz. ). Bu sınırlama, problemin çok büyük örneklerini (genellikle pratikte karşılaşılandan daha büyük) optimalliğe (minimum atıkla çözüm bulma anlamında) çözebilen modern algoritmalarda aşılır.

Stokta kesme sorunu, aynı miktarda atıkla birden fazla çözümün mümkün olması nedeniyle genellikle oldukça dejenere olur. Bu dejenerasyon, atık miktarını etkilemeden öğeleri hareket ettirmek, yeni modeller oluşturmak mümkün olduğu için ortaya çıkar. Bu, aşağıdakiler gibi diğer bazı kriterlerle ilgili problemlerin bütün bir koleksiyonuna yol açar:

• Minimum desen sayısı sorunu: minimum atık çözümleri arasında bir minimum desen sayısı çözümü bulmak. Atık bilindiğinde bile bu çok zor bir sorundur. N boyutlu herhangi bir eşitlik kısıtlamalı tek boyutlu örneğin n + 1 modelden fazla olmayan en az bir minimum atık çözümüne sahip olduğu varsayımı vardır . Bu varsayım ilk olarak Nisan 2020'de, 11 desen gerektiren 9 boyuttan oluşan bir örnekle çürütüldü.
• Minimum yığın sorunu: Bu, herhangi bir zamanda çok fazla kısmen tamamlanmış siparişe sahip olmamak için modellerin sıralanmasıyla ilgilidir. Bu, dinamik programlamaya dayalı verimli bir algoritmanın yayınlandığı 2007 yılına kadar açık bir sorundu.
• Minimum bıçak değişikliği sayısı problemi (tek boyutlu problem için): Bu, dilimleme bıçaklarının hareket ettirilmesi gereken sayısını en aza indirmek için modellerin sıralanması ve izin verilmesiyle ilgilidir. Bu, genelleştirilmiş seyyar satıcı sorununun özel bir durumudur .

Referanslar

daha fazla okuma

• Chvátal, V. (1983). Doğrusal Programlama . WH Freeman. ISBN   978-0-7167-1587-0 .
• Hatem Ben Amor, JM Valério de Carvalho, Column Generation'da Kesme Stok Sorunları , Guy Desaulniers, Jacques Desrosiers ve Marius M.Solomon, Springer, 2005, XVI, ISBN   0-387-25485-4 tarafından düzenlenmiştir.
• M. Delorme, M. Iori, S. Martello, Bin paketleme ve kesme stoğu problemleri: Matematiksel modeller ve kesin algoritmalar , European Journal of Operational Research 2016, 255, 1–20, doi : 10.1016 / j.ejor.2016.04.030