Matematika diskrete për WMS: algoritmi i kompresimit të produkteve në qeliza (pjesa 1)

Në këtë artikull do t'ju tregojmë si zgjidhëm problemin e mungesës së qelizave të lira në magazinë dhe zhvillimin e një algoritmi të optimizimit disket për zgjidhjen e këtij problemi. Do të tregojmë se si e "ndërtumonim" modelin matematikor të problemit të optimizimit dhe për cilat vështirësi u përballëm papritur gjatë përpunimit të të dhënave hyrëse për algoritmin.

Nëse jeni të interesuar për aplikimet e matematikës në biznes dhe nuk keni frikë nga transformimet rigorozë të formulave në nivelin e klasës së 5-të, ju mirëpresim në këtë artikull!

Ky artikull do të jetë i dobishëm për ata që implementojnë sistemat WMS-sistemi, punojnë në fushën e logjistikës magazinuese ose prodhuese, si dhe për programuesit që janë të interesuar për aplikimet e matematikës në biznes dhe optimizimin e proceseve në kompani.

Pjesa hyrëse

Ky publikim vazhdon serinë e artikujve ku ndajmë përvojën tonë të suksesshme në implementimin e algoritmeve të optimizimit në proceset e magazinës.

Në artikulli i mëparshëm do të përshkruajë specifikën e magazinës, ku ne kemi implementuar sistemat WMS-sistemi, dhe do të tregojë se përse ishte e nevojshme të zgjidhet problemi i klasterizimit të grupeve të mbetjeve të produkteve gjatë implementimit të sistemat WMS-sistemi, dhe se si e realizuam këtë.

Kur përfunduam shkrimin e artikullit mbi algoritmet e optimizimit, ai doli shumë i gjatë, prandaj vendosëm ta ndajmë materialin në 2 pjesë:

• Në pjesën e parë (ky artikull) do të tregojmë se si e "ndërtumonim" modelin matematikor të problemit dhe për cilat vështirësi të mëdha u përballëm papritur gjatë përpunimit dhe transformimit të të dhënave hyrëse për algoritmin.
• Në pjesën e dytë do të shqyrtojmë në detaje realizimin e algoritmit në gjuhën C++, do të kryejmë eksperimentin numerik dhe do të përmbledhim përvojën që fituam gjatë implementimit të këtyre "teknologjive inteligjente" në proceset biznesore të klientit.

Si të lexoni artikullin. Nëse keni lexuar artikullin e mëparshëm, mund të kaloni direkt në kapitullin "Përmbledhja e zgjidhjeve ekzistuese", nëse jo, përshkrimi i problemit të zgjidhur është në spoylerin më poshtë.

Përshkrimi i problemit të zgjidhur në magazinën e klientit

Pika e ngushtë në proceset

Në 2018, ne realizuam një projekt për implementimin e sistemat WMS-sistemi në magazinën "Shtëpia Tregtare 'LD'" në qytetin Çeljabinsk. Implementuam produktin "1C-Logistika: Menaxhimi i Magazinës 3" në 20 vende pune: operatoret. sistemat WMS, magazinjerë, shoferë ngarkuesish. Magazina është e mesme, rreth 4 mijë m2, me numër magazinash 5000 dhe numër SKU 4500. Në magazinë ruhen ventila sferikë të prodhimit të vet, në përmasa të ndryshme nga 1 kg deri në 400 kg. Stoket në magazinë ruhen sipas grupeve, pasiqë ka nevojë për përzgjedhjen e mallrave sipas FIFO.

gjatë projektimit të skemave të automatizimit të proceseve të magazinës, u ballafaquam me problemin ekzistues të ruajtjes jo optimale të stokut. Specificiteti i ruajtjes dhe vendosjes së ventileve është i tillë që në një qelizë ruajtjeje mund të ndodhen vetëm artikuj të një grupi (shih figurën 1). Produktet vijnë në depo çdo ditë dhe çdo ardhje është një grup i veçantë. Duke e përmbledhur, si rezultat i një muaji pune të magazinës krijohen 30 grupe të veçanta, ndonëse secila duhet të ruhet në një qelizë të veçantë. Mallrat shpesh përzgjidhen jo me paleta të plota, por me copa, dhe si rezultat, në zonën e përzgjedhjes së copave në shumë qeliza vërehet një pamje e tillë: në një qelizë me volum mbi 1m3 ka disa copë ventila, të cilat zënë më pak se 5-10% të volumit të qelisë.

Figura 1. Foto e disa copëve në qelizë

Këtu duket përdorimi jo optimal i kapaciteteve të magazinës. Për të ilustruar masën e problemit, mund të jap disa numra: mesatarisht, ka prej 100 deri në 300 qeliza të tilla me volum mbi 1m3 me 'mbetje minimale' në periudha të ndryshme të punës së magazinës. Duke qenë se magazina është relativisht e vogël, në sezonet e ngarkesës, ky faktor bëhet një 'prurës i ngushtë' që e ngadalëson ndjeshëm procesin e pranimit dhe dërgimit të mallrave.

Ideja për zgjidhjen e problemit

Lindi ideja: grumbujt e mbetjeve me data më të afërta t'i bashkojmë në një grup të vetëm dhe këto mbetje me grup të unifikuar të vendosen kompakt së bashku në një qelizë, ose në disa, nëse hapësira në një nuk është e mjaftueshme për të pranuar të gjithë sasinë e mbetjeve. Një shembull i një ‘tkurrjeje’ të tillë është ilustruar në figurën 2.

Figura 2. Skema e tkurrjes së mbetjeve në qeliza

Kjo lejon një reduktim të konsiderueshëm të hapësirave të magazinimit që do të përdoren për mallra të reja. Në situata me ngarkesë të tepruar të kapacitetit të magazinës, një masë e tillë është jashtëzakonisht e nevojshme, përndryshe mund të mos ketë hapësirë të mjaftueshme për vendosjen e mallrave të reja, që do të çojë në ndalimin e proceseve të vendosjes dhe furnizimit dhe, si pasojë, në ndalimin e pranimit dhe dërgimit. Më parë, para se të implementohej sistemi WMS, kjo operacion zhvillohej manualisht, gjë që ishte joefikase, pasi procesi i kërkimit të mbeturinave të përshtatshme në qelza merrte shumë kohë. Tani, me implementimin e sistemit WMS, vendosëm ta automatizojmë, ta përshpejtojmë dhe ta bëjmë atë inteligjent.

Procesi i zgjidhjes së kësaj detyre ndahet në 2 etapa:

• në etapën e parë, ne gjejmë grupe partish të afërta sipas datës për kompresim (kjo detyrë i është dedikuar) artikulli i mëparshëm);
• në etapën e dytë, për çdo grup partish, ne llogarisim vendosjen më kompakte të mbetjeve të mallrave në qelza.

Në këtë artikull do të ndalemi në etapën e dytë të algoritmit.

Përmbledhje e zgjidhjeve ekzistuese

Para se të kalojmë në përshkrimin e algoritmeve të zhvilluara nga ne, është e rëndësishme të bëjmë një përmbledhje të shkurtër të sistemeve që ekzistojnë në treg sistemat WMS, në të cilat implementohet një funksionalitet të tillë optimal kompresimi.

Së pari, është e nevojshme të theksohet produkti "1C: Ndërmarrja 8. WMS Logjistika. Menaxhimi i Magazinit 4", i cili i takon dhe shpërndahet nga firma 1C dhe i përket brezit të katërt sistemat WMS-sistemeve, të zhvilluara nga kompania AXELOT. Ky sistem ka funksionalitetin e kompresimit, i cili është dizenjuar për të bashkuar mbetje të ndryshme të mallrave në një qelzë të përbashkët. Duhet të sqarojmë se funksionaliteti i kompresimit në një sistem të tillë përfshin edhe mundësi të tjera, për shembull, korrigjimin e vendosjes së mallrave në qelza sipas klasave të tyre ABC, por për këto do të shmangim diskutimin.

Duke analizosh një kod të sistemit "1C: Ndërmarrja 8. WMS Logistika. Menaxhimi i Magazinit 4" (i cili në këtë pjesë të funksionalitetit është i hapur), mund të përfundojmë se algoritmi i kompresimit të mbetjeve implementon një logjikë relativisht primitive lineare dhe nuk mund të flitet për ndonjë "kompresim optimal". Natyrisht, ai nuk parashikon klasifikimin e grupeve. Disa klientë, tek të cilët ky sistem ishte implementuar, u ankuan për rezultatet e planifikimit të kompresimit. Për shembull, shpesh në praktikë gjatë kompresimit ndodhte një situatë e tillë: 100 copë mbetje produktesh nga një qeli planifikoheshin të transferoheshin në një qeli tjetër ku gjendej 1 copë produkti, ndonëse optimalisht nga pikëpamja e shpenzimeve të kohës do të ishte më mirë të bëhej e kundërta.

Po ashtu, funksionaliteti i kompresimit të mbetjeve të produkteve në qeli është deklaruar në shumë sistemat WMS-sisteme të huaja, por fatkeqësisht nuk kemi asnjë informacion real për efektivitetin e punës së algoritmeve (kjo është një sekret tregtar), as përderisa kemi ndonjë përfaqësim të thellësisë së logjikës së tyre (softuer pronësor me kod të mbyllur), prandaj nuk mund të gjykojmë.

Kërkimi i një modeli matematikor të problemit

Për të projektuar algoritme cilësore për zgjidhjen e problemit, është e nevojshme fillimisht të formulojmë këtë problem saktësisht në mënyrë matematikore, gjë që do ta bëjmë.

Janë shumë qeli , në të cilat ndodhen mbetje të disa produkteve. Më pas, këto qeli do të quhen qeli-dhuruese. Të shënojmë vëllimi i produktit që ndodhet në qelinë $.

Është e rëndësishme të thuhet se në procedurën e kompresimit mund të marrë pjesë vetëm një produkt i një grupi, ose disa grupe që janë paraprakisht të bashkuara në një klaster (lexo artikulli i mëparshëm), kjo është e kushtëzuar nga specifikati i ruajtjes dhe vendosjes së produkteve. Për produkte të ndryshme ose për grupe të ndryshme, duhet të nisen procedura e saj e veçantë e kompresimit.

Janë shumë qeli , në të cilat mund të vendosen potencialisht mbetjet nga qelitë-dhuruese. Këto qeli do t'i referohemi më tej si qeli-kontejner. Këto mund të jenë qeli të lira në magazinë, si dhe qelitë-dhuruese nga shumë . Gjithmonë shumë është një nënserie .

Për çdo qeli nga shumë janë të vendosura kufizime për kapacitetin , e matës në dm3. Një dm3 përfaqëson një kube me gjatësitë 10 cm. Produktet e ruajtura në depo janë mjaft të mëdha, prandaj në këtë rast një disretizimi i tillë është mjaft i përshtatshëm.

Matrica e distancave më të shkurtra është caktuar në metra midis çdo çifti të qelizave , ku dhe i përket grupeve dhe përkatësisht.

Të shënojmë kostot për zhvendosjen e mallrave nga qeliza në qelizën . Të shënojmë kostot për zgjedhjen e kontejnerit për të transferuar mbetjet nga qeliza të tjera. Si dhe në cilat njësi gjithashtu do të llogariten vlerat dhe do të shqyrtojmë më tej (shih seksionin përgatitja e të dhënave hyrëse), tani mjafton të thuhet se këto vlera do të jenë përmbledhëse me vlerat dhe përkatësisht.

Shenjësojmë përmes një variabël që merr vlerën 1, nëse mbetjet nga qelia ësht ne të lëvizura në kontenier , dhe 0 përndryshe. Shenjësojmë përmes një variabël që merr vlerën 1, nëse kontenieri përmban mbetjet e mallrave, dhe 0 përndryshe.

Detyra formullohet kështu: është e nevojshme të gjendet një shumës kontenierash dhe në këtë mënyrë ‘të lidhim’ qelitë-dhuruese me qelitë kontenier, në mënyrë që të minimizojmë funksionin

në kufizimet

Pra, gjatë llogaritjes së zgjidhjes së detyrës ne përpiqemi:

• së pari, të kursejmë kapacitetin e magazinave;
• së dyti, të kursejmë kohën e magazinierëve.

Kufizimi i fundit do të thotë se nuk mund të lëvizim mallrat në një kontenier që nuk e kemi zgjedhur, dhe për rrjedhojë nuk kemi ‘patur shpenzime’ për zgjedhjen e tij. Po ashtu, ky kufizim do të thotë se vëllimi i mallrave të lëvizura nga qelitë në kontenier nuk duhet të tejkalojë kapacitetin e kontenierit. Nga zgjidhja e detyrës, do të kuptojmë shumën e kontenierëve dhe mënyrat e lidhjes së qelive-dhuruese me kontenierët.

Një formulim i tillë i detyrës së optimizimit nuk është i ri dhe është studiuar nga shumë matematiciene që nga fillimi i viteve '80 të shekullit të kaluar. Në literaturën e huaj ekzistojnë 2 detyra optimizimi me një model matematikor të përshtatshëm: Single-Source Capacitated Facility Location Problem dhe Multi-Source Capacitated Facility Location Problem (për dallimet e detyrave do të flasim më vonë). Duhet thënë se në literaturën matematike formulimet e këtyre dy detyrave të optimizimit janë përshkruar në terma të vendosjes së ndërmarrjeve në territor, prej nga dhe emri ‘Facility Location’. Kryesisht kjo është një trashëgimi tradicionale, sepse nevoja për zgjidhjen e këtyre detyrave kombinatorial ka ardhur nga fusha e logjistikës, kryesisht, sektori industrial ushtarak në vitet '50 të shekullit të kaluar. Në terma të vendosjes së ndërmarrjeve, këto detyra formulohen kështu:

• Ekziston një shumicë e fundme qytetesh, ku potencialisht mund të vendosen ndërmarrje prodhimi (më pas qytetet-prodhues). Për secilin qytet-prodhues janë përcaktuar kostot për hapjen e një ndërmarrjeje atje, si dhe kufizimet e kapaciteteve prodhuese të ndërmarrjes së hapur.
• Ekziston një shumicë e fundme qytetesh, ku faktikisht ndodhen klientët (më pas qytetet-klient). Për secilin qytet-klient të tillë, është përcaktuar një vëllim kërkese për produktin. Për thjeshtësi, të supozojmë se produkti që prodhojnë ndërmarrjet dhe konsumojnë klientët është një.
• Për secilën palë qytet-prodhues dhe qytet-klient është përcaktuar një sasi e kostove të transportit për të dërguar vëllimin e kërkuar të produktit nga prodhuesi te klienti.

Duhet të gjendet se në cilat qytete të hapen ndërmarrjet dhe si të lidhën klientët me këto ndërmarrje, në mënyrë që:

• Kostot totale të hapjeve të ndërmarrjeve dhe kostot e transportit të jenë minimale;
• Vëllimi i kërkesës së klientëve, të lidhur me ndonjë ndërmarrje të hapur, të mos e kalojë kapacitetin prodhues të kësaj ndërmarrjeje.

Tani vlen të thuhet për dallimin e vetëm midis këtyre dy detyrave klasike:

• Single-Source Capacitated Facility Location Problem – klienti furnizohet vetëm nga një ndërmarrje të hapur;
• Multi-Source Capacitated Facility Location Problem – klienti mund të furnizohet nga disa ndërmarrje të hapura njëherazi.

Ky dallim midis detyrave, në shikim të parë, duket i parëndësishëm, por në të vërtetë, çon në një strukturë kombinatoriale krejtësisht të ndryshme të këtyre detyrave dhe, si pasojë, në algoritme krejtësisht të ndryshme për zgjidhjen e tyre. Dallimi midis detyrave është demonstruar në figurën më poshtë.

Fig.3. a) Multi-Source Capacitated Facility Location Problem

Fig.3. b) Single-Source Capacitated Facility Location Problem

Të dy detyrat janë të vështira, që do të thotë se nuk ekziston një algoritëm i saktë, i cili për një kohë polinomiale të madhësisë së të dhënave hyrëse do të zgjidhte një detyrë të tillë. Thënë ndryshe, të gjitha algoritmet e sakta për zgjidhjen e detyrës do të punojnë për një kohë eksponenciale, megjithatë, ndoshta më shpejt se provimi i plotë i mundësive. Siç janë të vështira, ne do të shqyrtojmë vetëm heuristika afër, që do të thotë algoritme që do të llogaritin zgjidhje të qëndrueshme shumë afër optimalëve dhe do të funksionojnë mjaft shpejt. Nëse ka interes për këto detyra, këtu mund të gjeni një përmbledhje të mirë në rusisht. Nëse e shikojmë në terminologjinë e detyrës sonë për optimizimin e mbushjes së mallrave në qelia, atëherë:

qytetet-klient janë qelitë-dhuruese

• me mbetje mallrash, qytetet-prodhues janë qelitë-kontenierë
• qatët e prodhuesve – qelizat-kontejnerë , në të cilat parashihet të vendosen mbetjet nga qeliza të tjera,
• kostot e transportit – kohëzgjatja e kostove të magjistarit për lëvizjet e volumit të mallrave nga qeliza burimore në qelizën-container ;
• kostot e hapjes së biznesit – kostot e zgjedhjes së qelizës-container , të barabarta me volumet e qelizës-container , të shumëzuara me një koeficient të caktuar të kursimeve të hapësirave të lira (vlera e koeficientit gjithmonë > 1) (shih seksionin përgatitja e të dhënave hyrëse).

Pasi të jetë bërë analogjia me dërgesat klasike të njohura, duhet të përgjigjemi në një pyetje të rëndësishme, nga e cila varet zgjedhja e arkitekturës së algoritmit të zgjidhjes: është e mundur që mbetjet të zhvendosen nga qeliza burimore vetëm në një dhe vetëm një container (Single-Source), ose është e mundur zhvendosja e mbetjeve në disa qeliza-container (Multi-Source)?

Vlen të theksohet se në praktikë të dy qasjet e problemit kanë vend. Do të paraqesim të gjitha 'pro' dhe 'kundër' për secilën prej tyre më poshtë:

Tavola 1. Avantazhet dhe disavantazhet e opsioneve Single-Source dhe Multi-Source.

Duke qenë se numri i avantazheve për opsionin Single-Source është më i madh, si dhe duke marrë parasysh faktin se sa më pak të jetë sasia e mbetjeve në qelizat burimore, aq më e vogël është dallimi në shkallën e kompaktësisë së kompresionit të llogaritur sipas të dy opsioneve të problemit, zgjedhja jonë ra në opsionin Single-Source.

Vlen të thuhet se zgjidhja e opsionit Multi-Source gjithashtu ka një vend. Ekzistojnë shumë algoritma efektivë për zgjidhjen e saj, shumica e të cilëve përfshihen në zgjidhjen e një sërë problemesh të transportit. Ka gjithashtu algoritma jo vetëm efektivë, por edhe elegantë, për shembull, këtu.

Përgatitja e të dhënave hyrëse

Para se të fillojmë analizën dhe zhvillimin e algoritmit për zgjidhjen e problemit, është e nevojshme të përcaktojmë se cilat të dhëna dhe në çfarë forme do t'i dorëzojmë atij. Me volumet e mbetjeve të mallrave në qelizat burimore dhe kapacitetin e qelizave-container nuk ka probleme, sepse ato janë triviale – këto sasi do të matet në m3, por me kostot e përdorimit të qelizës-container dhe matricën e kostove për zhvendosjen nuk është aq e thjeshtë!

Fillimisht do të shqyrtojmë llogaritjen e kostove të zhvendosjes së mallrave nga qeliza burimore në qeliza-container. Së pari, duhet të përcaktojmë në cilat njësi matëse do të llogarisim kostot e zhvendosjes. Dy opsionet më të dukshme – janë metrat dhe sekondat. Në 'metra të pastër' nuk ka sens të llogariten kostot e zhvendosjes. Do ta tregojmë këtë me një shembull. Le të themi se qeliza ndodhet në katin e parë, qeliza është e largët 30 metra dhe ndodhet në katin e dytë:

• Zhvendosja nga në është më e shtrenjtë se zhvendosja nga në , sepse është më e lehtë të zgjatësh poshtë nga kati i dytë (1.5-2 metra nga toka) sesa të ngresh në të dytin, megjithëse distanca do të kalojë e njëjtë;
• Të zhvendosësh 1 copë mall nga qeliza në do të jetë më e lehtë se të zhvendosësh 10 copë të atij mallit, megjithëse distanca do të kalojë e njëjtë.

Shpenzimet për transferim duhet të merren parasysh në sekonda, pasi kjo mundëson marrjen parasysh të dallimeve në katet dhe sasinë e mallrave të transferuar. Për të vlejtur shpenzimet e transferimit në sekonda, duhet të ndarje operacionin e transferimit në komponentët elementarë dhe të realizohet matja e kohës për përfundimin e çdo komponenti elementar.

Le të thuhet se nga qeliza transferohet copëra mallrash në kontejner . Le të thuhet se është shpejtësia mesatare e lëvizjes së punëtorit në depo, e matur në m/se. Le të thuhet se dhe janë shpejtësitë mesatare për kryerjen një herë të operacioneve të marrjes dhe vendosjes, për një volum mallrash të barabartë me 4 dm3 (vëllimi mesatar që punonjësi e merr një herë gjatë operacioneve në depo). Le të thuhet se dhe lartësitë e qelizave nga të cilat kryhen operacionet e marrjes dhe vendosjes janë përkatësisht. Për shembull, lartësia mesatare e katit të parë (dhe) 1 m, katit të dytë 2 m etj. Atëherë formula për të llogaritur kohën totale të përfundimit të operacionit të transferimit është si në vijim:

Tabela 2 paraqet statistikën e kohrave të përfundimit për çdo operacion elementar, të mbledhur nga punonjësit e depos duke marrë parasysh specifikën e mallrave të ruajtur.

Emri i operacionit	Simboli	Vlera mesatare
Shpejtësia mesatare e lëvizjes së punëtorit në depo		1.5 m/se
Shpejtësia mesatare e kryerjes së një operacioni të vendosjes (për volum mallrash 4 dm3)		2.4 sek

Tabela 2. Koha mesatare e kryerjes së operacioneve në depo

Tani e kemi përcaktuar mënyrën e llogaritjes së shpenzimeve për transferim. Tani duhet të zbulojmë se si llogaritet shpenzimi për zgjedhjen e qelisë-konteiner.Këtu gjithçka është shumë, shumë më e komplikuar se me shpenzimet për transferim, sepse:

• së pari, shpenzimet duhet të jenë në varësi të drejtpërdrejtë nga volumi i qelisë - një volum i njëjtë i mbetjeve, të transferuara nga qelizat dhuruese, është më mirë të vendoset në një kontejner më të vogël sesa në një kontejner të madh, nëse ky volum plotësisht arrin për të dy konteinerët. Kështu, me minimizimin e shpenzimeve totale për zgjedhjen e konteinerëve, ne përpiqemi të kursejmë kapacitetet e depozitimit "të deficituara" në fushën e zonës së përzgjedhjes, për të kryer operacione të mëtejshme të vendosjes së mallrave në qeliza. Në figurën 4 ilustrohen variantet e transferimit të mbetjeve në konteinerë të mëdhenj dhe të vegjël dhe pasojat e këtyre varianteve të transferimit gjatë përfundimit të operacioneve të mëtejshme në depo.
• së dyti, pasi na duhet të minimizojmë përgjithësisht shpenzimet, duke përfshirë si shpenzimet për transferim ashtu edhe shpenzimet për zgjedhjen e konteinerëve, volumin e qelive në metra kub duhet të lidhet disi me sekondat, gjë që nuk është aspak e thjeshtë.

Fig. 4. Variantet e transferimit të mbetjeve në konteinerë me kapacitet të ndryshëm.

Në figurën 4, me ngjyrë të kuqe paraqitet volumi i mbetjeve, i cili nuk mund të përshtatet në kontejner në fazën e dytë të vendosjes së mallrave të mëtejshëm.

Do të ndihmojë lidhja e metrave kub të shpenzimeve për zgjedhjen e konteinerit me sekondat e shpenzimeve për transferim këto kërkesa për zgjidhjet e llogaritura:

• Duhet të sigurohet që mbetjet nga qeliza-dhuruese të transferohen në qeliza-konteiner në çdo rast, nëse kjo redukton numrin e përgjithshëm të qelizave-konteiner në të cilat ndodhet mallri.
• Duhet të ruhet balanci mes volumit të konteinerëve dhe shpenzimeve të kohës për transferim: për shembull, nëse në variantin e ri të zgjidhjes së problemit, krahasuar me variantin e mëparshëm, fitimi në volum është i madh, ndërsa humbja në shpenzimet e kohës është e vogël, atëherë duhet të zgjidhet varianti i ri.

Të fillojmë me kërkesën e fundit. Për të konkretizuar fjalën shumëkuptimëshe "balancë", ne zhvilluam një anketë tek punonjësit e depos për të zbuluar sa vijon. Le të supozojmë se ka një qeli-konteiner me volum , në të cilin është caktuar transferimi i mbetjeve nga qelizat dhuruese dhe koha totale e këtij transferimi është e barabartë me . Le të ketë disa variante alternative për vendosjen e të njëjtës sasi mallrash nga të njëjtat qeliza dhuruese në konteinerë të ndryshëm, ku çdo vendosje ka vlerësimet e saj. , ku < dhe , ku >.

Cila është pyetja: cili është përfitimi minimal në volum i pranueshëm, me një vlerë të caktuar të humbjes në kohë. ? Поясним на примере. Изначально остатки полагалось размещать в контейнер объема 1000 дм3 (1 м3) и время на перемещение составило 70 секунд. Есть вариант размещения остатков в другой контейнер объема 500 дм3 и временем 130 секунд. Вопрос: готовы ли мы тратить еще дополнительные 60 секунд времени кладовщика на выполнение перемещения для того, чтобы сэкономить 500 дм3 свободного объема? По результатам опроса сотрудников склада была составлена следующая диаграмма.

Fig. 5. Diagrami i varshmërisë së kursimit minimal të volumin nga rritja e diferencës në kohën e përfundimit të operacionit.

Kështu, nëse shpenzimet shtesë të kohës janë 40 sekonda, ne jemi të gatshëm t’i shpenzojmë ato vetëm kur përfitimi në volum është të paktën 500 dm3. Pavarësisht nga fakti se në varshmëri ekziston një paksa jo-line, për thjeshtësinë e llogaritjeve të mëtejshme, do të supozojmë se varshmëria mes këtyre sasive është lineare dhe përshkruhet nga një barazim.

Në figurën më poshtë, ne do të shqyrtojmë mënyrat e ndryshme të vendosjes së produkteve në kontenierë.

Fig. 6. Varianti (a): 2 kontenierë, volumi total 400 dm3, koha totale 150 sekonda.

Fig. 6. Varianti (b): 2 kontenierë, volumi total 600 dm3, koha totale 190 sekonda.

Fig. 6. Varianti (c): 1 kontenier, volumi total 400 dm3, koha totale 200 sekonda.

Varianti (a) i zgjedhjes së kontenierëve është më i preferueshëm se varianti fillestar, pasi plotësohet pabarazia: (800-400)/10 >= 150-120 nga e cila ndjekim 40 >= 30. Varianti (b) është më pak i preferueshëm se varianti fillestar, pasi pabarazia nuk bëhet: (800-600)/10 >= 190-150 nga e cila ndjekim 20 >= 40. Por varianti (c) nuk përputhet me këtë logjikë! Le të shqyrtojmë këtë variant më në detaje. Nga ana e parë pabarazia (800-400)/10 >= 200-120, pra pabarazia 40 >= 80 nuk plotësohet, çka tregon se fitimi nga volumi nuk justifikon një humbje kaq të madhe në kohë.

Por nga ana tjetër, në këtë variant (c) ne jo vetëm që zvogëlojmë volumin e mbushur total, por gjithashtu ulim numrin e qelizave të zëna, që është kërkesa e parë nga dy kërkesat e rëndësishme për zgjidhjet e llogaritura të detyrave, të renditura më sipër. E qartë është se për të filluar ndaj këtij kërkese, duhet të shtojmë një konstante pozitive në anën e majtë të pabarazisë. , kështu që duhet të shtojmë një konstante të tillë vetëm kur numri i kontenierëve zvogëlohet. Kujtojmë se — është një variabël që është e barabartë me 1 kur kontenieri është zgjedhur, dhe 0 kur kontenieri nuk është zgjedhur. Le të shënojmë, – seti i kontenierëve në zgjidhjen fillestare dhe – seti i kontenierëve në zgjidhjen e re. Në formë të përgjithshme, pabarazia e re do të duket kështu:

Duke transformuar pabarazinë e lartpërmendur, ne marrim

Duke e pasur këtë, kemi formulën për llogaritjen e kostos totale e një varianti të caktuar të zgjidhjes së detyrës:

Por tani del pyetja: çfarë vlerë duhet të ketë kjo konstante ? Очевидно, что ее значение должно быть достаточно большим, для того, чтобы всегда выполнялось первое требование к решениям задачи. Можно конечно взять значение константы равное 103 или 106, но хотелось бы избежать таких «magic numbers». Если будем рассматривать специфику выполнения складских операций, мы можем вычислить несколько вполне обоснованных числовых оценок величины такой константы.

Le të themi se – distanca maksimale midis qelizave të magazinës në një zonë ABC, e barabartë në rastin tonë me 100 m. Le të themi se – volumi maksimal i qelizës-kontenier në magazinë, i barabartë në rastin tonë me 1000 dm3.

Mënyra e parë për llogaritjen e madhësisë . Le të shqyrtojmë situatën, kur ka 2 kontenierë në katin e parë, në të cilët tashmë fizikisht ndodhet produkti, domethënë, ata vetë janë qeliza-dhënës, ndërsa shpenzimet për zhvendosjen e produktit në të njëjtat qeliza, natyrisht, janë të barabarta me 0. Duhet të gjejmë një vlerë të tillë konstante , për të cilën do të ishte e favorshme gjithmonë të zhvendosnim mbetjet nga konteneri 1 në kontenerin 2. Duke vendosur vlerat dhe në pabarazinë e lartpërmendur, ne marrim:

nga e cila ndjekim

Duke vendosur vlerat e kohës mesatare të ekzekutimit të operacioneve elementare në formulën e lartpërmendur, ne marrim

Mënyra e dytë për llogaritjen e madhësisë . Le të shqyrtojmë situatën, kur ka qeliza-dhënëse nga të cilat planifikohet të zhvendosen produktet në kontenerin 1. Le të shënojmë – distanca nga qeliza-dhënëse në kontenerin 1. Gjithashtu ka një kontenier 2, në të cilin tashmë ka produkte, dhe volumi i tij lejon të përmbajë mbetjet nga të gjitha qelizat. Për thjeshtësi, le të supozojmë se volumi i produktit, që po zhvendoset nga qelizat-dhënëse në kontenierë, është i njëjtë dhe i barabartë me . Duhet të gjejmë një vlerë të tillë konstante , për të cilën vendosja e të gjitha mbetjeve nga qelizat në kontenerin 2 do të ishte gjithmonë më e favorshme se sa vendosja e tyre në mënyra të ndryshme:

Duke transformuar pabarazinë, ne marrim

Për të "forcuar" vlerën e madhësisë , le të pranojmë se = 0. Numri mesatar i qelizave që zakonisht janë të angazhuara në procedurën e shkrirjes së mbetjeve në magazinë është 10. Duke vendosur vlerat e njohura, kemi vlerën e mëposhtme të konstantes

Marrim vlerën më të madhe, të llogaritur për secilin variant, kjo do të jetë dhe vlera e madhësisë për parametrat e caktuar të magazinës. Tani për përfundim, le të shkruajmë formulën për llogaritjen e kostove totale për një zgjidhje të pranueshme :

Tani, pas të gjitha përpjekjeve titanike për transformimin e të dhënave hyrëse, mund të themi se të gjitha të dhënat hyrëse janë transformuar në formën e nevojshme dhe janë gati për t'u përdorur në algoritmin e optimizimit.

Përfundimi

Siç tregojnë praktikat, ngarkesa punuese dhe rëndësia e fazës së përgatitjes dhe transformimit të të dhënave hyrëse për algoritmin shpesh nënvlerësohet. Në këtë artikull ne i kemi kushtuar shumë vëmendje këtij treguesi, për të treguar se vetëm të dhënat hyrëse të përgatitura mirë dhe me mend mund t'i bëjnë zgjidhjet, të llogaritura nga algoritmi, vërtet të vlefshme për klientin. Po, ka pasur shumë formulash përfundimtare, por ju kemi paralajmëruar edhe para kësaj 🙂

Në artikullin e ardhshëm, ne përfundimisht do të arrijmë në atë për të cilin ishin menduar 2 publikimet e mëparshme – algoritmin e optimizimit diskret.

Artikulli është përgatitur nga
Roman Shangin, programatori i departamentit të projekteve,
kompania e Parë Bit, qyteti Chelyabinsk

Burimi: habr.com