U ovom članku ćemo vam reći kako smo riješili problem nedostatka slobodnih ćelija u skladištu i razvoj diskretnog optimizacijskog algoritma za rješavanje takvog problema. Razgovarajmo o tome kako smo “izgradili” matematički model optimizacijskog problema te o poteškoćama na koje smo neočekivano naišli prilikom obrade ulaznih podataka za algoritam.
Ako vas zanimaju primjene matematike u poslovanju i ne bojite se krutih transformacija identiteta formula na razini 5. razreda, onda dobrodošli u Cat!
Članak će biti koristan onima koji provode WMS-sustava, radi u skladišnoj ili proizvodnoj logističkoj industriji, kao i programerima koje zanima primjena matematike u poslovanju i optimizacija procesa u poduzeću.
Uvodni dio
Ovom publikacijom nastavljamo seriju članaka u kojima dijelimo naše uspješno iskustvo u implementaciji optimizacijskih algoritama u skladišnim procesima.
В opisuje specifičnosti skladišta gdje smo implementirali WMS-sustava, a također objašnjava zašto smo morali riješiti problem klasteriranja serija preostale robe tijekom implementacije WMS-sustava i kako smo to učinili.
Kada smo završili s pisanjem članka o optimizacijskim algoritmima, pokazalo se da je jako velik, pa smo odlučili podijeliti prikupljeni materijal u 2 dijela:
- U prvom dijelu (ovaj članak) govorit ćemo o tome kako smo “izgradili” matematički model problema, te o velikim poteškoćama na koje smo neočekivano naišli prilikom obrade i transformacije ulaznih podataka za algoritam.
- U drugom dijelu ćemo detaljno razmotriti implementaciju algoritma u jeziku C + +, provest ćemo računalni eksperiment i rezimirati iskustva koja smo stekli tijekom implementacije takvih „inteligentnih tehnologija“ u poslovne procese korisnika.
Kako čitati članak. Ako ste pročitali prethodni članak, onda možete odmah prijeći na poglavlje “Pregled postojećih rješenja”, ako niste, onda je opis problema koji se rješava u spojleru ispod.
Opis problema koji se rješava u skladištu kupca
Usko grlo u procesima
U 2018. godini završili smo projekt za realizaciju WMS-sustavi u skladištu “Trading House “LD” u Čeljabinsku. Implementirali smo proizvod “1C-Logistika: Warehouse Management 3” za 20 radnih mjesta: operateri WMS, skladištari, viličari. Prosječna površina skladišta je oko 4 tisuće m2, broj ćelija je 5000, a broj SKU-ova 4500. U skladištu se nalaze kuglasti ventili vlastite proizvodnje različitih veličina od 1 kg do 400 kg. Zalihe u skladištu se pohranjuju u serijama, jer postoji potreba za selekcijom robe prema FIFO.
Tijekom projektiranja shema automatizacije skladišnih procesa suočili smo se s postojećim problemom neoptimalnog skladištenja zaliha. Specifičnosti skladištenja i postavljanja dizalica su takve da jedna jedinična skladišna ćelija može sadržavati samo artikle iz jedne serije (vidi sliku 1). Proizvodi svakodnevno stižu u skladište i svaki dolazak je posebna serija. Ukupno, kao rezultat 1 mjeseca rada skladišta, stvoreno je 30 zasebnih serija, unatoč činjenici da bi svaka trebala biti pohranjena u zasebnoj ćeliji. Proizvodi se često biraju ne u cijelim paletama, već u komadima, i kao rezultat toga, u zoni odabira komada u mnogim ćelijama opaža se sljedeća slika: u ćeliji s volumenom većim od 1 m3 nalazi se nekoliko komada dizalica koje zauzimaju manje od 5-10% volumena stanice.
Slika 1. Fotografija nekoliko komada u ćeliji
Jasno je da se skladišni kapacitet ne koristi optimalno. Da zamislim razmjere katastrofe, mogu dati brojke: u prosjeku postoji od 1 do 3 ćelija takvih ćelija s volumenom većim od 100 m300 s "minimalnim" bilancama tijekom različitih razdoblja rada skladišta. Budući da je skladište relativno malo, tijekom sezona velikih skladišnih gužvi ovaj faktor postaje „usko grlo“ i uvelike usporava skladišne procese preuzimanja i otpreme.
Ideja za rješenje problema
Pojavila se ideja: serije ostataka s najbližim datumima svesti na jednu jedinu seriju, a takve ostatke s jedinstvenom serijom staviti kompaktno zajedno u jednu ćeliju, ili u nekoliko, ako u jednoj nema dovoljno mjesta za smještaj cjelokupna količina ostataka. Primjer takve "kompresije" prikazan je na slici 2.
sl.2. Shema za sabijanje ostataka u stanicama
To vam omogućuje značajno smanjenje zauzetog skladišnog prostora koji će se koristiti za plasiranje nove robe. U situaciji kada je skladišni kapacitet preopterećen, takva je mjera iznimno potrebna, inače jednostavno ne može biti dovoljno slobodnog prostora za smještaj nove robe, što će dovesti do zaustavljanja skladišnih procesa plasmana i nadopunjavanja i, kao posljedica toga, do zaustavljanja u prihvatu i otpremi. Ranije, prije implementacije WMS sustava, takva se operacija izvodila ručno, što je bilo neučinkovito, budući da je proces traženja odgovarajućih ravnoteža u ćelijama bio prilično dug. Sada, uvođenjem WMS sustava, odlučili smo automatizirati proces, ubrzati ga i učiniti ga inteligentnim.
Proces rješavanja takvog problema podijeljen je u 2 faze:
- u prvoj fazi nalazimo grupe serija bliskih datuma za kompresiju (posvećene ovom zadatku );
- u drugoj fazi, za svaku grupu serija izračunavamo najkompaktniji smještaj preostale robe u ćelijama.
U ovom članku usredotočit ćemo se na drugu fazu algoritma.
Pregled postojećih rješenja
Prije nego prijeđemo na opis algoritama koje smo razvili, vrijedi napraviti kratak pregled sustava koji već postoje na tržištu WMS, koji implementiraju sličnu optimalnu funkcionalnost kompresije.
Prije svega, potrebno je napomenuti proizvod “1C: Enterprise 8. WMS Logistics. Warehouse management 4", koji je u vlasništvu i replici 1C i pripada četvrtoj generaciji WMS-sustavi koje je razvio AXELOT. Ovaj sustav zahtijeva funkcionalnost kompresije, koja je dizajnirana za spajanje različitih ostataka proizvoda u jednu zajedničku ćeliju. Vrijedno je spomenuti da funkcionalnost kompresije u takvom sustavu uključuje i druge mogućnosti, na primjer, korekciju smještaja robe u ćelijama prema njihovim ABC klasama, ali na njima se nećemo zadržavati.
Ako analizirate kod sustava 1C: Enterprise 8. WMS Logistics. Warehouse management 4" (koji je otvoren u ovom dijelu funkcionalnosti), možemo zaključiti sljedeće. Algoritam rezidualne kompresije implementira prilično primitivnu linearnu logiku i ne može biti govora ni o kakvoj "optimalnoj" kompresiji. Naravno, ne predviđa grupiranje stranaka. Nekoliko klijenata koji su implementirali takav sustav žalili su se na rezultate planiranja kompresije. Na primjer, često se u praksi tijekom kompresije dogodila sljedeća situacija: 100 kom. Predviđeno je premještanje preostale robe iz jedne ćelije u drugu ćeliju, gdje se nalazi 1 kom. robu, iako je optimalno sa stajališta utroška vremena učiniti suprotno.
Također, funkcionalnost sažimanja preostale robe u ćelijama deklarirana je u mnogim stranim zemljama. WMS-sustava, ali, nažalost, nemamo stvarne povratne informacije o učinkovitosti algoritama (ovo je poslovna tajna), a još manje ideju o dubini njihove logike (vlasnički softver zatvorenog koda), pa ne možemo suditi.
Potraga za matematičkim modelom problema
Da bi se dizajnirali kvalitetni algoritmi za rješavanje problema, potrebno je prvo jasno matematički formulirati taj problem, što ćemo i učiniti.
Postoji mnogo stanica , koji sadrže ostatke neke robe. U nastavku ćemo takve stanice nazivati donorskim stanicama. Označimo volumen robe u ćeliji $.
Važno je napomenuti da samo jedan proizvod jedne serije ili više serija prethodno spojenih u klaster (čitaj: ), što je zbog specifičnosti skladištenja i skladištenja robe. Različiti proizvodi ili različiti grupni klasteri trebali bi pokrenuti vlastiti zasebni postupak kompresije.
Postoji mnogo stanica , u koje se potencijalno mogu smjestiti ostaci iz donorskih stanica. Takve ćemo ćelije dalje zvati kontejnerske ćelije. To mogu biti ili slobodne stanice u skladištu ili stanice donora iz raznih vrsta . Uvijek dosta je podskup .
Za svaku ćeliju od mnogih Postavljena su ograničenja kapaciteta , mjereno u dm3. Jedan dm3 je kocka sa stranicama 10 cm.Proizvodi koji se nalaze u skladištu su prilično veliki, pa je u ovom slučaju takva diskretizacija sasvim dovoljna.
Zadana je matrica najkraćih udaljenosti u metrima između svakog para ćelija Gdje и pripadaju skupovima и respektivno.
Označimo “troškovi” premještanja robe iz ćelije u ćeliju . Označimo “troškovi” odabira kontejnera da u njega premjesti ostatke iz drugih stanica. Kako točno i u kojim mjernim jedinicama će se izračunati vrijednosti и razmotrit ćemo dalje (vidi odjeljak priprema ulaznih podataka), za sada je dovoljno reći da će takve vrijednosti biti izravno proporcionalne vrijednostima и respektivno.
Označimo sa varijabla koja ima vrijednost 1 ako je ostatak iz ćelije premješten u kontejner , a inače 0. Označimo sa varijabla koja uzima vrijednost 1 ako je spremnik sadrži preostalu robu, a 0 inače.
Zadatak je naveden na sljedeći način: morate pronaći toliko kontejnera i tako "pričvrstiti" donorske stanice na stanice spremnika kako bi se smanjila funkcija
pod ograničenjima
Ukupno, pri izračunavanju rješenja problema nastojimo:
- prvo, za uštedu kapaciteta za pohranu;
- drugo, uštedjeti vrijeme skladištara.
Posljednje ograničenje znači da ne možemo premjestiti robu u spremnik koji nismo odabrali, te stoga nismo “složili troškove” za njegov odabir. Ovo ograničenje također znači da količina robe koja se premješta iz ćelija u spremnik ne smije premašiti kapacitet spremnika. Pod rješavanjem problema podrazumijevamo skup spremnika i metode za pričvršćivanje donorskih stanica na spremnike.
Ova formulacija optimizacijskog problema nije nova, a proučavali su je mnogi matematičari od ranih 80-ih godina prošlog stoljeća. U stranoj literaturi postoje 2 optimizacijska problema s odgovarajućim matematičkim modelom: и (kasnije ćemo govoriti o razlikama u zadacima). Vrijedno je reći da je u matematičkoj literaturi formulacija ova dva optimizacijska problema formulirana u smislu lokacije poduzeća na terenu, otuda i naziv "Facility Location". Uglavnom je to danak tradiciji, budući da je prvi put potreba rješavanja ovakvih kombinatoričkih problema došla iz područja logistike, ponajviše iz vojno-industrijskog sektora 50-ih godina prošlog stoljeća. Što se tiče lokacije poduzeća, takvi su zadaci formulirani na sljedeći način:
- Postoji konačan broj gradova u kojima je potencijalno moguće locirati proizvodna poduzeća (u daljnjem tekstu proizvodni gradovi). Za svaki proizvodni grad navedeni su troškovi otvaranja poduzeća u njemu, kao i ograničenje proizvodnog kapaciteta poduzeća koje se u njemu otvara.
- Postoji konačan skup gradova u kojima se klijenti zapravo nalaze (u daljnjem tekstu gradovi klijenti). Za svaki takav grad klijenta naveden je opseg potražnje za proizvodima. Radi jednostavnosti, pretpostavit ćemo da postoji samo jedan proizvod koji proizvode poduzeća, a konzumiraju kupci.
- Za svaki par grad-proizvođač i grad-naručitelj navedena je vrijednost transportnih troškova za isporuku potrebne količine proizvoda od proizvođača do naručitelja.
Morate pronaći u kojim gradovima otvoriti tvrtke i kako povezati klijente s takvim tvrtkama kako biste:
- Ukupni troškovi otvaranja poduzeća i troškovi transporta bili su minimalni;
- Opseg potražnje od strane kupaca dodijeljen bilo kojem otvorenom poduzeću nije premašio proizvodni kapacitet tog poduzeća.
Sada je vrijedno spomenuti jedinu razliku u ova dva klasična problema:
- Problem lokacije pogona s kapacitetom jednog izvora – klijent se opskrbljuje iz samo jednog otvorenog pogona;
- Problem lokacije višeizvornog kapacitiranog objekta – klijent se može opskrbljivati iz nekoliko otvorenih objekata istovremeno.
Takva razlika između ta dva problema je na prvi pogled beznačajna, ali, zapravo, dovodi do potpuno različite kombinatorne strukture takvih problema i, posljedično, do potpuno različitih algoritama za njihovo rješavanje. Razlike između zadataka prikazane su na slici ispod.
sl.3. a) Problem lokacije postrojenja s kapacitetom za više izvora
sl.3. b) Problem lokacije postrojenja s kapacitetom jednog izvora
Oba zadatka -teško, odnosno ne postoji egzaktan algoritam koji bi riješio takav problem u vremenskom polinomu veličine ulaznog podatka. Jednostavnije rečeno, svi egzaktni algoritmi za rješavanje problema radit će u eksponencijalnom vremenu, iako možda brže od potpunog traženja opcija. Budući da je zadatak -teško, tada ćemo razmatrati samo aproksimativne heuristike, odnosno algoritme koji će konzistentno izračunavati rješenja vrlo blizu optimalnim i raditi dosta brzo. Ako ste zainteresirani za takav zadatak, ovdje možete pronaći dobar pregled na ruskom.
Ako prijeđemo na terminologiju našeg problema optimalne kompresije robe u ćelijama, tada:
- gradovi klijenti su donorske stanice sa preostalom robom,
- proizvodni gradovi – kontejnerske ćelije , u koje se trebaju smjestiti ostaci iz drugih ćelija,
- troškovi prijevoza – troškovi vremena skladištar za premještanje količine robe iz donorske ćelije u ćeliju spremnika ;
- troškovi otvaranja obrta - troškovi odabira kontejnera , jednak volumenu ćelije spremnika , pomnožen s određenim koeficijentom za spremanje slobodnih volumena (vrijednost koeficijenta je uvijek > 1) (pogledajte odjeljak priprema ulaznih podataka).
Nakon što je povučena analogija s poznatim klasičnim rješenjima problema, potrebno je odgovoriti na važno pitanje o kojem ovisi izbor arhitekture algoritma rješenja: premještanje ostataka iz stanice donora moguće je samo u jednu i samo jedan spremnik (Single-Source) ili je moguće premjestiti ostatke u nekoliko ćelija spremnika (Multi-Source)?
Vrijedno je napomenuti da se u praksi pojavljuju obje formulacije problema. U nastavku predstavljamo sve prednosti i nedostatke svake takve postavke:
| Problemska varijanta | Prednosti opcije | Nedostaci opcije |
|---|---|---|
| Jedan izvor | Operacije kretanja robe izračunate pomoću ove varijante problema:
|
|
| Više izvora | Kompresije izračunate pomoću ove verzije problema obično su 10-15% kompaktnije u usporedbi s kompresijama izračunatim pomoću opcije "Jedan izvor". Ali također primjećujemo da što je manji broj ostataka u donorskim stanicama, to je manja razlika u kompaktnosti | Operacije kretanja robe izračunate pomoću ove varijante problema:
|
Tablica 1. Prednosti i mane opcija s jednim izvorom i više izvora.
Budući da Single-Source opcija ima više prednosti, a također uzimajući u obzir činjenicu da što je manji broj ostataka u donorskim stanicama, to je manja razlika u stupnju kompaktnosti kompresije izračunata za obje varijante problema, naš izbor je pao na opciju Single-Source. Izvor.
Vrijedno je reći da se također odvija rješenje opcije Multi-Source. Postoji veliki broj učinkovitih algoritama za njegovo rješavanje, od kojih se većina svodi na rješavanje niza prometnih problema. Također postoje ne samo učinkoviti algoritmi, već i elegantni, npr.
Priprema ulaznih podataka
Prije nego počnemo analizirati i razvijati algoritam za rješavanje problema, potrebno je odlučiti koje ćemo podatke i u kojem obliku unositi kao ulaz. Nema problema s volumenom preostale robe u donorskim ćelijama i kapacitetom kontejnerskih ćelija, budući da je to trivijalno - takve količine će se mjeriti u m3, ali s troškovima korištenja kontejnerske ćelije i matricom pokretnih troškova, nije sve je tako jednostavno!
Pogledajmo prvo izračun troškovi kretanja robe od stanice donora do stanice spremnika. Prije svega potrebno je odlučiti u kojim mjernim jedinicama ćemo obračunavati troškove kretanja. Dvije najočitije opcije su metri i sekunde. Nema smisla računati putne troškove u "čistim" metrima. Pokažimo to primjerom. Neka stanica nalazi se na prvom katu, ćelija udaljen 30 metara i smješten na drugom nivou:
- Krećući se iz в skuplje od selidbe iz в , budući da je spuštanje s druge razine (1,5-2 metra od poda) lakše nego penjanje na drugu, iako će udaljenost biti ista;
- Pomaknite 1 kom. robu iz ćelije в Bit će lakše nego pomicati 10 komada. isti proizvod, iako će udaljenost biti ista.
Bolje je uzeti u obzir troškove selidbe u sekundi jer vam to omogućuje da uzmete u obzir i razliku u razinama i razliku u količini premještene robe. Da bismo izračunali trošak kretanja u sekundama, moramo rastaviti operaciju kretanja na elementarne komponente i uzeti mjerenja vremena za izvršenje svake elementarne komponente.
Neka iz ćelije kreće se PC. roba u kontejneru ... Neka bude – prosječna brzina kretanja radnika u skladištu, mjerena u m/sek. Neka и – prosječne brzine jednokratnih operacija take and put za volumen robe jednak 4 dm3 (prosječni volumen koji zaposlenik uzima odjednom u skladištu prilikom obavljanja operacija). Neka и visina ćelija iz kojih se izvode operacije take i put. Na primjer, prosječna visina prvog sloja (kata) je 1 m, drugog sloja je 2 m, itd. Tada je formula za izračunavanje ukupnog vremena dovršetka operacije pomicanja Sljedeći:
U tablici 2 prikazana je statistika o vremenu izvršenja svake elementarne operacije koju su prikupili skladišni radnici, uzimajući u obzir specifičnosti skladištene robe.
| naziv operacije | Oznaka | Podlo |
|---|---|---|
| Prosječna brzina kretanja radnika po skladištu | |
1,5 m/s |
| Prosječna brzina jedne operacije za stavljanje (za volumen proizvoda od 4 dm3) | |
2,4 sek |
Tablica 2. Prosječno vrijeme dovršetka skladišnih operacija
Odlučili smo se za način obračuna troškova selidbe. Sada moramo smisliti kako izračunati troškovi odabira kontejnerske ćelije. Ovdje je sve puno, puno kompliciranije nego s troškovima selidbe, jer:
- prvo, troškovi bi trebali izravno ovisiti o volumenu stanice - isti volumen ostataka prenesenih iz donorskih stanica bolje je staviti u spremnik manjeg volumena nego u veliki spremnik, pod uvjetom da takav volumen potpuno stane u oba spremnika. Dakle, minimiziranjem ukupnih troškova odabira spremnika, nastojimo uštedjeti „oskudne“ slobodne skladišne kapacitete u području odabira za obavljanje naknadnih operacija postavljanja robe u ćelije. Slika 4 prikazuje mogućnosti prijenosa ostataka u velike i male spremnike i posljedice tih opcija prijenosa u kasnijim skladišnim operacijama.
- drugo, budući da u rješavanju izvornog problema trebamo minimizirati točno ukupne troškove, a to je zbroj i troškova selidbe i troškova odabira kontejnera, tada volumen ćelije u kubnim metrima treba nekako povezati sa sekundama, što je daleko od trivijalnog.
Riža. 4. Mogućnosti premještanja ostataka u spremnike različitih kapaciteta.
Na slici 4 crvenom bojom prikazan je volumen ostataka koji više ne stane u spremnik u drugoj fazi postavljanja sljedeće robe.
Pomoći će u povezivanju kubičnih metara troškova za odabir kontejnera sa sekundama troškova za premještanje sljedećih zahtjeva za izračunata rješenja problema:
- Neophodno je da se vaga iz donatorske kante u svakom slučaju premjesti u spremnik ako se time smanjuje ukupan broj spremnika u kojima se nalazi proizvod.
- Potrebno je održavati ravnotežu između volumena spremnika i vremena utrošenog na premještanje: npr. ako je u novom rješenju problema u odnosu na prethodno rješenje dobitak u volumenu velik, a gubitak u vremenu mali , tada je potrebno odabrati novu opciju.
Počnimo s posljednjim zahtjevom. Kako bismo razjasnili dvosmislenu riječ "stanje", proveli smo anketu među zaposlenicima skladišta kako bismo saznali sljedeće. Neka postoji ćelija spremnika volumena , kojemu je dodijeljeno kretanje preostale robe iz donorskih stanica, a ukupno vrijeme tog kretanja jednako je . Neka postoji nekoliko alternativnih opcija za stavljanje iste količine robe iz istih donorskih stanica u druge spremnike, gdje svako stavljanje ima vlastite procjene Gdje < и Gdje >.
Postavlja se pitanje: koji je minimalni dobitak u volumenu prihvatljivo, za danu vrijednost gubitka vremena ? Objasnimo na primjeru. Prvotno je posmrtne ostatke trebalo staviti u spremnik zapremine 1000 dm3 (1 m3), a vrijeme prijenosa bilo je 70 sekundi. Postoji mogućnost stavljanja ostataka u drugu posudu zapremine 500 dm3 i vremena 130 sekundi. Pitanje: jesmo li spremni potrošiti dodatnih 60 sekundi vremena skladištara na premještanje robe kako bismo uštedjeli 500 dm3 slobodnog volumena? Na temelju rezultata ankete skladišnih zaposlenika sastavljen je sljedeći dijagram.
Riža. 5. Dijagram ovisnosti minimalno dopuštene uštede volumena o porastu razlike u vremenu rada
Odnosno, ako su dodatni vremenski troškovi 40 sekundi, tada smo ih spremni potrošiti tek kada je dobitak u volumenu najmanje 500 dm3. Unatoč činjenici da postoji mala nelinearnost u ovisnosti, radi jednostavnosti daljnjih izračuna pretpostavit ćemo da je ovisnost između veličina linearna i da je opisana nejednakošću
Na donjoj slici razmatramo sljedeće metode stavljanja robe u kontejnere.
Riža. 6. Opcija (a): 2 spremnika, ukupni volumen 400 dm3, ukupno vrijeme 150 sec.
Riža. 6. Opcija (b): 2 spremnika, ukupni volumen 600 dm3, ukupno vrijeme 190 sec.
Riža. 6. Opcija (c): 1 spremnik, ukupni volumen 400 dm3, ukupno vrijeme 200 sec.
Opcija (a) za odabir spremnika je poželjnija od izvorne opcije, budući da vrijedi nejednakost: (800-400)/10>=150-120, što implicira 40 >= 30. Opcija (b) je manje poželjna od originalne opcija , jer ne vrijedi nejednakost: (800-600)/10>=190-150 što implicira 20 >= 40. Ali opcija (c) se ne uklapa u takvu logiku! Razmotrimo ovu opciju detaljnije. S jedne strane, nejednakost (800-400)/10>=200-120, što znači da nejednakost 40 >= 80 nije zadovoljena, što sugerira da dobitak u volumenu nije vrijedan tako velikog gubitka u vremenu.
Ali s druge strane, u ovoj opciji (c) ne samo da smanjujemo ukupni zauzeti volumen, već također smanjujemo broj zauzetih ćelija, što je prvi od dva važna zahtjeva za izračunljiva rješenja gore navedenih problema. Očito, da bi se ovaj zahtjev počeo ispunjavati, potrebno je lijevoj strani nejednadžbe dodati neku pozitivnu konstantu , a takvu konstantu potrebno je dodati tek kada se smanji broj spremnika. Podsjetimo da je varijabla jednaka 1 kada spremnik odabrano, a 0 kada je spremnik nije odabrano. Označimo – mnogo spremnika u početnoj otopini i – mnogo spremnika u novom rješenju. Općenito, nova nejednakost će izgledati ovako:
Transformirajući gornju nejednakost, dobivamo
Na temelju toga imamo formulu za izračun ukupnog troška neko rješenje problema:
Ali sada se postavlja pitanje: koju bi vrijednost trebala imati takva konstanta? ? Očito, njegova vrijednost mora biti dovoljno velika da uvijek bude ispunjen prvi zahtjev za rješenje problema. Možete, naravno, uzeti vrijednost konstante jednaku 103 ili 106, ali bih želio izbjeći takve "magične brojeve". Ako uzmemo u obzir specifičnosti obavljanja skladišnog poslovanja, možemo izračunati nekoliko dobro utemeljenih numeričkih procjena vrijednosti takve konstante.
pustiti – najveća udaljenost između skladišnih ćelija jedne zone ABC, jednaka u našem slučaju 100 m. Neka – najveći volumen kontejnerske ćelije u skladištu, u našem slučaju jednak 1000 dm3.
Prvi način za izračunavanje vrijednosti . Razmotrimo situaciju u kojoj postoje 2 spremnika na prvom sloju, u kojima je roba već fizički smještena, to jest, oni sami su donorske stanice, a trošak premještanja robe u iste ćelije je prirodno jednak 0. To je potrebno pronaći takvu vrijednost za konstantu , u kojem bi bilo korisno uvijek premještati ostatke iz spremnika 1 u spremnik 2. Zamjena vrijednosti и U gornjoj nejednakosti dobivamo:
iz čega slijedi
Zamjenom vrijednosti prosječnog vremena za izvođenje elementarnih operacija u gornju formulu dobivamo
Drugi način izračunavanja vrijednosti . Razmotrimo situaciju u kojoj postoji donorske stanice iz kojih se planira premjestiti robu u spremnik 1. Označimo – udaljenost od stanice donora u spremnik 1. Postoji i spremnik 2, koji već sadrži robu, a čiji volumen vam omogućuje da primite ostatak svih Stanice. Radi jednostavnosti, pretpostavit ćemo da je volumen robe premješten iz donorskih stanica u spremnike isti i jednak . Potrebno je pronaći takvu vrijednost konstante , u kojem je smještanje svih ostataka iz ćelije u spremnik 2 uvijek bi bilo isplativije nego njihovo stavljanje u različite spremnike:
Transformacijom nejednakosti dobivamo
Da bi se “pojačala” vrijednost količine , pretpostavimo to = 0. Prosječan broj ćelija koje su obično uključene u postupak sažimanja skladišnih stanja je 10. Zamjenom poznatih vrijednosti količina, imamo sljedeću vrijednost konstante
Uzimamo najveću vrijednost izračunatu za svaku opciju, to će biti vrijednost količine za zadane parametre skladišta. Sada, radi cjelovitosti, zapišimo formulu za izračun ukupnih troškova za neko izvedivo rješenje :
Sada, nakon svega titanski napori Transformacijom ulaznih podataka možemo reći da su svi ulazni podaci pretvoreni u željeni oblik i spremni za korištenje u optimizacijskom algoritmu.
Zaključak
Kao što praksa pokazuje, složenost i važnost faze pripreme i transformacije ulaznih podataka za algoritam često se podcjenjuje. U ovom članku smo ovoj fazi posebno posvetili dosta pažnje kako bismo pokazali da samo kvalitetni i inteligentno pripremljeni ulazni podaci mogu učiniti odluke izračunate algoritmom zaista vrijednima za klijenta. Da, bilo je mnogo izvođenja formula, ali upozorili smo vas i prije kata :)
U sljedećem članku ćemo konačno doći do onoga čemu su prethodne 2 objave bile namijenjene - algoritmu diskretne optimizacije.
Pripremio
Roman Shangin, programer odjela projekata,
Tvrtka First Bit, Čeljabinsk
Izvor: www.habr.com