En ĉi tiu artikolo ni rakontos al vi kiel ni solvis la problemon de manko de senpagaj ĉeloj en magazeno kaj la disvolviĝon de diskreta optimumigo-algoritmo por solvi tian problemon. Ni parolu pri kiel ni "konstruis" la matematikan modelon de la optimumiga problemo, kaj pri la malfacilaĵoj, kiujn ni neatendite renkontis dum la prilaborado de enigaĵoj por la algoritmo.
Se vi interesiĝas pri aplikoj de matematiko en komerco kaj vi ne timas rigidajn identecajn transformojn de formuloj ĉe la 5-a grado, tiam bonvenon al la kato!
La artikolo estos utila al tiuj, kiuj efektivigas WMS-sistemoj, laboras en la magazeno aŭ produktada loĝistiko industrio, same kiel programistoj, kiuj interesiĝas pri aplikoj de matematiko en komerco kaj optimumigo de procezoj en entrepreno.
Enkonduka parto
Ĉi tiu publikigado daŭrigas la serion de artikoloj, en kiuj ni dividas nian sukcesan sperton pri efektivigado de optimumigoj en magazenaj procezoj.
В priskribas la specifaĵoj de la magazeno kie ni efektivigis WMS-sistemo, kaj ankaŭ klarigas kial ni bezonis solvi la problemon de amasigado de aroj de ceteraj varoj dum efektivigo WMS-sistemoj, kaj kiel ni faris ĝin.
Kiam ni finis verki la artikolon pri optimumigo-algoritmoj, ĝi montriĝis tre granda, do ni decidis dividi la amasigitan materialon en 2 partojn:
- En la unua parto (ĉi tiu artikolo) ni parolos pri kiel ni "konstruis" la matematikan modelon de la problemo, kaj pri la grandaj malfacilaĵoj, kiujn ni neatendite renkontis dum la prilaborado kaj transformado de la enirdatumoj por la algoritmo.
- En la dua parto ni konsideros detale la efektivigon de la algoritmo en la lingvo C ++, ni faros komputilan eksperimenton kaj resumos la sperton, kiun ni akiris dum la efektivigo de tiaj "inteligentaj teknologioj" en la komercaj procezoj de la kliento.
Kiel legi artikolon. Se vi legas la antaŭan artikolon, vi povas tuj iri al la ĉapitro "Superrigardo de ekzistantaj solvoj"; se ne, tiam la priskribo de la problemo solvita estas en la suba spoiler.
Priskribo de la problemo solvita ĉe la magazeno de la kliento
Botelkolo en procezoj
En 2018, ni kompletigis projekton por efektivigi WMS-sistemoj ĉe la magazeno "Komerca Domo "LD" en Chelyabinsk. Ni efektivigis la produkton "1C-Logistiko: Warehouse Management 3" por 20 laborlokoj: funkciigistoj WMS, magazenistoj, ŝarĝaŭtoj. La averaĝa magazeno estas ĉirkaŭ 4 mil m2, la nombro da ĉeloj estas 5000 kaj la nombro da SKUoj estas 4500. La magazeno stokas pilkvalvojn de nia propra produktado de malsamaj grandecoj de 1 kg ĝis 400 kg. Inventaro en la magazeno estas stokita en aroj, ĉar necesas elekti varojn laŭ FIFO.
Dum la desegno de stokaj procezaj aŭtomatigskemoj, ni alfrontis la ekzistantan problemon de ne-optimuma stokregistro. La specifaĵoj de stokado kaj metado de gruoj estas tiaj, ke unu unuopa stokĉelo povas nur enhavi erojn de unu aro (vidu Fig. 1). Produktoj alvenas al la magazeno ĉiutage kaj ĉiu alveno estas aparta aro. Entute, kiel rezulto de 1 monato da magazena operacio, 30 apartaj aroj estas kreitaj, malgraŭ tio, ke ĉiu devus esti stokita en aparta ĉelo. Ofte oni elektas produktojn ne en tutaj paletoj, sed en pecoj, kaj kiel rezulto, en la zono de elekto de pecoj en multaj ĉeloj oni observas la jenan bildon: en ĉelo kun volumeno de pli ol 1 m3 estas pluraj pecoj de gruoj, kiuj okupas malpli ol 5-10% de la ĉela volumo.
Figo 1. Foto de pluraj pecoj en ĉelo
Estas klare, ke stoka kapacito ne estas uzata optimume. Por imagi la skalon de la katastrofo, mi povas doni ciferojn: averaĝe estas de 1 ĝis 3 ĉeloj de tiaj ĉeloj kun volumeno de pli ol 100 m300 kun "minuskulaj" ekvilibroj dum malsamaj periodoj de la funkciado de la magazeno. Ĉar la magazeno estas relative malgranda, dum la magazenaj okupataj sezonoj ĉi tiu faktoro fariĝas "botelkolo" kaj tre malrapidigas la stokajn procezojn de akcepto kaj sendo.
Problema solvo ideo
Ekestis ideo: aroj da restaĵoj kun la plej proksimaj datoj devus esti reduktitaj al unu sola aro, kaj tiaj restaĵoj kun unuigita aro devas esti metitaj kompakte kune en unu ĉelon, aŭ en pluraj, se ne estas sufiĉe da spaco en unu por akomodi la. tuta kvanto da restaĵoj. Ekzemplo de tia "kunpremado" estas montrita en Figuro 2.
Fig.2. Skemo por kunpremi restaĵojn en ĉeloj
Ĉi tio ebligas al vi signife redukti la okupatan stokejon, kiu estos uzata por novaj varoj metitaj. En situacio, kie stokkapacito estas troŝarĝita, tia mezuro estas ege necesa, alie eble simple ne estos sufiĉe libera spaco por gastigi novajn varojn, kio kondukos al halto en la stokprocezoj de lokigo kaj replenigo kaj, kiel konsekvenco, al halto en akcepto kaj sendo. Antaŭe, antaŭ la efektivigo de la WMS-sistemo, tia operacio estis farita permane, kio estis neefika, ĉar la procezo de serĉado de taŭgaj ekvilibroj en ĉeloj estis sufiĉe longa. Nun, kun la enkonduko de WMS-sistemo, ni decidis aŭtomatigi la procezon, akceli ĝin kaj igi ĝin inteligenta.
La procezo de solvado de tia problemo estas dividita en 2 etapoj:
- ĉe la unua etapo ni trovas grupojn de aroj proksimaj en dato por kunpremado (dediĉita al ĉi tiu tasko );
- en la dua etapo, por ĉiu grupo de aroj ni kalkulas la plej kompaktan lokigon de la ceteraj varoj en la ĉeloj.
En la nuna artikolo ni koncentriĝos pri la dua etapo de la algoritmo.
Revizio de ekzistantaj solvoj
Antaŭ ol pluiri al la priskribo de la algoritmoj, kiujn ni disvolvis, indas fari mallongan superrigardon de sistemoj jam ekzistantaj sur la merkato. WMS, kiuj efektivigas similan optimuman kunpremadfunkciecon.
Antaŭ ĉio, necesas noti la produkton "1C: Enterprise 8. WMS-Loĝistiko. Stokadministrado 4", kiu estas posedata kaj reproduktita de 1C kaj apartenas al la kvara generacio WMS-sistemoj evoluigitaj de AXELOT. Ĉi tiu sistemo postulas kunpremadfunkciecon, kiu estas dizajnita por kunigi malsimilajn produktajn restaĵojn en unu komuna ĉelo. Menciindas, ke la kunprema funkcieco en tia sistemo ankaŭ inkluzivas aliajn eblecojn, ekzemple, korekti la lokigon de varoj en ĉeloj laŭ iliaj ABC-klasoj, sed ni ne traktos ilin.
Se vi analizas la kodon de la 1C: Enterprise 8. WMS Logistics-sistemo. Stokadministrado 4" (kiu estas malfermita en ĉi tiu parto de la funkcieco), ni povas konkludi la jenon. La resta kunpremadalgoritmo efektivigas sufiĉe primitivan linearan logikon kaj oni ne povas paroli pri iu ajn "optimuma" kunpremado. Kompreneble, ĝi ne antaŭvidas amasiĝon de partioj. Pluraj klientoj, kiuj havis tian sistemon efektivigita, plendis pri la rezultoj de kunpremadplanado. Ekzemple, ofte praktike dum kunpremado okazis la jena situacio: 100 pcs. Estas planite movi la ceterajn varojn de unu ĉelo al alia ĉelo, kie troviĝas 1 peco. varoj, kvankam estas optimuma el la vidpunkto de tempokonsumo fari la malon.
Ankaŭ, la funkcieco de kunpremado de la ceteraj varoj en ĉeloj estas deklarita en multaj eksterlandoj. WMS-sistemoj, sed, bedaŭrinde, ni ne havas veran retrosciigon pri la efikeco de la algoritmoj (ĉi tio estas komerca sekreto), des malpli ideon pri la profundo de ilia logiko (proprieta fermita programaro), do ni ne povas juĝi.
Serĉu matematikan modelon de la problemo
Por desegni altkvalitajn algoritmojn por solvi problemon, unue necesas klare formuli ĉi tiun problemon matematike, kion ni faros.
Estas multaj ĉeloj , kiuj enhavas la restaĵojn de kelkaj varoj. En kio sekvas, ni nomos tiajn ĉelojn donacantajn ĉelojn. Ni signu volumeno de varoj en la ĉelo $.
Gravas diri, ke nur unu produkto de unu aro, aŭ pluraj aroj antaŭe kombinitaj en areton (legu: ), kiu estas pro la specifaĵoj de stokado kaj konservado de varoj. Malsamaj produktoj aŭ malsamaj aroj devus ruli sian propran apartan kunpremadproceduron.
Estas multaj ĉeloj , en kiujn restaĵoj de donacĉeloj eble povas esti metitaj. Ni plu nomos tiajn ĉelojn ujajn ĉelojn. Ĉi tiuj povas esti aŭ senpagaj ĉeloj en la magazeno aŭ donantaj ĉeloj el diversaj . Ĉiam multe estas subaro .
Por ĉiu ĉelo de multaj Kapacilimigoj estis starigitaj , mezurita en dm3. Unu dm3 estas kubo kun flankoj de 10 cm La produktoj stokitaj en la magazeno estas sufiĉe grandaj, do en ĉi tiu kazo tia diskretigo sufiĉas.
Donita matrico de plej mallongaj distancoj en metroj inter ĉiu paro de ĉeloj kie и apartenas al aroj и laŭe.
Ni signu "kostoj" movi varojn el la ĉelo al ĉelo . Ni signu "kostoj" de elekto de ujo movi restaĵojn de aliaj ĉeloj en ĝin. Kiel precize kaj en kiaj mezurunuoj la valoroj estos kalkulitaj и ni konsideros plu (vidu la sekcion pri preparado de enigo datumoj), nuntempe sufiĉas diri, ke tiaj valoroj estos rekte proporciaj al la valoroj. и laŭe.
Ni signu per variablo kiu prenas la valoron 1 se la resto estas de la ĉelo movita al ujo , kaj 0 alie. Ni signu per variablo kiu prenas la valoron 1 se la ujo enhavas la ceterajn varojn, kaj 0 alie.
La tasko estas deklarita jene: vi bezonas trovi tiom da ujoj kaj tiel "alkroĉi" donacĉelojn al kontenerĉeloj por minimumigi la funkcion
sub limigoj
Entute, kiam ni kalkulas la solvon de la problemo, ni strebas al:
- unue, ŝpari stokan kapablon;
- due, ŝpari la tempon de magazenistoj.
La lasta limigo signifas, ke ni ne povas movi varojn en ujon, kiun ni ne elektis, kaj tial ne "faris kostojn" por elekti ĝin. Ĉi tiu limigo ankaŭ signifas, ke la volumeno de varoj movitaj de ĉeloj al la ujo ne devus superi la kapaciton de la ujo. Per solvado de problemo ni celas aron da ujoj kaj metodoj por ligi donacantajn ĉelojn al ujoj.
Tiu ĉi formuliĝo de la optimumproblemo ne estas nova, kaj estis studita de multaj matematikistoj ekde la fruaj 80-aj jaroj de la lasta jarcento. En eksterlanda literaturo ekzistas 2 optimumproblemoj kun taŭga matematika modelo: и (pri la diferencoj en taskoj ni parolos poste). Indas diri, ke en la matematika literaturo, la formuliĝo de tiaj du optimumigo-problemoj estas formulita laŭ la loko de entreprenoj sur la tero, do la nomo "Loko de la Instalaĵo". Plejparte, tio estas omaĝo al tradicio, ĉar unuafoje la bezono solvi tiajn kombinecajn problemojn venis de la kampo de loĝistiko, plejparte de la milit-industria sektoro en la 50-aj jaroj de la pasinta jarcento. Koncerne al entreprena loko, tiaj taskoj estas formulitaj jene:
- Ekzistas finhava nombro da grandurboj kie estas eble lokalizi produktadentreprenojn (ĉi-poste referite kiel fabrikurboj). Por ĉiu fabrik-urbo, la kostoj de malfermo de entrepreno en ĝi estas precizigitaj, same kiel limigo de la produktadkapablo de la entrepreno malfermita en ĝi.
- Estas finia aro de urboj, kie klientoj fakte troviĝas (ĉi-poste nomataj klienturboj). Por ĉiu tia klienta urbo, la volumo de postulo por produktoj estas specifita. Por simpleco, ni supozos, ke ekzistas nur unu produkto, kiu estas produktita de entreprenoj kaj konsumita de klientoj.
- Por ĉiu paro de urbo-fabrikisto kaj urbo-kliento, la valoro de transportkostoj por liverado de la bezonata volumo de produktoj de la fabrikanto al la kliento estas specifita.
Vi devas trovi en kiuj urboj malfermi entreprenojn kaj kiel ligi klientojn al tiaj entreprenoj por:
- La totalkostoj de malfermado de entreprenoj kaj transportkostoj estis minimumaj;
- La volumeno de postulo de klientoj asignitaj al iu malferma entrepreno ne superis la produktadkapaciton de tiu entrepreno.
Nun indas mencii la nuran diferencon en ĉi tiuj du klasikaj problemoj:
- Unu-Fonto Kapacita Instalaĵa Loka Problemo - la kliento estas provizita de nur unu malferma instalaĵo;
- Plurfonta Kapacita Instalaĵa Loka Problemo - la kliento povas esti provizita de pluraj malfermaj instalaĵoj samtempe.
Tia diferenco inter la du problemoj estas sensignifa unuavide, sed, fakte, kondukas al tute alia kombineca strukturo de tiaj problemoj kaj, sekve, al tute malsamaj algoritmoj por solvi ilin. La diferencoj inter la taskoj estas montritaj en la suba figuro.
Fig.3. a) Plurfonta Kapacita Instalaĵa Loka Problemo
Fig.3. b) Unu-Fonto Kapacita Instalaĵa Loka Problemo
Ambaŭ taskoj -malfacila, tio estas, ne ekzistas ekzakta algoritmo, kiu solvus tian problemon en tempa polinomo en la grandeco de la eniga datumo. En pli simplaj vortoj, ĉiuj precizaj algoritmoj por solvi problemon funkcios en eksponenta tempo, kvankam eble pli rapide ol kompleta serĉo de opcioj. Ekde la tasko -malfacila, tiam ni konsideros nur proksimumajn heŭristikojn, tio estas, algoritmojn, kiuj konstante kalkulos solvojn tre proksimajn al optimumaj kaj funkcios sufiĉe rapide. Se vi interesiĝas pri tia tasko, vi povas trovi bonan superrigardon en la rusa ĉi tie.
Se ni ŝanĝas al la terminologio de nia problemo de optimuma kunpremo de varoj en ĉeloj, tiam:
- klienturboj estas donacantaj ĉeloj kun la ceteraj varoj,
- fabrikurboj - uj ĉeloj , en kiu la restaĵoj de aliaj ĉeloj supozeble estas metitaj,
- transport costs - tempokostoj magazenisto movi la volumon de varoj de la donacanto ĉelo en ujon ĉelon ;
- costs of opening a business - kostoj de elekto de ujo , egala al la volumeno de la uja ĉelo , multobligita per certa koeficiento por ŝpari liberajn volumojn (la valoro de la koeficiento estas ĉiam > 1) (vidu la sekcion pri preparado de enigdatenoj).
Post kiam la analogio kun la konataj klasikaj solvoj de la problemo estas desegnita, necesas respondi gravan demandon, de kiu dependas la elekto de solva algoritmo-arkitekturo: movi la restaĵojn de la donaca ĉelo eblas nur al unu kaj nur unu ujo. (Ununura Fonto), aŭ ĉu eblas movi la restaĵojn en plurajn ujajn ĉelojn (Multfonto)?
Indas noti, ke en la praktiko okazas ambaŭ formuliĝoj de la problemo. Ni prezentas ĉiujn avantaĝojn kaj malavantaĝojn por ĉiu tia agordo sube:
| Problema varianto | Avantaĝoj de la opcio | Malavantaĝoj de la opcio |
|---|---|---|
| Ununura-Fonto | Operacioj pri varoj kalkulitaj uzante ĉi tiun varianton de la problemo:
|
|
| Plurfonto | Kunpremoj kalkulitaj uzante ĉi tiun version de la problemo estas kutime 10-15% pli kompaktaj kompare kun kunpremoj kalkulitaj per la "Ununura Fonto". Sed ni ankaŭ rimarkas, ke ju pli malgranda estas la nombro da restaĵoj en la donacĉeloj, des pli malgranda estas la diferenco en kompakteco. | Operacioj pri varoj kalkulitaj uzante ĉi tiun varianton de la problemo:
|
Tabelo 1. Avantaĝoj kaj malavantaĝoj de Unufontaj kaj Plurfontaj elektoj.
Ĉar la Unu-Fonto-opcio havas pli da avantaĝoj, kaj ankaŭ konsiderante la fakton, ke ju pli malgranda estas la nombro da restaĵoj en donacĉeloj, des pli malgranda estas la diferenco en la grado de kunprema kompakteco kalkulita por ambaŭ variantoj de la problemo, nia elekto falis sur la opcio Unu-Fonto.Fonto.
Indas diri, ke ankaŭ okazas la solvo de la plurfonta opcio. Ekzistas granda nombro da efikaj algoritmoj por solvi ĝin, la plej multaj el kiuj venas al solvado de kelkaj transportproblemoj. Ekzistas ankaŭ ne nur efikaj algoritmoj, sed ankaŭ elegantaj, ekzemple,
Preparado de Eniga Datumo
Antaŭ ol komenci analizi kaj disvolvi algoritmon por solvi problemon, necesas decidi kiajn datumojn kaj en kia formo ni nutros ĝin kiel enigaĵon. Ne estas problemoj kun la volumo de ceteraj varoj en donacĉeloj kaj la kapablo de ujĉeloj, ĉar ĉi tio estas bagatela - tiaj kvantoj estos mezuritaj en m3, sed kun la kostoj de uzado de ujĉelo kaj la movanta kostmatrico, ne ĉio. estas tiel simpla!
Ni unue rigardu la kalkulon kostoj de translokado de varoj de la donaca ĉelo ĝis la uja ĉelo. Antaŭ ĉio, necesas decidi, en kiuj mezurunuoj ni kalkulos la kostojn de movado. La du plej evidentaj opcioj estas metroj kaj sekundoj. Ne havas sencon kalkuli vojaĝkostojn en "puraj" metroj. Ni montru ĉi tion per ekzemplo. Lasu la ĉelon situanta sur la unua parto, ĉelo forigita je 30 metroj kaj situanta sur la dua parto:
- Moviĝante de в pli multekosta ol translokiĝi de в , ĉar malsupreniri de la dua nivelo (1,5-2 metrojn de la planko) estas pli facila ol supreniri al la dua, kvankam la distanco estos la sama;
- Movu 1 komputilon. varoj el la ĉelo в Estos pli facile ol movi 10 pecojn. la sama produkto, kvankam la distanco estos la sama.
Pli bone estas konsideri movajn kostojn en sekundoj, ĉar ĉi tio ebligas al vi konsideri ambaŭ la diferencon en niveloj kaj la diferencon en la kvanto de varoj movitaj. Por kalkuli la koston de movado en sekundoj, ni devas malkomponi la movadan operacion en elementajn komponentojn kaj preni tempmezurojn por la ekzekuto de ĉiu elementa komponento.
Lasu el la ĉelo movoj komputilo. varoj en ujo ... Estu – la averaĝa movrapido de laboristo en la magazeno, mezurita en m/sec. Lasu и – averaĝaj rapidoj de unufojaj operacioj prenas kaj metas, respektive, por volumo de varoj egala al 4 dm3 (la averaĝa volumo, kiun dungito prenas samtempe en magazeno dum farado de operacioj). Lasu и la alteco de la ĉeloj de kiuj la preni kaj meti operaciojn estas faritaj, respektive. Ekzemple, la meza alteco de la unua parto (etaĝo) estas 1 m, la dua parto estas 2 m, ktp. Tiam la formulo por kalkuli la totalan tempon por plenumi movoperacion estas sekva:
Tablo 2 montras statistikojn pri la ekzekuttempo de ĉiu elementa operacio, kolektitaj de magazenaj dungitoj, konsiderante la specifaĵojn de la stokitaj varoj.
| la nomo de la operacio | Nomado | Mean |
|---|---|---|
| Averaĝa rapideco de laboristo moviĝanta ĉirkaŭ la magazeno | |
1,5 m/s |
| Meza rapido de unu operacio por meti (por produktovolumo de 4 dm3) | |
2,4 sek |
Tabelo 2. Averaĝa tempo por kompletigi magazenajn operaciojn
Ni decidis pri la metodo por kalkuli la kostojn de translokado. Nun ni devas eltrovi kiel kalkuli kostoj de elekto de ujo ĉelo. Ĉio ĉi tie estas multe, multe pli komplika ol kun translokaj kostoj, ĉar:
- unue, kostoj devas esti rekte dependaj de la volumeno de la ĉelo - la sama volumeno de restaĵoj transdonitaj de donacĉeloj estas pli bone metita en ujo de pli malgranda volumeno ol en granda ujo, kondiĉe ke tia volumeno tute taŭgas en ambaŭ ujoj. Tiel, minimumigante la totalajn kostojn de elektado de ujoj, ni strebas ŝpari "malabundan" senpagan stokan kapaciton en la elektareo por plenumi postajn operaciojn meti varojn en ĉelojn. Figuro 4 montras la eblojn por translokigi restaĵojn en grandajn kaj malgrandajn ujojn kaj la konsekvencojn de ĉi tiuj translokigaj elektoj en postaj stokaj operacioj.
- due, ĉar en solvado de la origina problemo ni devas minimumigi precize la totalajn kostojn, kaj ĉi tio estas la sumo de kaj la kostoj de translokado kaj la kostoj de elekto de ujoj, tiam la ĉelvolumoj en kubaj metroj devas esti iel ligitaj al sekundoj, kiu estas malproksime de bagatela.
Rizo. 4. Opcioj por movi restaĵojn en ujojn de malsamaj kapacitoj.
La figuro 4 montras ruĝe la volumon de restaĵoj, kiuj ne plu konvenas en la ujon ĉe la dua etapo de meti postaj varoj.
Ĝi helpos ligi la kubajn metrojn de kostoj por elekti ujo kun la sekundoj de kostoj por movi la sekvajn postulojn por kalkulitaj solvoj al la problemo:
- Necesas, ke la ekvilibroj de la donacujo estu ĉiuokaze movitaj al la ujujo, se tio reduktas la totalan nombron de ujujoj enhavantaj la produkton.
- Necesas konservi ekvilibron inter la volumo de ujoj kaj la tempo pasigita por moviĝado: ekzemple, se en nova solvo de problemo kompare kun la antaŭa solvo, la gajno de volumeno estas granda, sed la perdo de tempo estas malgranda. , tiam necesas elekti novan opcion.
Ni komencu per la lasta postulo. Por klarigi la ambiguan vorton "ekvilibro", ni faris enketon al magazenaj dungitoj por ekscii la jenon. Estu uja ĉelo de volumeno , al kiu la movado de ceteraj varoj de donacĉeloj estas asignita kaj la tuta tempo de tia movado estas egala al . Estu pluraj alternativaj elektoj por meti la saman kvanton da varoj de la samaj donacĉeloj en aliajn ujojn, kie ĉiu lokigo havas siajn proprajn taksojn. kie < и kie >.
La demando estas starigita: kio estas la minimuma gajno en volumeno akceptebla, por donita tempoperdovaloro ? Ni klarigu per ekzemplo. Komence, la restaĵoj devis esti metitaj en ujo kun volumeno de 1000 dm3 (1 m3) kaj la transiga tempo estis 70 sekundoj. Estas eblo meti la restaĵojn en alian ujon kun volumeno de 500 dm3 kaj tempo de 130 sekundoj. Demando: ĉu ni pretas pasigi pliajn 60 sekundojn de la tempo de la magazenisto por movi la varojn por ŝpari 500 dm3 da libera volumeno? Surbaze de la rezultoj de enketo de magazenaj dungitoj, la sekva diagramo estis kompilita.
Rizo. 5. Diagramo de la dependeco de la minimuma permesebla voluma ŝparado sur la pliiĝo de la diferenco en la operacia tempo
Tio estas, se la kromaj tempokostoj estas 40 sekundoj, tiam ni pretas elspezi ilin nur kiam la gajno en volumeno estas almenaŭ 500 dm3. Malgraŭ tio, ke ekzistas eta nelineareco en la dependeco, por la simpleco de pliaj kalkuloj ni supozos ke la dependeco inter la kvantoj estas linia kaj estas priskribita per la malegaleco.
En la suba figuro, ni konsideras la jenajn metodojn por meti varojn en ujojn.
Rizo. 6. Opcio (a): 2 ujoj, totala volumo 400 dm3, tuta tempo 150 sek.
Rizo. 6. Opcio (b): 2 ujoj, totala volumo 600 dm3, tuta tempo 190 sek.
Rizo. 6. Opcio (c): 1 ujo, totala volumo 400 dm3, tuta tempo 200 sek.
Opcio (a) por elekti ujojn estas pli preferinda ol la originala opcio, ĉar la malegaleco validas: (800-400)/10>=150-120, kio implicas 40 >= 30. Opcio (b) estas malpli preferinda ol la originalo. opcio , ĉar la malegaleco ne validas: (800-600)/10>=190-150 kiu implicas 20 >= 40. Sed opcio (c) ne taŭgas en tia logiko! Ni konsideru ĉi tiun opcion pli detale. Unuflanke, la malegaleco (800-400)/10>=200-120, kio signifas ke la malegaleco 40 >= 80 ne estas kontentigita, kio sugestas ke la gajno en volumeno ne valoras tiom grandan perdon en tempo.
Sed aliflanke, en ĉi tiu opcio (c) ni ne nur reduktas la totalan okupitan volumon, sed ankaŭ reduktas la nombron da okupitaj ĉeloj, kio estas la unua el du gravaj postuloj por komputeblaj solvoj al la supre listigitaj problemoj. Evidente, por ke ĉi tiu postulo komencu esti plenumita, necesas aldoni iun pozitivan konstanton al la maldekstra flanko de la malegaleco. , kaj tia konstanto devas esti aldonita nur kiam la nombro da ujoj malpliiĝas. Ni rememorigu tion al vi estas variablo egala al 1 kiam la ujo elektita, kaj 0 kiam ujo ne elektita. Ni signu – multaj ujoj en la komenca solvo kaj – multaj ujoj en la nova solvo. Ĝenerale, la nova malegaleco aspektos jene:
Transformante la malegalecon supre, ni ricevas
Surbaze de ĉi tio, ni havas formulon por kalkuli la totalan koston iu solvo al la problemo:
Sed nun leviĝas la demando: kian valoron havu tia konstanto? ? Evidente, ĝia valoro devas esti sufiĉe granda, por ke la unua postulo por solvoj al la problemo ĉiam estas plenumita. Vi povas, kompreneble, preni la valoron de la konstanto egala al 103 aŭ 106, sed mi ŝatus eviti tiajn "magiajn nombrojn". Se ni konsideras la specifaĵojn de farado de magazenaj operacioj, ni povas kalkuli plurajn bone bazitajn nombrajn taksojn de la valoro de tia konstanto.
Lasu – la maksimuma distanco inter magazenaj ĉeloj de unu zono ABC, egala en nia kazo al 100 m. – la maksimuma volumo de ujo ĉelo en magazeno, egala en nia kazo al 1000 dm3.
La unua maniero por kalkuli la valoron . Ni konsideru situacion, kie estas 2 ujoj sur la unua nivelo, en kiuj la varoj jam fizike situas, tio estas, ili mem estas donacantaj ĉeloj, kaj la kosto de movi la varojn al la samaj ĉeloj estas nature egala al 0. Ĝi necesas trovi tian valoron por la konstanto , en kiu estus avantaĝe ĉiam movi la restaĵojn de ujo 1 al ujo 2. Anstataŭigante la valorojn и En la malegaleco donita supre ni ricevas:
el kiu ĝi sekvas
Anstataŭigante la valorojn de la averaĝa tempo por farado de elementaj operacioj en la formulon supre, ni ricevas
La dua maniero kalkuli la valoron . Ni konsideru situacion kie ekzistas donantaj ĉeloj el kiuj oni planas movi la varojn en ujon 1. Ni signu – distanco de la donanta ĉelo al ujo 1. Estas ankaŭ ujo 2, kiu jam enhavas varojn, kaj kies volumeno permesas al vi gastigi la reston de ĉiuj. ĉeloj. Por simpleco, ni supozos ke la volumeno de varoj movitaj de donacĉeloj al ujoj estas la sama kaj egala al . Estas postulate trovi tian valoron de la konstanto , en kiu la lokigo de ĉiuj restaĵoj de ĉeloj en ujon 2 ĉiam estus pli enspeziga ol meti ilin en malsamajn ujojn:
Transformante la malegalecon, kiun ni ricevas
Por "fortigi" la valoron de la kvanto , ni supozu tion = 0. La averaĝa nombro da ĉeloj kutime implikitaj en la proceduro por kunpremi magazenajn ekvilibrojn estas 10. Anstataŭigante la konatajn valorojn de la kvantoj, ni havas la sekvan valoron de la konstanto
Ni prenas la plej grandan valoron kalkulitan por ĉiu opcio, ĉi tio estos la valoro de la kvanto por la donitaj stokparametroj. Nun, por kompleteco, ni skribu la formulon por kalkuli totalajn kostojn por iu farebla solvo :
Nun, post ĉio titanaj klopodoj Transformante la enigajn datumojn, ni povas diri, ke ĉiuj enigaj datumoj estis konvertitaj al la dezirata formo kaj estas pretaj por uzi en la optimumiga algoritmo.
konkludo
Kiel praktiko montras, la komplekseco kaj graveco de la stadio de preparado kaj transformado de enirdatenoj por algoritmo estas ofte subtaksitaj. En ĉi tiu artikolo, ni specife multe atentis ĉi tiun etapon por montri, ke nur altkvalitaj kaj inteligente pretaj enigaĵoj povas fari la decidojn kalkulitajn de la algoritmo vere valoraj por la kliento. Jes, estis multaj derivaĵoj de formuloj, sed ni avertis vin eĉ antaŭ la kata :)
En la sekva artikolo ni finfine venos al tio, por kio la 2 antaŭaj publikaĵoj estis destinitaj - diskreta optimumiga algoritmo.
Preparis la artikolon
Roman Shangin, programisto de la projektsekcio,
Unua Bit-firmao, Chelyabinsk
fonto: www.habr.com