Tässä artikkelissa kerromme sinulle, kuinka ratkaisimme varaston vapaiden solujen puutteen ongelman ja kehitimme erillisen optimointialgoritmin tällaisen ongelman ratkaisemiseksi. Puhutaanpa siitä, kuinka "rakensimme" optimointitehtävän matemaattisen mallin, ja vaikeuksista, joita kohtasimme odottamatta käsiteltäessä syöttödataa algoritmille.
Jos olet kiinnostunut matematiikan sovelluksista liiketoiminnassa etkä pelkää kaavojen jäykkiä identiteettimuunnoksia 5. luokkatasolla, niin tervetuloa kissalle!
Artikkeli on hyödyllinen niille, jotka toteuttavat WMS-järjestelmät, työt varasto- tai tuotantologistiikkateollisuudessa sekä ohjelmoijat, jotka ovat kiinnostuneita matematiikan sovelluksista liiketoiminnassa ja prosessien optimoinnista yrityksessä.
Johdanto-osa
Tämä julkaisu jatkaa artikkelisarjaa, jossa jaamme onnistuneen kokemuksemme optimointialgoritmien toteuttamisesta varastoprosesseissa.
В kuvaa sen varaston erityispiirteet, jossa toteutimme WMS-järjestelmä, ja selittää myös, miksi meidän piti ratkaista jäljellä olevien tavaroiden klusterointiongelma toteutuksen aikana WMS-järjestelmät ja miten teimme sen.
Kun lopetimme optimointialgoritmeja käsittelevän artikkelin kirjoittamisen, se osoittautui erittäin suureksi, joten päätimme jakaa kertyneen materiaalin kahteen osaan:
- Ensimmäisessä osassa (tässä artikkelissa) puhumme siitä, kuinka "rakensimme" ongelman matemaattisen mallin, ja suurista vaikeuksista, joita kohtasimme odottamatta käsiteltäessä ja muuntaessamme algoritmin syöttötietoja.
- Toisessa osassa tarkastelemme yksityiskohtaisesti algoritmin toteutusta kielellä C + +, teemme laskennallisen kokeilun ja teemme yhteenvedon kokemuksesta, jonka saimme tällaisten "älykkäiden teknologioiden" käyttöönotossa asiakkaan liiketoimintaprosesseissa.
Kuinka lukea artikkeli. Jos luet edellisen artikkelin, voit siirtyä välittömästi kappaleeseen "Yleiskatsaus olemassa oleviin ratkaisuihin"; jos ei, niin ratkaistavan ongelman kuvaus on alla olevassa spoilerissa.
Kuvaus asiakkaan varastossa ratkaistavasta ongelmasta
Pullonkaula prosesseissa
Vuonna 2018 saimme toteutusprojektin valmiiksi WMS-järjestelmät varastossa "Trading House "LD" Tšeljabinskissa. Otimme käyttöön tuotteen “1C-Logistics: Warehouse Management 3” 20 työpaikalle: operaattorit WMS, varastonhoitajat, trukinkuljettajat. Keskimääräinen varasto on noin 4 tuhatta m2, kennojen lukumäärä 5000 ja SKU:ita 4500. Varastossa on omaa tuotantoamme palloventtiilejä erikokoisia 1 kg - 400 kg. Varastossa varasto varastoidaan erissä, koska tavarat on valittava FIFO:n mukaan.
Varastoprosessien automaatiosuunnitelmia suunniteltaessa kohtasimme olemassa olevan epäoptimaalisen varaston varastoinnin ongelman. Varastoinnin ja nostureiden asennuksen erityispiirteet ovat sellaiset, että yksi yksikkövarasto voi sisältää vain yhden erän tuotteita (ks. kuva 1). Tuotteet saapuvat varastolle päivittäin ja jokainen saapuminen on erillinen erä. Yhteensä 1 kuukauden varastotoiminnan tuloksena syntyy 30 erillistä erää huolimatta siitä, että jokainen tulisi varastoida erilliseen soluun. Tuotteet valitaan usein ei kokonaisina lavoina, vaan kappaleina, ja sen seurauksena kappaleen valintavyöhykkeellä monissa soluissa havaitaan seuraava kuva: solussa, jonka tilavuus on yli 1 m3, on useita nostureita, jotka vievät alle 5-10 % solun tilavuudesta.
Kuva 1. Kuva useista kappaleista solussa
On selvää, että tallennuskapasiteettia ei käytetä optimaalisesti. Katastrofin laajuuden kuvittelemiseksi voin antaa lukuja: tällaisia soluja, joiden tilavuus on yli 1 m3, on keskimäärin 100 - 300 solua, joiden saldot ovat "pieniä" varaston eri toimintajaksojen aikana. Koska varasto on suhteellisen pieni, varaston kiireisinä aikoina tämä tekijä muodostuu "pullonkaulaksi" ja hidastaa suuresti varaston vastaanotto- ja lähetysprosesseja.
Idea ongelman ratkaisuun
Syntyi ajatus: lähimmän päiväyksen omaavat ylijäämäerät tulisi vähentää yhdeksi eräksi ja tällaiset yhtenäisen erän ylijäämät tulisi sijoittaa tiiviisti yhteen soluun tai useampaan, jos yhdessä ei ole tarpeeksi tilaa. koko määrä jäämiä. Esimerkki tällaisesta "pakkauksesta" on esitetty kuvassa 2.
Kuva 2. Kaavio jäämien puristamiseksi soluissa
Tämän avulla voit vähentää merkittävästi varattua varastotilaa, jota käytetään uusien tavaroiden sijoittamiseen. Tilanteessa, jossa varastokapasiteetti on ylikuormitettu, tällainen toimenpide on äärimmäisen välttämätön, sillä muuten ei yksinkertaisesti voi olla tarpeeksi vapaata tilaa uusien tavaroiden vastaanottamiseen, mikä johtaa varastointi- ja täydennysprosessien pysähtymiseen ja sen seurauksena vastaanottamisen ja lähetyksen pysähtymiseen. Aikaisemmin, ennen WMS-järjestelmän käyttöönottoa, tällainen toimenpide suoritettiin manuaalisesti, mikä oli tehotonta, koska solujen sopivien tasapainojen etsiminen oli melko pitkä. Nyt WMS-järjestelmän käyttöönoton myötä päätimme automatisoida prosessin, nopeuttaa sitä ja tehdä siitä älykkään.
Tällaisen ongelman ratkaisuprosessi on jaettu kahteen vaiheeseen:
- ensimmäisessä vaiheessa löydämme eräryhmiä, jotka ovat lähellä pakkausta (omistettu tälle tehtävälle );
- toisessa vaiheessa laskemme jokaiselle eräryhmälle jäljellä olevien tavaroiden pienimmän sijoituksen soluihin.
Tässä artikkelissa keskitymme algoritmin toiseen vaiheeseen.
Olemassa olevien ratkaisujen tarkastelu
Ennen kuin siirrymme kehittämiemme algoritmien kuvaukseen, kannattaa tehdä lyhyt katsaus markkinoilla jo oleviin järjestelmiin WMS, jotka toteuttavat samanlaisen optimaalisen pakkaustoiminnon.
Ensinnäkin on huomioitava tuote "1C: Enterprise 8. WMS Logistics. Varastonhallinta 4", jonka omistaa ja jäljentää 1C ja joka kuuluu neljänteen sukupolveen WMS-AXELOTin kehittämät järjestelmät. Tämä järjestelmä vaatii pakkaustoiminnallisuutta, joka on suunniteltu yhdistämään erilaiset tuotejäämät yhteen yhteiseen soluun. On syytä mainita, että pakkaustoiminnallisuus tällaisessa järjestelmässä sisältää myös muita mahdollisuuksia, esimerkiksi solujen tavaroiden sijoittelun korjaaminen niiden ABC-luokkien mukaan, mutta emme jää niihin.
Jos analysoit 1C: Enterprise 8. WMS Logistics -järjestelmän koodia. Varastonhallinta 4" (joka on auki tässä toiminnallisuuden osassa), voimme päätellä seuraavaa. Jäännöspakkausalgoritmi toteuttaa melko primitiivistä lineaarista logiikkaa, eikä mistään "optimaalisesta" pakkauksesta voi puhua. Siinä ei luonnollisestikaan määrätä puolueiden klusteroinnista. Useat asiakkaat, joilla oli tällainen järjestelmä käyttöön, valittivat pakkaussuunnittelun tuloksista. Esimerkiksi usein käytännössä puristuksen aikana tapahtui seuraava tilanne: 100 kpl. Loput tavarat on tarkoitus siirtää solusta toiseen soluun, jossa 1 kappale sijaitsee. tavaroita, vaikka ajankäytön kannalta on optimaalista toimia päinvastoin.
Myös soluissa jäljellä olevien tavaroiden pakkaamisen toimivuus on ilmoitettu monissa ulkomaissa. WMS-järjestelmät, mutta valitettavasti meillä ei ole todellista palautetta algoritmien tehokkuudesta (tämä on liikesalaisuus), saati vähemmän käsitystä niiden logiikan syvyydestä (omistettu suljetun lähdekoodin ohjelmisto), joten emme voi arvioida.
Etsi ongelman matemaattinen malli
Laadukkaiden algoritmien suunnittelemiseksi ongelman ratkaisemiseksi on ensin välttämätöntä muotoilla tämä ongelma selvästi matemaattisesti, mitä teemme.
Soluja on monia , jotka sisältävät joidenkin tavaroiden jäänteitä. Seuraavassa kutsumme tällaisia soluja luovuttajasoluiksi. Merkitään solussa olevien tavaroiden määrä $.
On tärkeää sanoa, että vain yksi tuote yhdestä erästä tai useita eriä, jotka on aiemmin yhdistetty klusteriin (lue: ), mikä johtuu tavaroiden varastoinnin ja varastoinnin erityispiirteistä. Eri tuotteille tai eri eräryhmille tulisi suorittaa oma erillinen pakkausprosessi.
Soluja on monia , johon voidaan mahdollisesti sijoittaa luovuttajasolujen tähteitä. Kutsumme edelleen tällaisia soluja konttisoluiksi. Nämä voivat olla joko vapaita soluja varastossa tai luovuttajasoluja eri lajikkeista . Aina runsaasti on osajoukko .
Jokaiselle solulle monilta Kapasiteettirajoituksia on asetettu , mitattuna dm3. Yksi dm3 on kuutio, jonka sivut ovat 10 cm. Varastossa olevat tuotteet ovat melko suuria, joten tässä tapauksessa tällainen diskretointi riittää.
Annettu lyhimpien etäisyyksien matriisi metreinä kunkin soluparin välillä Missä и kuuluvat sarjoihin и vastaavasti.
Merkitään "kustannukset" tavaroiden siirtämisestä solusta soluun . Merkitään kontin valinnan "kustannukset". siirtääkseen jäämiä muista soluista siihen. Kuinka tarkasti ja missä mittayksiköissä arvot lasketaan и harkitsemme edelleen (katso syöttötietojen valmistelua), toistaiseksi riittää, kun sanotaan, että tällaiset arvot ovat suoraan verrannollisia arvoihin и vastaavasti.
Merkitään muuttuja, joka saa arvon 1, jos loppuosa on solusta siirretty konttiin , ja 0 muuten. Merkitään muuttuja, joka saa arvon 1, jos kontti sisältää loput tavarat ja 0 muuten.
Tehtävä on esitetty seuraavasti: sinun täytyy löytää niin monta konttia ja siten "kiinnittää" luovuttajasoluja säiliösoluihin toiminnan minimoimiseksi
rajoitusten alla
Kaiken kaikkiaan ongelman ratkaisua laskettaessa pyrimme:
- ensinnäkin tallennuskapasiteetin säästämiseksi;
- toiseksi säästääkseen varastonpitäjien aikaa.
Viimeinen rajoitus tarkoittaa sitä, että emme voi siirtää tavaroita konttiin, jota emme ole valinneet, emmekä sen vuoksi "syntyneet kuluja" sen valinnasta. Tämä rajoitus tarkoittaa myös sitä, että soluista konttiin siirrettävien tavaroiden määrä ei saa ylittää kontin kapasiteettia. Ongelman ratkaisemisella tarkoitamme konttijoukkoa ja menetelmät luovuttajasolujen kiinnittämiseksi säiliöihin.
Tämä optimointiongelman muotoilu ei ole uusi, ja monet matemaatikot ovat sitä tutkineet viime vuosisadan 80-luvun alusta lähtien. Ulkomaisessa kirjallisuudessa on 2 optimointitehtävää sopivalla matemaattisella mallilla: и (Puhumme tehtävien eroista myöhemmin). On syytä sanoa, että matemaattisessa kirjallisuudessa tällaisten kahden optimointitehtävän muotoilu on muotoiltu yritysten sijainnin perusteella kentällä, mistä johtuu nimi "Facility Location". Suurimmaksi osaksi tämä on kunnianosoitus perinteelle, sillä ensimmäistä kertaa tarve tällaisten kombinatoristen ongelmien ratkaisemiseen tuli logistiikan alalta, lähinnä sotilasteollisuudesta viime vuosisadan 50-luvulla. Yrityksen sijainnin osalta tällaiset tehtävät on muotoiltu seuraavasti:
- On rajallinen määrä kaupunkeja, joihin on mahdollisesti mahdollista sijoittaa tuotantoyrityksiä (jäljempänä tuotantokaupungit). Jokaiselle valmistuskaupungille määritellään yrityksen avaamisen kustannukset siinä sekä rajoitus siihen avatun yrityksen tuotantokapasiteetille.
- On olemassa rajallinen joukko kaupunkeja, joissa asiakkaat todella sijaitsevat (jäljempänä asiakaskaupungit). Jokaiselle tällaiselle asiakaskaupungille määritellään tuotteiden kysynnän määrä. Yksinkertaisuuden vuoksi oletetaan, että on vain yksi tuote, jota yritykset valmistavat ja asiakkaat kuluttavat.
- Kullekin kaupunki-valmistaja- ja kaupunki-asiakasparille määritetään kuljetuskustannusten arvo vaaditun tuotemäärän toimittamisesta valmistajalta asiakkaalle.
Sinun on selvitettävä, missä kaupungeissa voit avata yrityksiä ja miten liittää asiakkaita tällaisiin yrityksiin, jotta:
- Yritysten avaamisen kokonaiskustannukset ja kuljetuskustannukset olivat minimaaliset;
- Avoimeen yritykseen osoitettujen asiakkaiden kysyntä ei ylittänyt kyseisen yrityksen tuotantokapasiteettia.
Nyt on syytä mainita näiden kahden klassisen ongelman ainoa ero:
- Yhden lähteen kapasitoidun laitoksen sijaintiongelma – asiakkaalle syötetään vain yhdestä avoimesta toimipaikasta;
- Monilähdekapasitoidun tilan sijaintiongelma – asiakkaalle voidaan toimittaa virtaa useista avoimista tiloista samanaikaisesti.
Tällainen ero näiden kahden ongelman välillä on ensi silmäyksellä merkityksetön, mutta itse asiassa johtaa tällaisten ongelmien täysin erilaiseen kombinatoriseen rakenteeseen ja sen seurauksena täysin erilaisiin algoritmeihin niiden ratkaisemiseksi. Tehtävien väliset erot näkyvät alla olevassa kuvassa.
Kuva 3. a) Usean lähteen kapasitoidun laitoksen sijaintiongelma
Kuva 3. b) Yhden lähteen kapasitoidun laitoksen sijaintiongelma
Molemmat tehtävät -vaikea, eli ei ole olemassa tarkkaa algoritmia, joka ratkaisisi tällaisen ongelman syöttödatan koon aikapolynomissa. Yksinkertaisemmin sanottuna kaikki tarkat algoritmit ongelman ratkaisemiseksi toimivat eksponentiaalisessa ajassa, vaikkakin ehkä nopeammin kuin täydellinen vaihtoehtojen haku. Tehtävästä lähtien -vaikeaa, silloin huomioidaan vain likimääräinen heuristiikka, eli algoritmit, jotka laskevat johdonmukaisesti ratkaisuja hyvin lähellä optimaalista ja toimivat melko nopeasti. Jos olet kiinnostunut tällaisesta tehtävästä, löydät täältä hyvän yleiskatsauksen venäjäksi.
Jos siirrymme soluissa olevien tavaroiden optimaalisen pakkaamisen ongelmamme terminologiaan, niin:
- asiakaskaupungit ovat luovuttajasoluja jäljellä olevien tavaroiden kanssa,
- valmistavat kaupungit – konttisolut , johon muiden solujen jäännökset on tarkoitus sijoittaa,
- kuljetuskustannukset - aikakustannukset varastonhoitaja siirtää tavaroita luovuttajasolusta konttikennoon ;
- yrityksen avaamisen kustannukset - kontin valinnan kustannukset , yhtä suuri kuin säiliökennon tilavuus , kerrottuna tietyllä kertoimella vapaiden volyymien säästämiseksi (kertoimen arvo on aina > 1) (katso syöttötietojen valmistelu).
Kun analogia ongelman tunnettujen klassisten ratkaisujen kanssa on piirretty, on tarpeen vastata tärkeään kysymykseen, josta ratkaisualgoritmin arkkitehtuurin valinta riippuu: jäännösten siirtäminen luovuttajasolusta on mahdollista vain yhteen. ja vain yksi säilö (Single-Source), vai onko mahdollista siirtää loput useisiin säilösoluihin (Multi-Source)?
On syytä huomata, että käytännössä tapahtuu molemmat ongelman muotoilut. Esittelemme alla jokaisen tällaisen asetuksen edut ja haitat:
| Ongelma variantti | Vaihtoehdon plussat | Vaihtoehdon miinukset |
|---|---|---|
| Ainoa lähde | Tavaransiirtooperaatiot lasketaan käyttämällä tätä ongelman muunnelmaa:
|
|
| Monilähde | Tällä ongelman versiolla lasketut pakkaukset ovat yleensä 10-15 % kompaktimpia verrattuna "Single-Source" -vaihtoehdolla laskettuihin pakkauksiin. Mutta huomaamme myös, että mitä pienempi jäämien määrä luovuttajasoluissa on, sitä pienempi on ero tiiviyden välillä | Tavaransiirtooperaatiot lasketaan käyttämällä tätä ongelman muunnelmaa:
|
Taulukko 1. Single-Source- ja Multi-Source-vaihtoehtojen edut ja haitat.
Koska Single-Source-vaihtoehdolla on enemmän etuja, ja kun otetaan huomioon myös se tosiasia, että mitä pienempi on jäämien määrä luovuttajasoluissa, sitä pienempi ero puristustiiviysasteessa lasketaan ongelman molemmille varianteille, valintamme osui Single-Source -vaihtoehto.
On syytä sanoa, että myös Multi-Source-vaihtoehdon ratkaisu tapahtuu. Sen ratkaisemiseen on olemassa suuri määrä tehokkaita algoritmeja, joista suurin osa rajoittuu useiden kuljetusongelmien ratkaisemiseen. Ei ole myöskään vain tehokkaita algoritmeja, vaan myös tyylikkäitä, esim.
Syötetietojen valmistelu
Ennen kuin aloitamme analysoimaan ja kehittämään algoritmia ongelman ratkaisemiseksi, on tarpeen päättää, mitä dataa ja missä muodossa syötämme sen syötteeksi. Luovuttajasolujen jäljellä olevien tavaroiden määrässä ja konttikennojen kapasiteetissa ei ole ongelmia, koska tämä on triviaalia - tällaiset määrät mitataan m3, mutta konttisolun käyttökustannuksilla ja muuttokustannusmatriisilla ei kaikkea. on niin yksinkertaista!
Katsotaan ensin laskelma tavaroiden siirtokustannukset luovuttajasolusta säiliösoluun. Ensinnäkin on päätettävä, missä mittayksiköissä laskemme liikkumiskustannukset. Kaksi ilmeisintä vaihtoehtoa ovat metrit ja sekunnit. Ei ole mitään järkeä laskea matkakuluja "puhtaina" metreinä. Osoitetaan tämä esimerkillä. Anna solun sijaitsee ensimmäisessä kerroksessa, solussa poistettu 30 metriä ja sijaitsee toisella tasolla:
- Muutto pois в kalliimpaa kuin muutto в , koska laskeutuminen toisesta tasosta (1,5-2 metriä lattiasta) on helpompaa kuin toiselle, vaikka etäisyys on sama;
- Siirrä 1 kpl. tavarat solusta в Se on helpompaa kuin 10 kappaleen siirtäminen. sama tuote, vaikka etäisyys on sama.
Muuttokustannukset kannattaa huomioida sekunneissa, koska näin voit ottaa huomioon sekä tasojen eron että eron siirrettävien tavaroiden määrissä. Liikkeen kustannusten huomioon ottamiseksi sekunneissa meidän on jaettava liiketoiminto peruskomponentteihin ja otettava aikamittaukset kunkin peruskomponentin suorittamiselle.
Päästä solusta liikkuu PC. tavarat konteissa . päästää – työntekijän keskimääräinen liikkumisnopeus varastossa, mitattuna m/s. Antaa и – Kertatoimien keskimääräiset nopeudet otetaan ja lasketaan vastaavasti 4 dm3:n tavaramäärälle (keskimääräinen tilavuus, jonka työntekijä kerrallaan vie varastosta toimiessaan). Antaa и niiden solujen korkeus, joista otto- ja put-operaatiot suoritetaan vastaavasti. Esimerkiksi ensimmäisen kerroksen (lattian) keskikorkeus on 1 m, toisen tason on 2 m jne. Sitten kaava siirtotoiminnon suorittamiseen kuluvan kokonaisajan laskemiseksi on seuraavat:
Taulukossa 2 on tilastot kunkin perusoperaation suoritusajasta varastotyöntekijöiden keräämänä ottaen huomioon varastoitavan tavaran erityispiirteet.
| operaation nimi | Nimitys | Tarkoittaa |
|---|---|---|
| Varastossa liikkuvan työntekijän keskinopeus | |
1,5 m/s |
| Yhden toimenpiteen keskimääräinen nopeus (tuotteen tilavuudelle 4 dm3) | |
2,4 sek |
Taulukko 2. Keskimääräinen aika varastotoimintojen suorittamiseen
Olemme päättäneet muuttokustannusten laskentatavan. Nyt meidän on selvitettävä, kuinka laskea säiliökennon valinnan kustannukset. Kaikki täällä on paljon, paljon monimutkaisempaa kuin muuttokustannukset, koska:
- Ensinnäkin kustannusten tulisi olla suoraan riippuvaisia solun tilavuudesta - sama määrä luovuttajasoluista siirrettyjä jäämiä sijoitetaan paremmin pienemmän tilavuuden säiliöön kuin suureen säiliöön, edellyttäen, että tällainen tilavuus sopii täysin molempiin säiliöihin . Näin ollen minimoimalla konttien valinnan kokonaiskustannukset pyrimme säästämään valintaalueella ”niukkaa” vapaata varastokapasiteettia myöhempien tavaroiden soluihin sijoittamisen toimenpiteiden suorittamiseksi. Kuvassa 4 on havainnollistettu vaihtoehdot jäännösten siirtämiseksi suuriin ja pieniin kontteihin ja näiden siirtovaihtoehtojen seuraukset myöhemmissä varastotoiminnoissa.
- toiseksi, koska alkuperäisen ongelman ratkaisemisessa meidän on minimoitava tarkalleen kokonaiskustannukset, ja tämä on sekä muuttokustannusten että konttien valintakustannusten summa, niin solujen tilavuudet kuutiometreissä on jotenkin linkitettävä sekunteihin, mikä on kaukana triviaalista.
Riisi. 4. Vaihtoehdot ylijäämien siirtämiseen erikokoisiin astioihin.
Kuvassa 4 näkyy punaisella jätteen määrä, joka ei enää mahdu säiliöön myöhempien tavaroiden sijoittamisen toisessa vaiheessa.
Se auttaa yhdistämään kontin valinnan kustannuskuutiot sekuntikustannuksiin, jotka aiheutuvat seuraavien vaatimusten siirtämisestä ongelman laskennallisille ratkaisuille:
- Luovutussäiliön saldot on joka tapauksessa siirrettävä konttiastiaan, jos tämä vähentää tuotetta sisältävien astioiden kokonaismäärää.
- Konttien tilavuuden ja liikkumiseen käytetyn ajan välillä on säilytettävä tasapaino: esimerkiksi jos ongelman uudessa ratkaisussa aikaisempaan ratkaisuun verrattuna tilavuuden lisäys on suuri, mutta aikahäviö pieni. , sinun on valittava uusi vaihtoehto.
Aloitetaan viimeisestä vaatimuksesta. Selventääksemme epäselvää sanaa ”tase”, teimme varaston työntekijöille kyselyn selvittääksemme seuraavat asiat. Olkoon tilavuuden konttisolu , johon luovuttajasoluista jäljellä olevien tavaroiden siirto on kohdistettu ja tällaisen siirron kokonaisaika on yhtä suuri . Olkoon useita vaihtoehtoisia vaihtoehtoja sijoittaa sama määrä tavaraa samoista luovuttajasoluista muihin astioihin, joissa jokaisella sijoittelulla on omat arvionsa Missä < и Missä >.
Kysymys esitetään: mikä on pienin äänenvoimakkuuden lisäys hyväksyttävä tietylle aikahäviön arvolle ? Selitetäänpä esimerkillä. Aluksi jäännökset piti laittaa säiliöön, jonka tilavuus oli 1000 dm3 (1 m3) ja siirtoaika oli 70 sekuntia. Jäännökset on mahdollista sijoittaa toiseen säiliöön, jonka tilavuus on 500 dm3 ja aika 130 sekuntia. Kysymys: olemmeko valmiita käyttämään 60 sekuntia lisää varastonhoitajan ajasta tavaroiden siirtoon säästääksemme 500 dm3 vapaata tilavuutta? Varastotyöntekijöille tehdyn kyselyn tulosten perusteella koottiin seuraava kaavio.
Riisi. 5. Kaavio pienimmän sallitun tilavuussäästön riippuvuudesta toiminta-ajan eron kasvusta
Eli jos lisäaikakustannukset ovat 40 sekuntia, olemme valmiita käyttämään niitä vasta kun tilavuuslisä on vähintään 500 dm3. Huolimatta siitä, että riippuvuudessa on lievää epälineaarisuutta, oletetaan jatkolaskennan yksinkertaisuuden vuoksi, että suureiden välinen riippuvuus on lineaarinen ja sitä kuvaa epäyhtälö
Alla olevassa kuvassa tarkastelemme seuraavia tavaroiden sijoittamista säiliöihin.
Riisi. 6. Vaihtoehto (a): 2 säiliötä, kokonaistilavuus 400 dm3, kokonaisaika 150 s.
Riisi. 6. Vaihtoehto (b): 2 säiliötä, kokonaistilavuus 600 dm3, kokonaisaika 190 s.
Riisi. 6. Vaihtoehto (c): 1 säiliö, kokonaistilavuus 400 dm3, kokonaisaika 200 s.
Vaihtoehto (a) säiliöiden valinnassa on edullisempi kuin alkuperäinen vaihtoehto, koska epäyhtälö pätee: (800-400)/10>=150-120, mikä tarkoittaa 40 >= 30. Vaihtoehto (b) on vähemmän edullinen kuin alkuperäinen. vaihtoehto , koska epäyhtälö ei päde: (800-600)/10>=190-150, mikä tarkoittaa 20 >= 40. Mutta vaihtoehto (c) ei sovi tähän logiikkaan! Harkitse tätä vaihtoehtoa tarkemmin. Toisaalta epäyhtälö (800-400)/10>=200-120, mikä tarkoittaa, että epäyhtälö 40 >= 80 ei täyty, mikä viittaa siihen, että volyymin lisäys ei ole niin suuren ajanhäviön arvoinen.
Mutta toisaalta, tässä vaihtoehdossa (c) emme vain vähennä käytössä olevaa kokonaistilavuutta, vaan vähennämme myös varattujen solujen määrää, mikä on ensimmäinen kahdesta tärkeästä vaatimuksesta yllä lueteltujen ongelmien laskennallisille ratkaisuille. Ilmeisesti, jotta tämä vaatimus alkaa täyttyä, on selvää, että epäyhtälön vasemmalle puolelle on lisättävä jokin positiivinen vakio , ja tällainen vakio on lisättävä vain, kun säiliöiden määrä vähenee. Muistakaamme se on muuttuja, joka on yhtä suuri kuin 1, kun säiliö valittuna ja 0, kun säiliö ei valittu. Merkitään – monia säiliöitä alkuperäisessä liuoksessa ja – monta konttia uudessa ratkaisussa. Yleisesti ottaen uusi epätasa-arvo näyttää tältä:
Muuttamalla yllä olevaa epätasa-arvoa saamme
Tämän perusteella meillä on kaava kokonaiskustannusten laskemiseksi jokin ratkaisu ongelmaan:
Mutta nyt herää kysymys: mikä arvo tällaisella vakiolla pitäisi olla? ? Ilmeisesti sen arvon tulee olla riittävän suuri, jotta ensimmäinen vaatimus ongelman ratkaisuista aina täyttyy. Voit tietysti ottaa vakion arvon, joka on yhtä suuri kuin 103 tai 106, mutta haluaisin välttää tällaisia "maagisia lukuja". Jos otamme huomioon varastotoimintojen suorittamisen erityispiirteet, voimme laskea useita perusteltuja numeerisia arvioita tällaisen vakion arvosta.
päästää – yhden vyöhykkeen ABC varastosolujen välinen maksimietäisyys, joka on meidän tapauksessamme 100 m. Olkoon – varastotilan konttisolun enimmäistilavuus, joka vastaa meidän tapauksessamme 1000 dm3.
Ensimmäinen tapa laskea arvo . Tarkastellaan tilannetta, jossa ensimmäisessä kerroksessa on 2 konttia, joissa tavarat sijaitsevat jo fyysisesti, eli ne ovat itse luovuttajasoluja ja tavaran siirtämisen hinta samoihin soluihin on luonnollisesti 0. on tarpeen löytää sellainen arvo vakiolle , jossa olisi edullista siirtää ylijäämät aina säiliöstä 1 säiliöön 2. Arvojen korvaaminen и Yllä annetussa epäyhtälössä saamme:
josta seuraa
Korvaamalla perustoimintojen suorittamisen keskimääräisen ajan arvot yllä olevaan kaavaan saadaan
Toinen tapa laskea arvo . Ajatellaanpa tilannetta, jossa on luovuttajasolut, joista tavarat on tarkoitus siirtää konttiin 1. Merkitään – etäisyys luovuttajasolusta konttiin 1. Siellä on myös kontti 2, jossa on jo tavaroita ja jonka tilavuuteen mahtuu loput tavarat soluja. Yksinkertaisuuden vuoksi oletetaan, että luovuttajasoluista säiliöihin siirrettyjen tavaroiden määrä on sama ja yhtä suuri . Tällainen vakion arvo on löydettävä , johon kaikki jäännökset sijoitetaan solujen sijoittaminen säiliöön 2 olisi aina kannattavampaa kuin niiden sijoittaminen eri säiliöihin:
Muuttaa saamamme eriarvoisuutta
Määrän arvon "vahvistamiseksi". , oletetaanpa niin = 0. Keskimääräinen solujen lukumäärä, joka tavallisesti osallistuu varastosaldojen pakkaamiseen, on 10. Korvaamalla määrien tunnetut arvot saadaan seuraava vakion arvo
Otamme kullekin vaihtoehdolle lasketun suurimman arvon, tämä on määrän arvo annetuille varastoparametreille. Täydellisyyden vuoksi kirjoitetaan nyt kokonaiskustannusten laskentakaava johonkin toteuttamiskelpoiseen ratkaisuun :
Nyt sentään Herkuleen ponnisteluja Muuntamalla syöttödataa voidaan sanoa, että kaikki syöttödata on muunnettu haluttuun muotoon ja on valmis käytettäväksi optimointialgoritmissa.
Johtopäätös
Kuten käytäntö osoittaa, algoritmin syöttötietojen valmistelu- ja muunnosvaiheen monimutkaisuus ja tärkeys aliarvioitiin usein. Tässä artikkelissa kiinnitimme erityisesti tähän vaiheeseen paljon huomiota osoittaaksemme, että vain laadukkaalla ja älykkäästi laaditulla syöttödatalla voidaan tehdä algoritmin laskemista päätöksistä todella arvokkaita asiakkaalle. Kyllä, kaavoista oli monia johdannaisia, mutta varoitimme sinua jo ennen kataa :)
Seuraavassa artikkelissa pääsemme vihdoin siihen, mihin 2 edellistä julkaisua oli tarkoitettu - diskreettiin optimointialgoritmiin.
Valmisteli artikkelin
Roman Shangin, projektiosaston ohjelmoija,
First Bit -yhtiö, Tšeljabinsk
Lähde: will.com