Ebben a cikkben elmondjuk, hogyan oldottuk meg a raktárban lévő szabad cellák hiányának problémáját, és egy diszkrét optimalizálási algoritmust fejlesztettünk ki egy ilyen probléma megoldására. Beszéljünk arról, hogyan „építettük fel” az optimalizálási feladat matematikai modelljét, és milyen nehézségekbe ütköztünk az algoritmus bemeneti adatainak feldolgozása során.
Ha érdekelnek a matematika üzleti alkalmazásai, és nem félsz a képletek merev identitástranszformációitól 5. osztályos szinten, akkor üdvözöljük a macskában!
A cikk hasznos lesz azoknak, akik végrehajtják WMS-rendszerek, raktári vagy termelési logisztikai iparban dolgozók, valamint programozók, akik érdeklődnek a matematika üzleti életben való alkalmazása és a folyamatok optimalizálása iránt egy vállalatnál.
Bevezető rész
Ez a kiadvány folytatja azt a cikksorozatot, amelyben megosztjuk sikeres tapasztalatainkat az optimalizáló algoritmusok raktári folyamatokban történő megvalósításában.
В leírja annak a raktárnak a sajátosságait, ahol megvalósítottuk WMS-rendszert, és azt is elmagyarázza, miért kellett megoldanunk a fennmaradó áruk kötegeinek klaszterezésének problémáját a megvalósítás során WMS-rendszereket, és hogyan csináltuk.
Amikor befejeztük az optimalizálási algoritmusokról szóló cikk megírását, az nagyon nagynak bizonyult, ezért úgy döntöttünk, hogy a felhalmozott anyagot 2 részre osztjuk:
- Az első részben (ebben a cikkben) arról lesz szó, hogyan „építettük fel” a probléma matematikai modelljét, és milyen nagy nehézségekbe ütköztünk az algoritmus bemeneti adatainak feldolgozása és átalakítása során.
- A második részben részletesen megvizsgáljuk az algoritmus nyelvi megvalósítását C + +, számítási kísérletet végzünk, és összefoglaljuk az ilyen „intelligens technológiák” vevő üzleti folyamataiban történő bevezetése során szerzett tapasztalatainkat.
Hogyan kell elolvasni egy cikket. Ha elolvasta az előző cikket, azonnal lépjen a „Létező megoldások áttekintése” fejezetre, ha nem, akkor a megoldandó probléma leírása az alábbi spoilerben található.
A vevő raktárában megoldandó probléma leírása
Szűk keresztmetszetek a folyamatokban
2018-ban befejeztük a megvalósításra váró projektet WMS-rendszerek a cseljabinszki „LD Kereskedelmi Ház” raktárában. Az „1C-Logistics: Warehouse Management 3” terméket 20 munkahelyre vezettük be: üzemeltetők WMS, raktárosok, targoncavezetők. Az átlagos raktár területe körülbelül 4 ezer m2, a cellák száma 5000, az SKU-k száma pedig 4500. A raktárban saját gyártású golyóscsapokat tárolunk, különböző méretű 1 kg-tól 400 kg-ig. A raktárban a készleteket tételesen tárolják, mivel az árukat a FIFO szerint kell kiválasztani.
A raktári folyamat automatizálási sémák tervezése során szembesültünk a nem optimális készlettárolás fennálló problémájával. A daruk tárolásának és lerakásának sajátosságai olyanok, hogy egy egységtároló cella csak egy tételből származó tételeket tartalmazhat (lásd 1. ábra). A termékek naponta érkeznek a raktárba, és minden beérkezés egy külön tétel. Összesen 1 hónapos raktári működés eredményeként 30 külön tétel jön létre, annak ellenére, hogy mindegyiket külön cellában kell tárolni. A termékeket gyakran nem egész raklapokban, hanem darabokban választják ki, és ennek eredményeként a darabkiválasztási zónában sok cellában a következő kép figyelhető meg: egy 1 m3-nél nagyobb térfogatú cellában több daru darab van, a sejttérfogat kevesebb mint 5-10%-át foglalják el.
1. ábra: több darab fényképe egy cellában
Nyilvánvaló, hogy a tárolókapacitást nem használják ki optimálisan. A katasztrófa mértékének elképzeléséhez számokat tudok közölni: átlagosan 1-3 ilyen cella van, amelyek térfogata meghaladja az 100 m300-t, „minimális” egyenlegekkel a raktár működésének különböző időszakaiban. Mivel a raktár viszonylag kicsi, a raktári forgalmas időszakokban ez a tényező „szűk keresztmetszetté” válik, és nagymértékben lelassítja az átvétel és a kiszállítás raktári folyamatait.
Probléma megoldási ötlet
Felmerült egy ötlet: a legközelebbi dátummal rendelkező maradékokat egyetlen tételre kell csökkenteni, és az egységes tételben lévő maradékokat tömören egy cellába, vagy többbe kell helyezni, ha az egyikben nincs elég hely a teljes mennyiségű maradékot. Az ilyen „tömörítés” példája a 2. ábrán látható.
2. ábra. A sejtekben lévő maradékok tömörítésének sémája
Ez lehetővé teszi, hogy jelentősen csökkentse az elfoglalt raktárterületet, amelyet az új áruk elhelyezésére használnak majd. Olyan helyzetben, amikor a raktári kapacitás túlterhelt, egy ilyen intézkedés rendkívül szükséges, különben egyszerűen nem lesz elegendő szabad hely az új áruk befogadására, ami a raktári elhelyezési és feltöltési folyamatok leállásához vezet, és ennek következtében az átvétel és a szállítás leállításához. Korábban, a WMS rendszer bevezetése előtt egy ilyen műveletet manuálisan hajtottak végre, ami nem volt hatékony, mivel a cellákban a megfelelő egyenlegek keresésének folyamata meglehetősen hosszú volt. Most, a WMS rendszer bevezetésével úgy döntöttünk, hogy automatizáljuk a folyamatot, felgyorsítjuk és intelligenssé tesszük.
Az ilyen probléma megoldásának folyamata 2 szakaszra oszlik:
- az első szakaszban a tömörítéshez közeli kötegcsoportokat találunk (ez a feladat );
- a második szakaszban minden tételcsoportra kiszámítjuk a maradék áruk legtömörebb elhelyezését a cellákban.
Jelen cikkünkben az algoritmus második szakaszára fogunk összpontosítani.
Meglévő megoldások áttekintése
Mielőtt rátérnénk az általunk kidolgozott algoritmusok ismertetésére, érdemes röviden áttekinteni a piacon már létező rendszereket. WMS, amelyek hasonló optimális tömörítési funkcionalitást valósítanak meg.
Először is meg kell jegyezni az „1C: Enterprise 8. WMS Logistics. Raktárkezelés 4", amely az 1C tulajdonában van és a negyedik generációhoz tartozik WMS-az AXELOT által fejlesztett rendszerek. Ez a rendszer tömörítési funkcionalitást igényel, amelynek célja, hogy a különböző termékmaradványokat egyetlen közös cellában egyesítse. Érdemes megemlíteni, hogy a tömörítési funkcionalitás egy ilyen rendszerben más lehetőségeket is tartalmaz, például az áruk cellákban való elhelyezésének korrigálását az ABC osztályok szerint, de ezeken nem térünk ki.
Ha elemzi az 1C: Enterprise 8. WMS Logistics rendszer kódját. Raktárkezelés 4" (amely a funkcionalitás ezen részében van nyitva), a következőket vonhatjuk le. A maradék tömörítési algoritmus meglehetősen primitív lineáris logikát valósít meg, és szó sem lehet „optimális” tömörítésről. Természetesen nem rendelkezik a pártok csoportosításáról. Több ügyfél, akinél ilyen rendszert telepítettek, panaszkodtak a tömörítési tervezés eredményeire. Például a gyakorlatban gyakran a tömörítés során a következő helyzet fordult elő: 100 db. A tervek szerint a megmaradt árukat egyik cellából a másik cellába helyezik át, ahol 1 db található. árukat, bár időfelhasználás szempontjából optimális ennek az ellenkezője.
Ezenkívül számos külföldi országban deklarálják a cellákban maradó áruk tömörítésének funkcionalitását. WMS-rendszereket, de sajnos nincs valódi visszajelzésünk az algoritmusok hatékonyságáról (ez üzleti titok), még kevésbé a logikájuk mélységéről (tulajdonos zárt forráskódú szoftver), így nem tudjuk megítélni.
Keresse meg a probléma matematikai modelljét
Ahhoz, hogy egy probléma megoldására jó minőségű algoritmusokat tervezhessünk, először egyértelműen matematikailag kell megfogalmazni ezt a problémát, amit meg is fogunk tenni.
Sok sejt van , amelyek egyes áruk maradványait tartalmazzák. A továbbiakban az ilyen sejteket donorsejteknek nevezzük. Jelöljük a cellában lévő áru mennyisége $.
Fontos elmondani, hogy egy tételből csak egy termék, vagy több, korábban egy klaszterbe egyesített tétel (olvassa el: ), ami az áruk tárolásának és tárolásának sajátosságaiból adódik. A különböző termékeknek vagy különböző kötegcsoportoknak saját külön tömörítési eljárást kell futtatniuk.
Sok sejt van , amelybe potenciálisan donorsejtekből származó maradványok helyezhetők el. Az ilyen cellákat a továbbiakban tárolócelláknak nevezzük. Ezek lehetnek szabad sejtek a raktárban vagy donor sejtek egy fajtából . Mindig bőven egy részhalmaz .
Minden egyes cellához sokaktól Kapacitáskorlátozásra került sor , dm3-ben mérve. Egy dm3 egy 10 cm-es oldalú kocka, a raktárban tárolt termékek meglehetősen nagyok, így ebben az esetben egy ilyen diszkretizálás bőven elegendő.
Adott a legrövidebb távolságok mátrixa méterben az egyes cellák között Ahol и halmazokhoz tartoznak и volt.
Jelöljük az áruk cellából történő kiszállításának „költségei”. egy sejtbe . Jelöljük konténer kiválasztásának „költségei”. hogy más sejtekből származó maradványokat mozgassanak belé. Hogyan és milyen mértékegységekben számítják ki az értékeket и tovább vizsgáljuk (lásd a bemeneti adatokat előkészítő részt), egyelőre elég annyit mondani, hogy ezek az értékek egyenesen arányosak lesznek az értékekkel и volt.
Jelöljük azzal olyan változó, amely 1-et vesz fel, ha a maradék a cellából származik konténerbe került , egyébként pedig 0. Jelöljük azzal egy olyan változó, amely 1 értéket vesz fel, ha a tároló tartalmazza a fennmaradó árukat, és 0 egyébként.
A feladat leírása a következő: annyi konténert kell találnod és így a donorsejteket „csatlakoztassa” a tárolósejtekhez a funkció minimalizálása érdekében
korlátozások alatt
Összességében a probléma megoldásának kiszámításakor arra törekszünk, hogy:
- először is a tárolási kapacitás megtakarítása érdekében;
- másodsorban a raktárosok idejét takarítsuk meg.
Az utolsó korlátozás azt jelenti, hogy nem szállíthatunk árut olyan konténerbe, amelyet nem mi választottunk, és ezért nem „merült költség” a kiválasztás miatt. Ez a korlátozás azt is jelenti, hogy a cellákból a konténerbe szállított áru mennyisége nem haladhatja meg a konténer kapacitását. Egy probléma megoldása alatt konténerek halmazát értjük és módszerek donor sejtek konténerekhez való rögzítésére.
Az optimalizálási probléma ezen megfogalmazása nem új keletű, és a múlt század 80-as évei óta sok matematikus tanulmányozta. A külföldi szakirodalomban 2 optimalizálási feladat van egy megfelelő matematikai modellel: и (a feladatok különbségeiről később lesz szó). Érdemes elmondani, hogy a matematikai szakirodalomban ilyen két optimalizálási probléma megfogalmazása a vállalkozások helyszíni elhelyezkedése alapján fogalmazódik meg, innen ered a „Facility Location” elnevezés. Ez nagyrészt tisztelgés a hagyomány előtt, hiszen a múlt század 50-es éveiben először jelentkezett ilyen kombinatorikus problémák megoldása a logisztika területéről, leginkább a hadiipari szektorból. A vállalkozások elhelyezkedését tekintve az ilyen feladatok a következőképpen fogalmazódnak meg:
- Véges számú város van, ahol potenciálisan lehetséges termelő vállalkozásokat elhelyezni (a továbbiakban: termelő városok). Minden gyártóvárosra meghatározzák a vállalkozás megnyitásának költségeit, valamint az ott megnyitott vállalkozás termelési kapacitásának korlátozását.
- A városoknak véges halmaza van, ahol az ügyfelek ténylegesen tartózkodnak (a továbbiakban ügyfélvárosok). Minden ilyen ügyfélváros esetében meg van határozva a termékek iránti kereslet mennyisége. Az egyszerűség kedvéért feltételezzük, hogy csak egy termék van, amelyet a vállalkozások állítanak elő és a vásárlók fogyasztanak el.
- Minden város-gyártó és város-ügyfél pár esetében meg van adva a szállítási költségek értéke a szükséges mennyiségű terméknek a gyártótól a megrendelőhöz való eljuttatásához.
Meg kell találnia, mely városokban nyithat vállalkozást, és hogyan köthet ügyfeleket az ilyen vállalkozásokhoz, hogy:
- A vállalkozások nyitásának összköltsége és a szállítási költség minimális volt;
- A nyitott vállalkozáshoz rendelt vevők kereslete nem haladta meg az adott vállalkozás termelési kapacitását.
Most érdemes megemlíteni az egyetlen különbséget e két klasszikus probléma között:
- Egy forrású kapacitású létesítmény helymeghatározási probléma – a klienst csak egy nyitott létesítményből látják el;
- Több forrású kapacitású létesítmény helymeghatározási probléma – az ügyfél egyszerre több nyitott létesítményből is ellátható.
A két probléma közötti ilyen különbség első pillantásra jelentéktelen, valójában azonban az ilyen problémák teljesen eltérő kombinatorikus struktúrájához, és ennek következtében teljesen eltérő megoldási algoritmusokhoz vezet. A feladatok közötti különbségeket az alábbi ábra szemlélteti.
3. ábra. a) Több forrású kapacitású létesítmény helymeghatározási probléma
3. ábra. b) Egyforrásos kapacitású létesítmény helymeghatározási probléma
Mindkét feladat -nehéz, vagyis nincs olyan egzakt algoritmus, ami a bemeneti adatok méretének időpolinomjában megoldana egy ilyen problémát. Egyszerűbben fogalmazva, a probléma megoldására szolgáló összes pontos algoritmus exponenciális időn belül működik, bár talán gyorsabban, mint a lehetőségek teljes keresése. A feladat óta -nehéz, akkor csak hozzávetőleges heurisztikát veszünk figyelembe, vagyis olyan algoritmusokat, amelyek következetesen az optimálishoz nagyon közeli megoldásokat számítanak ki, és elég gyorsan működnek. Ha érdekel egy ilyen feladat, itt talál egy jó áttekintést oroszul.
Ha áttérünk a cellákban lévő áruk optimális tömörítésének problémájára, akkor:
- kliens városok donorsejtek a maradék áruval,
- gyártó városok – konténercellák , amelybe a többi cellából származó maradékokat kell elhelyezni,
- szállítási költségek – időköltségek raktáros, hogy az áru mennyiségét a donor cellából mozgassa konténer cellába ;
- vállalkozás megnyitásának költségei - konténer kiválasztásának költségei , egyenlő a tárolócella térfogatával , megszorozva egy bizonyos együtthatóval a szabad mennyiségek megtakarításához (az együttható értéke mindig > 1) (lásd a bemeneti adatok előkészítése című részt).
A probléma jól ismert klasszikus megoldásaival való analógia felrajzolása után meg kell válaszolni egy fontos kérdést, amelytől függ a megoldási algoritmus architektúrájának megválasztása: a maradékok áthelyezése a donor cellából csak egybe lehetséges. és csak egy tároló (Single-Source), vagy lehetséges a maradékok több konténercellába áthelyezése (Multi-Source)?
Érdemes megjegyezni, hogy a gyakorlatban a probléma mindkét megfogalmazása megtörténik. Az alábbiakban bemutatjuk az összes ilyen beállítás előnyeit és hátrányait:
| Problémás változat | Az opció előnyei | Az opció hátrányai |
|---|---|---|
| Egyetlen forrás | Az árumozgatási műveletek a probléma ezen változatával kiszámítva:
|
|
| Többforrás | A probléma ezen verziójával számított tömörítések általában 10-15%-kal kompaktabbak az „Egyetlen forrás” opcióval számított tömörítésekhez képest. De azt is megjegyezzük, hogy minél kisebb a maradékok száma a donorsejtekben, annál kisebb a különbség a tömörségben | Az árumozgatási műveletek a probléma ezen változatával kiszámítva:
|
1. táblázat: Az egyforrású és a többforrású opciók előnyei és hátrányai.
Mivel a Single-Source opciónak több előnye van, és figyelembe véve azt a tényt is, hogy minél kisebb a maradékok száma a donorsejtekben, annál kisebb a különbség a kompressziós tömörség mértékében a probléma mindkét változatára számítva, a választásunk a következőre esett: a Single-Source opciót.
Érdemes elmondani, hogy a Multi-Source opció megoldása is megtörténik. Számos hatékony algoritmus létezik a megoldására, amelyek többsége számos szállítási probléma megoldására vezethető vissza. Nemcsak hatékony algoritmusok léteznek, hanem elegánsak is, pl.
Bemeneti adatok előkészítése
Mielőtt elkezdené elemezni és kidolgozni egy problémamegoldó algoritmust, el kell dönteni, hogy milyen adatokat és milyen formában adjuk meg bemenetként. A donorcellákban maradó áruk mennyiségével és a konténercellák kapacitásával nincs probléma, hiszen ez triviális - az ilyen mennyiségeket m3-ben fogják mérni, de a konténercella használatának költségeivel és a költözési költségmátrixszal nem minden. olyan egyszerű!
Nézzük először a számítást árumozgatás költségei a donor sejtből a konténersejtbe. Először is el kell dönteni, hogy milyen mértékegységekben számoljuk a mozgás költségeit. A két legkézenfekvőbb lehetőség a méter és a másodperc. Nincs értelme az utazási költségeket „tiszta” méterben számolni. Mutassuk meg ezt egy példával. Hagyja a sejtet az első szinten, cellában található 30 méterrel eltávolítva és a második szinten található:
- Költözés innen в drágább, mint elköltözni в , mivel a második szintről (1,5-2 méterrel a padlótól) könnyebb lemenni, mint a másodikra felmenni, bár a távolság ugyanaz lesz;
- Mozgatás 1 db. áruk a sejtből в Könnyebb lesz, mint 10 darabot mozgatni. ugyanaz a termék, bár a távolság azonos lesz.
Jobb, ha a költözési költségeket másodpercekben veszi figyelembe, mivel ez lehetővé teszi mind a szintek közötti különbség, mind a mozgott áruk mennyiségének különbségét. Ahhoz, hogy a mozgatási költséget másodpercben elszámolhassuk, a mozgási műveletet elemi komponensekre kell bontanunk, és minden elemi komponens végrehajtásához időmérést kell végeznünk.
Engedd ki a cellából mozog PC. áru konténerben . enged – egy dolgozó átlagos mozgási sebessége a raktárban, m/s-ban mérve. Hadd и – az egyszeri műveletek átlagos sebességét 4 dm3-nek megfelelő árumennyiségre veszik, illetve helyezik el (az az átlagos mennyiség, amelyet a munkavállaló egyszerre vesz el a raktárban műveletek végrehajtása során). Hadd и azon cellák magassága, ahonnan a take és put műveleteket hajtják végre. Például az első szint (padló) átlagos magassága 1 m, a második szint 2 m stb. Ekkor az áthelyezési művelet teljes időtartamának kiszámítására szolgáló képlet a következő következő:
A 2. táblázat az egyes elemi műveletek végrehajtási idejére vonatkozó statisztikákat mutatja, amelyeket a raktári alkalmazottak gyűjtenek össze, figyelembe véve a tárolt áruk sajátosságait.
| a művelet neve | Kijelölés | Átlagos |
|---|---|---|
| A raktárban mozgó munkás átlagos sebessége | |
1,5 m/s |
| Egy művelet átlagos sebessége (4 dm3 terméktérfogat esetén) | |
2,4 másodperc |
2. táblázat: A raktári műveletek befejezésének átlagos ideje
Elhatároztuk a költözési költségek számítási módját. Most ki kell találnunk, hogyan kell kiszámítani konténercella kiválasztásának költségei. Itt minden sokkal, de sokkal bonyolultabb, mint a költözési költségeknél, mert:
- először is, a költségeknek közvetlenül a sejt térfogatától kell függniük - a donorsejtekből átvitt maradék maradék mennyiségét jobb elhelyezni egy kisebb térfogatú tartályban, mint egy nagy tartályban, feltéve, hogy ez a térfogat teljesen belefér mindkét tartályba. Így a konténerek kiválasztásának összköltségének minimalizálásával arra törekszünk, hogy a kiválasztási területen „szűkös” szabad tárolókapacitást megtakarítsunk az áruk cellákba helyezésének későbbi műveleteinek elvégzéséhez. A 4. ábra szemlélteti a maradékanyagok nagy és kis konténerekbe történő átvitelének lehetőségeit, valamint ezeknek a szállítási lehetőségeknek a következményeit a későbbi raktári műveletekben.
- másodszor, mivel az eredeti probléma megoldásánál pontosan minimalizálni kell az összköltséget, és ez mind a költöztetés, mind a konténerválasztás költségeinek összege, akkor a köbméterben mért cellatérfogatokat valahogy másodpercekhez kell kapcsolni, ami korántsem triviális.
Rizs. 4. Lehetőségek a maradékok különböző űrtartalmú konténerekbe történő mozgatására.
A 4. ábrán pirossal látható azon maradék mennyisége, amely a következő áruk elhelyezésének második szakaszában már nem fér be a konténerbe.
Ez segít összekapcsolni a konténer kiválasztásához szükséges köbméteres költségeket a probléma kiszámított megoldásához szükséges következő követelmények áthelyezési költségével:
- Szükséges, hogy az adományozó edényből az egyenlegeket a konténeres edénybe kell vinni, ha ez csökkenti a terméket tartalmazó tárolóedények számát.
- Meg kell tartani az egyensúlyt a konténerek térfogata és a költözésre fordított idő között: ha például egy probléma új megoldásában a korábbi megoldáshoz képest nagy a térfogatnövekedés, de kicsi az időveszteség. , akkor új lehetőséget kell választani.
Kezdjük az utolsó feltétellel. A félreérthető „egyenleg” szó tisztázása érdekében felmérést végeztünk a raktári alkalmazottak körében, hogy megtudjuk a következőket. Legyen egy térfogatú tárolócella , amelyhez a donorsejtekből megmaradt áruk mozgása hozzá van rendelve, és az ilyen mozgás teljes ideje egyenlő . Legyen több alternatív lehetőség ugyanabból a donorsejtekből származó, azonos mennyiségű áru más konténerekbe helyezésére, ahol minden elhelyezésnek saját becslése van Ahol < и Ahol >.
Felteszik a kérdést: mi a minimális hangerőnövekedés elfogadható, adott időveszteségi érték mellett ? Magyarázzuk meg egy példával. Kezdetben a maradványokat egy 1000 dm3 (1 m3) térfogatú tartályba kellett volna helyezni, és az átviteli idő 70 másodperc volt. Lehetőség van a maradékok másik 500 dm3 térfogatú és 130 másodperces tartályba helyezésére. Kérdés: készek vagyunk-e további 60 másodpercet a raktáros idejéből az áru mozgatására fordítani, hogy 500 dm3 szabad térfogatot megspóroljunk? A raktári alkalmazottak körében végzett felmérés eredményei alapján az alábbi diagramot állítottuk össze.
Rizs. 5. A minimálisan megengedhető térfogat-megtakarítás függésének diagramja a működési idő különbségének növekedésétől
Vagyis ha a plusz időköltség 40 másodperc, akkor csak akkor vagyunk készek rákölteni, ha a térfogatnövekedés legalább 500 dm3. Annak ellenére, hogy a függésben van egy kis nemlinearitás, a további számítások egyszerűsége érdekében feltételezzük, hogy a mennyiségek közötti függés lineáris, és az egyenlőtlenség írja le
Az alábbi ábrán az áruk konténerekbe helyezésének alábbi módjait vesszük figyelembe.
Rizs. 6. (a) lehetőség: 2 tartály, teljes térfogat 400 dm3, teljes idő 150 mp.
Rizs. 6. (b) lehetőség: 2 tartály, teljes térfogat 600 dm3, teljes idő 190 mp.
Rizs. 6. (c) lehetőség: 1 tartály, teljes térfogat 400 dm3, teljes idő 200 mp.
Az (a) lehetőség a konténerek kiválasztásához előnyösebb, mint az eredeti opció, mivel az egyenlőtlenség teljesül: (800-400)/10>=150-120, ami azt jelenti, hogy 40 >= 30. A (b) lehetőség kevésbé előnyös, mint az eredeti opció , mivel az egyenlőtlenség nem áll fenn: (800-600)/10>=190-150, amiből következik, hogy 20 >= 40. De a (c) opció nem illik bele ilyen logikába! Tekintsük ezt a lehetőséget részletesebben. Egyrészt a (800-400)/10>=200-120 egyenlőtlenség, ami azt jelenti, hogy a 40 >= 80 egyenlőtlenség nem teljesül, ami arra utal, hogy a térfogatnövekedés nem ér meg ekkora időveszteséget.
Másrészt ebben a (c) opcióban nemcsak a teljes foglalt térfogatot csökkentjük, hanem a foglalt cellák számát is, ami az első két fontos követelmény közül a fent felsorolt problémák kiszámítható megoldásához. Nyilvánvalóan ahhoz, hogy ez a követelmény elkezdődjön teljesülni, szükség van egy pozitív állandó hozzáadására az egyenlőtlenség bal oldalához. , és egy ilyen állandót csak akkor kell hozzáadni, ha a konténerek száma csökken. Hadd emlékeztessük erre 1-gyel egyenlő változó, amikor a tároló kiválasztva, és 0, ha tároló nincs kiválasztva. Jelöljük – sok tartály a kezdeti megoldásban és – sok konténer az új megoldásban. Általában az új egyenlőtlenség így fog kinézni:
A fenti egyenlőtlenséget átalakítva azt kapjuk
Ez alapján van egy képletünk a teljes költség kiszámításához valami megoldás a problémára:
De most felvetődik a kérdés: milyen értéke legyen egy ilyen állandónak? ? Értékének nyilvánvalóan elég nagynak kell lennie ahhoz, hogy a probléma megoldásának első követelménye mindig teljesüljön. Természetesen a konstans értéke 103 vagy 106 is lehet, de én szeretném elkerülni az ilyen „bűvös számokat”. Ha figyelembe vesszük a raktári műveletek végzésének sajátosságait, akkor több megalapozott számszerű becslést is kiszámíthatunk egy ilyen állandó értékére.
enged – az egyik ABC zóna raktári cellái közötti maximális távolság, esetünkben 100 m – egy raktárban lévő konténercella maximális térfogata, esetünkben 1000 dm3.
Az érték kiszámításának első módja . Tekintsünk egy olyan helyzetet, amikor az első szinten 2 konténer van, amelyekben az áruk már fizikailag elhelyezkednek, vagyis maguk is donorsejtek, és az áruk ugyanazon cellákba való áthelyezésének költsége természetesen 0. szükséges ilyen értéket találni az állandóra , amelyben előnyös lenne az 1-es tárolóból a maradékot mindig a 2-es tárolóba mozgatni. Az értékek behelyettesítése и A fent megadott egyenlőtlenségben a következőket kapjuk:
amiből az következik
Ha behelyettesítjük az elemi műveletek végrehajtásának átlagos idejét a fenti képletbe, azt kapjuk
Az érték kiszámításának második módja . Nézzünk egy olyan helyzetet, ahol van donorsejtek, amelyekből az árut az 1-es konténerbe tervezik. Jelöljük – távolság a donor sejttől Az 1-es konténerhez. Van még a 2-es konténer, amely már tartalmaz árukat, és amelynek térfogata lehetővé teszi, hogy el tudja helyezni az összes többi részét sejteket. Az egyszerűség kedvéért feltételezzük, hogy a donorsejtekből a konténerekbe szállított áruk mennyisége azonos és egyenlő . Meg kell találni az állandó ilyen értékét , amelyben az összes maradék elhelyezése a cellákat a 2. tárolóba helyezni mindig jövedelmezőbb lenne, mint a különböző tartályokba helyezni:
A kapott egyenlőtlenség átalakítása
A mennyiség értékének „erősítése” érdekében , tegyük fel = 0. A raktári egyenlegek tömörítési eljárásában általában 10 cella vesz részt. A mennyiségek ismert értékeit behelyettesítve a következő állandó értéket kapjuk
Minden opcióhoz a legnagyobb számított értéket vesszük, ez lesz a mennyiség értéke az adott raktári paraméterekhez. Most a teljesség kedvéért írjuk le az összköltség kiszámításának képletét valami megvalósítható megoldásért :
Most végül is titáni erőfeszítések A bemeneti adatok átalakításával azt mondhatjuk, hogy minden bemeneti adat a kívánt formára konvertálódott, és készen áll az optimalizálási algoritmusban való használatra.
Következtetés
A gyakorlat azt mutatja, hogy az algoritmus bemeneti adatainak előkészítésének és átalakításának bonyolultságát és fontosságát gyakran alábecsülik. Ebben a cikkben kifejezetten erre a szakaszra fordítottunk nagy figyelmet, hogy megmutassuk, csak a jó minőségű és intelligensen előkészített bemeneti adatok teszik igazán értékessé az algoritmus által kiszámított döntéseket az ügyfél számára. Igen, sok képlet származéka volt, de már a kata előtt figyelmeztettünk :)
A következő cikkben végre elérkezünk ahhoz, amire a 2 korábbi publikációt szánták - egy diszkrét optimalizáló algoritmusra.
Elkészítette a cikket
Roman Shangin, a projektrészleg programozója,
First Bit cég, Cseljabinszk
Forrás: will.com