For developers
1D kesim stoku problemi
Gerekli boylardan oluşan bir seti, en az sayıda stok profil kullanarak nasıl keseceğiniz sorusu, 1D kesim stoku problemidir: klasik ve gerçekten zor bir optimizasyon problemi. Bu yazıda ne olduğu, kaba kuvvet yöntemlerine neden direndiği ve bu sitenin arkasındaki API de dahil olmak üzere pratikte nasıl çözüldüğü anlatılmaktadır.
1D kesim stoku problemi nedir
Size sabit boyda stok parçalar (örneğin 6000 mm'lik profiller) ve her birinin bir boyu ve adedi olan gerekli parçaların bir listesi verilir. Bir kesim şablonu, tek bir stok profili bu parçalardan bazılarını elde edecek şekilde kesmenin bir yoludur; artan her boy zayiattır. Problem, her gerekli parçanın üretilmesi ve toplam stok profil sayısının (veya eşdeğer olarak toplam zayiatın) mümkün olan en aza indirilmesi için hangi şablonların seçileceğini ve her birinde kaç profilin kesileceğini belirlemektir. Tek boyutludur, çünkü sadece uzunluk önemlidir: testere tüm kesit boyunca ilerler, bu nedenle genişlik ve profil yerleşime dahil olmaz.
1D kutu paketleme ve neden NP-zor olduğu
Kesim stoku problemi, 1D kutu paketleme probleminin bir genellemesidir: kutu paketleme, farklı boyutlardaki bir dizi öğeyi en az sayıda sabit boyutlu kutuya paketlemenizi ister. Kesim stoku ise, öğeler yüksek adetlerde tekrarlandığında aynı sorudur, bu yüzden tek tek öğeler yerine şablonlar üzerinden mantık yürütürsünüz. Kutu paketleme, klasik NP-zor problemlerden biridir ve 'bu öğeler k kutuya sığabilir mi' şeklindeki karar verme biçimi NP-tamdır. Kesim stoku da bu zorluğu miras alır.
Sebep, kombinatoryal patlamadır. Farklı kesim şablonlarının sayısı, parça boyutlarının sayısıyla katlanarak artar ve adetlerin bu şablonlara dağıtılma şekillerinin sayısı bunun da üzerine patlar. Garanti optimumu, girdiyle polinom olarak ölçeklenen bir sürede bulan bilinen bir algoritma yoktur ve P, NP'ye eşit olmadıkça da olmayacaktır. Bu yüzden gerçek çözücüler her şeyi listelemez; hangi olasılıkları eleyebilecekleri konusunda akıllıca davranırlar.
Pratikte nasıl çözülür
İlk-uygun-azalan (FFD)
İşin yükünü çeken sezgisel yöntem: gerekli parçaları en uzundan en kısaya doğru sıralayın, ardından her birini sığdığı ilk profile yerleştirin ve yalnızca hiçbirinde yer kalmadığında yeni bir profil açın. Hızlıdır ve şaşırtıcı derecede iyidir; kanıtlanabilir şekilde optimum profil sayısının yaklaşık 11/9'u artı küçük bir sabit kadar bir aralıkta sonuç verir. Çoğu araç burada durur; iyi bir araç ise FFD'yi bitiş çizgisi olarak değil, başlangıç noktası olarak kullanır.
Sütun oluşturma (Gilmore ve Gomory)
Büyük örnekleri çözülebilir kılan formülasyon. Gilmore ve Gomory (1961), problemi her kesim şablonu için bir değişkenle yazdılar ve katlanarak artan sayıda şablon olduğundan, doğrusal gevşemeyi gecikmeli sütun oluşturma ile çözdüler: bir avuç şablonla başlayın ve sınırlı bir sırt çantası alt problemini çözerek tekrar tekrar bir sonraki en kullanışlı olanı üretin. Ürettiği alt sınır, meşhur derecede kesindir.
Dal-sınır ve dal-fiyat
Bu kesirli gevşemeyi tam sayıda profile dönüştürmek için arama yapmanız gerekir, ama körü körüne değil. Dal-sınır, şimdiye kadar bulunan en iyi planı geçemeyecek tüm dalları budamak için LP sınırını kullanırken tamsayı seçenekleri ağacını keşfeder; sütun oluşturma ile birleştirildiğinde, çoğu kesin kesim stoku çözücüsünün temeli olan dal-fiyat haline gelir.
Alt sınırlar ve bir kanıt
Ciddi bir çözücü sadece bir plan döndürmez, bir alt sınır hesaplar (LP gevşemesinden veya daha basit bir toplam uzunluk argümanından) ve karşılaştırır. Bir plan, sınırın kaçınılmaz olduğunu kanıtladığı kadar profil kullandığında, kanıtlanabilir şekilde optimaldir: hiçbir plan daha iyisini yapamaz ve çözücü şanslı olduğunu ummak yerine bunu söyleyebilir.
LinearCutting bunu nasıl çözer
LinearCutting şöyle çalışır: önce hızlı bir sezgisel yöntemle anında uygulanabilir bir plan oluşturur, ardından sınıra dayalı bir arama ile planı sürekli iyileştirir. Bu arama, ya alt sınıra ulaşıp kanıtlanabilir şekilde en uygun planı bulur (ve bunu size bildirir) ya da zaman bütçesini doldurup o ana kadar bulduğu en iyi planı döndürür. Fiziksel koşulları da hesaba katar: her kesimde testere payı, kafa-kuyruk kesme payı, sabit miktarda fire ve fazladan malzeme gerektiren açılı kesimler. Çünkü testereyi hesaba katmayan bir plan sadece verimsiz değil, aynı zamanda yanlıştır. Sonuçları diğer araçlarla karşılaştırabilmeniz için referans işler yayınlanmıştır.
Bu hizmet bir JSON API olarak sunulur: parçalarınızı ve stok malzemenizi gönderin, karşılığında yerleşimleri, zayiatı, ayar sayısını ve planın optimum sınıra ulaşıp ulaşmadığını içeren doğrulanmış bir kesim planı alın. Python (pip install linearcutting) ve JavaScript veya TypeScript (npm install linearcutting) için resmi istemciler mevcuttur, bu sayede her iki dilde de birkaç satır kodla çağrı yapabilirsiniz.
Kodunuzdan çözün
Çözücü yazmakla uğraşmayın, hazır olanı çağırın. Bu sitedeki hesap makinesinin arkasında çalışan motorun aynısı, resmi Python ve JavaScript istemcileri, ücretsiz bir genel kullanım katmanı ve belgelerde çalıştırabileceğiniz canlı bir örneği olan bir JSON API'dir.
pip install linearcutting npm install linearcutting