Yn dit artikel sille wy jo fertelle hoe't wy it probleem hawwe oplost fan in gebrek oan frije sellen yn in pakhús en de ûntwikkeling fan in diskrete optimisaasjealgoritme om sa'n probleem op te lossen. Litte wy prate oer hoe't wy it wiskundige model fan it optimalisaasjeprobleem "boud" hawwe, en oer de swierrichheden dy't wy ûnferwachts tsjinkamen by it ferwurkjen fan ynfiergegevens foar it algoritme.
As jo ynteressearre binne yn tapassingen fan wiskunde yn bedriuw en jo binne net bang foar stive identiteitstransformaasjes fan formules op it nivo fan 5e klasse, dan wolkom by de kat!
It artikel sil nuttich wêze foar dyjingen dy't útfiere WMS-systemen, wurket yn it magazijn of produksje logistyk yndustry, likegoed as programmeurs dy't ynteressearre binne yn tapassingen fan wiskunde yn it bedriuwslibben en optimalisearjen fan prosessen yn in ûndernimming.
Ynliedend diel
Dizze publikaasje set de searje artikels troch wêryn wy ús suksesfolle ûnderfining diele yn it ymplementearjen fan optimalisaasjealgoritmen yn pakhúsprosessen.
В beskriuwt de spesifikaasjes fan it pakhús dêr't wy ymplementearre WMS-systeem, en ferklearret ek wêrom't wy it probleem moatte oplosse fan klustering fan batches fan oerbleaune guod by ymplemintaasje WMS-systemen, en hoe't wy it diene.
Doe't wy klear wiene mei it skriuwen fan it artikel oer optimisaasjealgoritmen, die bliken dat it heul grut wie, dus besleaten wy it sammele materiaal yn 2 dielen te splitsen:
- Yn it earste diel (dit artikel) sille wy prate oer hoe't wy "boud" it wiskundige model fan it probleem, en oer de grutte swierrichheden dy't wy ûnferwachts tsjinkaam by it ferwurkjen en transformearjen fan de ynfier gegevens foar it algoritme.
- Yn it twadde diel sille wy yn detail de ymplemintaasje fan it algoritme yn 'e taal beskôgje C ++, sille wy in komputerysk eksperimint útfiere en de ûnderfining gearfetsje dy't wy opdien hawwe by de ymplemintaasje fan sokke "yntelligente technologyen" yn 'e saaklike prosessen fan 'e klant.
Hoe kinne jo in artikel lêze. As jo it foarige artikel lêze, dan kinne jo fuortendaliks gean nei it haadstik "Oersjoch fan besteande oplossingen"; sa net, dan is de beskriuwing fan it probleem dat wurdt oplost yn 'e spoiler hjirûnder.
Beskriuwing fan it probleem dat wurdt oplost by de klant syn pakhús
Knelpunt yn prosessen
Yn 2018 hawwe wy in projekt foltôge om út te fieren WMS-systemen by it pakhús "Trading House "LD" yn Chelyabinsk. Wy ymplementearre it produkt "1C-Logistics: Warehouse Management 3" foar 20 wurkplakken: operators WMS, winkellju, heftrucksjauffeurs. It gemiddelde pakhús is sa'n 4 tûzen m2, it oantal sellen is 5000 en it oantal SKU's is 4500. It pakhús bewarret balkleppen fan ús eigen produksje fan ferskate dimensjes fan 1 kg oant 400 kg. Ynventarisaasje yn it pakhús wurdt opslein yn batches, om't d'r needsaak is om guod te selektearjen neffens FIFO.
Tidens it ûntwerp fan automatisearringskema's foar pakhúsproses waarden wy konfrontearre mei it besteande probleem fan net-optimale ynventarisaasje opslach. De spesifikaasjes fan it opslaan en lizzen fan kranen binne sa dat ien ienheid opslach sel kin allinnich befetsje items út ien batch (sjoch Fig. 1). Produkten komme deistich by it pakhús oan en elke oankomst is in aparte batch. Yn totaal, as gefolch fan 1 moanne fan magazyn operaasje, wurde 30 aparte batches makke, nettsjinsteande it feit dat elk moat wurde opslein yn in aparte sel. Produkten wurde faak selektearre net yn hiele pallets, mar yn stikken, en as gefolch, yn 'e stik seleksje sône yn in protte sellen it folgjende byld wurdt waarnommen: yn in sel mei in folume fan mear as 1 m3 binne d'r ferskate stikken kranen dy't besette minder as 5-10% fan it sel folume.
Fig 1. Foto fan ferskate stikken yn in sel
It is dúdlik dat de opslachkapasiteit net optimaal benut wurdt. Om de skaal fan 'e ramp foar te stellen, kin ik sifers jaan: gemiddeld binne d'r fan 1 oant 3 sellen fan sokke sellen mei in folume fan mear as 100 m300 mei "minuscule" saldo's yn ferskate perioaden fan 'e operaasje fan' e pakhús. Sûnt it pakhús is relatyf lyts, yn 'e drokke seizoenen fan' e pakhús wurdt dizze faktor in "knelhals" en fertraget de pakhúsprosessen fan akseptaasje en ferstjoering sterk.
Probleem oplossing idee
Der ûntstie in idee: batches fan oerbliuwsels mei de tichtste datums moatte wurde fermindere ta ien inkele batch, en sokke oerbliuwsels mei in unifoarme batch moatte kompakt byinoar pleatst wurde yn ien sel, of yn ferskate, as der net genôch romte yn ien is om de hiele bedrach fan oerbliuwsels. In foarbyld fan sa'n "kompresje" wurdt werjûn yn figuer 2.
Fig.2. Skema foar it komprimearjen fan resten yn sellen
Hjirmei kinne jo de besette pakhúsromte signifikant ferminderje dy't sil wurde brûkt foar nij guod dat wurdt pleatst. Yn in situaasje dêr't pakhúskapasiteit wurdt oerladen, is sa'n maatregel ekstreem needsaaklik, oars kin d'r gewoan net genôch frije romte wêze om nij guod op te nimmen, wat sil liede ta in stop yn 'e pakhúsprosessen fan pleatsing en oanfolling en, as gefolch, ta in halte yn akseptaasje en shipment. Earder, foar de ymplemintaasje fan it WMS-systeem, waard sa'n operaasje mei de hân útfierd, wat net effektyf wie, om't it proses fan sykjen nei passende saldo's yn sellen frij lang wie. No, mei de ynfiering fan in WMS-systeem, hawwe wy besletten om it proses te automatisearjen, it te fersnellen en it yntelligint te meitsjen.
It proses fan it oplossen fan sa'n probleem is ferdield yn 2 stadia:
- yn 'e earste faze fine wy groepen fan batches tichtby datum foar kompresje (wijd oan dizze taak );
- by de twadde etappe, foar elke groep batches wy berekkenje de meast kompakte pleatsing fan de oerbleaune guod yn 'e sellen.
Yn it hjoeddeistige artikel sille wy rjochtsje op 'e twadde etappe fan it algoritme.
Oersjoch fan besteande oplossings
Foardat jo oergean nei de beskriuwing fan 'e algoritmen dy't wy hawwe ûntwikkele, is it de muoite wurdich in koart oersjoch te meitsjen fan systemen dy't al op 'e merke besteane WMS, dy't ferlykbere optimale kompresjefunksjonaliteit ymplementearje.
Alderearst is it needsaaklik om it produkt te notearjen "1C: Enterprise 8. WMS Logistics. Warehouse management 4", dat is eigendom en replikearre troch 1C en heart ta de fjirde generaasje WMS-systemen ûntwikkele troch AXELOT. Dit systeem beweart kompresjefunksjonaliteit, dy't is ûntworpen om ferskate produktoerbliuwsels te ferienigjen yn ien mienskiplike sel. It is it neamen wurdich dat de kompresjefunksjonaliteit yn sa'n systeem ek oare mooglikheden omfettet, bygelyks it korrizjearjen fan 'e pleatsing fan guod yn sellen neffens har ABC-klassen, mar wy sille net op har dwaen.
As jo analysearje de koade fan de 1C: Enterprise 8. WMS Logistics systeem. Warehouse management 4" (dy't iepen is yn dit diel fan 'e funksjonaliteit), kinne wy it folgjende konkludearje. It residuele kompresje-algoritme ymplementearret in frij primitive lineêre logika en der kin gjin sprake wêze fan in "optimale" kompresje. Fansels soarget it net foar klustering fan partijen. Ferskate kliïnten dy't sa'n systeem ynfierd hiene, klagen oer de resultaten fan kompresjeplanning. Bygelyks, faak yn 'e praktyk by kompresje barde de folgjende situaasje: 100 pcs. It is pland om it oerbleaune guod fan de iene sel nei de oare sel te ferpleatsen, dêr't 1 stik leit. guod, hoewol't it is optimaal út it eachpunt fan tiid konsumpsje te dwaan it tsjinoerstelde.
Ek de funksjonaliteit fan it komprimearjen fan it oerbleaune guod yn sellen wurdt ferklearre yn in protte frjemde lannen. WMS-systemen, mar spitigernôch hawwe wy gjin echte feedback oer de effektiviteit fan 'e algoritmen (dit is in hannelsgeheim), folle minder in idee oer de djipte fan har logika (proprietary closed-source software), dus wy kinne net oardielje.
Sykje nei in wiskundich model fan it probleem
Om algoritmen fan hege kwaliteit te ûntwerpen foar it oplossen fan in probleem, is it earst nedich om dit probleem wiskundich dúdlik te formulearjen, wat wy sille dwaan.
Der binne in protte sellen , dy't de resten fan guon guod befetsje. Yn wat folget sille wy sokke sellen donorsellen neame. Litte wy oanjaan folume fan guod yn 'e sel $.
It is wichtich om te sizzen dat mar ien produkt fan ien batch, of ferskate batches earder kombinearre yn in kluster (lês: ), dat komt troch de spesifiken fan opslach en opslach fan guod. Ferskillende produkten as ferskate batchklusters moatte har eigen aparte kompresjeproseduere útfiere.
Der binne in protte sellen , dêr't mooglik resten fan donorsellen yn pleatst wurde kinne. Wy sille sokke sellen fierders container sellen neame. Dit kinne frije sellen wêze yn it pakhús as donorsellen fan in ferskaat . Altyd genôch is in subset .
Foar elke sel fan in protte Kapasiteitsbeperkingen binne ynsteld , metten yn dm3. Ien dm3 is in kubus mei kanten fan 10 sm. De produkten opslein yn it pakhús binne frij grut, dus yn dit gefal is sa'n diskretisaasje genôch.
Jûn in matrix fan koartste ôfstannen yn meters tusken elk pear sellen wêr и hearre ta sets и respektivelik.
Litte wy oanjaan "kosten" fan it ferpleatsen fan guod út 'e sel oan sel . Litte wy oanjaan "kosten" fan it kiezen fan in kontener om resten fan oare sellen deryn te ferpleatsen. Hoe krekt en yn hokker ienheden fan mjitting de wearden wurde berekkene и wy sille fierder beskôgje (sjoch de seksje foar it tarieden fan ynfiergegevens), foar no is it genôch om te sizzen dat sokke wearden direkt evenredich sille wêze mei de wearden и respektivelik.
Lit ús oantsjutte troch in fariabele dy't de wearde 1 nimt as de rest fan 'e sel is ferhuze nei kontener en 0 oars. Lit ús oantsjutte troch in fariabele dy't nimt de wearde 1 as de container befettet de oerbleaune guod, en 0 oars.
De taak wurdt as folget oanjûn: jo moatte safolle konteners fine en sa "heakje" donorsellen oan kontenersellen om de funksje te minimalisearjen
ûnder beheinings
Yn totaal, by it berekkenjen fan de oplossing foar it probleem, stribje wy nei:
- earst, om opslachkapasiteit te bewarjen;
- twadde, te bewarjen winkellju tiid.
De lêste beheining betsjut dat wy gjin guod kinne ferpleatse yn in kontener dy't wy net hawwe keazen, en hawwe dêrom gjin "kosten makke" foar it kiezen. Dizze beheining betsjuttet ek dat it folume fan guod ferpleatst fan sellen nei de kontener de kapasiteit fan 'e kontener net moat wêze. Mei it oplossen fan in probleem bedoele wy in set fan konteners en metoaden foar it heakjen fan donorsellen oan konteners.
Dizze formulearring fan it optimalisearjen probleem is net nij, en is studearre troch in protte wiskundigen sûnt de iere jierren '80 fan 'e foarige ieu. Yn bûtenlânske literatuer binne d'r 2 optimalisaasjeproblemen mei in passend wiskundich model: и (wy sille letter oer de ferskillen yn taken prate). It is it wurdich te sizzen dat yn 'e wiskundige literatuer de formulearring fan sokke twa optimisaasjeproblemen formulearre wurdt yn termen fan' e lokaasje fan bedriuwen op 'e grûn, fandêr de namme "Facility Location". Foar it grutste part is dit in earbetoan oan de tradysje, om't foar it earst de needsaak om sokke kombinatoryske problemen op te lossen kaam út it mêd fan logistyk, meast út 'e militêr-yndustriële sektor yn' e jierren '50 fan 'e foarige ieu. Wat de lokaasje fan it bedriuw oanbelanget, wurde sokke taken as folget formulearre:
- D'r is in beheind oantal stêden wêr't it mooglik mooglik is om produksjebedriuwen te lokalisearjen (hjirnei oantsjutten as produksjestêden). Foar elke produksjestêd wurde de kosten foar it iepenjen fan in ûndernimming dêryn spesifisearre, en ek in beheining op 'e produksjekapasiteit fan 'e ûndernimming dy't dêryn iepene is.
- D'r is in finite set fan stêden wêr't kliïnten wirklik lizze (hjirnei oantsjutten as kliïntstêden). Foar elke sa'n klantstêd wurdt it folume fan fraach nei produkten spesifisearre. Foar ienfâld sille wy oannimme dat d'r mar ien produkt is dat wurdt produsearre troch bedriuwen en konsumearre troch klanten.
- Foar elk pear stêd-fabrikant en stêd-kliïnt wurdt de wearde fan ferfierkosten foar it leverjen fan it fereaske folume fan produkten fan 'e fabrikant oan' e klant oanjûn.
Jo moatte fine yn hokker stêden om bedriuwen te iepenjen en hoe't jo kliïnten oan sokke bedriuwen kinne heakje om:
- De totale kosten fan it iepenjen fan bedriuwen en ferfierkosten wiene minimaal;
- It folume fan 'e fraach fan klanten dy't oan elke iepen ûndernimming binne tawiisd, wie net grutter as de produksjekapasiteit fan dy ûndernimming.
No is it wurdich te neamen it ienige ferskil yn dizze twa klassike problemen:
- Single-Source Capacitated Facility Lokaasje Probleem - de klant wurdt levere út mar ien iepen foarsjenning;
- Multi-Boarne Capacitated Facility Lokaasje Probleem - de klant kin wurde levere út ferskate iepen foarsjennings tagelyk.
Sa'n ferskil tusken de twa problemen is ûnbelangryk op it earste each, mar, yn feite, liedt ta in folslein oare kombinatoryske struktuer fan sokke problemen en, as gefolch, ta folslein ferskillende algoritmen foar it oplossen fan harren. De ferskillen tusken de taken wurde oantoand yn de ûndersteande figuer.
Fig.3. a) Multi-Source Capacitated Facility Lokaasje Probleem
Fig.3. b) Single-Source Capacitated Facility Lokaasje Problem
Beide taken -difficult, dat is, der is gjin eksakte algoritme dat soe oplosse sa'n probleem yn in tiid polynoom yn 'e grutte fan' e ynfier gegevens. Yn ienfâldiger wurden, alle krekte algoritmen foar it oplossen fan in probleem sille wurkje yn eksponinsjele tiid, hoewol miskien flugger as in folslein sykjen fan opsjes. Sûnt de taak -moeilik, dan sille wy beskôgje allinne approximate heuristics, dat is, algoritmen dy't sil konsekwint berekkenje oplossings hiel ticht by optimaal en sil wurkje frij fluch. As jo ynteressearre binne yn sa'n taak, kinne jo hjir in goed oersjoch fine yn it Russysk.
As wy ferskowe nei de terminology fan ús probleem fan optimale kompresje fan guod yn sellen, dan:
- kliïntstêden binne donorsellen mei it oerbliuwende guod,
- manufacturing stêden - container sellen , dêr't de oerbliuwsels fan oare sellen yn pleatst wurde moatte,
- ferfier kosten - tiid kosten winkelman om it folume fan guod út 'e donorsel te ferpleatsen yn in kontener sel ;
- kosten foar it iepenjen fan in bedriuw - kosten foar it kiezen fan in kontener , lyk oan it folume fan de kontener sel .
Nei't de analogy mei de bekende klassike oplossings fan it probleem is tekene, is it nedich om in wichtige fraach te beantwurdzjen wêrfan de kar fan 'e oplossingsalgoritme-arsjitektuer hinget: it ferpleatsen fan' e oerbliuwsels fan 'e donorselle is allinich mooglik nei ien en mar ien kontener (Single-Boarne), of is it mooglik om de oerbliuwsels te ferpleatsen yn ferskate kontenersellen (Multi-Boarne)?
It is de muoite wurdich opskriuwen dat yn de praktyk beide formulearrings fan it probleem plakfine. Wy presintearje hjirûnder alle foar- en neidielen foar elke sa'n ynstelling:
| Probleem fariant | Pros fan de opsje | Cons fan de opsje |
|---|---|---|
| Single-Boarne | Goederen beweging operaasjes berekkene mei help fan dizze fariant fan it probleem:
|
|
| Multi-Boarne | Kompresjes berekkene mei dizze ferzje fan it probleem binne normaal 10-15% kompakter yn ferliking mei kompresjes berekkene mei de opsje "Single-Source". Mar wy konstatearje ek dat hoe lytser it oantal residuen yn 'e donorsellen, hoe lytser it ferskil yn kompaktheid | Goederen beweging operaasjes berekkene mei help fan dizze fariant fan it probleem:
|
Tabel 1. Foar- en neidielen fan Single-Boarne en Multi-Boarne opsjes.
Sûnt de Single-Source-opsje mear foardielen hat, en ek rekken hâldend mei it feit dat hoe lytser it oantal residuen yn donorsellen, hoe lytser it ferskil yn 'e mjitte fan kompresje-kompaktens berekkene foar beide farianten fan it probleem, foel ús kar op de Single-Source opsje.
It is it wurdich te sizzen dat de oplossing foar de Multi-Boarne-opsje ek plakfynt. D'r binne in grut oantal effektive algoritmen om it op te lossen, wêrfan de measten delkomme op it oplossen fan in oantal transportproblemen. D'r binne ek net allinich effisjinte algoritmen, mar ek elegante, bygelyks,
Tariede Input Data
Foardat jo begjinne mei it analysearjen en ûntwikkeljen fan in algoritme om in probleem op te lossen, is it nedich om te besluten hokker gegevens en yn hokker foarm wy it as ynfier sille fiede. D'r binne gjin problemen mei it folume fan oerbleaune guod yn donorsellen en de kapasiteit fan kontenersellen, om't dit triviaal is - sokke hoemannichten wurde metten yn m3, mar mei de kosten fan it brûken fan in kontenersel en de bewegende kostenmatrix, net alles is sa ienfâldich!
Litte wy earst nei de berekkening sjen kosten fan ferpleatse guod fan de donorselle nei de kontenersel. Alderearst is it nedich om te besluten yn hokker ienheden fan mjitting sille wy de kosten fan beweging berekkenje. De twa meast foar de hân lizzende opsjes binne meters en sekonden. It hat gjin sin om reiskosten te berekkenjen yn "suvere" meters. Litte wy dit sjen litte mei in foarbyld. Lit de sel leit op de earste tier, sel fuorthelle troch 30 meter en leit op de twadde tier:
- Ferhúzje fan в djoerder as it ferpleatsen fan в , sûnt delgean fan 'e twadde tier (1,5-2 meter fan' e flier) is makliker as nei de twadde, hoewol de ôfstân itselde sil wêze;
- Ferpleats 1 pc. guod út de sel в It sil makliker wêze as it ferpleatsen fan 10 stikken. itselde produkt, hoewol't de ôfstân sil wêze itselde.
It is better om de ferpleatskosten yn sekonden te beskôgjen, om't dit jo kinne rekken hâlde mei sawol it ferskil yn tiers as it ferskil yn 'e kwantiteit fan ferpleatst guod. Om rekken te hâlden mei de kosten fan beweging yn sekonden, moatte wy de bewegingsoperaasje yn elemintêre komponinten decomposearje en tiidmjittingen nimme foar de útfiering fan elke elemintêre komponint.
Lit út 'e sel beweecht PC. guod yn container ... Lit wêze - de gemiddelde snelheid fan beweging fan in arbeider yn it pakhús, mjitten yn m / sek. Litte и - gemiddelde snelheden fan ien kear operaasjes nimme en sette, respektivelik, foar in folume fan guod gelyk oan 4 dm3 (it gemiddelde folume dat in meiwurker nimt op in tiid yn in pakhús by it útfieren fan operaasjes). Litte и de hichte fan 'e sellen wêrfan respektivelik de take- en put-operaasjes wurde útfierd. Bygelyks, de gemiddelde hichte fan 'e earste tier (flier) is 1 m, de twadde tier is 2 m, ensfh. Dan is de formule foar it berekkenjen fan de totale tiid om in ferhuzingsoperaasje te foltôgjen folgjende:
Tabel 2 toant statistiken oer de útfieringstiid fan elke elemintêre operaasje, sammele troch pakhúsmeiwurkers, rekken hâldend mei de spesifikaasjes fan it opsleine guod.
| de namme fan 'e operaasje | Notation | Betsjutte |
|---|---|---|
| Gemiddelde snelheid fan in arbeider dy't troch it pakhús beweecht | |
1,5 m/s |
| Gemiddelde snelheid fan ien operaasje te setten (foar in produkt folume fan 4 dm3) | |
2,4 sek |
Tabel 2. Gemiddelde tiid om te foltôgjen pakhús operaasjes
Wy hawwe besletten oer de metoade foar it berekkenjen fan de ferhuzingskosten. No moatte wy útfine hoe te berekkenjen kosten fan it kiezen fan in kontenersel. Alles is hjir folle, folle yngewikkelder dan mei ferpleatskosten, om't:
- As earste moatte de kosten direkt ôfhinklik wêze fan it folume fan 'e sel - itselde folume fan oerbliuwsels oerbrocht fan donorsellen is better pleatst yn in kontener fan in lytser folume as yn in grutte kontener, op betingst dat sa'n folume folslein yn beide konteners past. Sa, troch it minimalisearjen fan de totale kosten fan it selektearjen fan konteners, stribje wy nei it bewarjen fan "skrapte" frije opslachkapasiteit yn it seleksjegebiet om folgjende operaasjes út te fieren fan it pleatsen fan guod yn sellen. Figuer 4 toant de opsjes foar it oerbringen fan residuen yn grutte en lytse konteners en de gefolgen fan dizze oerdrachtopsjes yn folgjende magazijnoperaasjes.
- twadde, om't wy by it oplossen fan it orizjinele probleem krekt de totale kosten moatte minimalisearje, en dit is de som fan sawol de kosten fan it ferpleatsen as de kosten foar it kiezen fan konteners, dan moatte de selvoluminten yn kubike meter op ien of oare manier keppele wurde oan sekonden, dat is fier fan triviaal.
Rys. 4. Opsjes foar it ferpleatsen fan oerbliuwsels yn konteners fan ferskate kapasiteiten.
Figuer 4 lit yn read it folume fan oerbliuwsels sjen dy't net mear yn 'e kontener past by de twadde etappe fan it pleatsen fan folgjende guod.
It sil helpe om de kubike meter kosten te keppeljen foar it kiezen fan in kontener mei de sekonden fan kosten foar it ferpleatsen fan de folgjende easken foar berekkene oplossingen foar it probleem:
- It is needsaaklik dat de saldo's fan 'e donorbak yn alle gefallen nei de kontenerbak ferpleatst wurde as dit it totale oantal kontenerbakken mei it produkt ferminderet.
- It is needsaaklik om in lykwicht te hâlden tusken it folume fan konteners en de tiid bestege oan it ferpleatsen: bygelyks as yn in nije oplossing foar in probleem yn ferliking mei de foarige oplossing, de winst yn folume is grut, mar it ferlies yn 'e tiid is lyts , dan is it nedich om in nije opsje te kiezen.
Litte wy begjinne mei de lêste eask. Om it dûbelsinnige wurd "lykwicht" te ferdúdlikjen, hawwe wy in enkête útfierd ûnder magazynmeiwurkers om it folgjende út te finen. Lit der in kontener sel fan folume , dêr't de beweging fan oerbleaune guod út donorsellen oan is tawiisd en de totale tiid fan sa'n beweging is gelyk oan . Lit d'r ferskate alternative opsjes wêze foar it pleatsen fan deselde hoemannichte guod út deselde donorsellen yn oare konteners, wêr't elke pleatsing syn eigen skatten hat wêr < и wêr >.
De fraach wurdt steld: wat is de minimale winst yn folume akseptabel, foar in opjûne tiid ferlies wearde ? Lit ús útlizze mei in foarbyld. Yn it earstoan soene de oerbliuwsels yn in kontener mei in folume fan 1000 dm3 (1 m3) pleatst wurde en de oerdrachttiid wie 70 sekonden. Der is in opsje om de resten yn in oare kontener te pleatsen mei in folume fan 500 dm3 en in tiid fan 130 sekonden. Fraach: binne wy ree om noch 60 sekonden fan de winkelman syn tiid te besteegjen oan it ferpleatsen fan it guod om sa 500 dm3 frije folume te besparjen? Op grûn fan de resultaten fan in enkête fan magazynmeiwurkers is it folgjende diagram gearstald.
Rys. 5. Diagram fan 'e ôfhinklikens fan' e minimale tastiene folumebesparring op 'e ferheging fan it ferskil yn' e operaasjetiid
Dat is, as de ekstra tiidkosten 40 sekonden binne, dan binne wy ree om se allinich te besteegjen as de winst yn folume op syn minst 500 dm3 is. Nettsjinsteande it feit dat der in lichte net-lineariteit yn 'e ôfhinklikens is, sille wy foar de ienfâld fan fierdere berekkeningen oannimme dat de ôfhinklikens tusken de hoemannichten lineêr is en wurdt beskreaun troch de ûngelikens
Yn 'e ûndersteande figuer beskôgje wy de folgjende metoaden foar it pleatsen fan guod yn konteners.
Rys. 6. Opsje (a): 2 containers, totale folume 400 dm3, totale tiid 150 sek.
Rys. 6. Opsje (b): 2 containers, totale folume 600 dm3, totale tiid 190 sek.
Rys. 6. Opsje (c): 1 container, totale folume 400 dm3, totale tiid 200 sek.
Opsje (a) foar it kiezen fan konteners is de foarkar as de oarspronklike opsje, om't de ûngelikens jildt: (800-400)/10>=150-120, wat 40 >= 30 ymplisearret. Opsje (b) is minder de foarkar as it orizjineel opsje , om't de ûngelikens net hâldt: (800-600)/10>=190-150 wat 20 >= 40 ymplisearret. Mar opsje (c) past net yn sa'n logika! Litte wy dizze opsje yn mear detail beskôgje. Oan 'e iene kant is de ûngelikens (800-400)/10>=200-120, wat betsjut dat de ûngelikens 40>= 80 net tefreden is, wat suggerearret dat de winst yn folume net sa'n grut ferlies yn 'e tiid wurdich is.
Mar oan 'e oare kant, yn dizze opsje (c) wy net allinne ferminderje it totale besette folume, mar ek ferminderje it oantal besette sellen, dat is de earste fan twa wichtige easken foar computable oplossings foar de problemen neamd hjirboppe. Fansels, om dizze eask te begjinnen te folbringen, is it nedich om wat positive konstante ta te foegjen oan 'e lofterkant fan' e ûngelikens , en sa'n konstante moat allinich tafoege wurde as it oantal konteners ôfnimt. Lit ús jo dat herinnerje is in fariabele lyk oan 1 doe't de container selektearre, en 0 doe't container net selektearre. Lit ús oantsjutte - in protte konteners yn 'e earste oplossing en - in protte konteners yn 'e nije oplossing. Yn 't algemien sil de nije ûngelikens der sa útsjen:
Transformearje de ûngelikens hjirboppe, krije wy
Op grûn dêrfan hawwe wy in formule foar it berekkenjen fan de totale kosten wat oplossing foar it probleem:
Mar no komt de fraach op: hokker wearde moat sa'n konstante hawwe? ? Fansels moat de wearde derfan grut genôch wêze dat de earste eask foar oplossingen foar it probleem altyd foldien wurdt. Jo kinne, fansels, nimme de wearde fan de konstante gelyk oan 103 of 106, mar ik soe graach mije sokke "magyske nûmers". As wy beskôgje de spesifiken fan it útfieren fan magazyn operaasjes, kinne wy berekkenje ferskate goed-begrûne numerike skattings fan de wearde fan sa'n konstante.
Lit - de maksimale ôfstân tusken pakhússellen fan ien sône ABC, yn ús gefal gelyk oan 100 m. Lit - it maksimum folume fan in kontener sel yn in pakhús, gelyk yn ús gefal oan 1000 dm3.
De earste manier om de wearde te berekkenjen . Litte wy in situaasje beskôgje wêr't d'r 2 konteners op 'e earste tier binne, wêryn't it guod al fysyk leit, dat wol sizze, se sels binne donorsellen, en de kosten foar it ferpleatsen fan it guod nei deselde sellen binne natuerlik gelyk oan 0. is nedich om sa'n wearde foar de konstante te finen , wêryn it foardielich wêze soe om de oerbliuwsels altyd fan kontener 1 nei kontener 2 te ferpleatsen. De wearden ferfange и Yn 'e boppesteande ûngelikens krije wy:
dêr't it út folget
It ferfangen fan de wearden fan 'e gemiddelde tiid foar it útfieren fan elemintêre operaasjes yn' e boppesteande formule krije wy
De twadde manier om de wearde te berekkenjen . Litte wy in situaasje beskôgje wêr't d'r is donor sellen út dêr't it is pland te ferpleatsen it guod yn container 1. Lit ús oantsjutte - ôfstân fan de donor sel nei kontener 1. D'r is ek kontener 2, dy't al guod befettet, en it folume wêrfan jo de rest fan alle kinne bepale sellen. Foar de ienfâld sille wy oannimme dat it folume fan guod ferpleatst fan donorsellen nei konteners itselde is en gelyk oan . It is nedich om sa'n wearde fan 'e konstante te finen , dêr't de pleatsing fan alle oerbliuwsels út sellen yn kontener 2 soe altyd rendabeler wêze dan se yn ferskate konteners te pleatsen:
Transformearje de ûngelikens dy't wy krije
Om "fersterkje" de wearde fan 'e kwantiteit , lit ús dat oannimme = 0. It gemiddelde oantal sellen dy't normaal belutsen binne by de proseduere foar it komprimearjen fan magazynsaldo's is 10. It ferfangen fan de bekende wearden fan 'e hoemannichten, hawwe wy de folgjende wearde fan 'e konstante
Wy nimme de grutste wearde berekkene foar elke opsje, dit sil de wearde fan 'e kwantiteit wêze foar de opjûne pakhúsparameters. No, foar folsleinens, litte wy de formule opskriuwe foar it berekkenjen fan totale kosten foar guon mooglike oplossing :
No, ommers titanic ynspannings Troch de ynfiergegevens te transformearjen, kinne wy sizze dat alle ynfiergegevens binne omboud yn 'e winske foarm en binne klear foar gebrûk yn it optimisaasjealgoritme.
konklúzje
As praktyk docht bliken, wurdt de kompleksiteit en it belang fan it poadium fan it tarieden en transformearjen fan ynfiergegevens foar in algoritme faak ûnderskatte. Yn dit artikel hawwe wy spesifyk in soad omtinken jûn oan dit poadium om sjen te litten dat allinich heechweardige en yntelligint taret ynfiergegevens de besluten berekkene troch it algoritme echt weardefol meitsje kinne foar de kliïnt. Ja, d'r wiene in protte ôfliedingen fan formules, mar wy warskôgen jo sels foar de kata :)
Yn it folgjende artikel sille wy einlings komme ta wêr't de 2 eardere publikaasjes foar wiene bedoeld - in diskrete optimalisaasjealgoritme.
Tariede it artikel
Roman Shangin, programmeur fan 'e projektôfdieling,
First Bit bedriuw, Chelyabinsk
Boarne: www.habr.com