Diskreetne matemaatika WMS-ile: kaupade kokkusurumise algoritm rakkudes (1. osa)

Artiklis räägime, kuidas lahendasime lao vaba ruumi puudumise probleemi ja arendasime diskreetse optimeerimise algoritmi sellise ülesande lahendamiseks. Jagame ka, kuidas me «ehitasime» optimeerimise ülesande matemaatilise mudeli ning milliste probleemidega ootamatult kokku puutusime andmete töötlemisel algoritmi jaoks.

Kui teid huvitavad matemaatika rakendused äris ning te ei karda keerulisi valemite teisendusi 5. klassi tasemel, siis olete teretulnud allapoole!

Artikkel on kasulik neile, kes rakendavad WMS-süsteeme, töötavad lao või tootmislogistika valdkonnas, samuti programmeerijatele, kes on huvitatud matemaatika rakendustest äris ja protsesside optimeerimisest ettevõttes.

Sissejuhatav osa

See publikatsioon jätkab artiklite seeriat, kus jagame oma edukaid kogemusi optimeerimise algoritmide rakendamisel lao protsessides.

V eelnevas artiklis Kus kirjeldatakse ladude spetsiifikat, kuhu oleme rakendanud WMS-süsteemi, ning räägitakse, miks oli meil vaja lahendada kauba partiide klasterdamise ülesanne rakendamise käigus. WMS-süsteemid ja kuidas me seda tegime.

Kui lõpetasime optimeerimise algoritmide kohta artikli kirjutamise, osutus see väga pikaks, seetõttu otsustasime kogutud materjali jagada kaheks osaks:

• Esimeses osas (see artikkel) räägime sellest, kuidas me „ehitasime“ üles matemaatilise mudeli ülesande jaoks ja milliste suurte raskustega meil ootamatult tuli silmitsi seista sisendandmete töötlemisel ja muutmisel algoritmi jaoks.
• Teises osas vaatleme üksikasjalikult algoritmi rakendust keeles C++, teeme arvutuskatse ja kokkuvõtte kogemusest, mille saime nende „intellektuaaltehnoloogiate“ rakendamise käigus kliendi äri protsessidesse.

Kuidas artiklit lugeda. Kui olete eelmist artiklit lugenud, võite kohe liikuda peatükki „Olemasolevate lahenduste ülevaade“, kui ei, siis on lahendatava probleemi kirjeldus spoileris allpool.

Kliendi laos lahendatav probleem

Protsesside kitsaskoht

2018. aastal tegime projekti WMS-süsteemi juurutamiseks laos „Kaubamaja „LD““ Tšeljabinski linnas. Juhtisime toodet „1C-Logistika: Laohaldus 3“ 20 töökohta: operaatorid. WMS, laoajad, tõstukijuhid. Lao pindala on umbes 4000 m², lao üksuste arv 5000 ja SKUde arv 4500. Laos hoitakse erinevate mõõtudega kuulkraane kaaluga alates 1 kg kuni 400 kg, mis on toodetud enda tootmisüksuses. Laos hoitavad varud on partiide kaupa, kuna on vajalik kaupade valimine FIFO põhimõtte järgi.

Automatiseerimise skeemide projekteerimise käigus seisime silmitsi olemasoleva probleemi – varude mittetegemisel. Kraanide hoiustamise ja paigutamise iseloom on selline, et ühes tükihoiu ruumis võib olla ainult ühe partii nomenklatuur (vt joonis 1). Toode saabub laost iga päev ja iga saabumine on eraldi parti. Seega, kuu jooksul laos töö käigus luuakse 30 eraldi partiid, samas kui igaüks peab olema eraldiseisvas ruumis. Kauba valimine toimub sageli mitte täispakkides, vaid tükikaupa, ning seetõttu on tükivaliku alal paljudes ruumides selline pilt: ruumis, mille maht on üle 1m³, on mitu kraani, mis võtab alla 5-10% ruumi mahust.

Joonis 1. Foto mitmest tükist ruumis

Käimas on ebatõhus laopindade kasutamine. Probleemi ulatust illustreerivad numbrid: keskmiselt on selliseid üle 1m³ suuruseid lahtrid, kus on "pisikesed" jäägid, erinevatel ajaperioodidel 100 kuni 300. Kuna laod on suhteliselt väikesed, muutub see tegur laodo laadimisperioodidel "kitsaskohaks", mis aeglustab oluliselt vastuvõtu ja väljastamise protsesse.

Probleemi lahendamise idee

Tuli idee: jäägid, mille parim enne kuupäev on kõige lähemal, koondada ühte ainsasse partiisse ja selliseid jäätmeid koos ühtse partii peale paigutada kompaktselt ühes lahtris või mitmes, kui ühes ei piisa kogu jääki mahutamiseks. Sellise "kokkusurumise" näidis on näidatud joonisel 2.

Joonis 2. Lahtrite jääkide kokkusurumise skeem

See võimaldab oluliselt vähendada ladustamisruumi, mida kasutatakse uue kauba paigutamiseks. Situatsioonis, kus ladustamisvõimsused on ülekoormatud, on selline meede äärmiselt vajalik; vastasel juhul ei pruugi vaba ruumi uue kauba paigutamiseks piisavalt jääda, mis toob kaasa ladustamisprotsesside seiskumise ning seega ka vastuvõtmise ja laadimise peatumise. Enne WMS-süsteemide rakendamist tehti selline toiming käsitsi, mis oli ebaefektiivne, kuna sobivate jääkide leidmine rakkudest oli piisavalt ajamahukas. Nüüd, pärast WMS-süsteemi rakendamist, otsustati protsess automatiseerida, kiirendada ja muuta see nutikaks.

Selle ülesande lahendamise protsess jaguneb kaheks etapiks:

• esimeses etapis leiame kuupäeva poolest lähedased partiide rühmad tihendamiseks (see ülesanne on pühendatud eelmine artikkel);
• teises etapis arvutame iga partiide rühma kohta maksimaalselt kompaktse jääkide paigutuse rakkudesse.

Käesolevas artiklis käsitleme algoritmi teist etappi.

Olemasolevate lahenduste ülevaade

Enne kui liigume edasi meie välja töötatud algoritmide kirjeldamise juurde, tasub teha kiire ülevaade turul juba olemasolevatest süsteemidest WMS, milles on rakendatud sarnast optimaalse tihendamise funktsionaalsust.

Eelkõige tuleb märkida toodet „1C: Ettevõte 8. WMS Logistika. Laohaldus 4“, mis kuulub ja mida levitab ettevõte 1C ning kuulub neljanda põlvkonna WMS-süsteemide hulka, mille on välja töötanud ettevõte AXELOT. Antud süsteemis on välja kuulutatud tihendamise funktsionaalsus, mille eesmärk on organiseerida dispergeeritud kaubajäägid ühte üldisesse rakku. Tuleb märkida, et sellise süsteemi tihendamise funktsionaalsus sisaldab veel ka muid võimalusi, näiteks kaupade paigutamise parandamist rakkudes vastavalt nende ABC klassidele, kuid neid me siin käsitlema ei hakka.

Analüüsides süsteemi "1C: Ettevõte 8. WMS Logistika. Laohaldus 4" koodi (mis on selles funktsionaalsuse osas avatud), võib järeldada järgmist. Jääkide kokkutõmbamise algoritm rakendab üsna primitiivset lineaarset loogikat ning mingist "optimaalsest" kokkutõmbamisest ei saa olla juttu. Loomulikult ei ole ta ette nähtud partiide klasterdamiseks. Mitmed kliendid, kellel selline süsteem on rakendatud, on kaebanud kokkutõmbamise planeerimise tulemuste üle. Näiteks praktikas juhtus tihti, et 100 tk kaupa ühest rakkust plaanitakse teisaldada teise rakkusse, kus on 1 tk kaupa, kuigi ajakulude optimaalsuse seisukohalt oleks mõistlik teha vastupidi.

Samuti on kaupadest jääkide kokkutõmbamise funktsionaalsus välja kuulutatud paljudes välismaistes WMS-süsteemides, kuid kahjuks ei ole meil olemas reaalseid ülevaateid algoritmide tõhususest (see on ärisaladus), ega ka mingit ettekujutust nende loogika sügavusest (patenteeritud tarkvara suletud koodiga), seetõttu ei saa me hinnata.

Matemaatilise mudeli otsing

Kvaliteetsete algoritmide väljatöötamiseks ülesande lahendamiseks tuleb esmalt see ülesanne selgelt matemaatiliselt formuleerida, mida me ka teeme.

On olemas palju rakke , milles asuvad teatud kauba jäägid. Edasi nimetame neid rakke doonoriakendeks. Märgime kauba maht, mis asub rakus $.

Oluline on öelda, et kompressiooniprotsessis võib osaleda ainult ühe partii kaup või mitu partiid, mis on eelnevalt rühmitatud klastrisse (loe eelmist artiklit), mis on tingitud kaupade ladustamise ja paigutamise eripärast. Erinevate kaupade või erinevate partiide klastrite jaoks tuleb käivitada oma eraldi kompressiooniprotsess.

On olemas palju rakke , kuhu võivad potentsiaalselt paigutuda doonorrakkudest jäägid. Edasi nimetame neid rakke konteinerirakkudeks. Need võivad olla nii vabade rakkudena laos kui ka doonorrakkudena erinevatest . Alati on hulk alamhulk .

Iga rakk hulgas on määratud maht piirangud , mõõdetuna dm³-des. Üks dm³ on kuubik, mille kõik küljed on 10 cm. Selles kontekstis on ladustatava kauba suurus piisav, seega selline diskreetsus on täiesti piisav.

On määratud lühi-vahemaa maatriks meetrites iga kahe lahtri vahel , kus ja kuuluvad komplektidesse ja vastavalt.

Määratleme kauba liikumise "kulud" lahtrist lahtrisse . Määratleme "kulud" konteineri valimiseks kauba ülejääkide teisaldamiseks teistest lahtritest. Kuidas ja millistes mõõtühikutes need väärtused ja arvutatakse hiljem (vt peatükk sisendandmete ettevalmistamine), kuid praegu piisab öelda, et need suurused on otseselt proportsionaalsed ja vastavalt.

Määratleme läbi muutuja, mis omab väärtust 1, kui lahtri osad liiguvad konteinerisse , ja 0 vastupidisel juhul. Määratleme läbi muutuja, mis omab väärtust 1, kui konteiner sisaldab kaupa, ja 0 vastupidisel juhul.

Probleem on seatud nii: on vajalik leida selline konteinerite kogum ja seega „kinni siduda“ annetavad lahtrid konteinerlahtritega, et minimeerida funktsioon

piirangutega

Kokkuvõttes püüdleme ülesande lahendamise käigus järgmiste eesmärkide poole:

• esiteks, säästa laopinda;
• teiseks, säästa lao töötajate aega.

Viimane piirang tähendab, et me ei saa tooteid ümber paigutada konteinerisse, mida ei ole valitud, ja seega ei ole ka «kulutusi» selle valimise jaoks. Lisaks tähendab see piirang, et rakkudest konteinerisse paigutatavate kaupade maht ei tohi ületada konteineri mahutavust. Ülesande lahendust mõistame kui konteinerite kogumit ja viise, kuidas kinnitada doonorrakkude rakud konteineritega.

Selline optimeerimise ülesande sõnastus ei ole uus ja seda on uurinud paljud matemaatikud juba 80ndate aastate algusest. Välismaises kirjanduses on kaks optimeerimise ülesannet sobiva matemaatilise mudeliga: Single-Source Capacitated Facility Location Problem ja Multi-Source Capacitated Facility Location Problem (millestki ülesannete erinevustest räägime hiljem). Tuleb öelda, et matemaatilises kirjanduses formuleeritakse nende kahe optimeerimisülesande määratlemine ettevõtete asukoha kontekstis, seetõttu ka nimi «Facility Location». Suures osas on see traditsioon, kuna vajadus nende kombinatoorsete probleemide lahendamiseks tekkis esmakordselt logistika valdkonnast, peamiselt sõjaväe- ja tööstussektorist 20. sajandi 50. aastatel. Ettevõtete asukoha kontekstis formuleeritakse sellised ülesanded järgmiselt:

• On lõpmatu hulk linnu, kus on võimalik paigutada tootmisettevõtteid (edasi linnad-tootjad). Iga linna-tootja kohta on määratud ettevõtte avamise kulud ning piirang avatud ettevõtte tootmisvõimsusele.
• On lõpmatu hulk linnu, kus asuvad tegelikult kliendid (edasi linnad-kliendid). Iga sellise linna-kliendi puhul on määratud nõudmuse maht toote järele. Lihtsuse huvides oletame, et toode, mida tootavad ettevõtted ja mida kliendid tarbivad, on sama.
• Iga valmistaja-kliendi linna paari jaoks on määratud transpordikulud, et tarnida nõutav toote maht tootjalt kliendile.

Tuleb leida, millistes linnades avada ettevõtteid ja kuidas klientide sidumine nende ettevõtetega, et:

• Ettevõtete avamise kogukulud ja transpordikulud oleksid minimaalsed;
• Kliendikäive, mis on seotud mõne avatud ettevõttega, ei ületaks selle ettevõtte tootmisvõimsusi.

Nüüd tasub rääkida ainukesest erinevusest nende kahe klassikalise ülesande vahel:

• Üheahelaline võimekusega rajatise asukohaprobleem – klient saab tarne ühe avatud ettevõtte kaudu;
• Mitme allika võimekusega rajatise asukohaprobleem – klient saab tarne mitmest avatud ettevõttest samal ajal.

See kahe ülesande erinevus näib esmapilgul ebaoluline, kuid tegelikult toob see kaasa täiesti erineva kombinatoorse struktuuri ning seega täiesti erinevad lahendusmeetodid. Ülesannete vahelisi erinevusi illustreeritakse allpool olevas joonises.

Joon.3. a) Mitme allika võimekusega rajatise asukohaprobleem

Joon.3. b) Üheallika piiratud rajatise asukoha probleem

Mõlemad ülesanded -on keerulised, see tähendab, et ei ole olemas täpset algoritmi, mis suudaks sellist ülesannet lahendada polünoomse aja jooksul sisendi suurusest. Lihtsamalt öeldes, kõik täpsed algoritmid selle probleemi lahendamiseks töötavad eksponentsiaalset aega, ehkki võib-olla kiiremini kui täielik kõigi variantide läbiotsimine. Kuna probleem -on keeruline, käsitleme ainult lähenemisviise, see tähendab algoritme, mis arvutavad pidevalt lahendusi, mis on väga lähedased optimaalsele ja töötavad piisavalt kiiresti. Kui sellised ülesanded huvi pakuvad, siis siit leiate hea ülevaate vene keeles.

Kui tõlgime meie kauba optimaalse pakkimise ülesande terminoloogiasse, siis:

• klientide linnad – on donorikonteinerid , millel on ülejäägid,
• tootmislinnad – on konteinerikonteinerid , kuhu eeldatakse, et paigutatakse ülejäägid teistest konteineritest,
• transportimise kulud – on aeg ladustaja jaoks kauba mahu liigutamiseks donorikonteinerist konteinerikonteinerisse ;
• ettevõtte avamise kulud – konteineri valimise kulud , mis mõõdud on võrdsed konteineriraku mahuga , korrutatud teatud vabade mahtude säästufaktoriga (faktor on alati > 1) (vt jaotist sisendi ettevalmistamine).

Pärast analoogia tõmbamist tuntud klassikaliste ülesannete tarnimisega on oluline vastata küsimusele, mis mõjutab algoritmi lahenduse arhitektuuri valikut: kas jääkide üleviimine donorirakust on võimalik ainult ühte konteinerisse (Single-Source) või saab jääke viia mitmesse raku-konteinerisse (Multi-Source)?

Oluline on märkida, et praktikas esinevad mõlemad ülesande seadistused. Allpool toome välja kõik ‘plussid’ ja ‘miinused’ igas seadistuses:

Tabel 1. Single-Source ja Multi-Source variantide eelised ja puudused.

Kuna Single-Source variandi eeliseid on rohkem ja arvestades, et mida vähem on jääke doonor-üksustes, seda väiksem on erinevus kokkusurumise tiheduse osas mõlemas ülesande variandis, siis langetame valiku Single-Source variandi kasuks.

Tasub mainida, et Multi-Source variandi lahendamisel on samuti oma koht. Eksisteerib palju tõhusaid algoritme selle lahendamiseks, millest enamik tugineb mitmete transpordiülesannete lahendamisele. Samuti on olemas mitte ainult tõhusad algoritmid, vaid ka elegantsed, näiteks, siit.

Sisendandmete ettevalmistamine

Enne algoritmi analüüsi ja arendamisega tegelemist tuleb selgitada, milliseid andmeid ja millises vormis me neile edastame. Kaupade jääkide mahtude osas annetäidiku laadijates ja konteinerite mahutsuse osas ei ole probleeme, kuna need on triviaalne – sellised näitajad mõõdetakse m³-des, kuid konteineri kasutamise kulud ja kulude maatriks edasiviimiseks ei ole nii lihtsad!

Alustame kulude arvestus kauba edasiviimiseks annetäidikust konteinerisse. Esiteks tuleb välja selgitada, millistes mõõtühikutes me kulusid arvestame. Kaks kõige ilmsemat varianti on meeter ja sekund. „Puhastes” meetrites ei ole edasiviimise kulude arvestamine mõistlik. Näitame seda näitega. Oletame, et annetäidik asub esimesel tasemel, annetäidik on eemaldatud 30 meetri võrra ja asub teisel tasemel:

• Edasiviimine on ühes kulukam kui edasiviimine ühes , kuna allapoole laskmine teisest tasemest (1,5–2 meetrit põrandast) on kergem kui tõstmine teisele, kuigi kaugus on läbitud sama;
• Üks kaup tuleb kolida annetäidikust ühes on lihtsam kui 10 ühesuguse toote liigutamine, kuigi distantse läbitakse sama palju.

Liigutamise kulusid on parem arvestada sekundites, sest see võimaldab arvestada erinevusi tasandite ja liigutatava kauba koguse vahel. Liigutamise kulude arvestamiseks sekundites peame jaotama liikumise operatsiooni elementaarseteks komponentideks ja mõõtma igasuguse elementaarse komponendi täitmiseks kuluvat aega.

Olgu alusest liigutatakse tk kaupa konteinerisse . Olgu keskmine töötaja liikumise kiirus laos, mõõdetuna m/s. Olgu ja keskmised kiirus, millega ühest kohast teise pannakse vastavalt kauba mahule, mis on 4 dm3 (keskmine maht, mille töötaja laos korraga opereerib). Olgu ja korvi kõrgus, millest operatsioone teha. Näiteks esimese tasandi (põrand) keskmine kõrgus on 1 m, teise tasandi 2 m jne. Siis on valem koguaegade arvutamiseks liikumisoperatsioon järgmine:

Tabelis 2 on esitatud iga elementaarse operatsiooni täitmise statistika, mis on kogutud lao töötajate poolt vastavalt hoiustatava kauba eripäradele.

Operatsiooni nimetus	Tähistus	Keskmine väärtus
Töötaja keskmine liikumiskiirus laos		1,5 m/sek
Keskmine aeg ühe operatsiooni teostamiseks, panna (kauba maht 4 dm3)		2,4 sek

Tabel 2. Keskmine aeg laooperatsioonide teostamiseks

Liikumiskulude arvutamise meetod on paika saadud. Nüüd tuleb välja selgitada, kuidas arvutada kulud konteineri-rakukeskkonna valimiseks. Siin on kõik palju, palju keerulisem kui liikumiskulude puhul, kuna:

• Esiteks, kulud peavad olema otseses sõltuvuses ruumala mahutist – sama jääkide kogus, mis kantakse donormahutitest, on parem panna väiksemasse konteinerisse kui suuremasse, kui see mahutatakse täielikult mõlemasse konteinerisse. Nii vähendame konteinerite valimisega seotud kogukulusid, püüdes säästa „puudulikke” vabade laopinda valikualal, et tagada kaupade edasine paigutamine rakkudesse. Joonisel 4 on näidatud erinevad jääkide liigutamise võimalused suurtesse ja väikestesse konteineritesse ning nende liigutamise tagajärjed edasiste laooperatsioonide käigus.
• Teiseks, kuna algse ülesande lahendamisel peame minimiseerima just kogukulud, mis on summaks nii liikumiskuludest kui ka konteinerite valimise kuludest, tuleb rakud kuupmeetrites mingil moel seostada sekunditega, mis ei ole sugugi triviaalne.

Joonis 4. Jääkide liigutamise võimalused erineva mahutavusega konteineritesse.

Joonisel 4 on punase värviga kujutatud jääkide maht, mis ei mahu enam konteinerisse teisel etapil järgmiste toodete paigutamisel.

Aitab siduda kuupmeetrid konteineri valimise kulutustega sekundites järgmised nõuded probleemilahenduste arvutamiseks:

• Jäägid doonorrakkudest tuleb igal juhul liigutada konteinerirakkudesse, kui see vähendab kaupade seas olevate konteinerirakkude koguarvu.
• On oluline säilitada tasakaal konteinerite mahtude ja liikumise ajakulud vahel: näiteks, kui uue lahenduse korral võrreldes eelmise lahendusega on mahtu suurendanud ja ajakulud väiksemad, tuleks valida uus variant.

Alustame viimasest nõudest. Et täpsustada mitmuses olevat sõna 'tasakaal', viisime läbi küsitluse lao töötajate seas, et selgitada välja järgnev. Olgu meil konteinerirakk mahuga , kuhu on määratud kaupade jääkide liikumine doonorrakkudest ning selle liikumise koguaeg on võrdne . Oletame, et on veel mitu alternatiivset võimalust sama suuruse kauba paigutamiseks samadest donorirakkudest teistesse konteineritesse, kus igal paigutusel on oma hinnangud , kus < ja , kus >.

Küsimus on: kui suur minimaalne mahusääst on aktsepteeritav, antud aegade kaotuse korral kui aega kaotatakse ? Поясним на примере. Изначально остатки полагалось размещать в контейнер объема 1000 дм3 (1 м3) и время на перемещение составило 70 секунд. Есть вариант размещения остатков в другой контейнер объема 500 дм3 и временем 130 секунд. Вопрос: готовы ли мы тратить еще дополнительные 60 секунд времени кладовщика на выполнение перемещения для того, чтобы сэкономить 500 дм3 свободного объема? По результатам опроса сотрудников склада была составлена следующая диаграмма.

Joon. 5. Joonis minimaalsete lubatud mahusäästude sõltuvusest operatsiooni läbimise aja erinevuse suurenemisest

See tähendab, et kui lisakulud ajas on 40 sekundit, siis oleme valmis neid kulutama ainult siis, kui mahusääst on vähemalt 500 dm3. Hoolimata et sõltuvuses esineb väike mittelineaarusus, eeldame lihtsuse huvides edasistes arvutustes, et sõltuvus suuruste vahel on lineaarne ning seda kirjeldab ebavõrdsus

Alljärgneval joonisel vaatleme järgmisi kaupa kokku panemise viise konteineritesse.

Joon. 6. Variant (a): 2 konteinerit, kogumaht 400 dm3, koguaeg 150 sek.

Joon. 6. Variant (b): 2 konteinerit, kogumaht 600 dm3, koguaeg 190 sek.

Joon. 6. Variant (c): 1 konteiner, kogumaht 400 dm3, koguaeg 200 sek.

Alternatiiv (a) konteinerite valimiseks on eelistatum kui algne valik, kuna kehtib ebavõrdsus: (800-400)/10 >= 150-120, millest järeldub 40 >= 30. Alternatiiv (b) on vähem eelistatud kui algne valik, kuna ebavõrdsus ei kehti: (800-600)/10 >= 190-150, millest järeldub 20 >= 40. Kuid alternatiiv (c) ei mahu sellesse loogikasse! Vaadakem seda varianti lähemalt. Ühest küljest kehtib ebavõrdsus (800-400)/10 >= 200-120, seega ei kehti ebavõrdsus 40 >= 80, mis ütleb, et mahu gained ei õigusta aega, mille kaotame.

Aga teisest küljest ei vähenda me variandis (c) mitte ainult koguvõetud mahtu, vaid vähendame ka hõivatud lahtrite arvu, mis on esimene kahest olulisest nõudest arvutatavatele probleemilahendustele, nagu eespool loetletud. Ilmselgelt on selle nõude täitmiseks vajalik vasakusse ossa ebavõrdsust lisada mõningane positiivne konstant. , ning sellist konstantti tuleks lisada ainult siis, kui konteinerite arv väheneb. Meenutame, et — on muutuj, mille väärtus on 1, kui konteiner on valitud, ja 0 kui konteiner ei ole valitud. Märgime – konteinerite kogumit algses lahenduses ja – konteinerite kogumit uues lahenduses. Üldiselt näeb uus ebavõrdsus välja järgmiselt:

Korrigeerides ülaltoodud ebavõrdsust, saame

Kandnud selle põhjal, on meil valem, et arvutada üldkulusid mõne lahenduse variandi jaoks:

Kuid nüüd tekib küsimus: milliseks väärtuseks see konstand peaks olema ? Очевидно, что ее значение должно быть достаточно большим, для того, чтобы всегда выполнялось первое требование к решениям задачи. Можно конечно взять значение константы равное 103 или 106, но хотелось бы избежать таких «magic numbers». Если будем рассматривать специфику выполнения складских операций, мы можем вычислить несколько вполне обоснованных числовых оценок величины такой константы.

Olgu – maksimum kaugus ladustamisaluste vahel ABC tsoonis, mis meie puhul on 100 m. Olgu – maksimum maht ladustamisaluses, mis on meie puhul 1000 dm3.

Esimene viis suuruse arvutamiseks . Arutame olukorda, kus esimesel tasemel on 2 konteinerit, milles on juba füüsiliselt kaup, see tähendab, et nad on ise doonor-rakkudeks, ja kauba transportimise kulud nendesse samadesse rakudesse on loomulikult 0. On vajalik leida selline konstandi väärtus , mille korral oleks alati kasulik jääke konteinerist 1 konteinerisse 2 üle kanda. Asendades väärtused ja üleval nimetatud ebavõrdsuses, saame:

mille põhjal järeldub

Asendades elementaarsete tegevuste keskmise täitmise aja väärtused ülaltoodud valemisse, saame

Teine viis suuruse arvutamiseks . Vaatleme olukorda, kus on annetajarakke, millest plaanitakse tooteid konteinerisse 1 paigutada. Määratleme – kaugus annetajarakust konteinerisse 1. Samuti on konteiner 2, milles juba on kaupu, ja mille maht võimaldab mahutada jääke kõigist annetajarakust. Lihtsuse huvides oletame, et toote maht, mis liigub annetajarakust konteineritesse, on sama ja on võrdne . On vajalik leida selline konstanti väärtus , mille korral oleks kõigi jääkide paigutamine konteinerisse 2 alati kasulikum kui nende paigutamine erinevatesse konteineritesse: Muutes ebaühtlust saame

Selleks, et "tugevdada" suuruse väärtust

, eeldame, et = 0. Keskmine arv rakke, mis tavaliselt osalevad jääkide kokkusurumise protsessis laos, on võrreldes 10. Asendades teadaolevad suuruse väärtused, saame järgmise konstanti väärtuse = 0. Tüüpiline laoseisu tihendamise protsessis osalevate rakkude keskmine arv on 10. Asendades teadaolevad suurused, saame järgmise konstanti väärtuse

Võtame iga variandi põhjal arvutatud kõige suurema väärtuse, see ongi suuruse väärtus antudestikandmete puhul. Nüüd, et kõik oleks täielik, kirjutame välja kogukulude arvutamise valemi. mingi lubatud lahenduse jaoks. :

Nüüd, pärast kõiki titanilisi püüdeid sisendandmete ümberkujundamiseks saame öelda, et kõik sisendandmed on vajadusel ümber muudetud ja valmis kasutamiseks optimeerimisalgoritmis.

Kokkuvõte

Kogemus näitab, et sisendandmete ettevalmistamise ja muutmise etapi töömahukust ja tähtsust alahindavad sageli. Selles artiklis oleme sellele etapile erakordselt palju tähelepanu pööranud, et näidata, et ainult kvaliteetselt ja arukalt ette valmistatud sisendandmed võivad muuta algoritmiga arvutatud lahendused kliendi jaoks tõeliselt väärtuslikuks. Jah, valemeid oli palju, kuid me hoiatame teid juba enne katset 🙂

Järgmises artiklis jõuame lõpuks sinna, mille nimel kaks eelnevat väljaannet mõeldi – diskreetse optimeerimise algoritmini.

Artikli koostas
Roman Shangin, projektide osakonna programmeerija,
ettevõte Esimene Bitt, Chelyabinsk

Allikas: habr.com