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

Në këtë artikull ne do të flasim se si e zgjidhëm problemin e mungesës së vendeve të lira në magazinë dhe mbi zhvillimin e një algoritmi të optimizimit të disktret të zgjidhjes së këtij problemi. Do të flasim për mënyrën si 'ndërtuam' modelin matematikor të detyrës së optimizimit dhe për vështirësitë me të cilat papritur u përballëm 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 e forta identike të formula në nivelin e klasës së 5-të, atëherë mirë se vini nën kat!

Artikulli do të jetë i dobishëm për ata që aplikojnë sistemat WMS, punojnë në industrinë e logjistikës së magazinave ose prodhimit, si dhe për programuesit që janë të interesuar për aplikimet e matematikës në biznes dhe optimizimin e proceseve në ndërmarrje.-sistemat, punon në industrinë e logjistikës së magazinave ose prodhimit, si dhe për programuesit që janë të interesuar për aplikacionet e matematikës në biznes dhe optimizimin e proceseve në ndërmarrje.

Pjesa hyrëse

Ky publikim vazhdon ciklin e artikujve, ku ne ndajnë përvojën tonë të suksesshme në zbatimin e algoritmeve të optimizimit në proceset e magazinimit.

Në artikulli i mëparshëm Përshkruhet specifika e magazinës, ku ne kemi zbatuar sistemat WMS, punojnë në industrinë e logjistikës së magazinave ose prodhimit, si dhe për programuesit që janë të interesuar për aplikimet e matematikës në biznes dhe optimizimin e proceseve në ndërmarrje.-sistemin, si dhe tregohet përse na nevojitej të zgjidhnim detyrën e klasifikimit të grumbujve të mbetjeve të produkteve gjatë zbatimit të sistemat WMS, punojnë në industrinë e logjistikës së magazinave ose prodhimit, si dhe për programuesit që janë të interesuar për aplikimet e matematikës në biznes dhe optimizimin e proceseve në ndërmarrje.-sistemit dhe si e bëmë këtë.

Kur përfunduam së shkruari artikullin mbi algorithmat e optimizimit, rezultoi shumë i gjatë, ndaj materiali i akumuluar vendosëm ta ndajmë në 2 pjesë:

• Në pjesën e parë (ky artikull) ne do të flasim për mënyrën si 'ndërtuam' modelin matematikor të detyrës, dhe për vështirësitë e mëdha me të cilat papritur u përballëm gjatë përpunimit dhe transformimit të të dhënave hyrëse për algoritmin.
• Në pjesën e dytë ne do të shqyrtojmë në detaje realizimin e algoritmit me gjuhën C++, do të zhvillojmë një eksperiment llogaritar dhe do të përmbledhim përvojën që morëm gjatë zbatimit të këtyre 'teknologjive inteligjente' në proceset e biznesit të klientit.

Si ta lexoni artikullin. Nëse keni lexuar artikullin e mëparshëm, mund të kaloni drejtpërdrejt në kapitullin 'Përmbledhja e zgjidhjeve ekzistuese', nëse jo, përshkrimi i problemit të zgjidhur ndodhet në spoilerin më poshtë.

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

Ngushtica në proceset

Në vitin 2018 ne realizuam një projekt për zbatimin e sistemat WMS, punojnë në industrinë e logjistikës së magazinave ose prodhimit, si dhe për programuesit që janë të interesuar për aplikimet e matematikës në biznes dhe optimizimin e proceseve në ndërmarrje.-sistemit në magazinën 'Shtëpia e Tregtisë "LD" në qytetin Çeljabinsk. Zbatova produktin '1C-Logistika: Menaxhimi i magazinës 3' në 20 vende pune: operatorët sistemat WMS, punojnë në industrinë e logjistikës së magazinave ose prodhimit, si dhe për programuesit që janë të interesuar për aplikimet e matematikës në biznes dhe optimizimin e proceseve në ndërmarrje., magazinierë, shoferë ngarkuesish. Depo mesatare rreth 4 mijë m2, numri i qelizave 5000 dhe numri i SKU 4500. Në depo ruhen krane sferike të prodhimit tonë në madhësi të ndryshme nga 1 kg deri në 400 kg. Stoku në depo ruhet sipas grupeve, pasi ka nevojë për përzgjedhjen e mallrave sipas FIFO.

Gjatë projektimit të skemave për automatizimin e proceseve në depo, u përballëm me problemin ekzistues të ruajtjes jo optimale të stokut. Specifika e ruajtjes dhe renditjes së kranëve është e tillë që në një qelizë të ruajtjes individuale mund të ndodhet vetëm një nomenklaturë e një grupi (shih. fig. 1). Produkti arrin në depo çdo ditë dhe çdo ardhje është një grup i veçantë. Përveç kësaj, si rezultat i 1 muaji funksionimi të depos krijohen 30 grupe të veçanta, përkundër faktit se secila duhet të ruhet në një qelizë të veçantë. Malli shpesh përzgjidhet jo në paleta të plota, por njësi, dhe si rezultat, në zonën e përzgjedhjes individuale në shumë qeliza vërehet një pamje e tillë: në një qelizë me volum më shumë se 1m3 ndodhen disa stykë kranesh, të cilat zënë më pak se 5-10% të volumit të qelizës.

Fig. 1. Foto e disa stykëve në një qelizë

Dallohet një përdorim jo optimal i kapaciteteve të depos. Në mënyrë që të paraqesim shkallën e katastrofës, mund të japim numra: mesatarisht, ka nga 100 deri në 300 qeliza të tilla me volum më shumë se 1m3 me "restitucione të minushme" në periudha të ndryshme të funksionimit të depos. Duke qenë se depoja është relativisht e vogël, në sezonet e ngarkesës së depos, ky faktor bëhet "ngushticë" që rëndon shumë proceset e pranuara dhe dërgimit.

Ideja për zgjidhjen e problemit

Lindi ideja: grupet e mbetjeve me datat më të afërta të përzgjidhen në një grup të vetëm dhe këto mbetje me grupin e unifikuar vendosen kompaktet së bashku në një qelizë, ose në disa, nëse vendi në një nuk do të mjaftojë për vendosjen e gjithë numrit të mbetjeve. Një shembull i këtij "tkurrjeje" është ilustruar në fig. 2.

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

Kjo lejon një reduktim të ndjeshëm të hapësirave magazinuese, të cilat do të përdoren për mallrat e reja që do të vendosen. Në raste të mbipopullimit të kapaciteteve magazinuese, një masë e tillë është jashtëzakonisht e nevojshme, përndryshe mund të mos ketë hapësirë të mjaftueshme për të vendosur mallra të rinj, e cila do të çonte në bllokimin e proceseve të vendosjes dhe furnizimit dhe, si pasojë, në bllokimin e pranimeve dhe shkarkimeve. Më parë, para se të implementohej sistemi WMS, kjo operacion bëhej manualisht, e cila ishte e paefektshme, pasi procesi i kërkimit të stockeve të përshtatshme në qeliza ishte mjaft i gjatë. Tani, me implementimin e sistemit WMS, vendosëm ta automatizojmë, ta përshpejtojmë dhe ta bëjmë atë inteligjent.

Procesi i zgjidhjes së një detyre të tillë ndahet në 2 faza:

• në fazën e parë ne gjejmë grupe partiresh të afërta në datë për kompresimin (kjo detyrë është e dedikuar) artikulli i mëparshëm);
• në fazën e dytë ne llogarisim vendosjen më kompakte të stockeve të mallrave në qeliza për çdo grup partie.

Në artikullin aktual ne do të ndalem në fazë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 tashmë ekzistuese në treg sistemat WMS, punojnë në industrinë e logjistikës së magazinave ose prodhimit, si dhe për programuesit që janë të interesuar për aplikimet e matematikës në biznes dhe optimizimin e proceseve në ndërmarrje., në të cilat është realizuar funksionaliteti i ngjeshjes optimale.

Në radhë të parë, është e nevojshme të theksohet produkti "1C: Enterprise 8. WMS Logistika. Menaxhimi i Magazinit 4", i cili i përket dhe shpërndahet nga firma 1C dhe i përket gjeneratës së katërt sistemat WMS, punojnë në industrinë e logjistikës së magazinave ose prodhimit, si dhe për programuesit që janë të interesuar për aplikimet e matematikës në biznes dhe optimizimin e proceseve në ndërmarrje.-sistemeve të zhvilluara nga kompania AXELOT. Në këtë sistem është deklaruar funksionaliteti i ngjeshjes, i cili ka për qëllim të bashkojë stocket e ndryshme të mallrave në një qelize të vetme. Është e rëndësishme të përmendet se funksionaliteti i ngjeshjes në një sistem të tillë përfshin gjithashtu mundësi të tjera, për shembull, rregullimin e vendosjes së mallrave në qeliza sipas klasave të tyre ABC, por ne nuk do të ndalemi në to.

Nëse analizojmë kodin e sistemit "1C: Ndërmarrja 8. WMS Logjistika. Menaxhimi i Magazinës 4" (i cili në këtë pjesë funksionaliteti është i hapur), mund të arrijmë në përfundimin e mëposhtëm. Algoritmi i kompresimit të mbetjeve zbret një logjikë relativisht primitive lineare dhe nuk mund të flitet për një kompresim "optimal". Sigurisht, ai nuk parashikon klasifikimin e grupeve. Disa klientë, të cilët kishin implementuar një sistem të tillë, u ankua mbi rezultatet e planifikimit të kompresimit. Për shembull, shpesh ndodhte që në praktikë, gjatë kompresimit, ndodhte kjo situatë: 100 copë mbetjeve të një produkti nga një kuti planifikoheshin të zhvendoseshin në një kuti tjetër, ku ndodhej 1 copë produkti, kur në fakt do të ishte optimal në aspektin e shpenzimeve të kohës të bëhej përndryshe.

Të njëjtën funksionalitet të kompresimit të mbetjeve të produkteve në kutitë e magazinës e kanë shpallur edhe shumë sisteme të huaja. sistemat WMS, punojnë në industrinë e logjistikës së magazinave ose prodhimit, si dhe për programuesit që janë të interesuar për aplikimet e matematikës në biznes dhe optimizimin e proceseve në ndërmarrje.-sisteme, por, fatkeqësisht, asnjë rishikim real mbi efikasitetin e punës së algoritmeve (kjo është një sekret tregtar), as për më shumë një ide mbi thellësinë e logjikës së tyre (softuer pronar me kod të mbyllur) nuk kemi, 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 që ky problem të formulohet qartë në mënyrë matematikore, dhe këtë do ta bëjmë.

Ka shumë kuti , në të cilat ndodhen mbetjet e një produkti të caktuar. Më pas, këto kuti do t’i quajmë kuti-dhënëse. Do të shënojmë vëllimin e produktit që ndodhet në kuti $.

Është e rëndësishme të thuhet se në procedurën e kompresimit mund të marrë pjesë vetëm një produkt nga një grup, ose disa grupe, të bashkuara paraprakisht në një kluster (lexo artikullin e kaluar), që shpjegohet nga specifika e ruajtjes dhe vendosjes së produkteve. Për produkte të ndryshme ose grupe të ndryshme, duhet të nisë një procedurë e veçantë kompresimi.

Ka shumë kuti , në të cilat mund të vendosen potencialisht mbetjet nga kutitë-dhënëse. Këto kuti do t’i quajmë më pas kuti-kontejner. Këto mund të jenë si kuti të lira në magazinë, ashtu edhe kuti-dhënëse nga shumë. . Gjithmonë shumë është një nëngrup .

Për çdo kuti nga shumë janë të caktuara kufizime mbi kapacitetin , e matë në dm3. Një dm3 përfaqëson një kub me anët 10 cm. Produktet e ruajtura në magazinë janë mjaft të mëdha, prandaj në këtë rast kjo diskriminim është më se e mjaftueshme.

Është caktuar një matrice e distancave më të shkurtra në metra midis çdo çift qelie index dhe i përkasin grupeve dhe përkatësisht.

Le të përfaqësojmë kostot për transferimin e mallrave nga qelia në qeli . Le të përfaqësojmë kostot për zgjedhjen e kontejnerit për të transferuar në të mbetje nga qelia të tjera. Si do llogariten dhe në cilat njësi të matjes do të llogariten vlerat dhe do ta shqyrtojmë më vonë (shihni seksionin përgatitja e të dhënave hyrëse), tani është e mjaftueshme të thuhet se këto sasi do të jenë proporcionale drejtpërdrejt me sasinë dhe përkatësisht.

Le të përfaqësojmë me një variabël që merr vlerën 1, nëse mbetjet nga qelia shtë transferuar në kontejner , dhe 0 në rastin e kundërt. Le të përfaqësojmë me një variabël që merr vlerën 1, nëse kontejneri përmban mbetjet e mallrave, dhe 0 në rastin e kundërt.

Problemi formulon si: është e nevojshme të gjejmë një grup kontejnerësh dhe kështu "prikemi" qelitë-donatorë me qelitë e kontejnerëve, në mënyrë që të minimizojmë funksionin

në kushtet

Në përfundim, gjatë llogaritjes së zgjidhjes së problemit ne mundohemi:

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

Kjo kufizim i fundit do të thotë që ne nuk mund t'i transferojmë mallrat në një kontejner që nuk e kemi zgjedhur, pra nuk kemi "mbajtur kostot" për zgjedhjen e tij. Gjithashtu, ky kufizim do të thotë se sasia e mallrave që transferohen nga qelitë në kontejner nuk duhet të tejkalojë kapacitetin e kontejnerit. Ne do ta kuptojmë zgjidhjen e problemit si një grup kontejnerësh dhe mënyrat e lidhjes së qelive-donator me kontejnerët.

Kjo formulim e problemit të optimizimit nuk është e re dhe është studiuar nga shumë matematicienë që nga fillimi i viteve '80 të shekullit të kaluar. Në literaturën e huaj ka 2 probleme optimizimi me një model matematikor të përshtatshëm: Problem i Pozicionimit të Lehtësisë së Kufizuar nga Burimi i Vetëm dhe Problem i Pozicionimit të Lehtësisë së Kufizuar nga Burime të Shumta (do të flasim më vonë për ndryshimet e detyrave). Është e rëndësishme të themi se në literaturën matematike, formulimi i këtyre dy problemeve të optimizimit formulohet në terma të pozicionimit të ndërmarrjeve në territor, nga këtu dhe emri "Pozita e Ndërmarrjeve". Kryesisht, kjo është një trashëgimi tradicionale, pasi nevoja për zgjidhjen e këtyre problemeve kombinatorike u shfaq fillimisht në sferën e logjistikës, kryesisht në industrinë ushtarake në vitet 50-të të shekullit të kaluar. Në terma të pozicionimit të ndërmarrjeve, këto probleme formulohet si:

• Ka një numër të kufizuar qytetesh, ku potencialisht është e mundur të vendosen ndërmarrjet prodhuese (këtu qytetet-prodhues). Për çdo qytet-prodhues janë caktuar kostot për hapjen e një ndërmarrjeje në të, si dhe kufizimi në kapacitetet prodhuese të ndërmarrjes që hapet në të.
• Ka një numër të kufizuar qytetesh, ku realisht ndodhen klientët (këtu qytetet-klient). Për çdo qytet-klient të tillë është caktuar vëllimi i kërkesës për produktin. Për thjeshtësi, do të supozojmë se produkti që prodhojnë ndërmarrjet dhe konsumojnë klientët është i njëjtë.
• Për çdo çift qytet-prodhues dhe qytet-klient është caktuar madhësia e kostove të transportit për dërgimin e vëllimit të nevojshëm të produktit nga prodhuesi te klienti.

Kërkohet të përcaktohet në cilat qytete të hapen ndërmarrjet dhe si të lidhin klientët me këto ndërmarrje, në mënyrë që:

• Kostot për hapjen e 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 tejkalojë kapacitetet prodhuese të kësaj ndërmarrjeje.

Tani është e rëndësishme të përmendet vetëm një ndryshim në këto dy probleme klasike:

• Problemi i Pozitës së Ndërmarrjeve Kapaciteti një Burimi – klienti furnizohet vetëm nga një ndërmarrje e hapur;
• Problemi i Pozitës së Ndërmarrjeve Kapaciteti Shumë Burimesh – klienti mund të furnizohet nga disa ndërmarrje të hapura në të njëjtën kohë.

Ky ndryshim midis dy problemeve në shikim të parë duket i parëndësishëm, por në të vërtetë, çon në një strukturë të ndryshme kombinatorike të këtyre problemeve dhe, si pasojë, në algoritma të ndryshëm për zgjidhjen e tyre. Diferenca midis problemeve e demonstrohet në figurën më poshtë.

Fig.3. a) Problemi i Pozitës së Ndërmarrjeve Kapaciteti Shumë Burimesh

Fig.3. b) Problemi i Pozitës së Ndërmarrjeve Kapaciteti një Burimi

Të dy problemet -të vështirë, pra nuk ekziston një algoritem i saktë që do të zgjidhte këtë detyrë për kohë polinomiale për madhësinë e të dhënave hyrëse. Me fjalë më të thjeshta, të gjithë algoritmët e saktë për zgjidhjen e detyrës do të funksionojnë për një kohë eksponenciale, megjithatë, ndoshta, më shpejt se kontrollimi i plotë i mundësive nga nisma. Qëllimi është -të vështira, kështu që do të shqyrtojmë vetëm heuristikë të afërt, domethënë algoritme që do të llogarisin vazhdimisht zgjidhje shumë afër optimale dhe do të punojnë mjaft shpejt. Nëse ka interes për këto detyra, këtu mund të gjeni një pasqyrë të mirë në rusisht.

Nëse i referohemi terminologjisë të detyrës sonë për kompresionin optimal të mallrave në seksione, atëherë:

• city-clients – janë seksione-dhuruese me mbetjet e mallrave,
• city-producers – janë seksione-kontejnerë , në të cilat parashikohet të vendosen mbetjet nga seksione të tjerë,
• kostot e transportit – janë kostot e kohës të magazinierit për lëvizjen e vëllimit të mallrave nga seksioni-dhuruese në seksionin-kontejner ;
• kostot e hapjes së ndërmarrjes – janë kostot për zgjedhjen e konteinerit , të barabarta me vëllimin e seksionit-konteiner , të shumëzuara me një koeficient të caktuar të kursimit të hapësirave të lira (vlera e koeficientit gjithmonë > 1) (shih seksionin përgatitja e të dhënave hyrëse).

Pas krijimit të analogjisë me detyrat klasike të njohura, është e nevojshme të përgjigjemi në një pyetje të rëndësishme, nga e cila varet zgjedhja e arkitekturës së algoritmit të zgjidhjes: transferimi i mbetjeve nga seksioni-dhuruese është i mundshëm vetëm në një dhe vetëm një konteiner (Single-Source), ose është e mundur të transferohen mbetje në disa seksione-kontejnerë (Multi-Source)?

Është e rëndësishme të theksohet se në praktikë, të dy format e detyrës ekzistojnë. Do të paraqesim të gjitha 'për' dhe 'kundër' për çdo format të tillë më poshtë:

Tabela 1. Avantazhet dhe disavantazhet e varianteve Burim i vetëm dhe Burim shumëfishe.

Duke marrë parasysh se numri i avantazheve të variantit Burim i vetëm është më i madh, dhe gjithashtu duke marrë parasysh faktin se sa më e vogël të jetë sasia e mbetur në qelitë donatore, aq më i vogël është ndryshimi në shkallë të kompaktësisë së kompresimit të llogaritur sipas të dy varianteve të problemit, zgjedhja jonë ra në variantin Burim i vetëm.

Duhet thënë se zgjidhja e variantit Burim shumëfishe gjithashtu ka vendin e saj. Ekzistojnë një numër të madh algoritmesh efikas për ta zgjidhur atë, shumica prej të cilëve reduktohen në zgjidhjen e disa problemeve të transportit. Gjithashtu ka jo vetëm algoritme efikase, por edhe elegante, për shembull, këtu.

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

Para se të filloni me analizën dhe zhvillimin e algoritmit për zgjidhjen e problemit, është e nevojshme të përcaktoni se cilat të dhëna dhe në çfarë forme do t'i japim atij në hyrje. Me sasi të mbetjeve të produkteve në qelitë donatore dhe kapacitetin e qelive-container, nuk ka probleme, pasi kjo është triviale – këto sasi do të maten në m3, por me kostot për përdorimin e qelisë-container dhe matricën e kostove për lëvizjen, nuk është gjithçka kaq e thjeshtë!

Fillimisht le të shqyrtojmë llogaritjen kostos për lëvizjen e mallrave nga qelia-dhuruese në qelinë-kontejner. E para duhet të përcaktojmë se në cilat njësi matjeje do të llogarisim kostot e lëvizjes. Dy opsionet më të dukshme janë metrat dhe sekondat. Në "metra" të pastër, llogaritja e kostove të lëvizjes nuk ka kuptim. Do ta ilustruar këtë me një shembull. Le të themi se qelia është e vendosur në katin e parë, qelia është në një distancë prej 30 metrash dhe ndodhet në katin e dytë:

• Lëvizja nga në është më e shtrenjtë se lëvizja nga në , pasi që zbritja nga kati i dytë (1,5-2 metra nga toka) është më e lehtë se ngritja në të dytin, edhe pse distanca do të jetë e njëjtë;
• Të zhvendosësh 1 copë mall nga qelia në do të jetë më e lehtë se sa të zhvendosësh 10 copë të së njëjtës mall, edhe pse distanca do të jetë e njëjtë.

Kostot për lëvizje është më mirë të llogariten në sekonda, pasi kjo lejon të merret parasysh ndryshimi në katet dhe ndryshimi në sasinë e mallrave që po lëvizin. Për të llogaritur kostot e lëvizjes në sekonda, ne duhet të ndajmë operacionin e lëvizjes në përbërës elementarë dhe të masim kohën e realizimit të secilit përbërës elementar.

Le të themi se nga qelia po lëvizet copë mall në konteiner . Le t'i themi – shpejtësia mesatare e lëvizjes së punonjësit në depo, e matur në m/sec. Le t'i themi dhe – shpejtësitë mesatare për realizimin e operacioneve të marrjes dhe vendosjes përkatësisht për një vëllim të mallrave që është 4 dm3 (vëllimi mesatar që merr një punonjës në depot kur kryen operacionet). Le t'i themi dhe lartësitë e qelive nga të cilat realizohen operacionet e marrjes dhe vendosjes përkatësisht. Për shembull, lartësia mesatare e katit të parë (toka) është 1 m, kati i dytë 2 m etj. Atëherë formula për llogaritjen e kohës totale për realizimin e operacionit të lëvizjes është si vijon:

Në tabelën 2 jepet statistika e kohës së realizimit të çdo operacioni elementar, e mbledhur nga punonjësit e depot duke marrë parasysh specifikën e mallrave të ruajtura.

Emri i operacionit	Simboli	Vlera mesatare
Shpejtësia mesatare e lëvizjes së punonjësit në depo		1,5 m/sec
Shpejtësia mesatare për realizimin e një operacioni vendosje (për vëllimin e mallrave 4 dm3)		2,4 sekondë

Tabela 2. Koha mesatare për realizimin e operacioneve në depo

Kemi vendosur për metodën e llogaritjes së kostove të lëvizjes. Tani është e nevojshme të kuptojmë si të llogarisim kostot për zgjedhjen e qelisë-kontejnerKëtu është shumë më e komplikuar se sa kostot e zhvendosjes, pasi:

• së pari, kostot duhet të jenë në varësi të drejtpërdrejtë nga volumi i qelizave – të njëjtin volum të mbetjeve, që zhvendosen nga qelizat-donore, është më mirë ta vendosni në një kontejner më të vogël sesa në një kontejner të madh, me kusht që ky volum të futet plotësisht në të dy kontejnerët. Kështu, duke minimizuar kostot totale për zgjedhjen e kontejnerëve, ne kërkojmë të kursim fuqitë e depozitimit "me deficit" në zonën e ndarjes, për të realizuar operacione të mëtejshme të vendosjes së mallrave në qeliza. Në figurën 4 demonstrohen variantet e zhvendosjes së mbetjeve në kontejnerë të mëdhenj dhe të vegjël dhe pasojat e këtyre varianteve të zhvendosjes gjatë realizimit të operacioneve të mëtejshme në depo.
• së dyti, pasi në zgjidhjen e detyrës fillestare na nevojitet të minimizojmë pikërisht kostot totale, që është shuma e kostove të zhvendosjes dhe kostove për zgjedhjen e kontejnerëve, volumi i qelizave në metra kub duhet të lidhet ndonjëherë me sekondat, gjë që nuk është aspak e thjeshtë.

Fig. 4. Variantet e zhvendosjes së mbetjeve në kontejnerë me kapacitet të ndryshëm.

Në figurën 4, në ngjyrë të kuqe është paraqitur volumi i mbetjeve që nuk përputhet më në kontejner në fazën e dytë të vendosjes së mallrave të mëtejshme.

Do të ndihmojë të lidhim metrat kub të kostove për zgjedhjen e kontejnerit me sekondat e kostove për zhvendosje kërkesat e mëposhtme për zgjidhjet e llogaritura të detyrës:

• Është e nevojshme që mbetjet nga qeliza-donore të zhvendosen në qeliza-kontejner gjithmonë, nëse kjo zvogëlon numrin total të qelizave-kontejner ku ndodhen produktet.
• Duhet të respektohet balanca midis volumin e kontejnerëve dhe kostot e kohës për zhvendosje: për shembull, nëse në variantin e ri të zgjidhjes së detyrës krahasuar me variantin e mëparshëm, fitimi në volum është i madh, ndërsa humbja në kostot e kohës është e vogël, atëherë duhet të zgjidhet varianti i ri.

Le të fillojmë me kërkesën e fundit. Për të përcaktuar fjalën shumëkuptimshmëria "balancë" ne kryem një pyetje për punonjësit e depot me qëllim të zbulojmë si vijon. Le të kemi një qeli-kontejner me volum , në të cilën është caktuar zhvendosja e mbetjeve të mallrave nga qelizat-donore dhe koha totale e këtij zhvendosjeje është e barabartë me . Le të ketë disa varianta alternative për vendosjen e të njëjtit numër produktesh nga të njëjtat qeliza donatore në kontejnerë të tjerë, ku çdo vendosje ka vlerësimet e saj. index < dhe index >.

Shqetësimi është: çfarë është fitimi minimal në volum që pranohet, për një humbje të caktuar në kohë. ? Поясним на примере. Изначально остатки полагалось размещать в контейнер объема 1000 дм3 (1 м3) и время на перемещение составило 70 секунд. Есть вариант размещения остатков в другой контейнер объема 500 дм3 и временем 130 секунд. Вопрос: готовы ли мы тратить еще дополнительные 60 секунд времени кладовщика на выполнение перемещения для того, чтобы сэкономить 500 дм3 свободного объема? По результатам опроса сотрудников склада была составлена следующая диаграмма.

Fig. 5. Diagrami i varshmërisë së kursimit minimal të pranueshëm të volumit nga rritja e diferencës në kohën e realizimit të operacionit.

Pra, nëse kostot shtesë në kohë janë 40 sekonda, ne jemi të gatshëm t'i shpenzojmë ato vetëm kur fitimi në volum është të paktën 500 dm³. Megjithëse ka një jo-linearitet të vogël në varshmëri, për thjeshtësi në llogaritjet e mëtejshme, do të supozojmë se varshmëria midis vlerave është lineare dhe përshkruhet nga një pabarazi.

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

Fig. 6. Opsioni (a): 2 kontejnerë, volume totale 400 dm³, kohe totale 150 sekonda.

Fig. 6. Opsioni (b): 2 kontejnerë, volume totale 600 dm³, kohe totale 190 sekonda.

Fig. 6. Opsioni (c): 1 kontejner, volume totale 400 dm³, kohe totale 200 sekonda.

Opsioni (a) përzgjedhjeje të kontejnerëve është më i preferueshëm se opsioni origjinal, pasi përmbush pabarazinë: (800-400)/10 >= 150-120, nga e cila ndiqet 40 >= 30. Opsioni (b) është më pak i preferueshëm se opsioni origjinal, pasi pabarazia nuk përmbushet: (800-600)/10 >= 190-150, nga e cila ndiqet 20 >= 40. Por opsioni (c) nuk përputhet me këtë logjikë! Le ta shqyrtojmë këtë opsion më në detaje. Nga njëra anë, pabarazia (800-400)/10 >= 200-120, kështu që pabarazia 40 >= 80 nuk përmbushet, që tregon se fitimi në volum nuk vlejnë një humbje kaq të madhe në kohë.

Por nga ana tjetër, në këtë variant (c) ne jo vetëm se reduktojmë volumet totale të zënie, por gjithashtu zvogëlojmë 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ë problemeve të përmendura më sipër. Sigurisht, për të filluar përmbushjen e këtij kërkese, është e nevojshme të shtojmë një konstantë pozitive në anën e majtë të pabarazisë. , e cila duhet të shtohet vetëm kur numri i kontejnerëve zvogëlohet. Kujtojmë se — është një variabël, i barabartë me 1, kur kontejneri është zgjedhur, dhe 0 kur kontejneri nuk është zgjedhur. Do ta shënojmë, – një numër kontejnerësh në zgjidhjen fillestare dhe – një numër kontejnerësh në zgjidhjen e re. Në formatin e përgjithshëm, pabarazia e re do të duket kështu:

Duke e transformuar pabarazinë më lart, marrim

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

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

Le të themi – distanca maksimale midis qelizave të depozitës në një zonë ABC, e barabartë në rastin tonë me 100 m. Le të themi – vëllimi maksimale i qelizës-kontejner në depo, e barabartë në rastin tonë me 1000 dm3.

Metoda e parë për llogaritjen e madhësisë . Le të shqyrtojmë situatën ku ka 2 kontejnerë në katin e parë, në të cilët tashmë ndodhet fizikisht mall, pra ato vetë janë qeliza-dhurues, dhe shpenzimet për zhvendosjen e mallrave në këto qeliza, natyrisht që janë 0. Duhet të gjejmë një vlerë të tillë konstante , për të cilën do të ishte e leverdishme gjithmonë të zhvendosësh mbetjet nga kontejneri 1 në kontejnerin 2. Duke futur vlerat dhe në pabarazinë e përmendur më lart, marrim:

nga e cila pason

Duke futur vlerat e kohës mesatare të realizimit të operacioneve elementare në formulën më lart marrim

Metoda e dytë për llogaritjen e madhësisë . Le të shqyrtojmë situatën ku ka qeliza-dhuruese nga të cilat planifikohet të zhvendosen mallrat në kontejnerin 1. Le të shënojmë – distanca nga qeliza-dhuruese në kontejnerin 1. Ka gjithashtu një kontejner 2, në të cilin tashmë ka mallra, dhe vëllimi i të cilit lejon të akomodojë mbetjet nga të gjitha qelizat. Për lehtësi, le të supozojmë se vëllimi i mallrave të zhvendosura nga qelizat-dhuruese në kontejnerë ë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ë kontejnerin 2 do të ishte gjithmonë më e leverdisshme se sa vendosja e tyre në kontejnerë të ndryshëm:

Duke transformuar pabarazinë marrim

Për të "forcuar" vlerën e madhësisë , pranojmë se = 0. Numri mesatar i qelizave që zakonisht përfshihen në procedurën e kompresimit të mbetjeve në depo është 10. Duke futur vlerat e njohura, kemi mënyrën e mëposhtme të konstantes

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

Tani tani, pas të gjitha përpjekjeve titanike për transformimin e të dhënave hyrëse, tani mund të themi se të gjitha të dhënat janë përpunuar në formatin e nevojshëm dhe janë të gatshme për t'u përdorur në algoritmin e optimizimit.

Përfundim

Siç tregon praktika, puna 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 kushtuam shumë vëmendje kësaj faze, për të treguar se vetëm të dhënat hyrëse të përgatitura me cilësi dhe arsyeshëm mund të bëjnë vendimet, të llogaritura nga algoritmi, të jenë vërtet të vlefshme për klientin. Po, kishte shumë përfundime formulash, por ju paralajmëruam që më parë 🙂

Në artikullin e ardhshëm, ne përfundimisht do të arrijmë në atë që ishte qëllimi i dy publikimeve të mëparshme – algoritmin e optimizimit diskret.

Artikulli është përgatitur nga
Roman Shangin, programues në departamentin e projekteve,
kompania Parimi Bit, qyteti Çeljabinsk

Burimi: habr.com