Diskretna matematika za WMS: algoritam kompresije proizvoda u stanicama (dio 1)

U članku ćemo objasniti kako smo rješavali problem nedostatka slobodnih mjesta u skladištu i o razvoju algoritma diskretne optimizacije za rješavanje takvih problema. Objasnit ćemo kako smo 'gradili' matematički model optimizacijskog zadatka i na koje smo se poteškoće neočekivano susreli prilikom obrade ulaznih podataka za algoritam.

Ako vas zanimaju primjene matematike u poslovanju i ne bojite se složenih jednadžbi na razini 5. razreda, dobrodošli ispod!

Članak će biti koristan onima koji implementiraju WMS-sustave, rade u industriji skladišne ili proizvodne logistike, kao i programerima koji su zainteresirani za primjene matematike u poslovanju i optimizaciju procesa u poduzeću.

Uvodni dio

Ova publikacija nastavlja seriju članaka u kojima dijelimo svoje uspješne iskustva u implementaciji algoritama optimizacije u skladišne procese.

U prošlom članku opisuje specifičnosti skladišta u kojem je implementiran WMS-sustav, te objašnjava zašto smo morali rješavati problem klasterizacije serija ostataka proizvoda tijekom implementacije WMS-sustava i kako smo to postigli.

Kada smo završili s pisanjem članka o algoritmima optimizacije, ispostavilo se da je postao vrlo opsežan, stoga smo odlučili podijeliti prikupljeni materijal na 2 dijela:

• U prvom dijelu (ovaj članak) ćemo govoriti o tome kako smo 'gradili' matematički model zadatka i o velikim poteškoćama na koje smo neočekivano naišli prilikom obrade i transformacije ulaznih podataka za algoritam.
• U drugom dijelu detaljno ćemo razmotriti implementaciju algoritma na jeziku C++, provesti računalni eksperiment i sažeti iskustvo stečeno tijekom implementacije takvih 'inteligentnih tehnologija' u poslovne procese klijenta.

Kako čitati članak. Ako ste čitali prethodni članak, možete odmah prijeći na poglavlje 'Pregled postojećih rješenja', ako niste, opis rješavanog problema nalazi se u spoileru ispod.

Opis rješavanog problema u skladištu klijenta

Usko grlo u procesima

U 2018. godini realizirali smo projekt implementacije WMS-sustava u skladištu 'Trgovinski dom 'LD' u gradu Čeljabinsku. Implementirali smo proizvod '1C-Logistika: Upravljanje skladištem 3' na 20 radnih mjesta: operatori WMS, skladištari, vozači viličara. Skladište je srednje veličine, oko 4 tisuće m2, s 5000 sku i 4500 različitih artikala. U skladištu se čuvaju loptasti ventili vlastite proizvodnje različitih veličina od 1 kg do 400 kg. Zalihe se čuvaju prema serijama, jer postoji potreba za izborom roba po FIFO.

Tijekom projektiranja shema automatizacije skladišnih procesa suočili smo se s postojećim problemom suboptimalnog skladištenja zaliha. Specifika skladištenja i slaganja ventila je takva da u jednoj jedinici može biti samo jedan artikl iz jedne serije (vidi sl. 1). Proizvodi dolaze u skladište svaki dan, a svaki dolazak je posebna serija. U prosjeku, nakon mjesec dana rada skladišta stvara se 30 odvojenih serija, pri čemu svaka mora biti pohranjena u vlastitoj jedinici. Roba se često ne bira u cijelim paletama, već po komadima, i kao rezultat, u zoni odabira po komadu u mnogim jedinicama se može primijetiti sljedeća slika: u jedinici volumena više od 1m3 leži nekoliko komada ventila, koji zauzimaju manje od 5-10% volumena jedinice.

Sl. 1. Fotografija nekoliko komada u jedinici

Očigledno je neoptimalkno korištenje skladišnih kapaciteta. Da bi se ilustrirala ozbiljnost problema, mogu navesti brojke: u prosjeku takvih jedinica volumena većim od 1m3 s "mali" zalihama u različitim razdobljima rada skladišta ima između 100 i 300 jedinica. Budući da je skladište relativno malo, tijekom sezona opterećenja ovaj faktor postaje „usko grlo“ koje snažno usporava procese prijema i otpreme.

Ideja za rješenje problema

Pojavila se ideja: serije preostalih zaliha s najbližim datumima okupljati u jednu zajedničku seriju i takve zalihe s unificiranom serijom smjestiti kompaktno zajedno u jednoj jedinici, ili u nekoliko, ako u jednoj ne bude dovoljno mjesta za cjelokupnu količinu preostalog materijala. Primjer takvog "smanjenja" prikazan je na slici 2.

Sl. 2. Shema smanjenja zaliha u jedinicama

To significantly reduce the storage space occupied, which will be used for the new product placement. In a situation of overload in warehouse capacities, such a measure is critically necessary; otherwise, there may simply not be enough free space for placing new products, which will lead to a halt in warehouse placement and supply processes, and consequently, to a halt in receiving and shipping. Previously, before the implementation of the WMS system, this operation was performed manually, which was inefficient, as the process of finding suitable stock in cells was quite lengthy. Now, with the introduction of the WMS system, we decided to automate the process, speed it up, and make it intelligent.

The process of solving such a task is divided into 2 stages:

• in the first stage, we find groups of batches that are close in date for compression (this task is dedicated to prethodni članak);
• in the second stage, we calculate the most compact placement of product stock in the cells for each group of batches.

In the current article, we will focus on the second stage of the algorithm.

Overview of existing solutions

Before moving on to the description of the algorithms we have developed, it is worth conducting a brief overview of the systems already existing in the market WMS, where similar optimal compression functionality is implemented.

First of all, it is necessary to note the product "1C: Enterprise 8. WMS Logistics. Warehouse Management 4", which belongs to and is published by the company 1C and relates to the fourth generation WMS-systems developed by the company AXELOT. This system claims to have compression functionality, which is designed to combine disparate product stocks into a single common cell. It should be noted that the compression functionality in such a system also includes other capabilities, for example, correcting the placement of goods in cells according to their ABC classes, but we will not dwell on them.

Ako analiziramo kod sustava „1C: Poduzeće 8. WMS Logistika. Upravljanje skladištem 4” (koji je u ovom dijelu funkcionalnosti otvoren), možemo zaključiti sljedeće. Algoritam kompresije zaliha implementira prilično primitivnu linarnu logiku i ne može biti govora o bilo kakvoj „optimalnoj” kompresiji. Naravno, ne predviđa klasterizaciju serija. Nekoliko klijenata koji su uveli takav sustav žalilo se na rezultate planiranja kompresije. Primjerice, u praksi se često događalo sljedeće: 100 kom. zaliha proizvoda iz jedne ćelije planira se premjestiti u drugu ćeliju, gdje leži 1 kom. proizvoda, iako bi optimalno s obzirom na troškove vremena bilo obrnuto.

Također, funkcionalnost kompresije zaliha proizvoda u ćelijama najavljena je u mnogim stranim WMS-sustavima, ali nažalost, nemamo ni stvarnih recenzija o učinkovitosti rada algoritama (to je poslovna tajna), a ni predstavu o dubini njihove logike (proprijetarni softver sa zatvorenim kodom), pa ne možemo suditi.

Pretraživanje matematičkog modela zadatka

Da bismo projektirali kvalitetne algoritme za rješavanje zadatka, prvo moramo jasno matematički formulirati taj zadatak, što ćemo i učiniti.

Postoji mnogo ćelija , u kojima se nalaze zalihe nekog proizvoda. Takve ćelije ćemo nazvati ćelijama-donorima. Oznacimo volumen proizvoda koji se nalazi u ćeliji $.

Važno je napomenuti da u postupku kompresije može sudjelovati samo jedan proizvod iz jedne serije, ili nekoliko serija, prethodno spojenih u klaster (čitaj prethodni članak), što je uvjetovano specifičnošću skladištenja i slaganja proizvoda. Za različite proizvode ili različite klastere serija trebala bi se pokrenuti svoja posebna procedura kompresije.

Postoji mnogo ćelija , u koje se mogu potencijalno smjestiti zalihe iz ćelija-donora. Takve ćelije ćemo dalje nazvati ćelijama-kontejnerima. To mogu biti i slobodne ćelije u skladištu, kao i ćelije-donori iz mnoštva . Uvijek mnoštvo je podskup .

Za svaku ćeliju iz mnoštva postavljena su ograničenja na kapacitet , mjerenih u dm3. Jedan dm3 predstavlja kocku s rubovima od 10 cm. Proizvodi pohranjeni u skladištu su prilično veliki, stoga je u ovom slučaju takva diskretizacija sasvim dovoljna.

Zadana je matrica najkraćih udaljenosti u metrima između svake paire ćelija , gdje i pripadaju skupovima i odgovarajuće.

Označimo "troškove" za premještanje robe iz ćelije u ćeliju . Označimo "troškove" za odabir kontejnera za premještanje ostataka iz drugih ćelija. Kako i u kojim mjerama će se izračunavati vrijednosti i razmotrit ćemo dalje (vidi odjeljak priprema ulaznih podataka), sada je dovoljno reći da će takve veličine biti proporcionalne veličinama i odgovarajuće.

Označimo preko varijablu koja uzima vrijednost 1, ako se ostaci iz ćelije premještaju u kontejner , i 0 u suprotnom. Označimo preko varijablu koja uzima vrijednost 1, ako kontejner sadrži ostatke robe, i 0 u suprotnom.

Zadatak se postavlja ovako: potrebno je pronaći takav skup kontejnera i na taj način "priključiti" ćelije-donore kontejnerima, kako bi se minimizirala funkcija

uz ograničenja

Dakle, tijekom izračunavanja rješenja zadatka nastojimo:

• prvo, uštedjeti skladišni prostor;
• drugo, uštedjeti vrijeme skladištara.

Posljednje ograničenje znači da ne možemo premještati robu u kontejner koji nismo odabrali, a samim tim nismo ni "snosili troškove" za njegov odabir. Također, ovo ograničenje znači da volumen premještane robe iz ćelija u kontejner ne smije premašiti kapacitet kontejnera. Pod rješenjem zadatka podrazumijevamo skup kontejnera i načine priključivanja ćelija-donora kontejnerima.

Ova formulacija optimizacijskog zadatka nije nova i istraživana je od strane mnogih matematičara još od početka 80-ih godina prošlog stoljeća. U inozemnoj literaturi postoje 2 optimizacijska zadatka s odgovarajućim matematičkim modelom: Single-Source Capacitated Facility Location Problem i Multi-Source Capacitated Facility Location Problem (o razlikama u zadacima razgovarat ćemo kasnije). Vrijedi napomenuti da se u matematičkoj literaturi formulacije ovih dviju optimizacijskih problema izražavaju u terminima lociranja poduzeća na terenu, odakle i naziv „Facility Location“. U većini slučajeva to je odraz tradicije, budući da je prvi put potreba za rješavanjem takvih kombinatornih problema proizašla iz područja logistike, većinom u vojno-industrijskoj grani 50-ih godina prošlog stoljeća. U terminima lociranja poduzeća, takvi problemi se formuliraju ovako:

• Postoji konačan broj gradova gdje potencijalno mogu biti smještena proizvodna poduzeća (dalje gradovi-proizvođači). Za svaki grad-proizvođač dane su troškove otvaranja poduzeća, kao i ograničenje na proizvodne kapacitete otvorenog poduzeća.
• Postoji konačan broj gradova gdje se zapravo nalaze klijenti (dalje gradovi-klijenti). Za svaki od tih gradova-klijenata je specificiran obujam potražnje za proizvodom. Radi jednostavnosti, pretpostavit ćemo da je proizvod koji proizvode poduzeća i koji konzumiraju klijenti jedan.
• Za svaki par grad-proizvođač i grad-klijent zadan je iznos troškova prijevoza za isporuku potrebnog obujma proizvoda od proizvođača do klijenta.

Treba pronaći u kojim gradovima otvoriti poduzeća i kako povezati klijente s tim poduzećima, kako bi:

• Ukupni troškovi otvaranja poduzeća i troškovi prijevoza bili minimalni;
• Obujam potražnje klijenata povezanih s nekim otvorenim poduzećem ne prelazi proizvodne kapacitete tog poduzeća.

Sada vrijedi spomenuti jedinstvenu razliku između ova dva klasična problema:

• Single-Source Capacitated Facility Location Problem – klijent se opskrbljuje samo iz jednog otvorenog poduzeća;
• Multi-Source Capacitated Facility Location Problem – klijent se može opskrbljivati iz nekoliko otvorenih poduzeća istovremeno.

Takva razlika između dvaju problema na prvi pogled čini se beznačajnom, ali zapravo vodi do potpuno različite kombinatorne strukture tih problema i, kao posljedica, do potpuno različitih algoritama za njihovo rješavanje. Razlika između problema prikazana je na slici ispod.

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

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

Oba problema -teške, odnosno ne postoji točan algoritam koji bi za polinomno vrijeme u odnosu na veličinu ulaznih podataka riješio takav problem. Drugim riječima, svi točni algoritmi za rješavanje problema će raditi eksponencijalno vrijeme, iako, možda, brže od potpune brute-force metode. S obzirom na problem -težak, pa ćemo razmatrati samo približne heuristike, tj. algoritme koji izračunavaju rješenja koja su vrlo bliska optimalnim i rade dovoljno brzo. Ako postoji interes za takav problem, ovdje se može pronaći dobar pregled na hrvatskom.

Ako prebacimo na terminologiju našeg zadatka optimalnog skladištenja robe u ćelijama, tada:

• gradovi-klijenti – to su ćelije-donori s ostacima robe,
• gradovi-proizvođači – ćelije-kontejneri , u koje se planira smjestiti ostatke iz drugih ćelija,
• troškovi transporta – troškovi vremena skladištarima za premještanje volumena robe iz ćelije-donora u ćeliju-kontejner ;
• troškovi otvaranja poduzeća – troškovi odabira kontejnera , jednaki volumenu ćelije-kontejnera , pomnoženom s nekim koeficijentom uštede slobodnih volumena (vrijednost koeficijenta uvijek > 1) (vidi odjeljak priprema ulaznih podataka).

Nakon što je analogija s poznatim klasičnim zadatkom isporuke provedena, potrebno je odgovoriti na važno pitanje koje utječe na izbor arhitekture algoritma rješenja: je li premještanje ostataka iz ćelije-donora moguće samo u jedan i samo jedan kontejner (Single-Source), ili je li moguće premještanje ostataka u više ćelija-kontejnera (Multi-Source)?

Vrijedi napomenuti da u praksi obje formulacije problema postoje. Ispod ćemo navesti sve ‚za‘ i ‚protiv‘ za svaku takvu formulaciju:

Tabela 1. Prednosti i nedostaci varijanti Single-Source i Multi-Source.

S obzirom na to da opcija Single-Source ima više prednosti, a takođe uzimajući u obzir činjenicu da što je manji broj ostataka u ćelijama-donorima, to je razlika u stepenu kompaktnošću kompresije smanjena, naš izbor je pao na varijantu Single-Source.

Treba reći da rešenje varijante Multi-Source takođe ima svoje mesto. Postoji veliki broj efikasnih algoritama za njegovo rešenje, od kojih se većina svodi na rešavanje niza transportnih zadataka. Takođe postoje ne samo efikasni, već i elegantni algoritmi, na primer, ovde.

Priprema ulaznih podataka

Pre nego što započnemo analizu i razvoj algoritma za rešavanje zadatka, potrebno je utvrditi koje podatke i u kojem obliku ćemo mu dostaviti na ulaz. Sa količinama ostataka proizvoda u ćelijama-donorima i kapacitetom ćelija-kontejnera nema problema, jer je to trivijalno – takve veličine biće mjerene u m3, ali što se tiče troškova korišćenja ćelije-kontejnera i matrice troškova za kretanje, stvari nisu tako jednostavne!

Na početku ćemo razmotriti izračunavanje troškova premještanja robe iz ćelije-donora u ćeliju-kontejner. Prvo je potrebno odrediti u kojim jedinicama mjerenja ćemo izračunavati troškove premještanja. Dve naj očiglednije opcije su metri i sekunde. U „čistim” metrima troškove premještanja računati je besmisleno. Prikažimo to na primjeru. Pretpostavimo da je ćelija smještena na prvom spratu, ćelija udaljena 30 metara i nalazi se na drugom spratu:

• Premještanje iz u skuplje je nego premještanje iz u , jer je lakše spuštati se sa drugog sprata (1,5-2 metra od poda) nego podizati na drugi, iako će udaljenost biti jednaka;
• Premjestiti 1 kom. robe iz ćelije u bit će lakše nego premjestiti 10 kom. iste robe, iako će udaljenost biti jednaka.

Troškove premještanja bolje je pratiti u sekundama, jer to omogućava da se uzmu u obzir i razlika u spratovima i razlika u količini premještene robe. Da bismo izračunali troškove premještanja u sekundama, moramo razložiti operaciju premještanja na elementarne sastojke i mjeriti vreme potrebno za izvršavanje svake elementarne komponente.

Pretpostavimo da iz ćelije premješta kom. robe u kontejner . Neka bude prosječna brzina kretanja radnika po skladištu, mjerena u m/s. Neka i budu prosječne brzine jednokratnog izvršenja operacija uzeti i staviti za volumen robe jednak 4 dm3 (prosječan volumen koji uzima radnik u skladištu prilikom izvršavanja operacija). Neka i bude visina ćelija iz kojih se izvršavaju operacije uzeti i staviti. Na primjer, prosječna visina prvog sprata (pod) je 1 m, drugi sprat 2 m itd. Tada formula za izračun ukupnog vremena potrebnog za izvršenje operacije premještanja je sljedeća:

U tabeli 2 prikazana je statistika vremena izvršenja svake elementarne operacije, koju su prikupili zaposlenici skladišta uzimajući u obzir specifičnost čuvane robe.

Naziv operacije	Oznaka	Prosječna vrijednost
Prosječna brzina kretanja radnika po skladištu		1,5 m/s
Prosječna brzina izvršenja jedne operacije staviti (za volumen robe 4 dm3)		2,4 sek

Tabela 2. Prosječno vreme izvršenja skladišnih operacija

Sa načinom izračuna troškova premještanja smo se dogovorili. Sada je potrebno saznati kako izračunati troškove za odabir ćelije-kontejneraOvdje je sve puno, puno složenije nego s troškovima premještanja, jer:

• prvo, troškovi bi trebali biti u izravnoj vezi s volumenom ćelije – istu količinu zaliha koja se premješta iz ćelija-donora bolje je staviti u manji kontejner nego u veći, pod uvjetom da takav volumen u potpunosti stane u oba kontejnera. Tako, minimizirajući ukupne troškove izbora kontejnera, nastojimo uštedjeti 'deficitarne' slobodne skladišne kapacitete u području zone odabira, radi obavljanja narednih operacija postavljanja robe u ćelijama. Na slici 4 prikazani su načini premještanja zaliha u velike i male kontejnere i posljedice takvih opcija premještanja prilikom obavljanja narednih skladišnih operacija.
• drugo, s obzirom na to da u rješenju početnog zadatka moramo minimizirati ukupne troškove, a to je zbroj troškova premještanja i troškova izbora kontejnera, potrebno je nekako uskladiti volumene ćelija u kubnim metrima s sekundama, što nije nimalo trivijalno.

Sl. 4. Opcije premještanja zaliha u kontejnere različitih kapaciteta.

Na slici 4 crvenom bojom prikazan je volumen zaliha koji više ne stane u kontejner u drugoj fazi postavljanja sljedećih proizvoda.

Pomoći će uskladiti kubične metre troškova izbora kontejnera sa sekundama troškova premještanja sljedeći zahtjevi za proračunata rješenja zadatka:

• Moramo osigurati da se zalihe iz ćelije-donora premjeste u ćeliju-kontejner u svakom slučaju, ako to smanjuje ukupni broj ćelija-kontejnera u kojima se nalazi roba.
• Potrebno je održavati ravnotežu između volumena kontejnera i troškova vremena za premještanje: na primjer, ako je u novoj opciji rješenja zadatka u odnosu na prethodnu opciju dobitak u volumenu velik, a gubitak u troškovima vremena mali, tada je potrebno odabrati novu opciju.

Počet ćemo s posljednjim zahtjevom. Kako bismo konkretizirali višeznačnu riječ 'ravnoteža', proveli smo anketu među zaposlenicima skladišta s ciljem da saznamo sljedeće. Neka imamo ćeliju-kontejner volumena , u koju je predviđeno premještanje zaliha iz ćelija-donora, a ukupno vrijeme takvog premještanja jednako je . Postavite još nekoliko alternativnih opcija za smještaj iste količine robe iz istih donatorskih ćelija u druge kontejnere, pri čemu svaki smještaj ima svoje ocjene. , gdje < i , gdje >.

Postavlja se pitanje: koja je minimalna dobit u volumenu? pri zadanoj vrijednosti gubitka vremena? ? Поясним на примере. Изначально остатки полагалось размещать в контейнер объема 1000 дм3 (1 м3) и время на перемещение составило 70 секунд. Есть вариант размещения остатков в другой контейнер объема 500 дм3 и временем 130 секунд. Вопрос: готовы ли мы тратить еще дополнительные 60 секунд времени кладовщика на выполнение перемещения для того, чтобы сэкономить 500 дм3 свободного объема? По результатам опроса сотрудников склада была составлена следующая диаграмма.

Slika 5. Dijagram ovisnosti minimalne prihvatljive uštede volumena o povećanju razlike u vremenu izvršenja operacije.

Odnosno, ako dodatni troškovi u vremenu iznose 40 sekundi, spremni smo ih potrošiti samo ako će dobit u volumenu biti najmanje 500 dм3. Iako se u ovisnosti primjećuje mala nelineranost, radi jednostavnosti daljnjih izračuna pretpostavit ćemo da je ovisnost između veličina linearna i da ju opisuje nejednakost.

Na slici ispod razmatramo sljedeće načine smještaja robe u kontejnere.

Slika 6. Opcija (a): 2 kontejnera, ukupni volumen 400 dм3, ukupno vrijeme 150 sekundi.

Slika 6. Opcija (b): 2 kontejnera, ukupni volumen 600 dм3, ukupno vrijeme 190 sekundi.

Slika 6. Opcija (c): 1 kontejner, ukupni volumen 400 dм3, ukupno vrijeme 200 sekundi.

Opcija (a) odabira kontejnera je poželjnija od izvorne opcije, budući da je nejednakost ostvarena: (800-400)/10 ≥ 150-120, iz čega slijedi 40 ≥ 30. Opcija (b) je manje poželjna od izvorne opcije, jer nejednakost nije ostvarena: (800-600)/10 ≥ 190-150, iz čega slijedi 20 ≥ 40. Međutim, opcija (c) ne odgovara ovoj logici! Razmotrimo ovu opciju detaljnije. S jedne strane nejednakost (800-400)/10 ≥ 200-120, što znači da nejednakost 40 ≥ 80 nije ostvarena, što ukazuje na to da dobit u volumenu ne opravdava toliki gubitak vremena.

S druge strane, u takvoj opciji (c) ne samo da smanjujemo ukupno zauzeti volumen, nego također smanjujemo broj zauzetih ćelija, što je prvi od dva važna zahtjeva za izračunata rješenja problema, navedena gore. Očito je da je kako bi se ovaj zahtjev počeo ostvarivati potrebno u lijevu stranu nejednakosti dodati neku pozitivnu konstantu. , pri čemu tu konstantu treba dodati samo kada se broj kontejnera smanjuje. Podsjetimo se da — to je varijabla koja je jednaka 1 kada je kontejner odabran, i 0 kada kontejner nije odabran. Oznaka, – mnoštvo kontejnera u prvotnom rješenju i – mnoštvo kontejnera u novom rješenju. U općem obliku novo nejednakost će izgledati ovako:

Preoblikovanjem gornje nejednakosti, dobivamo

Iz ovoga imamo formulu za izračun ukupnih troškova neke varijante rješenja problema:

Ali sada se postavlja pitanje: koju vrijednost bi takva konstanta trebala imati ? Очевидно, что ее значение должно быть достаточно большим, для того, чтобы всегда выполнялось первое требование к решениям задачи. Можно конечно взять значение константы равное 103 или 106, но хотелось бы избежать таких «magic numbers». Если будем рассматривать специфику выполнения складских операций, мы можем вычислить несколько вполне обоснованных числовых оценок величины такой константы.

Neka – maksimalna udaljenost između ćelija skladišta jedne zone ABC, koja iznosi u našem slučaju 100 m. Neka – maksimalni volumen ćelije-kontejnera u skladištu, koji iznosi u našem slučaju 1000 dm3.

Prvi način izračuna veličine . Razmatramo situaciju u kojoj postoje 2 kontejnera na prvom sloju, u kojima se već fizički nalazi roba, tj. oni sami su ćelije-donatori, a troškovi premještanja robe u te iste ćelije su, naravno, 0. Potrebno je pronaći takvu vrijednost konstante , pri kojoj bi bilo isplativo uvijek premještati ostatke iz kontejnera 1 u kontejner 2. Umetanjem vrijednosti i u gornju nejednakost, dobivamo:

iz čega slijedi

Umetanjem vrijednosti prosječnog vremena izvedbe elementalnih operacija u gornju formulu dobivamo

Drugi način izračuna veličine . Razmatramo situaciju u kojoj postoji ćelija-donatora iz kojih se planira premjestiti roba u kontejner 1. Oznaka – udaljenost od ćelije-donatora do kontejnera 1. Ima također kontejner 2, u kojem već ima roba, a čiji volumen dopušta smještaj ostataka iz svih ćelija. Radi jednostavnosti, pretpostavit ćemo da je volumen robe koja se premješta iz ćelija-donatora u kontejnere jednak . Potrebno je pronaći takvu vrijednost konstante , pri kojoj bi smještaj svih ostataka iz ćelija u kontejner 2 uvijek bio isplativiji nego smještaj u različite kontejnere:

Preoblikovanjem nejednakosti dobivamo

Kako bismo "pojačali" vrijednost veličine , prihvaćamo da = 0. Prosječan broj ćelija koje obično sudjeluju u postupku skupljanja ostataka u skladištu iznosi 10. Umetanjem poznatih vrijednosti veličina, imamo sljedeću vrijednost konstante

Uzimamo najveću vrijednost, izračunatu za svaku varijantu, to će biti vrijednost veličine za zadata parametre skladišta. Sada, za cjelovitost, zapišimo formulu za izračun ukupnih troškova za neku prihvatljivu varijantu rješenja :

Evo sada, nakon svih titanovih napora u transformaciji ulaznih podataka, možemo reći da su svi ulazni podaci transformirani u željeni oblik i spremni za korištenje u algoritmu optimizacije.

Zaključak

Kao što praksa pokazuje, složenost i važnost faze pripreme i transformacije ulaznih podataka za algoritam često se podcjenjuju. U ovom članku posebno smo posvetili puno pažnje ovoj fazi kako bismo pokazali da samo kvalitetno i mudro pripremljeni ulazni podaci mogu učiniti rješenja koja izračunava algoritam zaista vrijednima za klijenta. Da, bilo je mnogih ispravaka formula, ali Vas upozoravamo još prije katas 🙂

U sljedećem članku napokon ćemo doći do onoga zbog čega su zamišljene prethodne 2 objave – do algoritma diskretne optimizacije.

Članak je pripremio
Roman Shangin, programer odjela projekata,
tvrtka Prvi Bit, Čeljabinsk

Izvor: habr.com