{"id":37108,"date":"2019-10-31T22:15:47","date_gmt":"2019-10-31T19:15:47","guid":{"rendered":"https:\/\/prohoster.info\/blog\/diskretnaya-matematika-dlya-wms-algoritm-szhatiya-tovarov-v-yachejkah-chast-1\/"},"modified":"2019-10-31T22:15:47","modified_gmt":"2019-10-31T19:15:47","slug":"diskretnaya-matematika-dlya-wms-algoritm-szhatiya-tovarov-v-yachejkah-chast-1","status":"publish","type":"post","link":"https:\/\/prohoster.info\/pl\/blog\/news\/diskretnaya-matematika-dlya-wms-algoritm-szhatiya-tovarov-v-yachejkah-chast-1","title":{"rendered":"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"<p><img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/89e9927c86cd36ee5b4ab37b5c0753c9.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nW artykule opiszemy, jak rozwi\u0105zali\u015bmy problem braku wolnych miejsc na magazynie oraz jak opracowali\u015bmy algorytm dyskretnej optymalizacji, aby poradzi\u0107 sobie z takim zadaniem. Opowiemy, jak \"budowali\u015bmy\" matematyczny model zadania optymalizacji i z jakimi trudno\u015bciami niespodziewanie si\u0119 zmierzyli\u015bmy podczas przetwarzania danych wej\u015bciowych do algorytmu.<\/p>\n<p>Je\u015bli interesuj\u0105 Ci\u0119 zastosowania matematyki w biznesie i nie boisz si\u0119 trudnych przekszta\u0142ce\u0144 wzor\u00f3w na poziomie 5. klasy, to serdecznie zapraszamy pod kat!<\/p>\n<p>Artyku\u0142 b\u0119dzie przydatny dla tych, kt\u00f3rzy wprowadzaj\u0105 <i>WMS<\/i>-systemy, pracuj\u0105 w bran\u017cy logistyki magazynowej lub produkcyjnej, a tak\u017ce dla programist\u00f3w, kt\u00f3rzy interesuj\u0105 si\u0119 zastosowaniami matematyki w biznesie i optymalizacj\u0105 proces\u00f3w w przedsi\u0119biorstwie.<\/p>\n<p><noindex><a rel=\"nofollow\" name=\"habracut\"><\/a><\/noindex><\/p>\n<h4>Cz\u0119\u015b\u0107 wprowadzaj\u0105ca<\/h4>\n<p>\nTa publikacja kontynuuje cykl artyku\u0142\u00f3w, w kt\u00f3rych dzielimy si\u0119 swoim udanym do\u015bwiadczeniem we wdra\u017caniu algorytm\u00f3w optymalizacji w procesy magazynowe. <\/p>\n<p>W <noindex><a rel=\"nofollow\" href=\"https:\/\/habr.com\/ru\/post\/463289\/\">poprzedniej artykule<\/a><\/noindex> opisano specyfik\u0119 magazynu, w kt\u00f3rym wdro\u017cyli\u015bmy <i>WMS<\/i>-system, a tak\u017ce opowiedziano, dlaczego potrzebne by\u0142o rozwi\u0105zanie problemu klasteryzacji partii pozosta\u0142ych towar\u00f3w podczas wdra\u017cania <i>WMS<\/i>-systemu, i jak to zrobili\u015bmy.<\/p>\n<p>Kiedy sko\u0144czyli\u015bmy pisa\u0107 artyku\u0142 o algorytmach optymalizacji, okaza\u0142 si\u0119 on bardzo obszerny, dlatego postanowili\u015bmy podzieli\u0107 zebrany materia\u0142 na 2 cz\u0119\u015bci:<\/p>\n<ul>\n<li>W pierwszej cz\u0119\u015bci (ten artyku\u0142) opowiemy, jak \"budowali\u015bmy\" matematyczny model zadania oraz z jakimi du\u017cymi trudno\u015bciami niespodziewanie si\u0119 zmierzyli\u015bmy podczas przetwarzania i przekszta\u0142cania danych wej\u015bciowych do algorytmu.<\/li>\n<li>W drugiej cz\u0119\u015bci szczeg\u00f3\u0142owo om\u00f3wimy realizacj\u0119 algorytmu w j\u0119zyku <i>C++<\/i>, przeprowadzimy eksperyment obliczeniowy i podsumujemy do\u015bwiadczenia, kt\u00f3re zdobyli\u015bmy podczas wdra\u017cania takich \"inteligentnych technologii\" w procesy biznesowe klienta.<\/li>\n<\/ul>\n<p>\nJak czyta\u0107 artyku\u0142. Je\u015bli czyta\u0142e\u015b poprzedni artyku\u0142, mo\u017cesz od razu przej\u015b\u0107 do rozdzia\u0142u \u201ePrzegl\u0105d istniej\u0105cych rozwi\u0105za\u0144\u201d, je\u015bli nie, to opis rozwi\u0105zania problemu znajduje si\u0119 w spoilerze poni\u017cej.<\/p>\n<p><b class=\"spoiler_title\">Opis rozwi\u0105zywanego problemu na magazynie klienta<\/b><\/p>\n<h4>W\u0105skie miejsce w procesach<\/h4>\n<p>\nW 2018 roku zrealizowali\u015bmy projekt wdro\u017cenia <i>WMS<\/i>-systemu w magazynie \"Dom Handlowy \"LD\" w Chelyabinsku. Wdro\u017cyli\u015bmy produkt \"1C-Logistyka: Zarz\u0105dzanie magazynem 3\" na 20 stanowisk roboczych: operatorzy <i>WMS<\/i>, magazynierzy, kierowcy w\u00f3zk\u00f3w wid\u0142owych. Magazyn \u015bredniej wielko\u015bci, oko\u0142o 4 tys. m2, liczba kom\u00f3rek 5000 i liczba SKU 4500. W magazynie przechowywane s\u0105 kulowe zawory w\u0142asnej produkcji w r\u00f3\u017cnych rozmiarach, od 1 kg do 400 kg. Zapasy w magazynie s\u0105 przechowywane w podziale na partie, poniewa\u017c istnieje potrzeba selekcji towaru wed\u0142ug FIFO.<\/p>\n<p>Podczas projektowania schemat\u00f3w automatyzacji proces\u00f3w magazynowych napotkali\u015bmy istniej\u0105cy problem nieoptymalnego przechowywania zapas\u00f3w. Specyfika przechowywania i uk\u0142adania zawor\u00f3w jest taka, \u017ce w jednej kom\u00f3rce do przechowywania jednostkowego mo\u017ce znajdowa\u0107 si\u0119 tylko asortyment jednej partii (patrz rys. 1). Produkty przychodz\u0105 do magazynu codziennie, a ka\u017cdy przyjazd to oddzielna partia. W wyniku miesi\u0105ca pracy magazynu powstaje 30 oddzielnych partii, przy tym ka\u017cda musi by\u0107 przechowywana w oddzielnej kom\u00f3rce. Towar cz\u0119sto jest pobierany nie w ca\u0142o\u015bci, a sztukami, co powoduje, \u017ce w strefie poboru jednostkowego w wielu kom\u00f3rkach sytuacja prezentuje si\u0119 nast\u0119puj\u0105co: w kom\u00f3rce o obj\u0119to\u015bci ponad 1 m3 znajduje si\u0119 kilka sztuk zawor\u00f3w, kt\u00f3re zajmuj\u0105 mniej ni\u017c 5-10% obj\u0119to\u015bci kom\u00f3rki. <\/p>\n<p><img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/a7c03f2302c3be02c00c670453353f16.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<i>Rys. 1. Zdj\u0119cie kilku sztuk w kom\u00f3rce<\/i><\/p>\n<p>Wida\u0107 nieoptymalne wykorzystanie mocy magazynowych. Aby obrazowa\u0107 skal\u0119 problemu, przytocz\u0119 liczby: \u015brednio takich kom\u00f3rek o obj\u0119to\u015bci powy\u017cej 1 m3 z 'niewielkimi' zapasami w r\u00f3\u017cnych okresach pracy magazynu mo\u017cna naliczy\u0107 od 100 do 300 kom\u00f3rek. Poniewa\u017c magazyn jest stosunkowo ma\u0142y, w sezonach wzmo\u017conej pracy to zjawisko staje si\u0119 'w\u0105skim gard\u0142em', co znacznie spowalnia procesy przyj\u0119\u0107 i wydania towar\u00f3w.<\/p>\n<h4>Pomys\u0142 rozwi\u0105zania problemu<\/h4>\n<p>\nPojawi\u0142 si\u0119 pomys\u0142: partie zapas\u00f3w z najbli\u017cszymi datami sprowadza\u0107 do jednej wsp\u00f3lnej partii, a takie zapasy z ujednolicon\u0105 parti\u0105 umieszcza\u0107 kompaktowo razem w jednej kom\u00f3rce lub w kilku, je\u015bli miejsca w jednej nie b\u0119dzie wystarczaj\u0105ce na przechowanie ca\u0142ej ilo\u015bci zapas\u00f3w. Przyk\u0142ad takiego '\u015bci\u015bni\u0119cia' przedstawiono na rysunku 2.<\/p>\n<p><img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/792f114a7afa6272a6d152a784650681.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<i>Rys. 2. Schemat \u015bci\u015bni\u0119cia zapas\u00f3w w kom\u00f3rkach<\/i><\/p>\n<p>To znacznie redukuje zajmowan\u0105 przestrze\u0144 magazynow\u0105, kt\u00f3ra b\u0119dzie wykorzystywana pod nowy towar. W sytuacji przeci\u0105\u017cenia zdolno\u015bci magazynowych taka miara jest absolutnie konieczna, w przeciwnym razie mo\u017ce zabrakn\u0105\u0107 wolnej przestrzeni na umieszczenie nowego towaru, co doprowadzi do zastoju proces\u00f3w magazynowania oraz zaopatrzenia, a co za tym idzie, do zastoju przyj\u0119\u0107 i wysy\u0142ek. Wcze\u015bniej, przed wdro\u017ceniem systemu WMS, tak\u0105 operacj\u0119 wykonywano r\u0119cznie, co by\u0142o ma\u0142o efektywne, poniewa\u017c proces wyszukiwania odpowiednich zapas\u00f3w w kom\u00f3rkach by\u0142 do\u015b\u0107 d\u0142ugi. Teraz, wraz z wdro\u017ceniem systemu WMS, zdecydowano si\u0119 zautomatyzowa\u0107, przyspieszy\u0107 i uczyni\u0107 go inteligentnym.<\/p>\n<p>Proces rozwi\u0105zania takiego zadania dzieli si\u0119 na 2 etapy: <\/p>\n<ul>\n<li>na pierwszym etapie znajdujemy grupy partii bliskie pod wzgl\u0119dem daty do skompresowania (temu zadaniu po\u015bwi\u0119cone <noindex><a rel=\"nofollow\" href=\"https:\/\/habr.com\/ru\/post\/463289\/\">poprzedni artyku\u0142<\/a><\/noindex>);<\/li>\n<li>na drugim etapie obliczamy dla ka\u017cdej grupy partii maksymalnie kompaktowe rozmieszczenie zapas\u00f3w towaru w kom\u00f3rkach. <\/li>\n<\/ul>\n<p>\nW bie\u017c\u0105cym artykule zatrzymamy si\u0119 na drugim etapie algorytmu.<\/p>\n<h4>Przegl\u0105d istniej\u0105cych rozwi\u0105za\u0144<\/h4>\n<p>\nZanim przejdziemy do opisu opracowanych przez nas algorytm\u00f3w, warto przeprowadzi\u0107 kr\u00f3tki przegl\u0105d system\u00f3w ju\u017c istniej\u0105cych na rynku, <i>WMS<\/i>w kt\u00f3rych zrealizowano podobn\u0105 funkcjonalno\u015b\u0107 optymalnego skompresowania.<\/p>\n<p>Na pierwszym miejscu nale\u017cy zauwa\u017cy\u0107 produkt \u201e1C: Przedsi\u0119biorstwo 8. WMS Logistyka. Zarz\u0105dzanie magazynem 4\u201d, kt\u00f3ry nale\u017cy do firmy 1C i jest dystrybuowany przez t\u0119 firm\u0119, i nale\u017cy do czwartej generacji <i>WMS<\/i>-system\u00f3w opracowanych przez firm\u0119 AXELOT. W tym systemie zg\u0142oszono funkcjonalno\u015b\u0107 kompresji, maj\u0105c\u0105 na celu \u0142\u0105czenie rozproszonych zapas\u00f3w towar\u00f3w w jednej wsp\u00f3lnej kom\u00f3rce. Nale\u017cy doda\u0107, \u017ce funkcjonalno\u015b\u0107 kompresji w takim systemie obejmuje tak\u017ce inne mo\u017cliwo\u015bci, na przyk\u0142ad popraw\u0119 rozmieszczenia towar\u00f3w w kom\u00f3rkach zgodnie z ich klasami ABC, ale na tym si\u0119 nie zatrzymamy. <\/p>\n<p>Analizuj\u0105c kod systemu \"1C: Przedsi\u0119biorstwo 8. WMS Logistyka. Zarz\u0105dzanie magazynem 4\" (kt\u00f3ry w tej cz\u0119\u015bci funkcjonalno\u015bci jest otwarty), mo\u017cna wyci\u0105gn\u0105\u0107 nast\u0119puj\u0105ce wnioski. Algorytm kompresji zapas\u00f3w wdra\u017ca do\u015b\u0107 prymitywn\u0105 liniow\u0105 logik\u0119, a o jakiejkolwiek \"optymalnej\" kompresji nie mo\u017ce by\u0107 mowy. Oczywi\u015bcie, nie przewiduje on klastrowania partii. Kilku klient\u00f3w, u kt\u00f3rych taki system zosta\u0142 wdro\u017cony, skar\u017cy\u0142o si\u0119 na wyniki planowania kompresji. Na przyk\u0142ad, w praktyce cz\u0119sto mia\u0142a miejsce taka sytuacja: 100 szt. zapas\u00f3w towaru z jednej kom\u00f3rki planuje si\u0119 przenie\u015b\u0107 do innej kom\u00f3rki, gdzie le\u017cy 1 szt. towaru, chocia\u017c optymalnie z punktu widzenia czasu lepiej by\u0142oby zrobi\u0107 odwrotnie.<\/p>\n<p>Funkcjonalno\u015b\u0107 kompresji zapas\u00f3w towar\u00f3w w kom\u00f3rkach jest r\u00f3wnie\u017c zg\u0142aszana w wielu zagranicznych <i>WMS<\/i>-systemach, ale niestety nie mamy ani rzeczywistych recenzji dotycz\u0105cych efektywno\u015bci pracy algorytm\u00f3w (to jest tajemnica handlowa), ani tym bardziej poj\u0119cia o g\u0142\u0119boko\u015bci ich logiki (oprogramowanie w\u0142asno\u015bciowe z zamkni\u0119tym kodem), wi\u0119c nie mo\u017cemy oceni\u0107.<\/p>\n<h4>Poszukiwanie modelu matematycznego zadania<\/h4>\n<p>\nAby zaprojektowa\u0107 wysokiej jako\u015bci algorytmy do rozwi\u0105zania zadania, najpierw nale\u017cy to zadanie jasno matematycznie sformu\u0142owa\u0107, co uczynimy.<\/p>\n<p>Istnieje wiele kom\u00f3rek <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/bfff1fb95dd0c633ada02b9398778eab.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, w kt\u00f3rych znajduj\u0105 si\u0119 zapasy pewnego towaru. Takie kom\u00f3rki b\u0119dziemy dalej nazywa\u0107 kom\u00f3rkami-dawcami. Oznaczmy <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/50ef693482cd4cb27410b30b0bc107b1.jpeg\" style=\"display:block;margin: 0 auto;\" \/> obj\u0119to\u015b\u0107 towaru znajduj\u0105cego si\u0119 w kom\u00f3rce <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/dc7faf1656fb12c8e467fe3a5b8977fa.jpeg\" style=\"display:block;margin: 0 auto;\" \/>$.<\/p>\n<p>Wa\u017cne jest, aby powiedzie\u0107, \u017ce w procedurze kompresji mo\u017ce bra\u0107 udzia\u0142 tylko jeden towar z jednej partii lub kilku partii, kt\u00f3re wcze\u015bniej zosta\u0142y po\u0142\u0105czone w klaster (czytaj <noindex><a rel=\"nofollow\" href=\"https:\/\/habr.com\/ru\/post\/463289\/\">poprzedni artyku\u0142<\/a><\/noindex>), co wynika ze specyfiki przechowywania i uk\u0142adania towar\u00f3w. Dla r\u00f3\u017cnych towar\u00f3w lub r\u00f3\u017cnych klastr\u00f3w partii powinna by\u0107 uruchamiana osobna procedura kompresji.<\/p>\n<p>Istnieje wiele kom\u00f3rek <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/b9aafca691626263d8ecc2faed8dfcfe.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, do kt\u00f3rych potencjalnie mog\u0105 by\u0107 przeniesione zapasy z kom\u00f3rek-dawc\u00f3w. Takie kom\u00f3rki b\u0119dziemy dalej nazywa\u0107 kom\u00f3rkami-pojemnikami. Mog\u0105 to by\u0107 zar\u00f3wno wolne kom\u00f3rki w magazynie, jak i kom\u00f3rki-dawcy z zbioru <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/25731bc72091e2284e76c434d2abdcfd.jpeg\" style=\"display:block;margin: 0 auto;\" \/>. Zawsze zbi\u00f3r <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/d407f97344131a3056b1eab1d3dd7dcd.jpeg\" style=\"display:block;margin: 0 auto;\" \/> jest podzbiorem <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/581806d446f3d8c91927045249698e71.jpeg\" style=\"display:block;margin: 0 auto;\" \/>.<\/p>\n<p>Dla ka\u017cdej kom\u00f3rki <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/b084d5852a1e4f00d2498640534d66e9.jpeg\" style=\"display:block;margin: 0 auto;\" \/> z zbioru <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/236efb40a21865f78240c8e14303cc2e.jpeg\" style=\"display:block;margin: 0 auto;\" \/> ustawione s\u0105 ograniczenia dotycz\u0105ce pojemno\u015bci <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/fe253cfe5f2aa39bc8e064674fb206f8.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, mierzone w dm3. Jeden dm3 to sze\u015bcian o bokach 10 cm. Produkty przechowywane w magazynie s\u0105 wystarczaj\u0105co du\u017ce, dlatego w tym przypadku taka dyskretyzacja jest jak najbardziej wystarczaj\u0105ca. <\/p>\n<p>Podano macierz najkr\u00f3tszych odleg\u0142o\u015bci <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/48c133b0affa17f6a2367a02241d5f17.jpeg\" style=\"display:block;margin: 0 auto;\" \/> w metrach mi\u0119dzy ka\u017cd\u0105 par\u0105 kom\u00f3rek <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/8fd860e331a8e42dd258857bdf580c05.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, gdzie <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/feb9a48c6e9e4ccd8e9fa1db5565e96e.jpeg\" style=\"display:block;margin: 0 auto;\" \/> i <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/d9a48a8a22ea984d0769373c5620c99a.jpeg\" style=\"display:block;margin: 0 auto;\" \/> nale\u017c\u0105 do zbior\u00f3w <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/e2dd20fda8a8b0b5ea2173c14f04fe00.jpeg\" style=\"display:block;margin: 0 auto;\" \/> i <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/0dabafdb55ac6b8495f6d5f657d6c01d.jpeg\" style=\"display:block;margin: 0 auto;\" \/> odpowiednio. <\/p>\n<p>Oznaczmy <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/2994defad9bb0a44741f31a85273abf2.jpeg\" style=\"display:block;margin: 0 auto;\" \/> \u201ekoszty\u201d przemieszczenia towaru z kom\u00f3rki<img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/a2e54425ec786d3a88290dda47f4b9cb.jpeg\" style=\"display:block;margin: 0 auto;\" \/> do kom\u00f3rki <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/bf4a9f1a1f396a9b7b6244cf8c77ecc8.jpeg\" style=\"display:block;margin: 0 auto;\" \/>. Oznaczmy <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/6f4c10386fc638f6ca37e0ccdcf4ccb4.jpeg\" style=\"display:block;margin: 0 auto;\" \/> \u201ekoszty\u201d wyboru kontenera <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/613d619ea5951551427f0cd45c7f79bf.jpeg\" style=\"display:block;margin: 0 auto;\" \/> do przemieszczenia w niego odpad\u00f3w z innych kom\u00f3rek. Jak dok\u0142adnie i w jakich jednostkach miar b\u0119d\u0105 obliczane warto\u015bci <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/22130f203fde6271e33cba0db14d6a80.jpeg\" style=\"display:block;margin: 0 auto;\" \/> i <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/d75c50be3ee4f8e02a9523f2d2109f0d.jpeg\" style=\"display:block;margin: 0 auto;\" \/> przyjrzymy si\u0119 dalej (zob. rozdzia\u0142 przygotowanie danych wej\u015bciowych), teraz wystarczy powiedzie\u0107, \u017ce takie wielko\u015bci b\u0119d\u0105 wprost proporcjonalne do wielko\u015bci <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/5e4e80f122ac1fe43f94de2726c0d3b7.jpeg\" style=\"display:block;margin: 0 auto;\" \/> i <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/1b6a9d41ba4ad68d5a5fbae883b80596.jpeg\" style=\"display:block;margin: 0 auto;\" \/> odpowiednio.<\/p>\n<p>Oznaczmy przez <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/1ebfe4179740aff474a78d11a004aaa7.jpeg\" style=\"display:block;margin: 0 auto;\" \/> zmienn\u0105 przyjmuj\u0105c\u0105 warto\u015b\u0107 1, je\u015bli odpady z kom\u00f3rki <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/48f9789788c38746ba4ac0c947e0a4ca.jpeg\" style=\"display:block;margin: 0 auto;\" \/> s\u0105 przemieszczenia do kontenera <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/58ce0b4c9bfb946c00bffdc0c50a05d6.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, i 0 w przeciwnym razie. Oznaczmy przez <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/642d5627193c55922be5274826b75cb4.jpeg\" style=\"display:block;margin: 0 auto;\" \/> zmienn\u0105 przyjmuj\u0105c\u0105 warto\u015b\u0107 1, je\u015bli kontener <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/6939c9f4daf2ecd531d9c2518c03401d.jpeg\" style=\"display:block;margin: 0 auto;\" \/> zawiera odpady towar\u00f3w, i 0 w przeciwnym razie.<\/p>\n<p><b>Zadanie jest sformu\u0142owane w ten spos\u00f3b<\/b>: nale\u017cy znale\u017a\u0107 taki zbi\u00f3r kontener\u00f3w <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/d6065db66f210083181dabb39f0e9e16.jpeg\" style=\"display:block;margin: 0 auto;\" \/> i w ten spos\u00f3b \u201eprzypi\u0105\u0107\u201d kom\u00f3rki-dawcy do kom\u00f3rek-kontener\u00f3w, aby zminimalizowa\u0107 funkcj\u0119<\/p>\n<p><img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/68d7f0271f9761fff2c762e0fe6f5207.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>przy ograniczeniach<\/p>\n<p><img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/d57b8752aa4a8140e239dfa7fdc9ec36.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>\u0141\u0105cznie w trakcie obliczania rozwi\u0105zania zadania d\u0105\u017cymy do: <\/p>\n<ul>\n<li>po pierwsze, oszcz\u0119dzania przestrzeni magazynowej; <\/li>\n<li>po drugie, oszcz\u0119dzania czasu magazynier\u00f3w. <\/li>\n<\/ul>\n<p>\nOstatnie ograniczenie oznacza, \u017ce nie mo\u017cemy przemieszcza\u0107 towar\u00f3w do kontenera, kt\u00f3rego nie wybrali\u015bmy, a tym samym nie \u201eponie\u015bli\u015bmy koszt\u00f3w\u201d jego wyboru. To ograniczenie oznacza r\u00f3wnie\u017c, \u017ce obj\u0119to\u015b\u0107 przemieszczanych towar\u00f3w z kom\u00f3rek do kontenera nie powinna przekracza\u0107 pojemno\u015bci kontenera. Pod rozwi\u0105zaniem zadania rozumiemy zbi\u00f3r kontener\u00f3w <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/db0f987f2d388ad1394d21404e183c93.jpeg\" style=\"display:block;margin: 0 auto;\" \/> i sposoby przypinania kom\u00f3rek-dawc\u00f3w do kontener\u00f3w.<\/p>\n<p>Takie sformu\u0142owanie zadania optymalizacji nie jest nowe i by\u0142o badane przez wielu matematyk\u00f3w ju\u017c od pocz\u0105tku lat 80. ubieg\u0142ego wieku. W literaturze zagranicznej istniej\u0105 2 zadania optymalizacji z odpowiednim modelem matematycznym: <noindex><a rel=\"nofollow\" href=\"http:\/\/www.math.nsc.ru\/AP\/benchmarks\/CFLP\/cflp.html\">Problem lokalizacji obiekt\u00f3w z jednego \u017ar\u00f3d\u0142a o ograniczonej pojemno\u015bci<\/a><\/noindex> i <noindex><a rel=\"nofollow\" href=\"https:\/\/waset.org\/publications\/10002290\/a-survey-of-discrete-facility-location-problems\">Problem lokalizacji obiekt\u00f3w z wielu \u017ar\u00f3de\u0142 o ograniczonej pojemno\u015bci<\/a><\/noindex> (o r\u00f3\u017cnicach zada\u0144 porozmawiamy p\u00f3\u017aniej). Warto zauwa\u017cy\u0107, \u017ce w literaturze matematycznej sformu\u0142owania tych dw\u00f3ch zada\u0144 optymalizacji wyra\u017cane s\u0105 w terminach rozmieszczenia przedsi\u0119biorstw na terenie, st\u0105d nazwa \u201eFacility Location\u201d. W wi\u0119kszo\u015bci to jest uk\u0142on w stron\u0119 tradycji, poniewa\u017c po raz pierwszy potrzeba rozwi\u0105zania takich zada\u0144 kombinatorycznych pojawi\u0142a si\u0119 w dziedzinie logistyki, g\u0142\u00f3wnie w przemy\u015ble wojskowym w latach 50. XX wieku. W terminach rozmieszczenia przedsi\u0119biorstw takie zadania formu\u0142uje si\u0119 w ten spos\u00f3b: <\/p>\n<ul>\n<li>Istnieje sko\u0144czona liczba miast, w kt\u00f3rych potencjalnie mo\u017cna ulokowa\u0107 zak\u0142ady produkcyjne (dalej miasta-producent\u00f3w). Dla ka\u017cdego miasta-producenta okre\u015blono koszty otwarcia zak\u0142adu oraz ograniczenia mocy produkcyjnych otwieranego w nim przedsi\u0119biorstwa.<\/li>\n<li>Istnieje sko\u0144czona liczba miast, w kt\u00f3rych faktycznie znajduj\u0105 si\u0119 klienci (dalej miasta-klienci). Dla ka\u017cdego takiego miasta-klienta okre\u015blono wolumen popytu na produkty. Dla uproszczenia przyjmijmy, \u017ce produkt wytwarzany przez zak\u0142ady i konsumowany przez klient\u00f3w jest jeden.<\/li>\n<li>Dla ka\u017cdej pary miasto-producent i miasto-klient okre\u015blono wysoko\u015b\u0107 koszt\u00f3w transportu zwi\u0105zanych z dostaw\u0105 wymaganego wolumenu produkt\u00f3w od producenta do klienta.<\/li>\n<\/ul>\n<p>\nNale\u017cy znale\u017a\u0107, w jakich miastach otworzy\u0107 zak\u0142ady oraz jak przypisa\u0107 klient\u00f3w do tych zak\u0142ad\u00f3w, aby:<\/p>\n<ul>\n<li>Suma koszt\u00f3w otwarcia zak\u0142ad\u00f3w i koszt\u00f3w transportu by\u0142a minimalna;<\/li>\n<li>Wolumen popytu klient\u00f3w przypisanych do jakiegokolwiek otwartego zak\u0142adu nie przekracza\u0142 mo\u017cliwo\u015bci produkcyjnych tego zak\u0142adu.<\/li>\n<\/ul>\n<p>\nTeraz warto powiedzie\u0107 o jedynej r\u00f3\u017cnicy mi\u0119dzy tymi dwoma klasycznymi zadaniami:<\/p>\n<ul>\n<li>Single-Source Capacitated Facility Location Problem \u2013 klient zaopatrywany jest tylko z jednego otwartego zak\u0142adu;<\/li>\n<li>Multi-Source Capacitated Facility Location Problem \u2013 klient mo\u017ce by\u0107 zaopatrywany z kilku otwartych zak\u0142ad\u00f3w jednocze\u015bnie.<\/li>\n<\/ul>\n<p>\nR\u00f3\u017cnica mi\u0119dzy tymi dwoma zadaniami na pierwszy rzut oka wydaje si\u0119 znikoma, ale w rzeczywisto\u015bci prowadzi do zupe\u0142nie r\u00f3\u017cnej struktury kombinatorycznej takich zada\u0144 i, w konsekwencji, do zupe\u0142nie r\u00f3\u017cnych algorytm\u00f3w ich rozwi\u0105zania. R\u00f3\u017cnice mi\u0119dzy zadaniami zaprezentowane s\u0105 na poni\u017cszym rysunku.<\/p>\n<p><img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/77962906c7de2fced174d4a2b7785cc2.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<i>Rys.3. a) Multi-Source Capacitated Facility Location Problem<\/i><\/p>\n<p><img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/0242437e488a1aea0f00ce9ede02886d.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<i>Rys.3. b) Single-Source Capacitated Facility Location Problem<\/i><\/p>\n<p>Oba zadania <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/b16678811fceca32d18c94e71cfaa603.jpeg\" style=\"display:block;margin: 0 auto;\" \/>-trudne, tzn. nie ma dok\u0142adnego algorytmu, kt\u00f3ry w czasie wielomianowym wzgl\u0119dem rozmiaru danych wej\u015bciowych rozwi\u0105za\u0142by takie zadanie. M\u00f3wi\u0105c pro\u015bciej, wszystkie dok\u0142adne algorytmy do rozwi\u0105zania tego problemu b\u0119d\u0105 dzia\u0142a\u0107 w czasie eksponencjalnym, chocia\u017c by\u0107 mo\u017ce szybciej ni\u017c pe\u0142ne przeszukiwanie wszystkich mo\u017cliwo\u015bci. Poniewa\u017c problem <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/09f42b4b905d9bdc3f00f21098f84ad7.jpeg\" style=\"display:block;margin: 0 auto;\" \/>-jest trudny, wi\u0119c b\u0119dziemy rozwa\u017ca\u0107 tylko przybli\u017cone heurystyki, czyli algorytmy, kt\u00f3re b\u0119d\u0105 oblicza\u0107 stabilne rozwi\u0105zania bardzo bliskie optymalnym i b\u0119d\u0105 dzia\u0142a\u0107 wystarczaj\u0105co szybko. Je\u015bli pojawi si\u0119 zainteresowanie takimi zadaniami, to tutaj mo\u017cna znale\u017a\u0107 dobry przegl\u0105d w j\u0119zyku rosyjskim.<\/p>\n<p>Je\u015bli odniesiemy to do terminologii naszego zadania optymalnego pakowania towar\u00f3w w kom\u00f3rkach, to:<\/p>\n<ul>\n<li>miasta-klienci \u2013 to kom\u00f3rki-dawcy <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/e6db70dbb85d1c7249f4c30e97e2942e.jpeg\" style=\"display:block;margin: 0 auto;\" \/> z pozosta\u0142o\u015bciami towaru, <\/li>\n<li>miasta-producenci \u2013 kom\u00f3rki-pojemniki <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/5ef31fe0483d2bc9a0c18b5dc25e9867.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, do kt\u00f3rych planowane jest umieszczenie pozosta\u0142o\u015bci z innych kom\u00f3rek,<\/li>\n<li>koszty transportu \u2013 koszty czasu <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/afac567e9057a46de6e0f3d29df9315a.jpeg\" style=\"display:block;margin: 0 auto;\" \/> magazyniera na przeniesienia obj\u0119to\u015bci towaru z kom\u00f3rki-dawcy <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/829df82255e40cb99024d7c8dd408d41.jpeg\" style=\"display:block;margin: 0 auto;\" \/> do kom\u00f3rki-pojemnika <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/b87c9d9260adb26ce623dbe80b4f22c2.jpeg\" style=\"display:block;margin: 0 auto;\" \/>; <\/li>\n<li>koszty otwarcia przedsi\u0119biorstwa \u2013 koszty wyboru pojemnika <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/db4d21fc2067a23b5af5bb01c412323a.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, r\u00f3wne obj\u0119to\u015bci kom\u00f3rki-pojemnika <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/b631a01a65f1ffd3348cbcaeeab11f0d.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, pomno\u017conej przez pewien wsp\u00f3\u0142czynnik oszcz\u0119dno\u015bci wolnych obj\u0119to\u015bci (warto\u015b\u0107 wsp\u00f3\u0142czynnika zawsze &gt; 1) (patrz rozdzia\u0142 przygotowanie danych wej\u015bciowych).<\/li>\n<\/ul>\n<p>\nPo tym, jak analogi\u0119 do znanych klasycznych zada\u0144 transportowych przeprowadzono, konieczne jest odpowiedzenie na wa\u017cne pytanie, od kt\u00f3rego zale\u017cy wyb\u00f3r architektury algorytmu rozwi\u0105zania: czy przenoszenie pozosta\u0142o\u015bci z kom\u00f3rki-dawcy jest mo\u017cliwe tylko do jednego i tylko jednego pojemnika (Single-Source), czy te\u017c przenoszenie pozosta\u0142o\u015bci mo\u017ce odbywa\u0107 si\u0119 do kilku kom\u00f3rek-pojemnik\u00f3w (Multi-Source)?<\/p>\n<p>Warto zauwa\u017cy\u0107, \u017ce w praktyce obie formy zadania mog\u0105 mie\u0107 miejsce. Przedstawimy wszystkie 'za' i 'przeciw' dla ka\u017cdej z takich form poni\u017cej:<\/p>\n<table>\n<tr>\n<th>Wariant zadania<\/th>\n<th>Zalety wariantu<\/th>\n<th>Wady wariantu<\/th>\n<\/tr>\n<tr>\n<td>Single-Source<\/td>\n<td>Operacje przenoszenia towar\u00f3w, obliczone na podstawie tego wariantu zadania:<\/p>\n<ul>\n<li>wymagaj\u0105 mniej kontroli ze strony magazyniera (wzi\u0105\u0142 WSZYSTKO z jednej kom\u00f3rki, po\u0142o\u017cy\u0142 WSZYSTKO w innej kom\u00f3rce-pojemniku), co eliminuje ryzyka: b\u0142\u0119d\u00f3w przy przeliczaniu ilo\u015bci towaru podczas wykonywania operacji \u201eW\u0142o\u017cy\u0107 do kom\u00f3rki\u201d; b\u0142\u0119d\u00f3w przy wprowadzaniu przeliczonej ilo\u015bci do TSD;<\/li>\n<li>Nie ma potrzeby przeliczania ilo\u015bci towar\u00f3w podczas realizacji operacji \u201eUmie\u015bci\u0107 w kom\u00f3rce\u201d oraz wprowadzania ich do TSD.<\/li>\n<\/ul>\n<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>Multi-Source<\/td>\n<td>Kompresje, obliczone dla tej wersji zadania, s\u0105 zazwyczaj bardziej kompaktowe o 10-15% w por\u00f3wnaniu do kompresji obliczonych dla wariantu \u201eSingle-Source\u201d. Nale\u017cy jednak zauwa\u017cy\u0107, \u017ce im mniejsza ilo\u015b\u0107 resztek w kom\u00f3rkach-dawcach, tym r\u00f3\u017cnica w kompaktowo\u015bci jest mniejsza.<\/td>\n<td>Operacje przenoszenia towar\u00f3w, obliczone na podstawie tego wariantu zadania:<\/p>\n<ul>\n<li>Wymaga wi\u0119kszej kontroli ze strony magazyniera (konieczno\u015b\u0107 przeliczania ilo\u015bci towaru przenoszonego do ka\u017cdej z zaplanowanych kom\u00f3rek-pojemnik\u00f3w), co eliminuje ryzyko b\u0142\u0119du podczas przeliczania ilo\u015bci towaru i wprowadzania danych do TSD podczas realizacji operacji \u201eUmie\u015bci\u0107 w kom\u00f3rce\u201d.<\/li>\n<li>Wymaga czasu na przeliczenie ilo\u015bci towar\u00f3w podczas realizacji operacji \u201eUmie\u015bci\u0107 w kom\u00f3rce\u201d.<\/li>\n<li>Wymaga czasu na \u201ekoszty po\u015brednie\u201d (zatrzymanie si\u0119, podej\u015bcie do palety, zeskanowanie kodu kreskowego kom\u00f3rki-pojemnika) podczas realizacji operacji \u201eUmie\u015bci\u0107 w kom\u00f3rce\u201d.<\/li>\n<li>Czasami algorytm mo\u017ce \u201edzieli\u0107\u201d ilo\u015b\u0107 praktycznie pe\u0142nego paleta pomi\u0119dzy du\u017c\u0105 ilo\u015b\u0107 kom\u00f3rek-pojemnik\u00f3w, gdzie ju\u017c znajduje si\u0119 odpowiedni towar, co z punktu widzenia klienta by\u0142o nieakceptowalne.<\/li>\n<\/ul>\n<\/td>\n<\/tr>\n<\/table>\n<p><i>Tabela 1. Plusy i minusy wariant\u00f3w Single-Source i Multi-Source.<\/i><\/p>\n<p>Poniewa\u017c liczba plus\u00f3w dla wariantu Single-Source jest wi\u0119ksza, a tak\u017ce bior\u0105c pod uwag\u0119, \u017ce im mniejsza ilo\u015b\u0107 resztek w kom\u00f3rkach-dawcach, tym r\u00f3\u017cnica w stopniu kompaktowo\u015bci kompresji, obliczonej w obu wariantach zadania, jest mniejsza, nasz wyb\u00f3r pad\u0142 na wariant Single-Source.<\/p>\n<p>Warto powiedzie\u0107, \u017ce rozwi\u0105zanie wariantu Multi-Source r\u00f3wnie\u017c ma swoje miejsce. Istnieje wiele efektywnych algorytm\u00f3w do jego rozwi\u0105zania, wi\u0119kszo\u015b\u0107 z nich sprowadza si\u0119 do rozwi\u0105zania szeregu zada\u0144 transportowych. S\u0105 tak\u017ce nie tylko efektywne algorytmy, ale i eleganckie, na przyk\u0142ad,<noindex><a rel=\"nofollow\" href=\"http:\/\/www.mathnet.ru\/php\/archive.phtml?wshow=paper&amp;jrnid=da&amp;paperid=791&amp;option_lang=rus\"> tutaj.<\/a><\/noindex><\/p>\n<h4>Przygotowanie danych wej\u015bciowych<\/h4>\n<p>\nZanim przyst\u0105pimy do analizy i opracowywania algorytmu do rozwi\u0105zania zadania, nale\u017cy okre\u015bli\u0107, jakie dane i w jakiej formie b\u0119dziemy mu dostarcza\u0107 na wej\u015bciu. Nie ma problemu z obj\u0119to\u015bciami resztek towar\u00f3w w kom\u00f3rkach-dawcach oraz pojemno\u015bci\u0105 kom\u00f3rek-pojemnik\u00f3w, poniewa\u017c to jest trywialne \u2013 takie wielko\u015bci b\u0119d\u0105 mierzone w m3, ale z kosztami korzystania z kom\u00f3rki-pojemnika i macierz\u0105 koszt\u00f3w przeniesienia sprawa nie jest ju\u017c taka prosta!<\/p>\n<p>Na pocz\u0105tku rozwa\u017cmy obliczenia. <b>koszt\u00f3w transportu towar\u00f3w<\/b> z kom\u00f3rki-dawcy do kom\u00f3rki-pojemnika. Przede wszystkim nale\u017cy okre\u015bli\u0107 w jakich jednostkach miary b\u0119dziemy oblicza\u0107 koszty transportu. Dwie najoczywistsze opcje to metry i sekundy. W \u201eczystych\u201d metrach liczenie koszt\u00f3w transportu jest bezsensowne. Poka\u017cmy to na przyk\u0142adzie. Niech kom\u00f3rka <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/990a5fae8988ddf41395483263de2bcc.jpeg\" style=\"display:block;margin: 0 auto;\" \/> znajduje si\u0119 na pierwszym poziomie, kom\u00f3rka <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/9d17b98e807444f431d01f2e77fc96f7.jpeg\" style=\"display:block;margin: 0 auto;\" \/> jest oddalona o 30 metr\u00f3w i znajduje si\u0119 na drugim poziomie:<\/p>\n<ul>\n<li>Transport z <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/3188fd9853d5cda2834a5083539ac11d.jpeg\" style=\"display:block;margin: 0 auto;\" \/> do <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/e212a0be19ea687b1017c3aacec3df19.jpeg\" style=\"display:block;margin: 0 auto;\" \/> jest bardziej kosztowny ni\u017c transport z <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/d65e60dec37fb3b83c83ca1c566f1ee9.jpeg\" style=\"display:block;margin: 0 auto;\" \/> do <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/4168198a4c90bdd3dd4b7f0c904b06e0.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, poniewa\u017c \u0142atwiej zsuwa\u0107 w d\u00f3\u0142 z drugiego poziomu (1,5-2 metry od pod\u0142ogi) ni\u017c podnosi\u0107 na drugi, chocia\u017c odleg\u0142o\u015b\u0107 b\u0119dzie przebyta taka sama;<\/li>\n<li>Przemieszczenie 1 szt. towaru z kom\u00f3rki <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/039864ccd0a2bd14a99a83494f056fa3.jpeg\" style=\"display:block;margin: 0 auto;\" \/> do <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/9f9bc7a256119b110f47760b145e174b.jpeg\" style=\"display:block;margin: 0 auto;\" \/> b\u0119dzie \u0142atwiejsze ni\u017c przemieszczenie 10 szt. tego samego towaru, chocia\u017c odleg\u0142o\u015b\u0107 b\u0119dzie przebyta taka sama.<\/li>\n<\/ul>\n<p>\nKoszty transportu najlepiej uwzgl\u0119dni\u0107 w sekundach, poniewa\u017c pozwala to uwzgl\u0119dni\u0107 r\u00f3\u017cnice w poziomach oraz r\u00f3\u017cnice w przemieszczeniu ilo\u015bci towaru. Aby uwzgl\u0119dni\u0107 koszty transportu w sekundach, musimy roz\u0142o\u017cy\u0107 operacj\u0119 transportu na elementarne sk\u0142adniki i dokona\u0107 pomiar\u00f3w czasu na wykonanie ka\u017cdej elementarnej cz\u0119\u015bci.<\/p>\n<p>Niech z kom\u00f3rki <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/538c4304e37f340a5a5a8e47e0ee2865.jpeg\" style=\"display:block;margin: 0 auto;\" \/> przemieszcza si\u0119 <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/6c7e32728f4771726f8ef9b2d78111d6.jpeg\" style=\"display:block;margin: 0 auto;\" \/> szt. towaru do kontenera <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/fc2ad051b500eae5884404f4b9419841.jpeg\" style=\"display:block;margin: 0 auto;\" \/>. Niech <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/6733192a31618a03e51e8e3133cb96ee.jpeg\" style=\"display:block;margin: 0 auto;\" \/> to \u015brednia pr\u0119dko\u015b\u0107 ruchu pracownika po magazynie, mierzona w m\/s. Niech <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/97f7e9c65c2196fa586f957618d1c8a2.jpeg\" style=\"display:block;margin: 0 auto;\" \/> i <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/bbe48d987f180e2f9ccec6e090e6f942.jpeg\" style=\"display:block;margin: 0 auto;\" \/> to \u015brednie pr\u0119dko\u015bci jednorazowego wykonania operacji we\u017a i po\u0142\u00f3\u017c odpowiednio dla obj\u0119to\u015bci towaru r\u00f3wnej 4 dm3 (\u015brednia obj\u0119to\u015b\u0107, jak\u0105 pracownik zabiera za 1 raz w magazynie podczas wykonywania operacji). Niech <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/267d74648f49d5a2d063b1377c6d2fe6.jpeg\" style=\"display:block;margin: 0 auto;\" \/> i <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/fefdd606d5a81ba4e2ce57b107dfe1e6.jpeg\" style=\"display:block;margin: 0 auto;\" \/> to wysoko\u015bci kom\u00f3rek, z kt\u00f3rych wykonywane s\u0105 operacje we\u017a i po\u0142\u00f3\u017c odpowiednio. Na przyk\u0142ad, \u015brednia wysoko\u015b\u0107 pierwszego poziomu (pod\u0142oga) wynosi 1 m, drugiego poziomu 2 m itd. Wtedy wz\u00f3r na obliczenie ca\u0142kowitego czasu wykonania operacji transportu <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/a48ae3c2e9dc8f2c3108cb2be1f96c40.jpeg\" style=\"display:block;margin: 0 auto;\" \/> wygl\u0105da nast\u0119puj\u0105co:<\/p>\n<p><img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/55afb96b1141bb5656351bdaeba31ae4.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>W tabeli 2 przedstawiono statystyki czasu wykonania ka\u017cdej elementarnej operacji, zebrane przez pracownik\u00f3w magazynu z uwzgl\u0119dnieniem specyfiki przechowywanego towaru.<\/p>\n<table>\n<tr>\n<th>Nazwa operacji<\/th>\n<th>Oznaczenie<\/th>\n<th>\u015arednia warto\u015b\u0107<\/th>\n<\/tr>\n<tr>\n<td>\u015arednia pr\u0119dko\u015b\u0107 ruchu pracownika po magazynie<\/td>\n<td><img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/dadbfb13d2b84b95ab2c5d653a21668b.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/td>\n<td>1,5 m\/s<\/td>\n<\/tr>\n<tr>\n<td>\u015arednia pr\u0119dko\u015b\u0107 wykonania jednej operacji po\u0142\u00f3\u017c (dla obj\u0119to\u015bci towaru 4 dm3)<\/td>\n<td><img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/aa619b43a70a7cf646ad35d5c8883329.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/td>\n<td>2,4 sek<\/td>\n<\/tr>\n<\/table>\n<p><i>Tabela 2. \u015aredni czas wykonania operacji magazynowych<\/i><\/p>\n<p>Ustalili\u015bmy metod\u0119 obliczania koszt\u00f3w transportu. Teraz nale\u017cy ustali\u0107, jak je oblicza\u0107. <b>koszty wyboru pojemnika<\/b>. Tutaj wszystko jest znacznie, znacznie bardziej skomplikowane ni\u017c w przypadku koszt\u00f3w przemieszczania, poniewa\u017c: <\/p>\n<ul>\n<li>po pierwsze, koszty powinny by\u0107 \u015bci\u015ble powi\u0105zane z obj\u0119to\u015bci\u0105 pojemnika \u2013 t\u0119 sam\u0105 obj\u0119to\u015b\u0107 reszty, przemieszczan\u0105 z kom\u00f3rek-donor\u00f3w, lepiej umie\u015bci\u0107 w mniejszym pojemniku ni\u017c w du\u017cym pojemniku, pod warunkiem, \u017ce taka obj\u0119to\u015b\u0107 ca\u0142kowicie mie\u015bci si\u0119 w obu pojemnikach. W ten spos\u00f3b, minimalizuj\u0105c ca\u0142kowite koszty wyboru pojemnik\u00f3w, staramy si\u0119 oszcz\u0119dza\u0107 \"deficytowe\" wolne moce magazynowe w obszarze strefy selekcji, aby zrealizowa\u0107 nast\u0119pne operacje rozlokowania towaru w kom\u00f3rkach. Na rysunku 4 pokazano opcje przemieszczania reszty do du\u017cych i ma\u0142ych pojemnik\u00f3w oraz konsekwencje tych opcji przemieszczania przy wykonywaniu nast\u0119pnych operacji magazynowych.<\/li>\n<li>po drugie, poniewa\u017c w rozwi\u0105zaniu pierwotnego zadania musimy zminimalizowa\u0107 ca\u0142kowite koszty, a to suma koszt\u00f3w zar\u00f3wno przemieszczania, jak i wyboru pojemnik\u00f3w, to obj\u0119to\u015bci kom\u00f3rek w metrach sze\u015bciennych nale\u017cy jako\u015b powi\u0105za\u0107 z sekundami, co wcale nie jest trywialne.<\/li>\n<\/ul>\n<p>\n<img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/2c906f9e80b32fcb111fcba7000ea2ba.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<i>Rys. 4. Opcje przemieszczania reszty do pojemnik\u00f3w o r\u00f3\u017cnej pojemno\u015bci.<\/i><\/p>\n<p>Na rysunku 4 na czerwono przedstawiono obj\u0119to\u015b\u0107 reszty, kt\u00f3ra ju\u017c nie mie\u015bci si\u0119 w pojemniku na drugim etapie rozmieszczania nast\u0119pnych towar\u00f3w. <\/p>\n<p>Pomog\u0105 powi\u0105za\u0107 metry sze\u015bcienne koszt\u00f3w wyboru pojemnika z sekundami koszt\u00f3w przemieszczania nast\u0119puj\u0105ce wymagania dotycz\u0105ce obliczanych rozwi\u0105za\u0144 zadania:<\/p>\n<ul>\n<li>Nale\u017cy zapewni\u0107, aby reszty z kom\u00f3rki-donora by\u0142y przemieszczane do kom\u00f3rki-pojemnika w ka\u017cdym przypadku, je\u015bli zmniejsza to og\u00f3ln\u0105 liczb\u0119 kom\u00f3rek-pojemnik\u00f3w, w kt\u00f3rych znajduje si\u0119 towar.<\/li>\n<li>Nale\u017cy zachowa\u0107 r\u00f3wnowag\u0119 mi\u0119dzy obj\u0119to\u015bciami pojemnik\u00f3w a kosztami czasu na przemieszczanie: na przyk\u0142ad, je\u015bli w nowej wersji rozwi\u0105zania zadania w por\u00f3wnaniu z poprzedni\u0105 wersj\u0105 zysk na obj\u0119to\u015bci jest du\u017cy, a strata w kosztach czasu ma\u0142a, to nale\u017cy wybiera\u0107 now\u0105 wersj\u0119.<\/li>\n<\/ul>\n<p>\nZacznijmy od ostatniego wymagania. Aby sprecyzowa\u0107 wieloznaczne s\u0142owo \u201er\u00f3wnowaga\u201d przeprowadzili\u015bmy ankiet\u0119 w\u015br\u00f3d pracownik\u00f3w magazynu w celu ustalenia nast\u0119puj\u0105cego. Niech b\u0119dzie kom\u00f3rka-pojemnik o obj\u0119to\u015bci <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/2b831b12448ccaee33c528ac622b7ee3.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, do kt\u00f3rej zaplanowano przemieszczanie reszty towar\u00f3w z kom\u00f3rek-donor\u00f3w, a ca\u0142kowity czas tego przemieszczania wynosi <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/8050f4b02464164d334048bda86b3923.jpeg\" style=\"display:block;margin: 0 auto;\" \/>. Niech b\u0119d\u0105 jeszcze kilka alternatywnych opcji rozmieszczenia tej samej ilo\u015bci towaru z tych samych kom\u00f3rek-donator\u00f3w w inne pojemniki, gdzie ka\u017cde rozmieszczenie ma swoje oceny. <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/76f11cd5ab85f9092c8f458d01ac347b.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, gdzie <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/9e735d8a9c4cff3c69fd926eac8c85aa.jpeg\" style=\"display:block;margin: 0 auto;\" \/>&lt;<img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/d963e193a263a1505467c19e874f0aab.jpeg\" style=\"display:block;margin: 0 auto;\" \/> i <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/ff5d990cf5a1752d7bb45da9fd58cd7a.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, gdzie <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/485f34b3e720011c38740712cdb8edd9.jpeg\" style=\"display:block;margin: 0 auto;\" \/>&gt;<img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/c66b20d93fd1791e9f186f707b1517bb.jpeg\" style=\"display:block;margin: 0 auto;\" \/>. <\/p>\n<p>Pytanie brzmi: jaki minimalny zysk obj\u0119to\u015bci <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/86861ad2236d827efdc683d759d4c120.jpeg\" style=\"display:block;margin: 0 auto;\" \/> jest akceptowalny, przy danej warto\u015bci straty czasowej? <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/3d49171042fd83244c054dfd84e5c6bb.jpeg\" style=\"display:block;margin: 0 auto;\" \/>? \u041f\u043e\u044f\u0441\u043d\u0438\u043c \u043d\u0430 \u043f\u0440\u0438\u043c\u0435\u0440\u0435. \u0418\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e \u043e\u0441\u0442\u0430\u0442\u043a\u0438 \u043f\u043e\u043b\u0430\u0433\u0430\u043b\u043e\u0441\u044c \u0440\u0430\u0437\u043c\u0435\u0449\u0430\u0442\u044c \u0432 \u043a\u043e\u043d\u0442\u0435\u0439\u043d\u0435\u0440 \u043e\u0431\u044a\u0435\u043c\u0430 1000 \u0434\u043c3 (1 \u043c3) \u0438 \u0432\u0440\u0435\u043c\u044f \u043d\u0430 \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0435\u043d\u0438\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u0438\u043b\u043e 70 \u0441\u0435\u043a\u0443\u043d\u0434. \u0415\u0441\u0442\u044c \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u0440\u0430\u0437\u043c\u0435\u0449\u0435\u043d\u0438\u044f \u043e\u0441\u0442\u0430\u0442\u043a\u043e\u0432 \u0432 \u0434\u0440\u0443\u0433\u043e\u0439 \u043a\u043e\u043d\u0442\u0435\u0439\u043d\u0435\u0440 \u043e\u0431\u044a\u0435\u043c\u0430 500 \u0434\u043c3 \u0438 \u0432\u0440\u0435\u043c\u0435\u043d\u0435\u043c 130 \u0441\u0435\u043a\u0443\u043d\u0434. \u0412\u043e\u043f\u0440\u043e\u0441: \u0433\u043e\u0442\u043e\u0432\u044b \u043b\u0438 \u043c\u044b \u0442\u0440\u0430\u0442\u0438\u0442\u044c \u0435\u0449\u0435 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0435 60 \u0441\u0435\u043a\u0443\u043d\u0434 \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u043a\u043b\u0430\u0434\u043e\u0432\u0449\u0438\u043a\u0430 \u043d\u0430 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0435\u043d\u0438\u044f \u0434\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u0441\u044d\u043a\u043e\u043d\u043e\u043c\u0438\u0442\u044c 500 \u0434\u043c3 \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u043e\u0433\u043e \u043e\u0431\u044a\u0435\u043c\u0430? \u041f\u043e \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430\u043c \u043e\u043f\u0440\u043e\u0441\u0430 \u0441\u043e\u0442\u0440\u0443\u0434\u043d\u0438\u043a\u043e\u0432 \u0441\u043a\u043b\u0430\u0434\u0430 \u0431\u044b\u043b\u0430 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0430\u044f \u0434\u0438\u0430\u0433\u0440\u0430\u043c\u043c\u0430.<\/p>\n<p><img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/283289c63fe1232e95b73d1dffdaa030.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<i>Rys. 5. Wykres zale\u017cno\u015bci minimalnej dopuszczalnej oszcz\u0119dno\u015bci obj\u0119to\u015bci od zwi\u0119kszenia r\u00f3\u017cnicy w czasie wykonania operacji.<\/i><\/p>\n<p>To znaczy, je\u015bli dodatkowy czas wydatkuje 40 sekund, to jeste\u015bmy gotowi go po\u015bwi\u0119ci\u0107 tylko wtedy, gdy zysk w obj\u0119to\u015bci b\u0119dzie wynosi\u0142 co najmniej 500 dm3. Pomimo tego, \u017ce w obserwowanej zale\u017cno\u015bci wyst\u0119puje niewielka nieliniowo\u015b\u0107, dla u\u0142atwienia dalszych oblicze\u0144 b\u0119dziemy przyjmowa\u0107, \u017ce zale\u017cno\u015b\u0107 jest liniowa i opisuje j\u0105 nier\u00f3wno\u015b\u0107.<\/p>\n<p><img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/666802648033d918a1119e58963feffe.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>Na poni\u017cszym rysunku rozwa\u017camy nast\u0119puj\u0105ce sposoby rozmieszczenia towaru w pojemnikach.<\/p>\n<p><img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/a1cb3a5bce4c369f63b3ebeebb738911.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<i>Rys. 6. Opcja (a): 2 pojemniki, \u0142\u0105czna obj\u0119to\u015b\u0107 400 dm3, \u0142\u0105czny czas 150 sek.<\/i><br \/>\n<img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/a13f35b0e2a188e9a8cbf27bcfbf0292.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<i>Rys. 6. Opcja (b): 2 pojemniki, \u0142\u0105czna obj\u0119to\u015b\u0107 600 dm3, \u0142\u0105czny czas 190 sek.<\/i><br \/>\n<img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/35699c8bd00546c9828dbe50d4b53c46.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<i>Rys. 6. Opcja (c): 1 pojemnik, \u0142\u0105czna obj\u0119to\u015b\u0107 400 dm3, \u0142\u0105czny czas 200 sek.<\/i><\/p>\n<p>Opcja (a) wyboru pojemnik\u00f3w jest bardziej preferowana ni\u017c pierwotna opcja, poniewa\u017c nier\u00f3wno\u015b\u0107 jest spe\u0142niona: (800-400)\/10&gt;=150-120, z czego wynika 40 &gt;= 30. Opcja (b) jest mniej preferowana ni\u017c pierwotna opcja, poniewa\u017c nier\u00f3wno\u015b\u0107 nie jest spe\u0142niona: (800-600)\/10&gt;=190-150, z czego wynika 20 &gt;= 40. Ale opcja (c) nie mie\u015bci si\u0119 w podobnej logice! Przyjrzyjmy si\u0119 tej opcji bli\u017cej. Z jednej strony nier\u00f3wno\u015b\u0107 (800-400)\/10&gt;=200-120, a wi\u0119c nier\u00f3wno\u015b\u0107 40 &gt;= 80 nie jest spe\u0142niona, co oznacza, \u017ce zysk w obj\u0119to\u015bci nie jest wart tak du\u017cej straty czasu. <\/p>\n<p>Z drugiej strony, w takiej opcji (c) nie tylko zmniejszamy \u0142\u0105czn\u0105 zaj\u0119t\u0105 obj\u0119to\u015b\u0107, ale tak\u017ce zmniejszamy liczb\u0119 zaj\u0119tych kom\u00f3rek, co jest jednym z dw\u00f3ch istotnych wymaga\u0144 stawianych rozwi\u0105zywaniu problem\u00f3w, wymienionych powy\u017cej. Oczywi\u015bcie, aby to wymaganie zacz\u0119\u0142o by\u0107 spe\u0142niane, konieczne jest dodanie do lewej strony nier\u00f3wno\u015bci pewnej dodatniej sta\u0142ej. <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/61d6b2cb21474a2f4512d6a130a15a0a.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, przy czym t\u0119 sta\u0142\u0105 nale\u017cy dodawa\u0107 tylko wtedy, gdy liczba pojemnik\u00f3w maleje. Przypomnijmy, \u017ce <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/d80d33679896035041d0ca9a78e8177a.jpeg\" style=\"display:block;margin: 0 auto;\" \/> \u2014 to zmienna, kt\u00f3ra wynosi 1, gdy pojemnik <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/a83cd6273e544b63099939e6845740fb.jpeg\" style=\"display:block;margin: 0 auto;\" \/> zosta\u0142 wybrany, i 0, gdy pojemnik <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/bc94d9e952782e630125a6e8919ba5ad.jpeg\" style=\"display:block;margin: 0 auto;\" \/> nie wybrano. Oznaczamy, <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/1e3fb5d7013e60f67c56a56899630852.jpeg\" style=\"display:block;margin: 0 auto;\" \/> \u2013 zbi\u00f3r pojemnik\u00f3w w pierwotnym rozwi\u0105zaniu i <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/26ac9732af37e865cea1bb10a343175c.jpeg\" style=\"display:block;margin: 0 auto;\" \/> \u2013 zbi\u00f3r pojemnik\u00f3w w nowym rozwi\u0105zaniu. W og\u00f3lnym uj\u0119ciu nowe nier\u00f3wno\u015b\u0107 b\u0119dzie wygl\u0105da\u0107 tak:<\/p>\n<p><img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/1237914e5fdafcc6013203e2624009d0.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>Przekszta\u0142caj\u0105c nier\u00f3wno\u015b\u0107 powy\u017cej, otrzymujemy <\/p>\n<p><img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/80b039f9ef44301c3b624ada42c28db8.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>Na podstawie tego mamy formu\u0142\u0119 do obliczania ca\u0142kowitych koszt\u00f3w <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/cb5bce584fee0156b23adbab83f66b33.jpeg\" style=\"display:block;margin: 0 auto;\" \/> pewnej wersji rozwi\u0105zania problemu:<\/p>\n<p><img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/34f382d40368a980674914916c65b4ec.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p><b>Ale teraz pojawia si\u0119 pytanie<\/b>: jakie powinno by\u0107 takie warto\u015b\u0107 konstanta <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/e4754f88bcddfba85b3c785512bee697.jpeg\" style=\"display:block;margin: 0 auto;\" \/>? \u041e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e \u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0434\u043e\u043b\u0436\u043d\u043e \u0431\u044b\u0442\u044c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0431\u043e\u043b\u044c\u0448\u0438\u043c, \u0434\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u0432\u0441\u0435\u0433\u0434\u0430 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u043b\u043e\u0441\u044c \u043f\u0435\u0440\u0432\u043e\u0435 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u0435 \u043a \u0440\u0435\u0448\u0435\u043d\u0438\u044f\u043c \u0437\u0430\u0434\u0430\u0447\u0438. \u041c\u043e\u0436\u043d\u043e \u043a\u043e\u043d\u0435\u0447\u043d\u043e \u0432\u0437\u044f\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u044b \u0440\u0430\u0432\u043d\u043e\u0435 103 \u0438\u043b\u0438 106, \u043d\u043e \u0445\u043e\u0442\u0435\u043b\u043e\u0441\u044c \u0431\u044b \u0438\u0437\u0431\u0435\u0436\u0430\u0442\u044c \u0442\u0430\u043a\u0438\u0445 \u00abmagic numbers\u00bb. \u0415\u0441\u043b\u0438 \u0431\u0443\u0434\u0435\u043c \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c \u0441\u043f\u0435\u0446\u0438\u0444\u0438\u043a\u0443 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0441\u043a\u043b\u0430\u0434\u0441\u043a\u0438\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439, \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0432\u043f\u043e\u043b\u043d\u0435 \u043e\u0431\u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u0447\u0438\u0441\u043b\u043e\u0432\u044b\u0445 \u043e\u0446\u0435\u043d\u043e\u043a \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u044b \u0442\u0430\u043a\u043e\u0439 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u044b.<\/p>\n<p>Za\u0142\u00f3\u017cmy, <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/50deefe99bf1d5f948a49591904a8bfe.jpeg\" style=\"display:block;margin: 0 auto;\" \/> \u2013 maksymalny dystans mi\u0119dzy kom\u00f3rkami magazynowymi w jednej strefie ABC, r\u00f3wny w naszym przypadku 100 m. Za\u0142\u00f3\u017cmy, <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/466892dd75279d08b4835a42e62444d4.jpeg\" style=\"display:block;margin: 0 auto;\" \/> \u2013 maksymalna obj\u0119to\u015b\u0107 kom\u00f3rki-pojemnika w magazynie, wynosz\u0105ca w naszym przypadku 1000 dm3.<\/p>\n<p><b>Pierwszy spos\u00f3b obliczenia warto\u015bci<\/b> <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/29b94b534da709020cbef206cb0d7dac.jpeg\" style=\"display:block;margin: 0 auto;\" \/>. Rozwa\u017cmy sytuacj\u0119, w kt\u00f3rej znajduj\u0105 si\u0119 2 pojemniki na pierwszym pi\u0119trze, w kt\u00f3rych fizycznie ju\u017c znajduje si\u0119 towar, co oznacza, \u017ce \u200b\u200bsami s\u0105 kom\u00f3rkami-dawcami, a koszty przemieszczania towaru do tych samych kom\u00f3rek s\u0105 oczywi\u015bcie r\u00f3wne 0. Nale\u017cy znale\u017a\u0107 tak\u0105 warto\u015b\u0107 konstanta <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/5cf81db57dd2a18cc0ec29bb7ca3da62.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, przy kt\u00f3rej op\u0142acalne by\u0142oby zawsze przenosi\u0107 resztki z pojemnika 1 do pojemnika 2. Podstawiaj\u0105c warto\u015bci <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/20bbd09e167edc3eb1ed49d8078ecf19.jpeg\" style=\"display:block;margin: 0 auto;\" \/> i <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/605017af48e7b3ca4a323642db4227cd.jpeg\" style=\"display:block;margin: 0 auto;\" \/> do nier\u00f3wno\u015bci, przedstawionej powy\u017cej, otrzymujemy:<\/p>\n<p><img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/2794955b8f9f3d64ffe4e2b449547555.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>z czego wynika<\/p>\n<p><img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/292a6e80c646c7eed80e888c8805990c.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>Podstawiaj\u0105c warto\u015bci \u015bredniego czasu realizacji operacji elementarnych do powy\u017cszej formu\u0142y otrzymujemy<\/p>\n<p><img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/1f56bf1f98c1a3bbd65a4cea99da7efb.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p><b>Drugi spos\u00f3b obliczenia warto\u015bci<\/b> <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/78e3dff7183b15136d9e03f4a5724479.jpeg\" style=\"display:block;margin: 0 auto;\" \/>. Rozwa\u017cmy sytuacj\u0119, w kt\u00f3rej istnieje <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/02daff1eff70a2963ab8eaa067f15584.jpeg\" style=\"display:block;margin: 0 auto;\" \/> kom\u00f3rki-dawcy, z kt\u00f3rych planuje si\u0119 przemieszczenie towaru do pojemnika 1. Oznaczmy <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/df20c3f27815f2060aae20d260210893.jpeg\" style=\"display:block;margin: 0 auto;\" \/> \u2013 odleg\u0142o\u015b\u0107 od kom\u00f3rki-dawcy <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/a29ace66656cf1680c9e00258a9ff597.jpeg\" style=\"display:block;margin: 0 auto;\" \/> do pojemnika 1. Jest r\u00f3wnie\u017c pojemnik 2, w kt\u00f3rym ju\u017c s\u0105 towary, a jego obj\u0119to\u015b\u0107 pozwala pomie\u015bci\u0107 resztki ze wszystkich <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/e25f0828e7d794f8d804528395f6dc7e.jpeg\" style=\"display:block;margin: 0 auto;\" \/> kom\u00f3rek. Dla uproszczenia przyjmujemy, \u017ce obj\u0119to\u015b\u0107 towaru, przenoszonego z kom\u00f3rek-dawc\u00f3w do pojemnik\u00f3w jest taka sama i wynosi <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/35c3392a83fc3b7eef928ddb5e93961a.jpeg\" style=\"display:block;margin: 0 auto;\" \/>. Nale\u017cy znale\u017a\u0107 tak\u0105 warto\u015b\u0107 konstanta <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/c9bc10aade46cc3c63628c0ba100b364.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, przy kt\u00f3rej umieszczenie wszystkich resztek z <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/e610d9981da2857a541f028a217f2306.jpeg\" style=\"display:block;margin: 0 auto;\" \/> kom\u00f3rek w pojemniku 2 by\u0142oby zawsze korzystniejsze ni\u017c umieszczenie ich w r\u00f3\u017cnych pojemnikach:<\/p>\n<p><img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/27f4f99a920799fba9725f30a04c8ebc.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>Przekszta\u0142caj\u0105c nier\u00f3wno\u015b\u0107 otrzymujemy<\/p>\n<p><img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/56abddb4fc3e54eeb1fe466c68e5d8d7.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>Aby \"wzmocni\u0107\" warto\u015b\u0107 wielko\u015bci <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/d77359ea816f9d45a8910cb26649f717.jpeg\" style=\"display:block;margin: 0 auto;\" \/>, przyjmujemy, \u017ce <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/9edf13fb4e34b5da26957e451300046f.jpeg\" style=\"display:block;margin: 0 auto;\" \/> = 0. \u015arednia liczba kom\u00f3rek, kt\u00f3re zwykle bior\u0105 udzia\u0142 w procedurze kompresji resztek w magazynie wynosi 10. Podstawiaj\u0105c znane warto\u015bci wielko\u015bci, mamy nast\u0119puj\u0105c\u0105 warto\u015b\u0107 konstanta<\/p>\n<p><img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/40323791fd8cd2be3f29a2becf78e175.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>Bierzemy najwi\u0119ksz\u0105 warto\u015b\u0107, obliczon\u0105 dla ka\u017cdej wersji, to b\u0119dzie warto\u015b\u0107 wielko\u015bci <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/fd018460792c79b8a7953c06b839711d.jpeg\" style=\"display:block;margin: 0 auto;\" \/> dla zadanych parametr\u00f3w magazynu. Teraz dla pe\u0142no\u015bci zapiszmy formu\u0142\u0119 obliczenia ca\u0142kowitych koszt\u00f3w <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/d4cb2c81bcc788380f1f0c1123b0eeda.jpeg\" style=\"display:block;margin: 0 auto;\" \/> dla pewnego dopuszczalnego rozwi\u0105zania <img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/052e710199e9417aaea94b16dbed47d3.jpeg\" style=\"display:block;margin: 0 auto;\" \/>:<\/p>\n<p><img decoding=\"async\" alt=\"Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1)\" src=\"\/wp-content\/uploads\/2019\/08\/8dd672c7b91639fe1872ef50dca7a220.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>A wi\u0119c teraz, po wszystkich <b>titanicznych wysi\u0142kach<\/b> w przekszta\u0142ceniu danych wej\u015bciowych, mo\u017cemy powiedzie\u0107, \u017ce wszystkie dane wej\u015bciowe zosta\u0142y przekszta\u0142cone do po\u017c\u0105danego formatu i s\u0105 gotowe do u\u017cycia w algorytmie optymalizacji.<\/p>\n<h4>Podsumowanie<\/h4>\n<p>\nJak pokazuje praktyka, pracoch\u0142onno\u015b\u0107 i znaczenie etapu przygotowania i przekszta\u0142cenia danych wej\u015bciowych dla algorytmu cz\u0119sto s\u0105 niedoszacowane. W tym artykule postarali\u015bmy si\u0119 szczeg\u00f3lnie zwr\u00f3ci\u0107 uwag\u0119 na ten etap, aby pokaza\u0107, \u017ce tylko jako\u015bciowo i m\u0105drze przygotowane dane wej\u015bciowe mog\u0105 uczyni\u0107 wyniki obliczane przez algorytm naprawd\u0119 cennymi dla klienta. Tak, by\u0142o wiele wniosk\u00f3w z formu\u0142, ale ostrzegali\u015bmy was o tym ju\u017c przed katem \ud83d\ude42<\/p>\n<p>W nast\u0119pnym artykule w ko\u0144cu dotrzemy do celu, dla kt\u00f3rego zaplanowane by\u0142y 2 poprzednie publikacje \u2013 do algorytmu dyskretnej optymalizacji.<\/p>\n<p><i>Artyku\u0142 przygotowa\u0142<br \/>\nRoman Szangin, programista dzia\u0142u projekt\u00f3w,<br \/>\nfirma Pierwszy Bit, m. Chelyabinsk<\/i><br \/>\n<br \/>\u0179r\u00f3d\u0142o: <a content=\"nofollow\" rel=\"nofollow\" href=\"https:\/\/habr.com\/ru\/post\/463481\/\">habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"<p>\u0412 \u0441\u0442\u0430\u0442\u044c\u0435 \u043c\u044b \u0440\u0430\u0441\u0441\u043a\u0430\u0436\u0435\u043c, \u043a\u0430\u043a \u0440\u0435\u0448\u0430\u043b\u0438 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0443 \u043d\u0435\u0445\u0432\u0430\u0442\u043a\u0438 \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u044b\u0445 \u044f\u0447\u0435\u0435\u043a \u043d\u0430 \u0441\u043a\u043b\u0430\u0434\u0435 \u0438 \u043e \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u043a\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u043e\u0439 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0442\u0430\u043a\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438. \u0420\u0430\u0441\u0441\u043a\u0430\u0436\u0435\u043c \u043e \u0442\u043e\u043c, \u043a\u0430\u043a \u043c\u044b \u00ab\u0441\u0442\u0440\u043e\u0438\u043b\u0438\u00bb \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u043c\u043e\u0434\u0435\u043b\u044c \u0437\u0430\u0434\u0430\u0447\u0438 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438, \u0438 \u043e \u0442\u043e\u043c \u0441 \u043a\u0430\u043a\u0438\u043c\u0438 \u0442\u0440\u0443\u0434\u043d\u043e\u0441\u0442\u044f\u043c\u0438 \u043c\u044b \u043d\u0435\u043e\u0436\u0438\u0434\u0430\u043d\u043d\u043e \u0441\u0442\u043e\u043b\u043a\u043d\u0443\u043b\u0438\u0441\u044c \u043f\u0440\u0438 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0435 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 \u0434\u043b\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430. \u0415\u0441\u043b\u0438 \u0432\u0430\u043c \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b \u043f\u0440\u0438\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0438 \u0432 \u0431\u0438\u0437\u043d\u0435\u0441\u0435 \u0438 [&hellip;]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":27819,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[702],"tags":[],"class_list":["post-37108","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-news"],"aioseo_notices":[],"aioseo_head":"\n\t\t<!-- All in One SEO 5.0.1.1 - aioseo.com -->\n\t<meta name=\"description\" content=\"\u0412 \u0441\u0442\u0430\u0442\u044c\u0435 \u043c\u044b.\" \/>\n\t<meta name=\"robots\" content=\"max-image-preview:large\" \/>\n\t<meta name=\"author\" content=\"Yuri Gagarin\"\/>\n\t<link rel=\"canonical\" href=\"https:\/\/prohoster.info\/pl\/blog\/news\/diskretnaya-matematika-dlya-wms-algoritm-szhatiya-tovarov-v-yachejkah-chast-1\" \/>\n\t<meta name=\"generator\" content=\"All in One SEO (AIOSEO) 5.0.1.1\" \/>\n\t\t<meta property=\"og:locale\" content=\"pl_PL\" \/>\n\t\t<meta property=\"og:site_name\" content=\"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b\" \/>\n\t\t<meta property=\"og:type\" content=\"article\" \/>\n\t\t<meta property=\"og:title\" content=\"\ud83e\udd47\u0414\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u0430\u044f \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0430 \u0434\u043b\u044f WMS: \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441\u0436\u0430\u0442\u0438\u044f \u0442\u043e\u0432\u0430\u0440\u043e\u0432 \u0432 \u044f\u0447\u0435\u0439\u043a\u0430\u0445 (\u0447\u0430\u0441\u0442\u044c 1) | ProHoster\" \/>\n\t\t<meta property=\"og:description\" content=\"\u0412 \u0441\u0442\u0430\u0442\u044c\u0435 \u043c\u044b.\" \/>\n\t\t<meta property=\"og:url\" content=\"https:\/\/prohoster.info\/pl\/blog\/news\/diskretnaya-matematika-dlya-wms-algoritm-szhatiya-tovarov-v-yachejkah-chast-1\" \/>\n\t\t<meta property=\"og:image\" content=\"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg\" \/>\n\t\t<meta property=\"og:image:secure_url\" content=\"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg\" \/>\n\t\t<meta property=\"og:image:width\" content=\"350\" \/>\n\t\t<meta property=\"og:image:height\" content=\"350\" \/>\n\t\t<meta property=\"article:published_time\" content=\"2019-10-31T19:15:47+00:00\" \/>\n\t\t<meta property=\"article:modified_time\" content=\"2019-10-31T19:15:47+00:00\" \/>\n\t\t<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/prohoster\" \/>\n\t\t<meta property=\"article:author\" content=\"https:\/\/www.facebook.com\/prohoster\" \/>\n\t\t<!-- All in One SEO -->\n\n","aioseo_head_json":{"title":"\ud83e\udd47Matematyka dyskretna dla WMS: algorytm kompresji towar\u00f3w w kom\u00f3rkach (cz\u0119\u015b\u0107 1) | ProHoster","description":"W artykule my.","canonical_url":"https:\/\/prohoster.info\/pl\/blog\/news\/diskretnaya-matematika-dlya-wms-algoritm-szhatiya-tovarov-v-yachejkah-chast-1","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"pl_PL","og:site_name":"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b","og:type":"article","og:title":"\ud83e\udd47\u0414\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u0430\u044f \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0430 \u0434\u043b\u044f WMS: \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441\u0436\u0430\u0442\u0438\u044f \u0442\u043e\u0432\u0430\u0440\u043e\u0432 \u0432 \u044f\u0447\u0435\u0439\u043a\u0430\u0445 (\u0447\u0430\u0441\u0442\u044c 1) | ProHoster","og:description":"\u0412 \u0441\u0442\u0430\u0442\u044c\u0435 \u043c\u044b.","og:url":"https:\/\/prohoster.info\/pl\/blog\/news\/diskretnaya-matematika-dlya-wms-algoritm-szhatiya-tovarov-v-yachejkah-chast-1","og:image":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:secure_url":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:width":350,"og:image:height":350,"article:published_time":"2019-10-31T19:15:47+00:00","article:modified_time":"2019-10-31T19:15:47+00:00","article:publisher":"https:\/\/www.facebook.com\/prohoster","article:author":"https:\/\/www.facebook.com\/prohoster"},"aioseo_meta_data":{"post_id":"37108","title":null,"description":null,"keywords":null,"keyphrases":null,"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"local_seo":null,"seo_analyzer_scan_date":"2026-01-22 06:08:19","breadcrumb_settings":null,"limit_modified_date":false,"reviewed_by":null,"ai":null,"created":"2021-03-01 01:33:24","updated":"2026-01-22 06:08:19","focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"gt_translate_keys":[{"key":"link","format":"url"}],"_links":{"self":[{"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/posts\/37108","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/comments?post=37108"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/posts\/37108\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/media\/27819"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/media?parent=37108"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/categories?post=37108"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/tags?post=37108"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}