W tym artykule opowiemy jak rozwiązaliśmy problem braku wolnych ogniw w magazynie i opracowaliśmy algorytm optymalizacji dyskretnej, który rozwiązałby taki problem. Porozmawiajmy o tym, jak „zbudowaliśmy” model matematyczny problemu optymalizacyjnego oraz o trudnościach, jakie nieoczekiwanie napotkaliśmy podczas przetwarzania danych wejściowych do algorytmu.
Jeśli interesują Cię zastosowania matematyki w biznesie i nie boisz się sztywnych przekształceń tożsamościowych formuł na poziomie 5 klasy, to zapraszamy do kota!
Artykuł będzie przydatny dla tych, którzy wdrażają WMS-systemów, pracuje w branży logistyki magazynowej lub produkcyjnej, a także programistów zainteresowanych zastosowaniami matematyki w biznesie i optymalizacją procesów w przedsiębiorstwie.
Część wprowadzająca
Niniejsza publikacja stanowi kontynuację cyklu artykułów, w których dzielimy się naszymi udanymi doświadczeniami we wdrażaniu algorytmów optymalizacyjnych w procesach magazynowych.
В opisuje specyfikę magazynu, w którym realizowaliśmy WMS-system, a także wyjaśnia, dlaczego musieliśmy rozwiązać problem grupowania partii pozostałych towarów podczas wdrożenia WMS-systems i jak to zrobiliśmy.
Kiedy skończyliśmy pisać artykuł o algorytmach optymalizacyjnych, okazał się on bardzo duży, dlatego postanowiliśmy podzielić zgromadzony materiał na 2 części:
- W pierwszej części (tym artykule) porozmawiamy o tym, jak „zbudowaliśmy” matematyczny model problemu oraz o dużych trudnościach, jakie nieoczekiwanie napotkaliśmy podczas przetwarzania i przekształcania danych wejściowych do algorytmu.
- W drugiej części szczegółowo rozważymy implementację algorytmu w języku C + +, przeprowadzimy eksperyment obliczeniowy i podsumujemy doświadczenia, które zdobyliśmy podczas wdrażania takich „inteligentnych technologii” w procesach biznesowych Klienta.
Jak przeczytać artykuł. Jeśli przeczytałeś poprzedni artykuł, możesz od razu przejść do rozdziału „Przegląd istniejących rozwiązań”, jeśli nie, to opis rozwiązywanego problemu znajduje się w spoilerze poniżej.
Opis problemu rozwiązywanego w magazynie klienta
Wąskie gardło w procesach
W 2018 roku zakończyliśmy projekt do realizacji WMS-systemy w magazynie „Dom Handlowy „LD” w Czelabińsku. Wdrożyliśmy produkt „1C-Logistics: Magazynowanie 3” dla 20 stanowisk pracy: operatorzy WMS, magazynierzy, kierowcy wózków widłowych. Przeciętny magazyn ma powierzchnię około 4 tys. m2, ilość ogniw to 5000, a liczba SKU to 4500. W magazynie znajdują się zawory kulowe własnej produkcji o różnych rozmiarach od 1 kg do 400 kg. Zapasy w magazynie przechowywane są partiami, ponieważ istnieje konieczność selekcji towarów według FIFO.
Projektując schematy automatyzacji procesów magazynowych, stanęliśmy przed istniejącym problemem nieoptymalnego przechowywania zapasów. Specyfika dźwigów składujących i układających jest taka, że w jednym jednostkowym ogniwie magazynowym mogą znajdować się wyłącznie towary z jednej partii (patrz rys. 1). Produkty docierają do magazynu codziennie i każdy przyjazd stanowi osobną partię. Łącznie w wyniku 1 miesiąca pracy magazynu powstaje 30 odrębnych partii, mimo że każda powinna być przechowywana w osobnej komórce. Produkty często wybierane są nie w całych paletach, ale w kawałkach, w wyniku czego w strefie wyboru sztuk w wielu komórkach obserwuje się następujący obraz: w komórce o objętości większej niż 1 m3 znajduje się kilka sztuk dźwigów, które zajmują mniej niż 5-10% objętości komórki.
Ryc. 1. Zdjęcie kilku kawałków w komórce
Oczywiste jest, że pojemność magazynu nie jest wykorzystywana optymalnie. Aby wyobrazić sobie skalę katastrofy, mogę podać liczby: średnio znajduje się od 1 do 3 ogniw tego typu o objętości powyżej 100 m300 z „drobnymi” saldami w różnych okresach funkcjonowania magazynu. Ponieważ magazyn jest stosunkowo mały, w okresach zwiększonego ruchu magazynowego czynnik ten staje się „wąskim gardłem” i znacznie spowalnia procesy magazynowe związane z przyjęciem i wysyłką.
Pomysł na rozwiązanie problemu
Pojawił się pomysł: partie resztek o najbliższych terminach należy zredukować do jednej partii, a takie resztki o jednolitej partii należy złożyć kompaktowo w jednej komórce lub w kilku, jeśli w jednej nie ma miejsca na umieszczenie całą ilość resztek. Przykład takiej „kompresji” pokazano na rysunku 2.
Ryc.2. Schemat kompresji pozostałości w komórkach
Pozwala to znacząco ograniczyć zajmowaną powierzchnię magazynową, która będzie wykorzystywana do umieszczania nowego towaru. W sytuacji przeciążenia magazynu takie działanie jest niezwykle potrzebne, w przeciwnym razie może po prostu zabraknąć wolnego miejsca na przyjęcie nowego towaru, co doprowadzi do wstrzymania procesów magazynowych rozmieszczania i uzupełniania, a w konsekwencji do: do zatrzymania przyjęcia i wysyłki. Wcześniej, przed wdrożeniem systemu WMS, operację taką wykonywano ręcznie, co było nieskuteczne, gdyż proces wyszukiwania odpowiednich sald w komórkach był dość długi. Teraz wraz z wprowadzeniem systemu WMS postanowiliśmy zautomatyzować proces, przyspieszyć go i uczynić inteligentnym.
Proces rozwiązania takiego problemu dzieli się na 2 etapy:
- w pierwszym etapie odnajdujemy grupy partii bliskie terminowi kompresji (dedykowane do tego zadania );
- w drugim etapie dla każdej grupy partii obliczamy najbardziej kompaktowe rozmieszczenie pozostałych towarów w komórkach.
W bieżącym artykule skupimy się na drugim etapie algorytmu.
Przegląd istniejących rozwiązań
Zanim przejdziemy do opisu opracowanych przez nas algorytmów, warto przeprowadzić krótki przegląd systemów już istniejących na rynku WMS, które implementują podobną optymalną funkcjonalność kompresji.
Przede wszystkim należy zwrócić uwagę na produkt „1C: Enterprise 8. WMS Logistics. Zarządzanie magazynem 4”, które jest własnością i jest replikowane przez 1C i należy do czwartej generacji WMS-systemy opracowane przez AXELOT. System ten zapewnia funkcję kompresji, która ma na celu połączenie różnych pozostałości produktu w jedną wspólną komórkę. Warto wspomnieć, że funkcjonalność kompresji w takim systemie obejmuje także inne możliwości, na przykład korygowanie ułożenia towarów w komórkach według ich klas ABC, ale nie będziemy się nad nimi rozwodzić.
Jeśli przeanalizujesz kod systemu 1C: Enterprise 8. WMS Logistics. Zarządzanie magazynem 4” (otwarte w tej części funkcjonalności) możemy podsumować co następuje. Algorytm kompresji resztkowej realizuje dość prymitywną logikę liniową i nie można mówić o jakiejkolwiek „optymalnej” kompresji. Oczywiście nie przewiduje łączenia partii. Kilku klientów, którzy wdrożyli taki system, skarżyło się na wyniki planowania kompresji. Przykładowo często w praktyce podczas kompresji miała miejsce następująca sytuacja: 100 szt. Planowane jest przeniesienie pozostałego towaru z jednej celi do drugiej, gdzie znajduje się 1 sztuka. towarów, choć optymalne z punktu widzenia czasochłonności jest postępowanie odwrotne.
W wielu innych krajach deklarowana jest także funkcjonalność kompresowania pozostałych towarów w komórkach. WMS-systems, ale niestety nie mamy rzeczywistych opinii na temat skuteczności algorytmów (jest to tajemnica handlowa), a tym bardziej pojęcia o głębokości ich logiki (zastrzeżone oprogramowanie o zamkniętym kodzie źródłowym), więc nie możemy oceniać.
Poszukaj modelu matematycznego problemu
Aby zaprojektować wysokiej jakości algorytmy rozwiązywania problemu, należy najpierw jasno sformułować ten problem matematycznie i właśnie to zrobimy.
Jest wiele komórek , w których znajdują się pozostałości niektórych towarów. W dalszej części takie komórki będziemy nazywać komórkami dawcy. Oznaczmy objętość towaru w komórce $.
Warto dodać, że tylko jeden produkt z jednej partii lub kilka partii wcześniej połączonych w klaster (czytaj: ), co wynika ze specyfiki składowania i przechowywania towarów. Dla różnych produktów lub różnych klastrów partii należy przeprowadzić własną, oddzielną procedurę kompresji.
Jest wiele komórek , w którym można potencjalnie umieścić pozostałości komórek dawcy. Takie komórki będziemy dalej nazywać komórkami kontenerowymi. Mogą to być albo wolne komórki w magazynie, albo komórki dawcy z różnych odmian . Zawsze mnóstwo jest podzbiorem .
Dla każdej komórki od wielu Ustawiono ograniczenia wydajności , mierzone w dm3. Jeden dm3 to sześcian o boku 10 cm.Produkty przechowywane w magazynie są dość duże, dlatego w tym przypadku taka dyskretyzacja jest wystarczająca.
Biorąc pod uwagę macierz najkrótszych odległości w metrach pomiędzy każdą parą ogniw Gdzie и należą do zestawów и odpowiednio.
Oznaczmy „koszty” przeniesienia towaru z komórki w komórkę . Oznaczmy „koszty” wyboru kontenera aby przenieść do niego pozostałości z innych komórek. Jak dokładnie i w jakich jednostkach miary zostaną obliczone wartości и zastanowimy się dalej (patrz rozdział przygotowanie danych wejściowych), na razie wystarczy powiedzieć, że takie wartości będą wprost proporcjonalne do wartości и odpowiednio.
Oznacz przez zmienna, która przyjmuje wartość 1, jeśli reszta pochodzi z komórki przeniesiony do kontenera i 0 w przeciwnym razie. Oznaczmy przez zmienna, która przyjmuje wartość 1, jeśli kontener zawiera pozostałe towary, a 0 w przeciwnym razie.
Zadanie jest określone w następujący sposób: musisz znaleźć tyle pojemników i w ten sposób „przyłączają” komórki dawcy do komórek pojemnikowych, aby zminimalizować tę funkcję
pod ograniczeniami
Łącznie przy obliczaniu rozwiązania problemu staramy się:
- po pierwsze, aby zaoszczędzić pojemność;
- po drugie, aby zaoszczędzić czas magazynierów.
Ostatnie ograniczenie oznacza, że do kontenera, którego nie wybraliśmy, nie możemy wrzucić towaru, a co za tym idzie, nie „ponieśliśmy kosztów” za jego wybranie. Ograniczenie to oznacza również, że objętość towaru przemieszczanego z ogniw do kontenera nie powinna przekraczać pojemności kontenera. Przez rozwiązanie problemu rozumiemy zestaw pojemników oraz sposoby przyłączania komórek dawcy do pojemników.
Takie sformułowanie problemu optymalizacji nie jest nowe i było badane przez wielu matematyków od początku lat 80-tych ubiegłego wieku. W literaturze zagranicznej istnieją 2 problemy optymalizacyjne z odpowiednim modelem matematycznym: и (o różnicach w zadaniach porozmawiamy później). Warto dodać, że w literaturze matematycznej formułowanie takich dwóch problemów optymalizacyjnych formułowane jest w kontekście lokalizacji przedsiębiorstw w terenie, stąd nazwa „Lokalizacja obiektu”. W dużej mierze jest to hołd złożony tradycji, gdyż po raz pierwszy potrzeba rozwiązywania takich kombinatorycznych problemów wyszła z dziedziny logistyki, głównie z sektora wojskowo-przemysłowego, w latach 50. ubiegłego wieku. Ze względu na lokalizację przedsiębiorstwa zadania takie formułuje się następująco:
- Istnieje skończona liczba miast, w których potencjalnie możliwa jest lokalizacja przedsiębiorstw produkcyjnych (zwanych dalej miastami produkcyjnymi). Dla każdego miasta produkcyjnego określone są koszty otwarcia w nim przedsiębiorstwa, a także ograniczenie mocy produkcyjnej otwartego w nim przedsiębiorstwa.
- Istnieje skończony zbiór miast, w których faktycznie znajdują się klienci (zwanych dalej miastami-klientami). Dla każdego takiego miasta-klienta określona jest wielkość zapotrzebowania na produkty. Dla uproszczenia założymy, że istnieje tylko jeden produkt, który jest wytwarzany przez przedsiębiorstwa i konsumowany przez klientów.
- Dla każdej pary miasto-producent i miasto-klient określona jest wartość kosztów transportu za dostarczenie wymaganej ilości produktów od producenta do klienta.
Musisz dowiedzieć się, w jakich miastach otwierać firmy i jak przyciągnąć klientów do takich biznesów, aby:
- Całkowite koszty otwierania przedsiębiorstw i koszty transportu były minimalne;
- Wielkość popytu ze strony klientów przypisanych do dowolnego przedsiębiorstwa otwartego nie przekraczała możliwości produkcyjnych tego przedsiębiorstwa.
Teraz warto wspomnieć o jedynej różnicy w tych dwóch klasycznych problemach:
- Problem lokalizacji obiektu o pojemności jednego źródła – klient zasilany jest tylko z jednego otwartego obiektu;
- Problem lokalizacji wieloźródłowego obiektu o pojemności pojemnościowej – klient może być zasilany z kilku otwartych obiektów jednocześnie.
Taka różnica między obydwoma problemami jest na pierwszy rzut oka nieistotna, ale w rzeczywistości prowadzi do zupełnie innej kombinatorycznej struktury takich problemów, a w konsekwencji do zupełnie innych algorytmów ich rozwiązywania. Różnice między zadaniami pokazano na poniższym rysunku.
Ryc.3. a) Problem lokalizacji obiektu o pojemności wieloźródłowej
Ryc.3. b) Problem lokalizacji obiektu o pojemności jednego źródła
Obydwa zadania -trudne, czyli nie ma dokładnego algorytmu, który rozwiązałby taki problem w wielomianu czasu w wielkości danych wejściowych. Mówiąc prościej, wszystkie dokładne algorytmy rozwiązywania problemu będą działać w czasie wykładniczym, chociaż być może szybciej niż pełne przeszukiwanie opcji. Od zadania -trudne, wtedy będziemy brać pod uwagę tylko heurystyki przybliżone, czyli algorytmy, które będą konsekwentnie obliczać rozwiązania bardzo zbliżone do optymalnych i będą działać dość szybko. Jeśli jesteś zainteresowany takim zadaniem, tutaj znajdziesz dobry przegląd w języku rosyjskim.
Jeśli przejdziemy do terminologii naszego problemu optymalnej kompresji dóbr w komórkach, to:
- miasta-klienci są komórkami dawców z pozostałym towarem,
- miasta produkcyjne – komórki kontenerowe , w którym mają zostać umieszczone pozostałości z innych komórek,
- koszty transportu - koszty czasu magazynier, aby przenieść ilość towarów z komórki dawcy do komórki kontenerowej ;
- koszty otwarcia działalności - koszty wyboru kontenera równy objętości komórki pojemnika , pomnożony przez określony współczynnik oszczędzania wolnych objętości (wartość współczynnika jest zawsze > 1) (patrz rozdział przygotowanie danych wejściowych).
Po dokonaniu analogii ze znanymi klasycznymi rozwiązaniami problemu należy odpowiedzieć na ważne pytanie, od którego zależy wybór architektury algorytmu rozwiązania: przeniesienie resztek z komórki dawcy jest możliwe tylko do jednego i tylko jeden kontener (Single-Source), czy też można przenieść resztę do kilku komórek kontenerów (Multi-Source)?
Warto zauważyć, że w praktyce mają miejsce obydwa sformułowania problemu. Poniżej przedstawiamy wszystkie zalety i wady każdego takiego ustawienia:
| Wariant problemowy | Plusy opcji | Wady opcji |
|---|---|---|
| Pojedyncze źródło | Operacje przemieszczania towarów obliczone przy zastosowaniu tego wariantu zadania:
|
|
| Wiele źródeł | Uciski obliczone przy użyciu tej wersji problemu są zwykle o 10–15% bardziej zwarte w porównaniu do ucisków obliczonych przy użyciu opcji „Jedno źródło”. Ale zauważamy również, że im mniejsza liczba reszt w komórkach dawcy, tym mniejsza różnica w zwartości | Operacje przemieszczania towarów obliczone przy zastosowaniu tego wariantu zadania:
|
Tabela 1. Plusy i minusy opcji z jednym źródłem i wieloma źródłami.
Ponieważ opcja Single-Source ma więcej zalet, a także biorąc pod uwagę fakt, że im mniejsza liczba reszt w komórkach dawcy, tym mniejsza różnica w stopniu zwartości kompresji obliczonej dla obu wariantów problemu, nasz wybór padł na opcja Jedno źródło Źródło.
Warto powiedzieć, że rozwiązanie opcji Multi-Source również ma miejsce. Istnieje wiele skutecznych algorytmów jego rozwiązania, z których większość sprowadza się do rozwiązania szeregu problemów transportowych. Istnieją również algorytmy nie tylko wydajne, ale także eleganckie, np.
Przygotowanie danych wejściowych
Zanim zaczniemy analizować i opracowywać algorytm rozwiązania problemu, należy zdecydować, jakie dane i w jakiej formie wprowadzimy jako dane wejściowe. Problemów z ilością towaru pozostającego w komórkach dawcy i pojemnością komórek kontenerowych nie ma, bo to drobnostka – takie ilości będą mierzone w m3, ale przy kosztach korzystania z komórki kontenerowej i matrycy kosztów przeprowadzki to nie wszystko jest takie proste!
Przyjrzyjmy się najpierw obliczeniom koszty transportu towarów z komórki dawcy do komórki pojemnikowej. Przede wszystkim należy zdecydować, w jakich jednostkach miary będziemy obliczać koszty przemieszczania się. Dwie najbardziej oczywiste opcje to metry i sekundy. Obliczanie kosztów podróży w „czystych” metrach nie ma sensu. Pokażmy to na przykładzie. Niech komórka znajduje się na pierwszym poziomie, komórka usunięty o 30 metrów i umieszczony na drugim poziomie:
- Przenosić się z в droższe niż przeprowadzka в , ponieważ zejście z drugiego poziomu (1,5-2 metry od podłogi) jest łatwiejsze niż wejście na drugi poziom, chociaż odległość będzie taka sama;
- Przenieś 1 szt. towar z komórki в Będzie to łatwiejsze niż przeniesienie 10 sztuk. ten sam produkt, chociaż odległość będzie taka sama.
Lepiej jest rozważyć koszty przeniesienia w sekundach, ponieważ pozwala to uwzględnić zarówno różnicę poziomów, jak i różnicę w ilości przewożonych towarów. Aby uwzględnić koszt ruchu w sekundach, musimy rozłożyć operację ruchu na elementy elementarne i dokonać pomiarów czasu wykonania każdego elementu elementarnego.
Niech z celi porusza się komputer. towar w kontenerze , RџSѓSЃS, SЊ – średnia prędkość poruszania się pracownika w magazynie, mierzona w m/s. Pozwalać и – średnie prędkości operacji jednorazowych, odpowiednio, pobierają i odkładają dla objętości towaru równej 4 dm3 (średnia objętość, jaką pracownik jednorazowo zabiera na magazyn podczas wykonywania operacji). Pozwalać и wysokość komórek, z których wykonywane są odpowiednio operacje take i put. Na przykład średnia wysokość pierwszego poziomu (podłogi) wynosi 1 m, drugiego poziomu 2 m itd. Następnie wzór na obliczenie całkowitego czasu wykonania operacji przenoszenia wynosi: następny:
W tabeli 2 przedstawiono statystyki czasu wykonania każdej elementarnej operacji, zebrane przez pracowników magazynu, z uwzględnieniem specyfiki składowanego towaru.
| Nazwa operacji | Oznaczenie | Średnia wartość |
|---|---|---|
| Średnia prędkość pracownika poruszającego się po magazynie | |
1,5 m/s |
| Średnia prędkość jednej operacji układania (dla objętości produktu 4 dm3) | |
2,4 sek |
Tabela 2. Średni czas realizacji operacji magazynowych
Zdecydowaliśmy się na sposób kalkulacji kosztów przeprowadzki. Teraz musimy dowiedzieć się, jak obliczyć koszty wyboru ogniwa kontenerowego. Wszystko tutaj jest o wiele, wiele bardziej skomplikowane niż w przypadku kosztów przeprowadzki, ponieważ:
- po pierwsze, koszty powinny być bezpośrednio zależne od objętości kuwety – tę samą objętość pozostałości przeniesionych z komórek dawcy lepiej umieścić w pojemniku o mniejszej objętości niż w dużym pojemniku, pod warunkiem, że taka objętość w całości zmieści się w obu pojemnikach. Tym samym minimalizując całkowite koszty doboru kontenerów, dążymy do zaoszczędzenia „niedostatecznej” wolnej przestrzeni magazynowej w obszarze selekcji w celu wykonywania kolejnych operacji umieszczania towaru w komórkach. Rysunek 4 przedstawia możliwości przenoszenia pozostałości do dużych i małych pojemników oraz konsekwencje tych opcji przenoszenia w kolejnych operacjach magazynowych.
- po drugie, ponieważ przy rozwiązywaniu pierwotnego problemu musimy dokładnie zminimalizować koszty całkowite, a jest to suma zarówno kosztów przeprowadzki, jak i kosztów wyboru kontenerów, to objętości ogniw w metrach sześciennych trzeba jakoś powiązać z sekundami, co wcale nie jest trywialne.
Ryż. 4. Możliwości przenoszenia resztek do pojemników o różnej pojemności.
Na rysunku 4 na czerwono pokazano objętość resztek, która nie mieści się już w pojemniku na drugim etapie układania kolejnych towarów.
Pomoże to powiązać metry sześcienne kosztów wyboru kontenera z sekundami kosztów przeniesienia następujących wymagań dla obliczonych rozwiązań problemu:
- W każdym przypadku konieczne jest przeniesienie sald z pojemnika dawcy do pojemnika pojemnikowego, jeśli zmniejsza to całkowitą liczbę pojemników zawierających produkt.
- Konieczne jest zachowanie równowagi między objętością pojemników a czasem spędzonym na przeprowadzce: na przykład, jeśli w nowym rozwiązaniu problemu w porównaniu z poprzednim rozwiązaniem przyrost objętości jest duży, ale strata czasu jest niewielka , należy wówczas wybrać nową opcję.
Zacznijmy od ostatniego wymagania. Aby wyjaśnić dwuznaczne słowo „bilans”, przeprowadziliśmy ankietę wśród pracowników magazynu, z której uzyskaliśmy następujące informacje. Niech będzie komórka pojemnikowa o objętości , do którego przypisany jest ruch pozostałych towarów z komórek dawcy i równy jest całkowity czas tego przemieszczania . Niech będzie kilka alternatywnych opcji umieszczenia tej samej ilości towarów z tych samych komórek dawcy w innych pojemnikach, gdzie każde rozmieszczenie ma własne szacunki Gdzie < и Gdzie >.
Powstaje pytanie: jakie jest minimalne wzmocnienie głośności dopuszczalne, dla danej wartości straty czasu ? Wyjaśnijmy na przykładzie. Początkowo szczątki miały być umieszczone w pojemniku o pojemności 1000 dm3 (1 m3), a czas przenoszenia wynosił 70 sekund. Istnieje możliwość umieszczenia pozostałości w innym pojemniku o pojemności 500 dm3 i czasie 130 sekund. Pytanie: czy jesteśmy gotowi poświęcić dodatkowe 60 sekund czasu magazyniera na przemieszczanie towaru, aby zaoszczędzić 500 dm3 wolnej objętości? Na podstawie wyników ankiety przeprowadzonej wśród pracowników magazynów sporządzono poniższy wykres.
Ryż. 5. Wykres zależności minimalnej dopuszczalnej oszczędności objętości od wzrostu różnicy czasu pracy
Oznacza to, że jeśli dodatkowe koszty czasu wynoszą 40 sekund, to jesteśmy gotowi je wydać dopiero wtedy, gdy przyrost objętości wyniesie co najmniej 500 dm3. Pomimo, że zależność wykazuje niewielką nieliniowość, dla uproszczenia dalszych obliczeń przyjmiemy, że zależność pomiędzy wielkościami ma charakter liniowy i jest opisana nierównością
Na poniższym rysunku rozważamy następujące sposoby umieszczania towarów w kontenerach.
Ryż. 6. Opcja (a): 2 kontenery, całkowita objętość 400 dm3, całkowity czas 150 sek.
Ryż. 6. Opcja (b): 2 kontenery, całkowita objętość 600 dm3, całkowity czas 190 sek.
Ryż. 6. Opcja (c): 1 kontener, całkowita objętość 400 dm3, całkowity czas 200 sek.
Opcja (a) wyboru pojemników jest bardziej preferowana niż opcja pierwotna, ponieważ nierówność zachodzi: (800-400)/10>=150-120, co implikuje 40 >= 30. Opcja (b) jest mniej korzystna niż wersja oryginalna opcja , ponieważ nierówność nie zachodzi: (800-600)/10>=190-150, co implikuje 20 >= 40. Ale opcja (c) nie pasuje do takiej logiki! Rozważmy tę opcję bardziej szczegółowo. Z jednej strony nierówność (800-400)/10>=200-120, co oznacza, że nierówność 40 >= 80 nie jest spełniona, co sugeruje, że przyrost objętości nie jest wart tak dużej straty czasu.
Ale z drugiej strony w tej opcji (c) nie tylko zmniejszamy całkowitą zajętą objętość, ale także zmniejszamy liczbę zajętych komórek, co jest pierwszym z dwóch ważnych wymagań dla obliczeniowych rozwiązań wymienionych powyżej problemów. Oczywiście, aby warunek ten zaczął być spełniany, należy dodać do lewej strony nierówności pewną dodatnią stałą , a taką stałą należy dodać tylko wtedy, gdy liczba kontenerów maleje. Przypomnijmy Ci to jest zmienną równą 1, gdy kontener wybrany i 0, gdy kontener nie zaznaczone. Oznaczmy – wiele pojemników w rozwiązaniu początkowym i – wiele pojemników w nowym rozwiązaniu. Ogólnie nowa nierówność będzie wyglądać następująco:
Przekształcając powyższą nierówność, otrzymujemy
Na tej podstawie mamy wzór na obliczenie całkowitego kosztu jakieś rozwiązanie problemu:
Ale teraz pojawia się pytanie: jaką wartość powinna mieć taka stała? ? Oczywiście jego wartość musi być na tyle duża, aby zawsze był spełniony pierwszy warunek rozwiązania problemu. Można oczywiście przyjąć wartość stałej równą 103 lub 106, jednak chciałbym uniknąć takich „magicznych liczb”. Jeśli weźmiemy pod uwagę specyfikę wykonywania operacji magazynowych, możemy obliczyć kilka uzasadnionych szacunków numerycznych wartości takiej stałej.
Pozwól – maksymalna odległość pomiędzy komórkami magazynowymi jednej strefy ABC, równa w naszym przypadku 100 m. Niech – maksymalna objętość komórki kontenerowej w magazynie, równa w naszym przypadku 1000 dm3.
Pierwszy sposób obliczenia wartości . Rozważmy sytuację, gdy na pierwszym poziomie znajdują się 2 kontenery, w których towar jest już fizycznie zlokalizowany, czyli same są komórkami dawcy, a koszt przeniesienia towaru do tych samych komórek jest oczywiście równy 0. To konieczne jest znalezienie takiej wartości dla stałej , w którym korzystne byłoby zawsze przenoszenie resztek z pojemnika 1 do pojemnika 2. Podstawianie wartości и Z nierówności podanej powyżej otrzymujemy:
z czego wynika
Podstawiając wartości średniego czasu wykonywania elementarnych operacji do powyższego wzoru otrzymujemy
Drugi sposób obliczenia wartości . Rozważmy sytuację, w której tak jest komórki dawcy, z których planowane jest przeniesienie towaru do kontenera 1. Oznaczmy – odległość od komórki dawcy do kontenera 1. Jest też kontener 2, w którym już znajduje się towar, a którego objętość pozwala na zmieszczenie pozostałej części komórki. Dla uproszczenia założymy, że objętość towarów przenoszonych z komórek dawcy do kontenerów jest taka sama i równa . Należy znaleźć taką wartość stałej , w którym umieszczane są wszystkie pozostałości z komórek do pojemnika 2 zawsze byłoby bardziej opłacalne niż umieszczanie ich w różnych pojemnikach:
Przekształcając otrzymaną nierówność
W celu „wzmocnienia” wartości ilościowej , załóżmy, że = 0. Średnia liczba komórek zwykle biorących udział w procedurze kompresji sald magazynowych wynosi 10. Podstawiając znane wartości ilości, otrzymujemy następującą wartość stałej
Przyjmujemy największą wartość obliczoną dla każdej opcji, będzie to wartość ilości dla zadanych parametrów magazynowych. Teraz dla kompletności zapiszmy wzór na obliczenie kosztów całkowitych na jakieś możliwe rozwiązanie :
W końcu teraz Herkulesowe wysiłki Dokonując transformacji danych wejściowych, można powiedzieć, że wszystkie dane wejściowe zostały skonwertowane do pożądanej postaci i są gotowe do wykorzystania w algorytmie optymalizacyjnym.
wniosek
Jak pokazuje praktyka, często niedoceniana jest złożoność i znaczenie etapu przygotowania i przekształcenia danych wejściowych dla algorytmu. W tym artykule szczególnie dużo uwagi poświęciliśmy temu etapowi, aby pokazać, że tylko wysokiej jakości i inteligentnie przygotowane dane wejściowe mogą sprawić, że wyliczone przez algorytm decyzje będą naprawdę wartościowe dla klienta. Tak, wyprowadzeń formuł było wiele, ale ostrzegaliśmy jeszcze przed kata :)
W następnym artykule wreszcie dotrzemy do tego, czemu miały służyć 2 poprzednie publikacje – algorytmowi optymalizacji dyskretnej.
Przygotowałem artykuł
Roman Shangin, programista działu projektów,
Firma First Bit, Czelabińsk
Źródło: www.habr.com