Sa artikulong ito sasabihin namin sa iyo kung paano namin nalutas ang problema ng kakulangan ng mga libreng cell sa isang bodega at ang pagbuo ng isang discrete optimization algorithm upang malutas ang naturang problema. Pag-usapan natin kung paano namin "itinayo" ang modelo ng matematika ng problema sa pag-optimize, at tungkol sa mga paghihirap na hindi namin inaasahang naranasan kapag nagpoproseso ng data ng input para sa algorithm.
Kung interesado ka sa mga aplikasyon ng matematika sa negosyo at hindi ka natatakot sa matibay na pagbabago ng pagkakakilanlan ng mga formula sa antas ng ika-5 baitang, pagkatapos ay maligayang pagdating sa pusa!
Ang artikulo ay magiging kapaki-pakinabang sa mga nagpapatupad WMS-mga sistema, gumagana sa bodega o industriya ng logistik ng produksyon, pati na rin ang mga programmer na interesado sa mga aplikasyon ng matematika sa negosyo at pag-optimize ng mga proseso sa isang negosyo.
Panimulang bahagi
Ipinagpapatuloy ng publikasyong ito ang serye ng mga artikulo kung saan ibinabahagi namin ang aming matagumpay na karanasan sa pagpapatupad ng mga algorithm ng pag-optimize sa mga proseso ng bodega.
Π inilalarawan ang mga detalye ng warehouse kung saan namin ipinatupad WMS-system, at ipinapaliwanag din kung bakit kailangan naming lutasin ang problema sa pag-cluster ng mga batch ng natitirang mga produkto sa panahon ng pagpapatupad WMS-systems, at kung paano namin ito ginawa.
Nang matapos naming isulat ang artikulo sa mga algorithm ng pag-optimize, naging napakalaki nito, kaya nagpasya kaming hatiin ang naipon na materyal sa 2 bahagi:
- Sa unang bahagi (artikulong ito) ay pag-uusapan natin kung paano namin "itinayo" ang modelo ng matematika ng problema, at tungkol sa mga malalaking paghihirap na hindi namin inaasahang nakatagpo kapag pinoproseso at binabago ang data ng input para sa algorithm.
- Sa ikalawang bahagi ay isasaalang-alang namin nang detalyado ang pagpapatupad ng algorithm sa wika C + +, magsasagawa kami ng eksperimento sa computational at ibubuod ang karanasang natamo namin sa panahon ng pagpapatupad ng naturang "mga matalinong teknolohiya" sa mga proseso ng negosyo ng customer.
Paano magbasa ng isang artikulo. Kung nabasa mo ang nakaraang artikulo, maaari kang pumunta kaagad sa kabanata na "Pangkalahatang-ideya ng mga umiiral na solusyon"; kung hindi, kung gayon ang paglalarawan ng problemang nalutas ay nasa spoiler sa ibaba.
Paglalarawan ng problemang nireresolba sa bodega ng customer
Bottleneck sa mga proseso
Noong 2018, natapos namin ang isang proyektong ipapatupad WMS-mga sistema sa warehouse na "Trading House "LD" sa Chelyabinsk. Ipinatupad namin ang produktong "1C-Logistics: Warehouse Management 3" para sa 20 lugar ng trabaho: mga operator WMS, mga tindera, mga driver ng forklift. Ang average na bodega ay humigit-kumulang 4 na libong m2, ang bilang ng mga cell ay 5000 at ang bilang ng mga SKU ay 4500. Ang bodega ay nag-iimbak ng mga ball valve ng aming sariling produksyon ng iba't ibang laki mula 1 kg hanggang 400 kg. Ang imbentaryo sa bodega ay naka-imbak sa mga batch, dahil may pangangailangan na pumili ng mga kalakal ayon sa FIFO.
Sa panahon ng disenyo ng mga scheme ng automation ng proseso ng warehouse, nahaharap kami sa umiiral na problema ng hindi pinakamainam na imbakan ng imbentaryo. Ang mga detalye ng pag-iimbak at paglalagay ng mga crane ay tulad na ang isang unit storage cell ay maaari lamang maglaman ng mga item mula sa isang batch (tingnan ang Fig. 1). Dumarating ang mga produkto sa bodega araw-araw at bawat pagdating ay isang hiwalay na batch. Sa kabuuan, bilang isang resulta ng 1 buwan na operasyon ng bodega, 30 hiwalay na mga batch ang nilikha, sa kabila ng katotohanan na ang bawat isa ay dapat na naka-imbak sa isang hiwalay na cell. Ang mga produkto ay madalas na pinipili hindi sa buong pallets, ngunit sa mga piraso, at bilang isang resulta, sa zone ng pagpili ng piraso sa maraming mga cell ang sumusunod na larawan ay sinusunod: sa isang cell na may dami ng higit sa 1 m3 mayroong ilang mga piraso ng cranes na sumasakop ng mas mababa sa 5-10% ng dami ng cell.
Fig 1. Larawan ng ilang piraso sa isang cell
Malinaw na ang kapasidad ng imbakan ay hindi ginagamit nang husto. Upang isipin ang laki ng sakuna, maaari akong magbigay ng mga numero: sa karaniwan, mayroong mula 1 hanggang 3 na mga cell ng naturang mga cell na may dami na higit sa 100 m300 na may "minuscule" na balanse sa iba't ibang panahon ng operasyon ng bodega. Dahil medyo maliit ang bodega, sa panahon ng abalang panahon ng bodega ang salik na ito ay nagiging "bottleneck" at lubos na nagpapabagal sa mga proseso ng bodega ng pagtanggap at pagpapadala.
Ideya ng solusyon sa problema
Lumitaw ang isang ideya: ang mga batch ng mga natira na may pinakamalapit na petsa ay dapat na bawasan sa isang solong batch, at ang mga natira na may pinag-isang batch ay dapat ilagay nang magkakasama sa isang cell, o sa ilan, kung walang sapat na espasyo sa isa upang ma-accommodate ang buong dami ng natira. Ang isang halimbawa ng naturang "compression" ay ipinapakita sa Figure 2.
Fig.2. Scheme para sa pag-compress ng mga nalalabi sa mga cell
Ito ay nagpapahintulot sa iyo na makabuluhang bawasan ang inookupahang espasyo ng bodega na gagamitin para sa mga bagong kalakal na inilalagay. Sa isang sitwasyon kung saan ang kapasidad ng bodega ay na-overload, ang naturang panukala ay lubhang kailangan, kung hindi man ay maaaring walang sapat na libreng espasyo upang mapaunlakan ang mga bagong kalakal, na hahantong sa paghinto sa mga proseso ng bodega ng paglalagay at muling pagdadagdag at, bilang kinahinatnan, sa paghinto sa pagtanggap at pagpapadala. Noong nakaraan, bago ang pagpapatupad ng sistema ng WMS, ang naturang operasyon ay ginanap nang manu-mano, na hindi epektibo, dahil ang proseso ng paghahanap ng angkop na mga balanse sa mga cell ay medyo mahaba. Ngayon, sa pagpapakilala ng isang WMS system, nagpasya kaming i-automate ang proseso, pabilisin ito at gawin itong matalino.
Ang proseso ng paglutas ng naturang problema ay nahahati sa 2 yugto:
- sa unang yugto nakita namin ang mga pangkat ng mga batch na malapit sa petsa para sa compression (nakatuon sa gawaing ito );
- sa ikalawang yugto, para sa bawat pangkat ng mga batch ay kinakalkula namin ang pinaka-compact na paglalagay ng natitirang mga kalakal sa mga cell.
Sa kasalukuyang artikulo ay tututuon natin ang ikalawang yugto ng algorithm.
Pagsusuri ng mga kasalukuyang solusyon
Bago lumipat sa paglalarawan ng mga algorithm na aming binuo, ito ay nagkakahalaga ng pagsasagawa ng isang maikling pangkalahatang-ideya ng mga system na mayroon na sa merkado WMS, na nagpapatupad ng katulad na pinakamainam na functionality ng compression.
Una sa lahat, kinakailangang tandaan ang produktong β1C: Enterprise 8. WMS Logistics. Pamamahala ng bodega 4", na pagmamay-ari at kinopya ng 1C at kabilang sa ikaapat na henerasyon WMS-mga system na binuo ng AXELOT. Sinasabi ng system na ito ang functionality ng compression, na idinisenyo upang pag-isahin ang mga nananatili sa isang karaniwang cell. Ito ay nagkakahalaga ng pagbanggit na ang pag-andar ng compression sa naturang sistema ay kasama rin ang iba pang mga posibilidad, halimbawa, pagwawasto sa paglalagay ng mga kalakal sa mga cell ayon sa kanilang mga klase sa ABC, ngunit hindi namin ito papansinin.
Kung susuriin mo ang code ng 1C: Enterprise 8. WMS Logistics system. Pamamahala ng bodega 4" (na bukas sa bahaging ito ng functionality), maaari nating tapusin ang mga sumusunod. Ang natitirang algorithm ng compression ay nagpapatupad ng isang medyo primitive na linear logic at walang pag-uusapan ng anumang "pinakamainam" na compression. Naturally, hindi ito nagbibigay ng clustering ng mga partido. Ilang mga kliyente na may ganitong sistema na ipinatupad ay nagreklamo tungkol sa mga resulta ng pagpaplano ng compression. Halimbawa, madalas sa pagsasanay sa panahon ng compression ang sumusunod na sitwasyon ay naganap: 100 mga PC. Ito ay binalak na ilipat ang natitirang mga kalakal mula sa isang cell patungo sa isa pang cell, kung saan matatagpuan ang 1 piraso. mga kalakal, bagaman ito ay pinakamainam mula sa punto ng view ng pagkonsumo ng oras na gawin ang kabaligtaran.
Gayundin, ang pag-andar ng pag-compress ng natitirang mga kalakal sa mga cell ay idineklara sa maraming dayuhang bansa. WMS-systems, ngunit, sa kasamaang-palad, wala kaming tunay na feedback sa pagiging epektibo ng mga algorithm (ito ay isang trade secret), higit na hindi isang ideya tungkol sa lalim ng kanilang logic (proprietary closed-source software), kaya hindi namin maaaring hatulan.
Maghanap ng isang mathematical model ng problema
Upang magdisenyo ng mataas na kalidad na mga algorithm para sa paglutas ng isang problema, kailangan munang malinaw na bumalangkas sa problemang ito sa matematika, na kung ano ang gagawin natin.
Mayroong maraming mga cell , na naglalaman ng mga labi ng ilang kalakal. Sa mga sumusunod, tatawagin natin ang mga naturang cell na donor cells. Tukuyin natin dami ng mga kalakal sa cell $.
Mahalagang sabihin na isang produkto lamang ng isang batch, o ilang batch na dating pinagsama sa isang cluster (basahin ang: ), na dahil sa mga detalye ng pag-iimbak at pag-iimbak ng mga kalakal. Ang iba't ibang produkto o iba't ibang batch cluster ay dapat magpatakbo ng sarili nilang hiwalay na pamamaraan ng compression.
Mayroong maraming mga cell , kung saan posibleng mailagay ang mga residue mula sa mga donor cell. Tatawagin pa natin ang mga naturang cell na container cells. Ang mga ito ay maaaring alinman sa mga libreng cell sa bodega o mga donor cell mula sa iba't ibang uri . Laging marami ay isang subset .
Para sa bawat cell mula sa marami Ang mga paghihigpit sa kapasidad ay naitakda , sinusukat sa dm3. Ang isang dm3 ay isang kubo na may mga gilid na 10 cm. Ang mga produkto na nakaimbak sa bodega ay medyo malaki, kaya sa kasong ito ang naturang discretization ay sapat na.
Ibinigay ang isang matrix ng pinakamaikling distansya sa metro sa pagitan ng bawat pares ng mga cell Saan ΠΈ nabibilang sa set ΠΈ ayon sa pagkakabanggit.
Tukuyin natin "mga gastos" ng paglipat ng mga kalakal mula sa cell sa isang cell . Tukuyin natin "mga gastos" sa pagpili ng isang lalagyan upang ilipat ang mga nalalabi mula sa iba pang mga cell papunta dito. Paano eksakto at sa anong mga yunit ng pagsukat ang mga halaga ay kakalkulahin ΠΈ isasaalang-alang pa natin (tingnan ang seksyon na naghahanda ng data ng pag-input), sa ngayon ay sapat na upang sabihin na ang mga naturang halaga ay direktang proporsyonal sa mga halaga ΠΈ ayon sa pagkakabanggit.
Ipahiwatig natin sa pamamagitan ng isang variable na kumukuha ng value 1 kung ang natitira ay mula sa cell inilipat sa lalagyan , at 0 kung hindi man. Ipahiwatig natin sa pamamagitan ng isang variable na kumukuha ng value 1 kung ang container naglalaman ng mga natitirang kalakal, at 0 kung hindi man.
Ang gawain ay nakasaad tulad ng sumusunod: kailangan mong maghanap ng napakaraming lalagyan at sa gayon ay "ilakip" ang mga donor cell sa mga cell ng lalagyan upang mabawasan ang paggana
sa ilalim ng mga paghihigpit
Sa kabuuan, kapag kinakalkula ang solusyon sa problema, nagsusumikap kaming:
- una, upang makatipid ng kapasidad ng imbakan;
- pangalawa, para makatipid sa oras ng mga storekeeper.
Ang huling paghihigpit ay nangangahulugan na hindi namin maaaring ilipat ang mga kalakal sa isang lalagyan na hindi namin pinili, at samakatuwid ay hindi "nagkaroon ng mga gastos" para sa pagpili nito. Ang paghihigpit na ito ay nangangahulugan din na ang dami ng mga kalakal na inilipat mula sa mga cell patungo sa lalagyan ay hindi dapat lumampas sa kapasidad ng lalagyan. Sa pamamagitan ng paglutas ng isang problema ang ibig naming sabihin ay isang set ng mga lalagyan at mga paraan para sa pag-attach ng mga donor cell sa mga lalagyan.
Ang pormulasyon na ito ng problema sa pag-optimize ay hindi bago, at pinag-aralan ng maraming mathematician mula noong unang bahagi ng 80s ng huling siglo. Sa dayuhang panitikan mayroong 2 mga problema sa pag-optimize na may angkop na modelo ng matematika: ΠΈ (pag-uusapan natin ang mga pagkakaiba sa mga gawain sa ibang pagkakataon). Ito ay nagkakahalaga ng pagsasabi na sa matematikal na literatura, ang pagbabalangkas ng naturang dalawang problema sa pag-optimize ay nabuo sa mga tuntunin ng lokasyon ng mga negosyo sa lupa, samakatuwid ang pangalang "Lokasyon ng Pasilidad". Para sa karamihan, ito ay isang pagkilala sa tradisyon, dahil sa kauna-unahang pagkakataon ang pangangailangan upang malutas ang mga naturang kombinatoryal na problema ay nagmula sa larangan ng logistik, karamihan ay mula sa sektor ng militar-industriya noong 50s ng huling siglo. Sa mga tuntunin ng lokasyon ng negosyo, ang mga naturang gawain ay binabalangkas tulad ng sumusunod:
- Mayroong isang tiyak na bilang ng mga lungsod kung saan posibleng mahanap ang mga negosyo sa pagmamanupaktura (mula rito ay tinutukoy bilang mga lungsod ng pagmamanupaktura). Para sa bawat lungsod ng pagmamanupaktura, ang mga gastos sa pagbubukas ng isang negosyo dito ay tinukoy, pati na rin ang isang limitasyon sa kapasidad ng produksyon ng negosyo na binuksan dito.
- Mayroong isang tiyak na hanay ng mga lungsod kung saan ang mga kliyente ay aktwal na matatagpuan (mula rito ay tinutukoy bilang mga lungsod ng kliyente). Para sa bawat naturang client city, ang dami ng demand para sa mga produkto ay tinukoy. Para sa pagiging simple, ipagpalagay namin na mayroon lamang isang produkto na ginawa ng mga negosyo at ginagamit ng mga customer.
- Para sa bawat pares ng city-manufacturer at city-client, ang halaga ng mga gastos sa transportasyon para sa paghahatid ng kinakailangang dami ng mga produkto mula sa tagagawa hanggang sa kliyente ay tinukoy.
Kailangan mong hanapin kung aling mga lungsod ang magbubukas ng mga negosyo at kung paano mag-attach ng mga kliyente sa mga naturang negosyo upang:
- Ang kabuuang gastos sa pagbubukas ng mga negosyo at mga gastos sa transportasyon ay minimal;
- Ang dami ng demand mula sa mga customer na nakatalaga sa anumang bukas na negosyo ay hindi lumampas sa kapasidad ng produksyon ng negosyong iyon.
Ngayon ay nararapat na banggitin ang tanging pagkakaiba sa dalawang klasikal na problemang ito:
- Problema sa Lokasyon ng Single-Source Capacitated Pasilidad β ang kliyente ay ibinibigay mula lamang sa isang bukas na pasilidad;
- Problema sa Lokasyon ng Multi-Source Capacitated Facility β ang kliyente ay maaaring ibigay mula sa ilang bukas na pasilidad nang sabay-sabay.
Ang gayong pagkakaiba sa pagitan ng dalawang problema ay hindi gaanong mahalaga sa unang sulyap, ngunit, sa katunayan, ay humahantong sa ganap na magkakaibang mga istrukturang kombinatoryal ng mga naturang problema at, bilang isang resulta, sa ganap na magkakaibang mga algorithm para sa paglutas ng mga ito. Ang mga pagkakaiba sa pagitan ng mga gawain ay ipinapakita sa figure sa ibaba.
Fig.3. a) Problema sa Lokasyon ng Pasilidad na Pinagmulan ng Multi-Source Capacitated
Fig.3. b) Problema sa Lokasyon ng Pasilidad na May Iisang Pinagmulan na Capacitated
Parehong gawain -mahirap, ibig sabihin, walang eksaktong algorithm na malulutas ang ganoong problema sa isang polynomial ng oras sa laki ng data ng input. Sa mas simpleng salita, ang lahat ng eksaktong algorithm para sa paglutas ng isang problema ay gagana sa exponential time, kahit na marahil ay mas mabilis kaysa sa kumpletong paghahanap ng mga opsyon. Mula sa gawain -mahirap, pagkatapos ay isasaalang-alang lamang namin ang tinatayang heuristics, iyon ay, mga algorithm na patuloy na magkalkula ng mga solusyon na napakalapit sa pinakamainam at gagana nang mabilis. Kung interesado ka sa ganoong gawain, makakahanap ka ng magandang pangkalahatang-ideya sa Russian dito.
Kung lumipat tayo sa terminolohiya ng ating problema ng pinakamainam na pag-compress ng mga kalakal sa mga cell, kung gayon:
- Ang mga lungsod ng kliyente ay mga donor cell kasama ang natitirang mga kalakal,
- mga lungsod ng pagmamanupaktura β mga container cell , kung saan ang mga natitira mula sa iba pang mga cell ay dapat na ilagay,
- gastos sa transportasyon - gastos sa oras storekeeper upang ilipat ang dami ng mga kalakal mula sa donor cell sa isang container cell ;
- mga gastos sa pagbubukas ng negosyo - mga gastos sa pagpili ng lalagyan , katumbas ng volume ng container cell , na pinarami ng isang tiyak na koepisyent para sa pag-save ng mga libreng volume (ang halaga ng koepisyent ay palaging > 1) (tingnan ang seksyong naghahanda ng data ng input).
Matapos iguhit ang pagkakatulad sa mga kilalang klasikal na solusyon ng problema, kinakailangan na sagutin ang isang mahalagang tanong kung saan nakasalalay ang pagpili ng arkitektura ng algorithm ng solusyon: ang paglipat ng mga natitira mula sa donor cell ay posible lamang sa isa at isang lalagyan lamang. (Single-Source), o posible bang ilipat ang mga natitira sa ilang container cell (Multi-Source)?
Ito ay nagkakahalaga ng noting na sa pagsasanay parehong formulations ng problema ay nagaganap. Ipinapakita namin ang lahat ng mga kalamangan at kahinaan para sa bawat ganoong setting sa ibaba:
| Variant ng problema | Mga kalamangan ng pagpipilian | Kahinaan ng opsyon |
|---|---|---|
| Single-Source | Ang mga operasyon ng paggalaw ng mga kalakal ay kinakalkula gamit ang variant na ito ng problema:
|
|
| Maramihang Pinagmulan | Ang mga compression na kinakalkula gamit ang bersyon na ito ng problema ay karaniwang 10-15% na mas compact kumpara sa mga compression na kinakalkula gamit ang "Single-Source" na opsyon. Ngunit tandaan din namin na mas maliit ang bilang ng mga nalalabi sa mga selula ng donor, mas maliit ang pagkakaiba sa pagiging compact | Ang mga operasyon ng paggalaw ng mga kalakal ay kinakalkula gamit ang variant na ito ng problema:
|
Talahanayan 1. Mga kalamangan at kahinaan ng mga opsyon na Single-Source at Multi-Source.
Dahil ang pagpipiliang Single-Source ay may higit pang mga pakinabang, at isinasaalang-alang din ang katotohanan na mas maliit ang bilang ng mga nalalabi sa mga selula ng donor, mas maliit ang pagkakaiba sa antas ng pagiging compact ng compression na kinakalkula para sa parehong mga variant ng problema, ang aming pinili ay nahulog sa ang pagpipiliang Single-Source. Source.
Ito ay nagkakahalaga na sabihin na ang solusyon sa Multi-Source na opsyon ay nagaganap din. Mayroong isang malaking bilang ng mga epektibong algorithm para sa paglutas nito, karamihan sa mga ito ay bumaba sa paglutas ng ilang mga problema sa transportasyon. Mayroon ding hindi lamang mahusay na mga algorithm, kundi pati na rin ang mga eleganteng, halimbawa,
Paghahanda ng Data ng Input
Bago simulan ang pag-aralan at bumuo ng isang algorithm upang malutas ang isang problema, ito ay kinakailangan upang magpasya kung ano ang data at sa anong anyo namin ito ipapakain bilang input. Walang mga problema sa dami ng natitirang mga kalakal sa mga cell ng donor at ang kapasidad ng mga cell ng lalagyan, dahil ito ay walang kabuluhan - ang mga naturang dami ay susukatin sa m3, ngunit sa mga gastos sa paggamit ng isang container cell at ang moving cost matrix, hindi lahat. ay napakasimple!
Tingnan muna natin ang kalkulasyon gastos sa paglipat ng mga kalakal mula sa donor cell hanggang sa container cell. Una sa lahat, kinakailangang magpasya kung anong mga yunit ng pagsukat ang kalkulahin natin ang mga gastos sa paggalaw. Ang dalawang pinaka-halatang opsyon ay metro at segundo. Walang saysay na kalkulahin ang mga gastos sa paglalakbay sa "purong" metro. Ipakita natin ito sa isang halimbawa. Hayaan ang cell matatagpuan sa unang baitang, cell inalis ng 30 metro at matatagpuan sa pangalawang baitang:
- Lumilipat mula sa Π² mas mahal kaysa sa paglipat mula sa Π² , dahil ang pagbaba mula sa pangalawang baitang (1,5-2 metro mula sa sahig) ay mas madali kaysa sa pag-akyat sa pangalawa, bagaman ang distansya ay magiging pareho;
- Ilipat ang 1 pc. mga kalakal mula sa selda Π² Ito ay magiging mas madali kaysa sa paglipat ng 10 piraso. ang parehong produkto, bagaman ang distansya ay magiging pareho.
Mas mainam na isaalang-alang ang mga gastos sa paglipat sa ilang segundo, dahil pinapayagan ka nitong isaalang-alang ang parehong pagkakaiba sa mga tier at ang pagkakaiba sa dami ng inilipat na mga kalakal. Upang maisaalang-alang ang halaga ng paggalaw sa ilang segundo, dapat nating i-decompose ang pagpapatakbo ng paggalaw sa mga elementaryang bahagi at magsagawa ng mga sukat ng oras para sa pagpapatupad ng bawat elementong bahagi.
Hayaan mula sa cell gumagalaw PC. mga kalakal sa lalagyan . Hayaan β ang average na bilis ng paggalaw ng isang manggagawa sa bodega, na sinusukat sa m/sec. Hayaan ΠΈ β ang average na bilis ng isang beses na operasyon ay kumukuha at inilalagay, ayon sa pagkakabanggit, para sa dami ng mga kalakal na katumbas ng 4 dm3 (ang average na volume na kinukuha ng isang empleyado sa isang oras sa isang bodega kapag nagsasagawa ng mga operasyon). Hayaan ΠΈ ang taas ng mga cell kung saan isinasagawa ang mga operasyon ng take at put, ayon sa pagkakabanggit. Halimbawa, ang average na taas ng unang baitang (sahig) ay 1 m, ang pangalawang baitang ay 2 m, atbp. Kung gayon ang formula para sa pagkalkula ng kabuuang oras upang makumpleto ang isang paglipat ng operasyon ay susunod:
Ang talahanayan 2 ay nagpapakita ng mga istatistika sa oras ng pagpapatupad ng bawat elementarya na operasyon, na nakolekta ng mga empleyado ng bodega, na isinasaalang-alang ang mga detalye ng mga nakaimbak na kalakal.
| ang pangalan ng operasyon | Pagtatanda | Average na halaga |
|---|---|---|
| Average na bilis ng paggalaw ng isang manggagawa sa bodega | |
1,5 m/s |
| Average na bilis ng isang operasyon na ilalagay (para sa dami ng produkto na 4 dm3) | |
2,4 sec |
Talahanayan 2. Average na oras upang makumpleto ang mga operasyon ng warehouse
Napagpasyahan namin ang paraan para sa pagkalkula ng mga gastos sa paglipat. Ngayon kailangan nating malaman kung paano makalkula gastos sa pagpili ng container cell. Ang lahat dito ay higit, mas kumplikado kaysa sa mga gastos sa paglipat, dahil:
- una, ang mga gastos ay dapat na direktang nakadepende sa dami ng cell - ang parehong dami ng residues na inilipat mula sa mga donor cell ay mas mainam na ilagay sa isang lalagyan na may mas maliit na volume kaysa sa isang malaking lalagyan, sa kondisyon na ang naturang volume ay ganap na magkasya sa parehong lalagyan . Kaya, sa pamamagitan ng pagliit sa kabuuang gastos sa pagpili ng mga lalagyan, nagsusumikap kaming makatipid ng "kakaunti" na libreng kapasidad ng imbakan sa lugar ng pagpili upang maisagawa ang mga kasunod na operasyon ng paglalagay ng mga kalakal sa mga cell. Ipinapakita ng Figure 4 ang mga opsyon para sa paglilipat ng mga nalalabi sa malalaki at maliliit na lalagyan at ang mga kahihinatnan ng mga opsyon sa paglilipat na ito sa mga susunod na operasyon ng warehouse.
- pangalawa, dahil sa paglutas ng orihinal na problema kailangan nating i-minimize nang eksakto ang kabuuang mga gastos, at ito ang kabuuan ng parehong mga gastos sa paglipat at mga gastos sa pagpili ng mga lalagyan, kung gayon ang mga volume ng cell sa metro kubiko ay kailangang kahit papaano ay maiugnay sa mga segundo, na malayo sa walang kabuluhan.
kanin. 4. Mga opsyon para sa paglipat ng mga natira sa mga lalagyan na may iba't ibang kapasidad.
Ipinapakita ng Figure 4 sa pula ang dami ng mga natira na hindi na kasya sa lalagyan sa ikalawang yugto ng paglalagay ng mga kasunod na kalakal.
Makakatulong ito na i-link ang kubiko metro ng mga gastos para sa pagpili ng isang lalagyan na may mga segundo ng mga gastos para sa paglipat ng mga sumusunod na kinakailangan para sa mga kinakalkula na solusyon sa problema:
- Kinakailangan na ang mga balanse mula sa donor bin ay ilipat sa container bin sa anumang kaso kung mababawasan nito ang kabuuang bilang ng mga container bin na naglalaman ng produkto.
- Ito ay kinakailangan upang mapanatili ang isang balanse sa pagitan ng dami ng mga lalagyan at ang oras na ginugol sa paglipat: halimbawa, kung sa isang bagong solusyon sa isang problema kumpara sa nakaraang solusyon, ang pakinabang sa dami ay malaki, ngunit ang pagkawala sa oras ay maliit. , pagkatapos ay kinakailangan na pumili ng isang bagong opsyon.
Magsimula tayo sa huling kinakailangan. Upang linawin ang hindi malinaw na salitang "balanse," nagsagawa kami ng isang survey sa mga empleyado ng warehouse upang malaman ang mga sumusunod. Hayaang magkaroon ng container cell ng volume , kung saan ang paggalaw ng mga natitirang kalakal mula sa mga donor cell ay itinalaga at ang kabuuang oras ng naturang paggalaw ay katumbas ng . Hayaang magkaroon ng ilang alternatibong opsyon para sa paglalagay ng parehong dami ng mga kalakal mula sa parehong mga donor cell sa ibang mga container, kung saan ang bawat placement ay may sariling mga pagtatantya Saan < ΠΈ Saan >.
Ang tanong ay ibinibigay: ano ang pinakamababang pakinabang sa dami katanggap-tanggap, para sa isang naibigay na halaga ng pagkawala ng oras ? Ipaliwanag natin gamit ang isang halimbawa. Sa una, ang mga labi ay dapat na ilagay sa isang lalagyan na may dami na 1000 dm3 (1 m3) at ang oras ng paglipat ay 70 segundo. Mayroong isang pagpipilian upang ilagay ang mga nalalabi sa isa pang lalagyan na may dami na 500 dm3 at isang oras na 130 segundo. Tanong: handa na ba kaming gumastos ng karagdagang 60 segundo ng oras ng storekeeper sa paglipat ng mga kalakal upang makatipid ng 500 dm3 ng libreng volume? Batay sa mga resulta ng isang survey ng mga empleyado ng warehouse, ang sumusunod na diagram ay pinagsama-sama.
kanin. 5. Diagram ng pag-asa ng pinakamababang pinahihintulutang pagtitipid sa dami sa pagtaas ng pagkakaiba sa oras ng operasyon
Iyon ay, kung ang mga karagdagang gastos sa oras ay 40 segundo, pagkatapos ay handa kaming gastusin lamang ang mga ito kapag ang pagtaas sa dami ay hindi bababa sa 500 dm3. Sa kabila ng katotohanan na mayroong isang bahagyang nonlinearity sa dependence, para sa pagiging simple ng karagdagang mga kalkulasyon ay ipagpalagay natin na ang dependence sa pagitan ng mga dami ay linear at inilalarawan ng hindi pagkakapantay-pantay.
Sa figure sa ibaba, isinasaalang-alang namin ang mga sumusunod na paraan ng paglalagay ng mga kalakal sa mga lalagyan.
kanin. 6. Opsyon (a): 2 lalagyan, kabuuang volume 400 dm3, kabuuang oras 150 segundo.
kanin. 6. Opsyon (b): 2 lalagyan, kabuuang volume 600 dm3, kabuuang oras 190 segundo.
kanin. 6. Opsyon (c): 1 lalagyan, kabuuang volume 400 dm3, kabuuang oras 200 segundo.
Ang opsyon (a) para sa pagpili ng mga lalagyan ay mas pinipili kaysa sa orihinal na opsyon, dahil ang hindi pagkakapantay-pantay ay mayroong: (800-400)/10>=150-120, na nagpapahiwatig ng 40 >= 30. Ang opsyon (b) ay hindi gaanong kanais-nais kaysa sa orihinal option , dahil ang hindi pagkakapantay-pantay ay hindi humahawak: (800-600)/10>=190-150 na nagpapahiwatig ng 20 >= 40. Ngunit ang opsyon (c) ay hindi akma sa ganoong lohika! Isaalang-alang natin ang pagpipiliang ito nang mas detalyado. Sa isang banda, ang hindi pagkakapantay-pantay (800-400)/10>=200-120, na nangangahulugang ang hindi pagkakapantay-pantay 40 >= 80 ay hindi nasisiyahan, na nagmumungkahi na ang pagtaas sa dami ay hindi katumbas ng malaking pagkawala sa oras.
Ngunit sa kabilang banda, sa pagpipiliang ito (c) hindi lamang namin binabawasan ang kabuuang dami ng inookupahan, ngunit binabawasan din ang bilang ng mga sinasakop na mga cell, na siyang una sa dalawang mahahalagang kinakailangan para sa mga computable na solusyon sa mga problemang nakalista sa itaas. Malinaw, upang magsimulang matupad ang pangangailangang ito, kinakailangan na magdagdag ng ilang positibong pare-pareho sa kaliwang bahagi ng hindi pagkakapantay-pantay. , at ang ganoong pare-pareho ay kailangang idagdag lamang kapag bumababa ang bilang ng mga lalagyan. Paalalahanan ka namin ay isang variable na katumbas ng 1 kapag ang lalagyan pinili, at 0 kapag lalagyan hindi pinili. Ipahiwatig natin β maraming lalagyan sa paunang solusyon at β maraming lalagyan sa bagong solusyon. Sa pangkalahatan, ang bagong hindi pagkakapantay-pantay ay magiging ganito:
Ang pagbabago sa hindi pagkakapantay-pantay sa itaas, nakukuha natin
Batay dito, mayroon kaming formula para sa pagkalkula ng kabuuang gastos ilang solusyon sa problema:
Ngunit ngayon ang tanong ay lumitaw: anong halaga ang dapat magkaroon ng ganoong pare-pareho? ? Malinaw, ang halaga nito ay dapat na sapat na malaki upang ang unang kinakailangan para sa mga solusyon sa problema ay palaging natutugunan. Maaari mong, siyempre, kunin ang halaga ng pare-pareho na katumbas ng 103 o 106, ngunit nais kong iwasan ang gayong "magic number". Kung isasaalang-alang namin ang mga detalye ng pagsasagawa ng mga pagpapatakbo ng warehouse, maaari naming kalkulahin ang ilang mga mahusay na itinatag na pagtatantya ng numero ng halaga ng naturang pare-pareho.
Hayaan β ang maximum na distansya sa pagitan ng mga cell ng warehouse ng isang zone ABC, katumbas sa aming kaso sa 100 m. Hayaan β ang maximum na dami ng isang container cell sa isang bodega, katumbas sa aming kaso sa 1000 dm3.
Ang unang paraan upang makalkula ang halaga . Isaalang-alang natin ang isang sitwasyon kung saan mayroong 2 lalagyan sa unang baitang, kung saan ang mga kalakal ay pisikal na matatagpuan, iyon ay, sila mismo ay mga donor cell, at ang halaga ng paglipat ng mga kalakal sa parehong mga cell ay natural na katumbas ng 0. Ito ay kinakailangan upang mahanap ang ganoong halaga para sa pare-pareho , kung saan magiging kapaki-pakinabang na palaging ilipat ang mga natira mula sa lalagyan 1 patungo sa lalagyan 2. Pagpapalit sa mga halaga ΠΈ Sa hindi pagkakapantay-pantay na ibinigay sa itaas ay nakukuha natin:
kung saan ito sumusunod
Ang pagpapalit ng mga halaga ng average na oras para sa pagsasagawa ng mga elementary operation sa formula sa itaas na nakukuha namin
Ang pangalawang paraan upang makalkula ang halaga . Isaalang-alang natin ang isang sitwasyon kung saan mayroon donor cell na kung saan ito ay binalak na ilipat ang mga kalakal sa lalagyan 1. Let us denote β distansya mula sa donor cell sa lalagyan 1. Mayroon ding lalagyan 2, na naglalaman na ng mga kalakal, at ang dami nito ay nagbibigay-daan sa iyo upang mapaunlakan ang natitira sa lahat mga selula. Para sa pagiging simple, ipagpalagay namin na ang dami ng mga kalakal na inilipat mula sa mga donor cell patungo sa mga lalagyan ay pareho at katumbas ng . Kinakailangang hanapin ang gayong halaga ng pare-pareho , kung saan ang paglalagay ng lahat ng natitira ay mula sa ang mga cell sa lalagyan 2 ay palaging magiging mas kumikita kaysa sa paglalagay ng mga ito sa iba't ibang mga lalagyan:
Pagbabago ng hindi pagkakapantay-pantay na nakukuha natin
Upang "palakasin" ang halaga ng dami , ipagpalagay natin na = 0. Ang average na bilang ng mga cell na karaniwang kasangkot sa pamamaraan para sa pag-compress ng mga balanse sa bodega ay 10. Ang pagpapalit sa mga kilalang halaga ng mga dami, mayroon kaming sumusunod na halaga ng pare-pareho
Kinukuha namin ang pinakamalaking halaga na kinakalkula para sa bawat opsyon, ito ang magiging halaga ng dami para sa ibinigay na mga parameter ng warehouse. Ngayon, para sa pagkakumpleto, isulat natin ang formula para sa pagkalkula ng kabuuang gastos para sa ilang magagawang solusyon :
Ngayon, pagkatapos ng lahat titanic na pagsisikap Sa pamamagitan ng pagbabago sa data ng input, masasabi nating ang lahat ng data ng input ay na-convert sa nais na form at handa na para sa paggamit sa algorithm ng pag-optimize.
Konklusyon
Tulad ng ipinapakita ng kasanayan, ang pagiging kumplikado at kahalagahan ng yugto ng paghahanda at pagbabago ng data ng input para sa isang algorithm ay madalas na minamaliit. Sa artikulong ito, partikular na binigyan namin ng malaking pansin ang yugtong ito upang ipakita na ang mataas na kalidad at matalinong inihanda na data ng pag-input lamang ang maaaring gumawa ng mga desisyon na kinakalkula ng algorithm na tunay na mahalaga sa kliyente. Oo, maraming mga derivasyon ng mga formula, ngunit binalaan ka namin bago pa man ang kata :)
Sa susunod na artikulo, sa wakas ay matututuhan natin kung para saan ang 2 nakaraang publikasyon - isang discrete optimization algorithm.
Inihanda ang artikulo
Roman Shangin, programmer ng departamento ng mga proyekto,
Unang Bit kumpanya, Chelyabinsk
Pinagmulan: www.habr.com