Bu yazıda size bir depodaki boş hücre eksikliği sorununu nasıl çözdüğümüzü ve böyle bir sorunu çözmek için ayrık bir optimizasyon algoritmasının geliştirilmesini anlatacağız. Optimizasyon probleminin matematiksel modelini nasıl "oluşturduğumuzdan" ve algoritma için girdi verilerini işlerken beklenmedik bir şekilde karşılaştığımız zorluklardan bahsedelim.
Eğer matematiğin iş hayatındaki uygulamalarıyla ilgileniyorsanız ve 5. sınıf düzeyinde formüllerin katı kimlik dönüşümlerinden korkmuyorsanız, kediye hoş geldiniz!
Makale uygulayanlara faydalı olacaktır. WMS-sistemler, depo veya üretim lojistiği endüstrisinde çalışan kişilerin yanı sıra matematiğin iş dünyasındaki uygulamaları ve bir kuruluştaki süreçlerin optimizasyonu ile ilgilenen programcılar.
Giriş kısmı
Bu yayın, depo süreçlerinde optimizasyon algoritmalarının uygulanmasındaki başarılı deneyimimizi paylaştığımız makale serisinin devamı niteliğindedir.
В uyguladığımız deponun özelliklerini açıklıyor WMS-sistem ve ayrıca uygulama sırasında kalan mal gruplarının kümelenmesi sorununu neden çözmemiz gerektiğini açıklıyor WMS-sistemler ve bunu nasıl yaptığımız.
Optimizasyon algoritmaları hakkındaki makaleyi yazmayı bitirdiğimizde makalenin çok büyük olduğu ortaya çıktı, bu yüzden biriken materyali 2 parçaya ayırmaya karar verdik:
- İlk bölümde (bu makalede), problemin matematiksel modelini nasıl “kurduğumuzdan” ve algoritma için girdi verilerini işlerken ve dönüştürürken beklenmedik bir şekilde karşılaştığımız büyük zorluklardan bahsedeceğiz.
- İkinci bölümde algoritmanın dilde uygulanmasını ayrıntılı olarak ele alacağız. C + +, hesaplamalı bir deney gerçekleştireceğiz ve bu tür "akıllı teknolojilerin" müşterinin iş süreçlerinde uygulanması sırasında edindiğimiz deneyimi özetleyeceğiz.
Bir makale nasıl okunur? Önceki makaleyi okuduysanız hemen “Mevcut çözümlere genel bakış” bölümüne gidebilirsiniz; okumadıysanız, çözülen sorunun açıklaması aşağıdaki spoilerde yer almaktadır.
Müşterinin deposunda çözülmekte olan sorunun açıklaması
Süreçlerde darboğaz
2018 yılında hayata geçirmek üzere bir proje tamamladık. WMS- Çelyabinsk'teki “Ticaret Evi “LD” deposundaki sistemler. “1C-Logistics: Warehouse Management 3” ürününü 20 işyerinde (operatörler) hayata geçirdik. WMS, mağaza sahipleri, forklift sürücüleri. Ortalama depo alanı yaklaşık 4 bin m2, hücre sayısı 5000 ve SKU sayısı 4500'dür. Depoda 1 kg'dan 400 kg'a kadar farklı boyutlarda kendi imalatımız olan küresel vanalar depolanmaktadır. Malların FIFO'ya göre seçilmesi gerektiğinden depodaki envanter partiler halinde depolanır.
Depo süreç otomasyon şemalarının tasarımı sırasında, mevcut optimal olmayan envanter depolama sorunuyla karşı karşıya kaldık. Vinçlerin depolanması ve döşenmesinin özellikleri, bir birim depolama hücresinin yalnızca bir partiden ürünleri içerebileceği şekildedir (bkz. Şekil 1). Ürünler depoya günlük olarak gelir ve her varış ayrı bir partidir. Toplamda 1 aylık depo operasyonu sonucunda her birinin ayrı bir hücrede depolanması gerekmesine rağmen 30 ayrı parti oluşturuluyor. Ürünler genellikle bütün paletler halinde değil, parçalar halinde seçilir ve sonuç olarak, birçok hücredeki parça seçim bölgesinde aşağıdaki resim gözlenir: hacmi 1 m3'ten fazla olan bir hücrede, birkaç adet vinç vardır. Hücre hacminin %5-10'undan daha azını kaplar.
Şekil 1. Bir hücredeki birkaç parçanın fotoğrafı
Depolama kapasitesinin en iyi şekilde kullanılmadığı açıktır. Felaketin ölçeğini hayal etmek için rakamlar verebilirim: ortalama olarak, deponun farklı operasyon dönemlerinde "küçük" bakiyelerle 1 m3'ten fazla hacme sahip bu tür hücrelerin 100 ila 300 hücresi vardır. Depo nispeten küçük olduğundan, deponun yoğun olduğu sezonlarda bu faktör bir "darboğaz" haline gelir ve deponun kabul ve sevkiyat süreçlerini büyük ölçüde yavaşlatır.
Sorun çözüm fikri
Bir fikir ortaya çıktı: en yakın tarihlere sahip kalan partiler tek bir partiye indirilmeli ve birleşik bir partiye sahip olan bu tür artıklar, bir hücrede veya bir hücrede yeterli alan yoksa birkaç hücrede kompakt bir şekilde birlikte yerleştirilmelidir. kalan miktarın tamamı. Böyle bir "sıkıştırma" örneği Şekil 2'de gösterilmektedir.
İncir. 2. Hücrelerdeki kalıntıları sıkıştırmak için şema
Bu, yeni malların yerleştirilmesi için kullanılacak olan depo alanını önemli ölçüde azaltmanıza olanak tanır. Depo kapasitesinin aşırı yüklendiği bir durumda, böyle bir önlem son derece gereklidir, aksi takdirde yeni malları yerleştirmek için yeterli boş alan olmayabilir, bu da depo yerleştirme ve yenileme süreçlerinin durmasına ve sonuç olarak, kabul ve sevkiyatın durması. Daha önce WMS sisteminin uygulanmasından önce böyle bir işlem manuel olarak yapılıyordu ve hücrelerde uygun dengelerin aranması süreci oldukça uzun olduğundan etkisizdi. Artık WMS sisteminin kullanıma sunulmasıyla süreci otomatikleştirmeye, hızlandırmaya ve akıllı hale getirmeye karar verdik.
Böyle bir sorunu çözme süreci 2 aşamaya ayrılır:
- ilk aşamada, sıkıştırma tarihi yakın olan parti gruplarını buluruz (bu göreve adanmıştır) );
- ikinci aşamada, her parti grubu için kalan malların hücrelere en kompakt şekilde yerleştirilmesini hesaplıyoruz.
Bu yazıda algoritmanın ikinci aşamasına odaklanacağız.
Mevcut çözümlerin gözden geçirilmesi
Geliştirdiğimiz algoritmaların açıklamasına geçmeden önce piyasada halihazırda mevcut olan sistemlere kısa bir genel bakış yapmakta fayda var WMS, benzer optimum sıkıştırma işlevselliğini uygulayan.
Öncelikle “1C: Enterprise 8. WMS Logistics” ürününe dikkat çekmek gerekiyor. 4C'nin sahibi olduğu ve kopyaladığı ve dördüncü nesle ait olan Depo yönetimi 1" WMS-AXELOT tarafından geliştirilen sistemler. Bu sistem, farklı ürün kalıntılarını tek bir ortak hücrede birleştirmek için tasarlanmış sıkıştırma işlevselliğini talep ediyor. Böyle bir sistemdeki sıkıştırma işlevselliğinin, örneğin hücrelerdeki malların ABC sınıflarına göre yerleştirilmesinin düzeltilmesi gibi başka olasılıkları da içerdiğini belirtmekte fayda var, ancak bunlar üzerinde durmayacağız.
1C: Enterprise 8. WMS Lojistik sisteminin kodunu analiz ederseniz. Depo yönetimi 4" (işlevselliğin bu bölümünde açıktır), aşağıdaki sonuca varabiliriz. Artık sıkıştırma algoritması oldukça ilkel bir doğrusal mantık uygular ve herhangi bir "optimal" sıkıştırmadan söz edilemez. Doğal olarak partilerin kümelenmesine imkan vermiyor. Böyle bir sistemi uygulayan birçok müşteri, sıkıştırma planlamasının sonuçlarından şikayetçi oldu. Örneğin, sıkıştırma sırasında pratikte sıklıkla şu durum meydana geldi: 100 adet. Kalan malların bir hücreden 1 adetin bulunduğu başka bir hücreye taşınması planlanmaktadır. mallar, ancak zaman tüketimi açısından tam tersini yapmak en uygunudur.
Ayrıca hücrelerde kalan malların sıkıştırılması işlevi de birçok yabancı ülkede ilan edilmiştir. WMS-sistemler, ancak ne yazık ki algoritmaların etkinliği hakkında gerçek bir geri bildirimimiz yok (bu bir ticari sırdır), mantıklarının derinliği hakkında bir fikrimiz bile yok (özel kapalı kaynak yazılım), bu yüzden yargılayamayız.
Sorunun matematiksel modelini arayın
Bir problemi çözmeye yönelik yüksek kaliteli algoritmalar tasarlamak için öncelikle bu problemi matematiksel olarak net bir şekilde formüle etmek gerekir ki biz de bunu yapacağız.
Çok sayıda hücre var bazı malların kalıntılarını içeren. Aşağıda bu tür hücrelere donör hücreler adını vereceğiz. Haydi belirtelim hücredeki malların hacmi $.
Bir partiden yalnızca bir ürünün veya daha önce birkaç partinin bir kümede birleştirildiğini söylemek önemlidir (okuyun: ), malların depolanması ve depolanmasının özelliklerinden kaynaklanmaktadır. Farklı ürünler veya farklı toplu kümeler kendi ayrı sıkıştırma prosedürlerini çalıştırmalıdır.
Çok sayıda hücre var Donör hücrelerinden gelen kalıntıların potansiyel olarak yerleştirilebileceği yer. Bu tür hücrelere ayrıca taşıyıcı hücreler adını vereceğiz. Bunlar depodaki serbest hücreler veya çeşitli donör hücreler olabilir. . Her zaman bol bir alt kümedir .
Her hücre için birçoktan Kapasite sınırlamaları getirildi , dm3 cinsinden ölçülür. Bir dm3, kenarları 10 cm olan bir küptür Depoda depolanan ürünler oldukça büyüktür, dolayısıyla bu durumda bu tür bir ayrıklaştırma oldukça yeterlidir.
En kısa mesafelerin matrisi verildiğinde her hücre çifti arasında metre cinsinden Nerede и setlere ait и sırasıyla.
Haydi belirtelim Hücreden mal taşımanın “maliyetleri” bir hücreye . Haydi belirtelim Konteyner seçmenin “maliyetleri” kalıntıları diğer hücrelerden ona taşımak için. Değerlerin tam olarak nasıl ve hangi ölçü birimlerinde hesaplanacağı и daha fazla ele alacağız (giriş verilerinin hazırlanması bölümüne bakınız), şimdilik bu tür değerlerin değerlerle doğru orantılı olacağını söylemek yeterli и sırasıyla.
ile belirtmek geri kalanı hücreden geliyorsa 1 değerini alan değişken konteynere taşındı , aksi halde 0. ile belirtelim kapsayıcı ise 1 değerini alan bir değişken kalan malları içerir, aksi takdirde 0'dır.
Görev şu şekilde belirtiliyor: çok fazla kap bulmanız gerekiyor ve böylece işlevi en aza indirmek için donör hücrelerini taşıyıcı hücrelere "bağlar"
kısıtlamalar altında
Toplamda, sorunun çözümünü hesaplarken şunları yapmaya çalışıyoruz:
- ilk olarak depolama kapasitesinden tasarruf etmek;
- ikincisi, mağaza sahiplerinin zamanından tasarruf etmek.
Son kısıtlama, malları seçmediğimiz bir konteynere taşıyamayacağımız ve dolayısıyla onu seçerken "maliyet ödemeyeceğimiz" anlamına gelir. Bu kısıtlama aynı zamanda hücrelerden konteynere taşınan malların hacminin konteynerin kapasitesini aşmaması gerektiği anlamına da gelmektedir. Bir problemi çözmek derken bir dizi konteyneri kastediyoruz ve donör hücrelerini kaplara bağlama yöntemleri.
Optimizasyon probleminin bu formülasyonu yeni değildir ve geçen yüzyılın 80'li yıllarının başından beri birçok matematikçi tarafından incelenmektedir. Yabancı literatürde uygun bir matematiksel modele sahip 2 optimizasyon problemi bulunmaktadır: и (Görevlerdeki farklılıklara daha sonra değineceğiz). Matematik literatüründe bu tür iki optimizasyon probleminin formülasyonunun işletmelerin yerdeki konumuna göre formüle edildiğini, dolayısıyla “Tesis Konumu” adını aldığını söylemekte fayda var. Çoğunlukla bu geleneğe bir övgüdür, çünkü bu tür kombinatoryal sorunları çözme ihtiyacı ilk kez geçen yüzyılın 50'li yıllarında çoğunlukla askeri-sanayi sektöründen olmak üzere lojistik alanından geldi. İşletmenin konumu açısından bu tür görevler aşağıdaki şekilde formüle edilmiştir:
- İmalat işletmelerini yerleştirmenin potansiyel olarak mümkün olduğu sınırlı sayıda şehir vardır (bundan sonra imalat şehirleri olarak anılacaktır). Her üretim şehri için, içinde bir işletme açmanın maliyeti ve içinde açılan işletmenin üretim kapasitesinin bir sınırlaması belirtilir.
- Müşterilerin gerçekte bulunduğu sınırlı sayıda şehir vardır (bundan sonra müşteri şehirleri olarak anılacaktır). Bu tür her müşteri şehri için ürünlere olan talebin hacmi belirlenir. Basitlik açısından işletmeler tarafından üretilen ve müşteriler tarafından tüketilen tek bir ürün olduğunu varsayacağız.
- Her bir şehir-üretici ve şehir-müşteri çifti için, gerekli miktarda ürünün üreticiden müşteriye teslim edilmesine yönelik nakliye maliyetlerinin değeri belirlenir.
Aşağıdakileri gerçekleştirmek için hangi şehirlerde işletme açacağınızı ve bu tür işletmelere nasıl müşteri ekleyeceğinizi bulmanız gerekir:
- İşletme açmanın toplam maliyeti ve nakliye maliyetleri minimum düzeydeydi;
- Herhangi bir açık işletmeye atanan müşterilerden gelen talep hacmi, o işletmenin üretim kapasitesini aşmamıştır.
Şimdi bu iki klasik problemin tek farkını belirtmekte fayda var:
- Tek Kaynaklı Kapasiteli Tesis Yeri Sorunu – müşteriye yalnızca tek bir açık tesisten besleme sağlanır;
- Çok Kaynaklı Kapasiteli Tesis Yerleştirme Problemi – müşteriye aynı anda birden fazla açık tesisten besleme sağlanabilir.
İki problem arasındaki böyle bir fark ilk bakışta önemsizdir, ancak aslında bu tür problemlerin tamamen farklı bir kombinatoryal yapısına ve sonuç olarak bunları çözmek için tamamen farklı algoritmalara yol açmaktadır. Görevler arasındaki farklar aşağıdaki şekilde gösterilmiştir.
Şek. 3. a) Çok Kaynaklı Kapasiteli Tesis Yeri Sorunu
Şek. 3. b) Tek Kaynaklı Kapasiteli Tesis Yeri Sorunu
Her iki görev -zor, yani giriş verilerinin boyutunda bir zaman polinomunda böyle bir sorunu çözecek kesin bir algoritma yoktur. Daha basit bir ifadeyle, bir sorunu çözmeye yönelik tüm kesin algoritmalar, seçeneklerin tam olarak aranmasından daha hızlı olmasına rağmen, üstel zamanda çalışacaktır. Görevden bu yana -zor, o zaman yalnızca yaklaşık buluşsal yöntemleri, yani optimale çok yakın çözümleri tutarlı bir şekilde hesaplayacak ve oldukça hızlı çalışacak algoritmaları ele alacağız. Böyle bir görevle ilgileniyorsanız, burada Rusça olarak iyi bir genel bakış bulabilirsiniz.
Hücrelerdeki malların optimal sıkıştırılması sorunumuzun terminolojisine geçersek, o zaman:
- Müşteri şehirler bağışçı hücrelerdir kalan mallarla
- imalat şehirleri – konteyner hücreleri diğer hücrelerden kalanların yerleştirildiği yer,
- taşıma maliyetleri - zaman maliyetleri malların hacmini donör hücresinden taşımak için mağaza sorumlusu bir konteyner hücresine ;
- bir işletme açmanın maliyetleri - konteyner seçmenin maliyetleri , konteyner hücresinin hacmine eşit , serbest hacim tasarrufu için belirli bir katsayı ile çarpılır (katsayının değeri her zaman > 1'dir) (giriş verilerinin hazırlanması bölümüne bakın).
Sorunun iyi bilinen klasik çözümleriyle analoji çizildikten sonra, çözüm algoritmasının mimarisinin seçiminin bağlı olduğu önemli bir soruyu yanıtlamak gerekir: kalanların donör hücresinden taşınması yalnızca bir kişiye mümkündür. ve yalnızca bir konteyner (Tek Kaynak) veya kalanları birkaç konteyner hücresine (Çoklu Kaynak) taşımak mümkün mü?
Pratikte sorunun her iki formülasyonunun da gerçekleştiğini belirtmekte fayda var. Aşağıda bu tür her ayarın tüm artılarını ve eksilerini sunuyoruz:
| Sorun çeşidi | Seçeneğin artıları | Seçeneğin eksileri |
|---|---|---|
| Tek kaynak | Sorunun bu varyantı kullanılarak hesaplanan mal hareketi işlemleri:
|
|
| Çoklu kaynak | Sorunun bu versiyonu kullanılarak hesaplanan sıkıştırmalar, "Tek Kaynak" seçeneği kullanılarak hesaplanan sıkıştırmalara kıyasla genellikle %10-15 daha kompakttır. Ancak donör hücrelerindeki kalıntı sayısı ne kadar az olursa, yoğunluk farkının da o kadar küçük olacağını da not ediyoruz. | Sorunun bu varyantı kullanılarak hesaplanan mal hareketi işlemleri:
|
Tablo 1. Tek Kaynaklı ve Çoklu Kaynak seçeneklerinin artıları ve eksileri.
Tek Kaynaklı seçeneğin daha fazla avantajı olduğundan ve ayrıca donör hücrelerindeki kalıntı sayısı ne kadar az olursa, sorunun her iki varyantı için hesaplanan sıkıştırma kompaktlığı derecesindeki farkın da o kadar küçük olduğu dikkate alındığında, seçimimiz şuna düştü: Tek Kaynak seçeneği.
Çoklu Kaynak seçeneğinin çözümünün de gerçekleştiğini söylemekte fayda var. Bunu çözmek için çok sayıda etkili algoritma vardır ve bunların çoğu bir dizi ulaşım problemini çözmeye yöneliktir. Ayrıca sadece etkili algoritmalar değil, aynı zamanda zarif algoritmalar da vardır; örneğin,
Giriş Verilerini Hazırlama
Bir problemi çözmek için analiz etmeye ve algoritma geliştirmeye başlamadan önce, onu hangi veriyi, hangi biçimde girdi olarak besleyeceğimize karar vermek gerekir. Donör hücrelerinde kalan malların hacmi ve konteyner hücrelerinin kapasitesi ile ilgili herhangi bir sorun yoktur, çünkü bu önemsizdir - bu tür miktarlar m3 cinsinden ölçülecektir, ancak bir konteyner hücresi kullanmanın maliyetleri ve taşıma maliyeti matrisi ile her şey değil çok basit!
Önce hesaplamaya bakalım mal taşıma masrafları Donör hücresinden taşıyıcı hücreye. Öncelikle hareket maliyetlerini hangi ölçü birimleriyle hesaplayacağımıza karar vermek gerekiyor. En belirgin iki seçenek metre ve saniyedir. Seyahat masraflarını “saf” sayaçlarla hesaplamanın bir anlamı yok. Bunu bir örnekle gösterelim. Bırak hücre birinci kademede yer alan hücre 30 metre kaldırılmış ve ikinci kademede yer almaktadır:
- Bir yerden taşınmak в taşınmaktan daha pahalı в , mesafe aynı olmasına rağmen ikinci kademeden (yerden 1,5-2 metre yükseklikte) aşağı inmek ikinci kademeye çıkmaktan daha kolaydır;
- 1 adet hareket ettirin. hücreden çıkan mallar в 10 parçayı taşımaktan daha kolay olacaktır. mesafe aynı olmasına rağmen aynı ürün.
Taşıma maliyetlerini saniyeler içinde dikkate almak daha iyidir, çünkü bu hem katmanlardaki farkı hem de taşınan mal miktarındaki farkı hesaba katmanızı sağlar. Hareketin maliyetini saniye cinsinden hesaplamak için, hareket işlemini temel bileşenlere ayırmalı ve her temel bileşenin yürütülmesi için zaman ölçümleri yapmalıyız.
Hücreden izin ver hamle PC. konteynerdeki mallar . Let – m/sn cinsinden ölçülen, depodaki bir işçinin ortalama hareket hızı. İzin vermek и - 4 dm3'e eşit bir mal hacmi için sırasıyla tek seferlik operasyonların ortalama alım ve satım hızları (bir çalışanın operasyonları gerçekleştirirken bir depoda bir seferde aldığı ortalama hacim). İzin vermek и sırasıyla alma ve koyma işlemlerinin gerçekleştirildiği hücrelerin yüksekliği. Örneğin, birinci katın (zemin) ortalama yüksekliği 1 m, ikinci katın 2 m'dir vb. Daha sonra bir taşıma işlemini tamamlamak için gereken toplam süreyi hesaplama formülü şu şekildedir: aşağıdaki:
Tablo 2, depolanan malların özelliklerini dikkate alarak depo çalışanları tarafından toplanan her temel operasyonun yürütme süresine ilişkin istatistikleri göstermektedir.
| operasyonun adı | Atama | ortalama |
|---|---|---|
| Depoda dolaşan bir işçinin ortalama hızı | |
1,5 m / s |
| Bir işlemin ortalama hızı (4 dm3 ürün hacmi için) | |
2,4 sn |
Tablo 2. Depo operasyonlarının ortalama tamamlanma süresi
Taşınma maliyetlerini hesaplama yöntemine karar verdik. Şimdi nasıl hesaplayacağımızı bulmamız gerekiyor. konteyner hücresi seçmenin maliyeti. Burada her şey taşıma maliyetlerine göre çok ama çok daha karmaşık, çünkü:
- ilk olarak, maliyetler doğrudan hücrenin hacmine bağlı olmalıdır - donör hücrelerinden aktarılan aynı hacimdeki kalıntıları, bu hacmin her iki kaba da tamamen uyması koşuluyla, büyük bir kaptan daha küçük hacimli bir kaba yerleştirmek daha iyidir. Böylece, konteyner seçiminin toplam maliyetini en aza indirerek, malların hücrelere yerleştirilmesine ilişkin müteakip işlemleri gerçekleştirmek için seçim alanındaki "kıt" serbest depolama kapasitesinden tasarruf etmeye çalışıyoruz. Şekil 4, kalıntıların büyük ve küçük kaplara aktarılmasına yönelik seçenekleri ve bu aktarma seçeneklerinin sonraki depo operasyonlarındaki sonuçlarını göstermektedir.
- ikinci olarak, orijinal sorunu çözerken toplam maliyetleri tam olarak en aza indirmemiz gerektiğinden ve bu hem taşıma maliyetlerinin hem de konteyner seçme maliyetlerinin toplamı olduğundan, metreküp cinsinden hücre hacimlerinin bir şekilde saniyelerle ilişkilendirilmesi gerekir, bu önemsiz olmaktan uzaktır.
Pirinç. 4. Artıkları farklı kapasitelerdeki kaplara taşıma seçenekleri.
Şekil 4, sonraki malların yerleştirilmesinin ikinci aşamasında artık konteynere sığmayan artıkların hacmini kırmızı renkle göstermektedir.
Bir konteyner seçmek için metreküp maliyetleri, soruna hesaplanmış çözümler için aşağıdaki gereksinimleri taşımak için saniye cinsinden maliyetlerle ilişkilendirmeye yardımcı olacaktır:
- Ürünü içeren konteyner silolarının toplam sayısını azaltacaksa, her durumda donör silosundaki bakiyelerin konteyner silosuna taşınması gerekir.
- Konteynerlerin hacmi ile taşınmak için harcanan zaman arasında bir denge sağlamak gerekir: örneğin, bir problemin yeni çözümünde önceki çözümle karşılaştırıldığında hacim kazancı büyük, ancak zaman kaybı azdır. , o zaman yeni bir seçenek seçmek gerekir.
Son gereksinimle başlayalım. Muğlak "denge" sözcüğünü açıklığa kavuşturmak amacıyla aşağıdakileri öğrenmek amacıyla depo çalışanları arasında bir anket düzenledik. Hacimsel bir kap hücresi olsun Donör hücrelerinden kalan malların hareketinin atandığı ve bu hareketin toplam süresinin şuna eşit olduğu: . Aynı donör hücrelerinden aynı miktarda malın, her yerleştirmenin kendi tahminlerine sahip olduğu diğer kaplara yerleştirilmesi için birkaç alternatif seçenek olsun. Nerede < и Nerede >.
Soru ortaya çıkıyor: Hacimdeki minimum kazanç nedir? Belirli bir zaman kaybı değeri için kabul edilebilir ? Bir örnekle açıklayalım. Başlangıçta kalıntıların 1000 dm3 (1 m3) hacimli bir kaba yerleştirilmesi gerekiyordu ve transfer süresi 70 saniyeydi. Artıkları 500 dm3 hacimli ve 130 saniye süreli başka bir kaba koyma seçeneği mevcuttur. Soru: 60 dm500 serbest hacim tasarrufu sağlamak için depo sahibinin 3 saniyelik ek zamanını malların taşınmasına ayırmaya hazır mıyız? Depo çalışanları arasında yapılan bir anketin sonuçlarına dayanarak aşağıdaki diyagram derlendi.
Pirinç. 5. İzin verilen minimum hacim tasarrufunun çalışma süresindeki farktaki artışa bağımlılığının şeması
Yani, eğer ek zaman maliyeti 40 saniye ise, o zaman bunları ancak hacim kazancı en az 500 dm3 olduğunda harcamaya hazırız. Bağımlılıkta hafif bir doğrusal olmama gerçeğine rağmen, daha sonraki hesaplamaların basitliği için, nicelikler arasındaki bağımlılığın doğrusal olduğunu ve eşitsizlikle tanımlandığını varsayacağız.
Aşağıdaki şekilde malları konteynerlere yerleştirmenin aşağıdaki yöntemlerini ele alıyoruz.
Pirinç. 6. Seçenek (a): 2 konteyner, toplam hacim 400 dm3, toplam süre 150 saniye.
Pirinç. 6. Seçenek (b): 2 konteyner, toplam hacim 600 dm3, toplam süre 190 saniye.
Pirinç. 6. Seçenek (c): 1 konteyner, toplam hacim 400 dm3, toplam süre 200 saniye.
Kapları seçmek için (a) seçeneği orijinal seçeneğe göre daha fazla tercih edilir, çünkü eşitsizlik şu şekildedir: (800-400)/10>=150-120, yani 40 >= 30 anlamına gelir. (b) seçeneği orijinalinden daha az tercih edilir seçenek , çünkü eşitsizlik geçerli değil: (800-600)/10>=190-150, bu da 20 >= 40 anlamına gelir. Ancak (c) seçeneği bu mantığa uymuyor! Bu seçeneği daha ayrıntılı olarak ele alalım. Bir tarafta (800-400)/10>=200-120 eşitsizliği yani 40 >= 80 eşitsizliği karşılanmıyor, bu da hacim kazancının bu kadar büyük bir zaman kaybına değmeyeceğini gösteriyor.
Ancak diğer taraftan, bu (c) seçeneğinde yalnızca işgal edilen toplam hacmi azaltmakla kalmıyoruz, aynı zamanda yukarıda sıralanan sorunların hesaplanabilir çözümlerine yönelik iki önemli gereksinimden ilki olan işgal edilen hücrelerin sayısını da azaltıyoruz. Açıkçası, bu şartın yerine getirilmeye başlanması için eşitsizliğin sol tarafına bir miktar pozitif sabit eklemek gerekir. ve böyle bir sabitin yalnızca kapsayıcı sayısı azaldığında eklenmesi gerekir. Bunu hatırlayalım kapsayıcı olduğunda 1'e eşit bir değişkendir seçildiğinde ve kapsayıcı olduğunda 0 seçili değil. belirtelim – başlangıç çözümünde çok sayıda kap ve – yeni çözümde çok sayıda kap var. Genel olarak yeni eşitsizlik şöyle görünecektir:
Yukarıdaki eşitsizliği dönüştürürsek şunu elde ederiz:
Buna dayanarak toplam maliyeti hesaplamak için bir formülümüz var soruna bazı çözümler:
Ama şimdi soru ortaya çıkıyor: Böyle bir sabitin değeri ne olmalı? ? Açıkçası, sorunun çözümüne yönelik ilk gereksinimin her zaman karşılanması için değerinin yeterince büyük olması gerekir. Elbette sabitin değerini 103 veya 106'ya eşitleyebilirsiniz, ancak ben bu tür "sihirli sayılardan" kaçınmak istiyorum. Depo operasyonlarını gerçekleştirmenin özelliklerini dikkate alırsak, böyle bir sabitin değerine ilişkin sağlam temellere dayanan birkaç sayısal tahmin hesaplayabiliriz.
Let – bir ABC bölgesinin depo hücreleri arasındaki maksimum mesafe, bizim durumumuzda 100 m'ye eşit olsun. – bir depodaki konteyner hücresinin maksimum hacmi, bizim durumumuzda 1000 dm3'e eşittir.
Değeri hesaplamanın ilk yolu . Birinci kademede 2 konteynerin olduğu, malların zaten fiziksel olarak bulunduğu, yani kendilerinin donör hücreler olduğu ve malları aynı hücrelere taşıma maliyetinin doğal olarak 0'a eşit olduğu bir durumu düşünelim. sabit için böyle bir değer bulmak gereklidir , burada artıkları her zaman konteyner 1'den konteyner 2'ye taşımak avantajlı olacaktır. и Yukarıda verilen eşitsizlikte şunu elde ederiz:
ne takip ediyor
Temel işlemleri gerçekleştirmek için ortalama sürenin değerlerini yukarıdaki formüle koyarsak, elde ederiz
Değeri hesaplamanın ikinci yolu . olan bir durumu ele alalım. Malların konteyner 1'e taşınmasının planlandığı donör hücreleri. – donör hücresinden uzaklık 1. konteynere. Ayrıca, halihazırda mal içeren ve hacminin geri kalanını almanıza izin veren 2. konteyner de vardır. hücreler. Basitlik açısından, donör hücrelerinden konteynerlere taşınan malların hacminin aynı ve eşit olduğunu varsayacağız. . Sabitin böyle bir değerini bulmak gerekiyor , tüm kalanların yerleştirildiği yer Hücreleri 2. konteynere koymak, onları farklı konteynerlere yerleştirmekten her zaman daha karlı olacaktır:
Elde ettiğimiz eşitsizliği dönüştürmek
Miktarın değerini “güçlendirmek” için , varsayalım ki = 0. Genellikle depo bakiyelerini sıkıştırma prosedüründe yer alan ortalama hücre sayısı 10'dur. Bilinen miktarların değerlerini değiştirerek, aşağıdaki sabit değerini elde ederiz.
Her seçenek için hesaplanan en büyük değeri alıyoruz, bu miktarın değeri olacaktır Verilen depo parametreleri için. Şimdi bütünlüğü sağlamak için toplam maliyetleri hesaplama formülünü yazalım. bazı uygulanabilir çözümler için :
Sonuçta şimdi Herkül'ün çabaları Giriş verilerinin dönüştürülmesiyle tüm giriş verilerinin istenilen forma dönüştürüldüğünü ve optimizasyon algoritmasında kullanıma hazır olduğunu söyleyebiliriz.
Sonuç
Uygulamada görüldüğü gibi, bir algoritma için girdi verilerinin hazırlanması ve dönüştürülmesi aşamasının karmaşıklığı ve önemi genellikle hafife alınmaktadır. Bu makalede, yalnızca yüksek kaliteli ve akıllıca hazırlanmış giriş verilerinin, algoritma tarafından hesaplanan kararların müşteri için gerçekten değerli hale gelebileceğini göstermek için bu aşamaya özellikle çok dikkat ettik. Evet formüllerin pek çok türevi vardı ama daha katadan önce uyarmıştık :)
Bir sonraki makalede nihayet önceki 2 yayının amacına ulaşacağız: ayrık bir optimizasyon algoritması.
Makaleyi hazırladım
Roman Shangin, proje departmanı programcısı,
First Bit şirketi, Çelyabinsk
Kaynak: habr.com