In diesem Artikel erzählen wir Ihnen, wie wir das Problem des Mangels an freien Zellen in einem Lager gelöst haben und wie wir einen diskreten Optimierungsalgorithmus zur Lösung dieses Problems entwickelt haben. Lassen Sie uns darüber sprechen, wie wir das mathematische Modell des Optimierungsproblems „gebaut“ haben und über die Schwierigkeiten, auf die wir unerwartet bei der Verarbeitung der Eingabedaten für den Algorithmus gestoßen sind.
Wenn Sie sich für Anwendungen der Mathematik in der Wirtschaft interessieren und keine Angst vor starren Identitätsumwandlungen von Formeln in der 5. Klasse haben, dann willkommen bei der Katze!
Der Artikel wird für diejenigen nützlich sein, die ihn umsetzen WMS-Systeme, die in der Lager- oder Produktionslogistikbranche arbeiten, sowie Programmierer, die sich für Anwendungen der Mathematik in der Wirtschaft und die Optimierung von Prozessen in einem Unternehmen interessieren.
Einführender Teil
Mit dieser Veröffentlichung setzen wir die Artikelserie fort, in der wir unsere erfolgreichen Erfahrungen bei der Implementierung von Optimierungsalgorithmen in Lagerprozessen teilen.
В beschreibt die Besonderheiten des Lagers, in dem wir implementiert haben WMS-System und erklärt auch, warum wir das Problem der Clusterung von Chargen verbleibender Waren während der Implementierung lösen mussten WMS-Systeme und wie wir es gemacht haben.
Als wir mit dem Schreiben des Artikels über Optimierungsalgorithmen fertig waren, stellte sich heraus, dass er sehr umfangreich war, und so beschlossen wir, das gesammelte Material in zwei Teile aufzuteilen:
- Im ersten Teil (dieser Artikel) werden wir darüber sprechen, wie wir das mathematische Modell des Problems „gebaut“ haben und über die großen Schwierigkeiten, auf die wir unerwartet bei der Verarbeitung und Transformation der Eingabedaten für den Algorithmus gestoßen sind.
- Im zweiten Teil werden wir uns ausführlich mit der Implementierung des Algorithmus in der Sprache befassen C + +Wir führen ein rechnerisches Experiment durch und fassen die Erfahrungen zusammen, die wir bei der Implementierung solcher „intelligenten Technologien“ in die Geschäftsprozesse des Kunden gesammelt haben.
Wie liest man einen Artikel? Wenn Sie den vorherigen Artikel gelesen haben, können Sie sofort zum Kapitel „Überblick über vorhandene Lösungen“ wechseln. Wenn nicht, finden Sie die Beschreibung des zu lösenden Problems im Spoiler unten.
Beschreibung des Problems, das im Lager des Kunden gelöst wird
Engpass in den Prozessen
Im Jahr 2018 haben wir ein Projekt zur Umsetzung abgeschlossen WMS-Systeme im Lager „Handelshaus „LD“ in Tscheljabinsk. Wir haben das Produkt „1C-Logistics: Warehouse Management 3“ für 20 Arbeitsplätze: Bediener implementiert WMS, Lagerhalter, Gabelstaplerfahrer. Das durchschnittliche Lager ist etwa 4 m2 groß, die Anzahl der Zellen beträgt 5000 und die Anzahl der Artikel beträgt 4500. Das Lager lagert Kugelhähne aus eigener Produktion in verschiedenen Größen von 1 kg bis 400 kg. Der Lagerbestand wird in Chargen gelagert, da die Warenauswahl nach FIFO erfolgen muss.
Bei der Konzeption von Systemen zur Automatisierung von Lagerprozessen standen wir vor dem bestehenden Problem einer nicht optimalen Lagerhaltung. Die Besonderheiten von Lager- und Verlegekränen bestehen darin, dass eine Einheitslagerzelle nur Artikel einer Charge enthalten kann (siehe Abb. 1). Die Produkte kommen täglich im Lager an und bei jedem Eingang handelt es sich um eine separate Charge. Insgesamt entstehen in einem Monat Lagerbetrieb 1 separate Chargen, obwohl jede in einer separaten Zelle gelagert werden sollte. Produkte werden oft nicht in ganzen Paletten, sondern in Stücken ausgewählt, und als Ergebnis ist in der Stückauswahlzone in vielen Zellen das folgende Bild zu beobachten: In einer Zelle mit einem Volumen von mehr als 30 m1 gibt es mehrere Kräne, die nehmen weniger als 3-5 % des Zellvolumens ein.
Abb. 1. Foto mehrerer Teile in einer Zelle
Es ist klar, dass die Lagerkapazität nicht optimal genutzt wird. Um sich das Ausmaß der Katastrophe vorzustellen, kann ich Zahlen nennen: Im Durchschnitt gibt es zwischen 1 und 3 solcher Zellen mit einem Volumen von mehr als 100 m300 mit „winzigen“ Salden während verschiedener Betriebsperioden des Lagers. Da das Lager relativ klein ist, wird dieser Faktor während der Hochsaison im Lager zu einem „Engpass“ und verlangsamt die Annahme- und Versandprozesse im Lager erheblich.
Idee zur Problemlösung
Es entstand eine Idee: Chargen von Resten mit den nächstgelegenen Daten sollten auf eine einzige Charge reduziert werden, und solche Reste mit einer einheitlichen Charge sollten kompakt zusammen in einer Zelle oder in mehreren platziert werden, wenn in einer nicht genügend Platz für die Unterbringung vorhanden ist gesamte Restmenge. Ein Beispiel für eine solche „Komprimierung“ ist in Abbildung 2 dargestellt.
Abb.2. Schema zur Komprimierung von Rückständen in Zellen
Dadurch können Sie die belegte Lagerfläche, die für die Einlagerung neuer Waren genutzt wird, deutlich reduzieren. In einer Situation, in der die Lagerkapazität überlastet ist, ist eine solche Maßnahme äußerst notwendig, da andernfalls möglicherweise einfach nicht genügend freier Platz für die Unterbringung neuer Waren vorhanden ist, was zu einem Stopp der Lagerprozesse der Einlagerung und Auffüllung und in der Folge dazu führt, dass zu einem Annahme- und Versandstopp führen. Bisher, vor der Implementierung des WMS-Systems, wurde ein solcher Vorgang manuell durchgeführt, was ineffektiv war, da die Suche nach geeigneten Salden in Zellen ziemlich langwierig war. Mit der Einführung eines WMS-Systems haben wir uns nun entschieden, den Prozess zu automatisieren, zu beschleunigen und intelligent zu machen.
Der Prozess zur Lösung eines solchen Problems ist in zwei Phasen unterteilt:
- In der ersten Phase finden wir Gruppen von Stapeln mit ähnlichem Datum für die Komprimierung (die dieser Aufgabe gewidmet sind). );
- Im zweiten Schritt berechnen wir für jede Chargengruppe die kompakteste Platzierung der restlichen Ware in den Zellen.
Im aktuellen Artikel konzentrieren wir uns auf die zweite Stufe des Algorithmus.
Überprüfung vorhandener Lösungen
Bevor mit der Beschreibung der von uns entwickelten Algorithmen begonnen wird, lohnt es sich, einen kurzen Überblick über bereits auf dem Markt befindliche Systeme zu geben WMS, die eine ähnliche optimale Komprimierungsfunktionalität implementieren.
Zunächst ist das Produkt „1C: Enterprise 8. WMS Logistics“ zu beachten. Warehouse Management 4“, das 1C gehört und von XNUMXC repliziert wird und zur vierten Generation gehört WMS-Systeme entwickelt von AXELOT. Dieses System beansprucht eine Komprimierungsfunktion, die darauf ausgelegt ist, unterschiedliche Produktreste in einer gemeinsamen Zelle zu vereinen. Es ist erwähnenswert, dass die Komprimierungsfunktionalität in einem solchen System auch andere Möglichkeiten umfasst, beispielsweise die Korrektur der Platzierung von Waren in Zellen entsprechend ihrer ABC-Klassen, aber wir werden uns nicht damit befassen.
Wenn Sie den Code des 1C: Enterprise 8. WMS Logistics-Systems analysieren. Lagerverwaltung 4“ (die in diesem Teil der Funktionalität geöffnet ist) können wir folgendes schließen. Der Restkomprimierungsalgorithmus implementiert eine eher primitive lineare Logik und von einer „optimalen“ Komprimierung kann keine Rede sein. Selbstverständlich ist eine Bündelung der Parteien nicht vorgesehen. Mehrere Kunden, die ein solches System implementiert hatten, beschwerten sich über die Ergebnisse der Komprimierungsplanung. Beispielsweise kam es in der Praxis beim Komprimieren häufig zu folgender Situation: 100 Stk. Es ist geplant, die restlichen Waren von einer Zelle in eine andere Zelle zu transportieren, in der sich 1 Stück befindet. Waren, obwohl es aus Sicht des Zeitverbrauchs optimal ist, das Gegenteil zu tun.
Auch die Funktionalität der Komprimierung der restlichen Ware in Zellen wird in vielen ausländischen Ländern deklariert. WMS-Systeme, aber leider haben wir kein wirkliches Feedback zur Wirksamkeit der Algorithmen (dies ist ein Geschäftsgeheimnis), geschweige denn eine Vorstellung von der Tiefe ihrer Logik (proprietäre Closed-Source-Software), sodass wir kein Urteil fällen können.
Suchen Sie nach einem mathematischen Modell des Problems
Um qualitativ hochwertige Algorithmen zur Lösung eines Problems zu entwerfen, ist es zunächst notwendig, dieses Problem mathematisch klar zu formulieren, was wir tun werden.
Es gibt viele Zellen , die Reste einiger Waren enthalten. Im Folgenden nennen wir solche Zellen Spenderzellen. Bezeichnen wir Warenvolumen in der Zelle $.
Es ist wichtig zu sagen, dass nur ein Produkt einer Charge oder mehrere Chargen, die zuvor zu einem Cluster zusammengefasst wurden (sprich: ), was auf die Besonderheiten der Lagerung und Lagerung von Gütern zurückzuführen ist. Unterschiedliche Produkte oder unterschiedliche Batch-Cluster sollten ihr eigenes separates Komprimierungsverfahren ausführen.
Es gibt viele Zellen , in die möglicherweise Rückstände von Spenderzellen eingebracht werden können. Wir werden solche Zellen im Folgenden Containerzellen nennen. Dabei kann es sich entweder um freie Zellen im Lager oder um Spenderzellen einer Sorte handeln . Immer reichlich ist eine Teilmenge .
Für jede Zelle Von vielen Es wurden Kapazitätsbeschränkungen festgelegt , gemessen in dm3. Ein dm3 ist ein Würfel mit einer Seitenlänge von 10 cm. Die im Lager gelagerten Produkte sind recht groß, daher reicht in diesem Fall eine solche Diskretisierung völlig aus.
Gegeben sei eine Matrix kürzester Entfernungen in Metern zwischen jedem Zellenpaar Wo и gehören zu Mengen и jeweils.
Bezeichnen wir „Kosten“ für den Transport von Waren aus der Zelle in eine Zelle . Bezeichnen wir „Kosten“ für die Auswahl eines Containers um Rückstände aus anderen Zellen hineinzubewegen. Wie genau und in welchen Maßeinheiten werden die Werte berechnet и Wir werden weiter darüber nachdenken (siehe Abschnitt „Vorbereitung der Eingabedaten“), denn jetzt reicht es zu sagen, dass solche Werte direkt proportional zu den Werten sind и jeweils.
Bezeichnen wir mit eine Variable, die den Wert 1 annimmt, wenn der Rest aus der Zelle stammt in den Container verschoben , andernfalls 0. Bezeichnen wir mit eine Variable, die den Wert 1 annimmt, wenn der Container enthält die restlichen Waren, andernfalls 0.
Die Aufgabenstellung lautet wie folgt: Sie müssen so viele Container finden und so Spenderzellen an Behälterzellen „anheften“, um die Funktion zu minimieren
unter Einschränkungen
Insgesamt streben wir bei der Berechnung der Lösung des Problems an:
- erstens, um Lagerkapazität zu sparen;
- Zweitens, um den Ladenbesitzern Zeit zu sparen.
Die letzte Einschränkung bedeutet, dass wir keine Waren in einen Container transportieren können, den wir nicht ausgewählt haben und für den daher keine „Kosten“ für die Auswahl entstanden sind. Diese Einschränkung bedeutet auch, dass die Menge der von den Zellen in den Container transportierten Güter das Fassungsvermögen des Containers nicht überschreiten darf. Mit der Lösung eines Problems meinen wir eine Reihe von Containern und Methoden zum Anbringen von Spenderzellen an Behältern.
Diese Formulierung des Optimierungsproblems ist nicht neu und wurde seit den frühen 80er Jahren des letzten Jahrhunderts von vielen Mathematikern untersucht. In der ausländischen Literatur gibt es 2 Optimierungsprobleme mit einem geeigneten mathematischen Modell: и (Über die Unterschiede bei den Aufgaben sprechen wir später). Es ist erwähnenswert, dass in der mathematischen Literatur die Formulierung dieser beiden Optimierungsprobleme in Bezug auf den Standort von Unternehmen vor Ort formuliert wird, daher der Name „Facility Location“. Dies ist größtenteils eine Hommage an die Tradition, da die Notwendigkeit, solche kombinatorischen Probleme zu lösen, erstmals in den 50er Jahren des letzten Jahrhunderts aus dem Bereich der Logistik, hauptsächlich aus dem militärisch-industriellen Bereich, kam. Bezogen auf den Unternehmensstandort werden solche Aufgaben wie folgt formuliert:
- Es gibt eine begrenzte Anzahl von Städten, in denen potenziell produzierende Unternehmen angesiedelt werden können (im Folgenden „Produktionsstädte“ genannt). Für jede Produktionsstadt werden die Kosten für die Eröffnung eines Unternehmens sowie eine Begrenzung der Produktionskapazität des dort eröffneten Unternehmens angegeben.
- Es gibt eine begrenzte Anzahl von Städten, in denen Kunden tatsächlich ansässig sind (im Folgenden als Kundenstädte bezeichnet). Für jede dieser Kundenstädte wird das Nachfragevolumen nach Produkten angegeben. Der Einfachheit halber gehen wir davon aus, dass es nur ein Produkt gibt, das von Unternehmen hergestellt und von Kunden konsumiert wird.
- Für jedes Paar Stadt-Hersteller und Stadt-Kunde wird der Wert der Transportkosten für die Lieferung der erforderlichen Produktmenge vom Hersteller zum Kunden angegeben.
Sie müssen herausfinden, in welchen Städten Sie Unternehmen eröffnen und wie Sie Kunden an solche Unternehmen binden können, um:
- Die Gesamtkosten für die Eröffnung von Unternehmen und die Transportkosten waren minimal;
- Das Nachfragevolumen der Kunden, die einem offenen Unternehmen zugeordnet waren, überstieg nicht die Produktionskapazität dieses Unternehmens.
Nun lohnt es sich, den einzigen Unterschied zwischen diesen beiden klassischen Problemen zu erwähnen:
- Standortproblem einer kapazitierten Anlage aus einer einzigen Quelle – der Kunde wird nur von einer offenen Anlage beliefert;
- Standortproblem einer kapazitierten Einrichtung mit mehreren Quellen – der Kunde kann gleichzeitig von mehreren offenen Einrichtungen versorgt werden.
Ein solcher Unterschied zwischen den beiden Problemen ist auf den ersten Blick unbedeutend, führt aber tatsächlich zu einer völlig anderen kombinatorischen Struktur solcher Probleme und in der Folge zu völlig unterschiedlichen Algorithmen zu deren Lösung. Die Unterschiede zwischen den Aufgaben werden in der folgenden Abbildung veranschaulicht.
Abb. 3. a) Standortproblem einer kapazitierten Anlage mit mehreren Quellen
Abb. 3. b) Standortproblem einer kapazitierten Anlage mit einer einzigen Quelle
Beide Aufgaben -schwierig, das heißt, es gibt keinen genauen Algorithmus, der ein solches Problem in einem Zeitpolynom in der Größe der Eingabedaten lösen würde. Einfacher ausgedrückt: Alle exakten Algorithmen zur Lösung eines Problems funktionieren in exponentieller Zeit, wenn auch möglicherweise schneller als eine vollständige Suche nach Optionen. Da die Aufgabe -schwierig, dann betrachten wir nur Näherungsheuristiken, also Algorithmen, die konsistent Lösungen berechnen, die sehr nahe am Optimum liegen und recht schnell arbeiten. Wenn Sie sich für eine solche Aufgabe interessieren, finden Sie hier eine gute Übersicht auf Russisch.
Wenn wir zur Terminologie unseres Problems der optimalen Komprimierung von Gütern in Zellen übergehen, dann:
- Kundenstädte sind Spenderzellen mit der restlichen Ware,
- Produktionsstädte – Containerzellen , in dem die Reste aus anderen Zellen untergebracht werden sollen,
- Transportkosten - Zeitkosten Ladenbesitzer, um die Warenmenge aus der Spenderzelle zu transportieren in eine Containerzelle ;
- Kosten für die Eröffnung eines Unternehmens – Kosten für die Auswahl eines Containers , gleich dem Volumen der Behälterzelle , multipliziert mit einem bestimmten Koeffizienten zur Einsparung freier Volumina (der Wert des Koeffizienten ist immer > 1) (siehe Abschnitt „Vorbereitung der Eingabedaten“).
Nachdem die Analogie zu den bekannten klassischen Lösungen des Problems gezogen wurde, muss eine wichtige Frage beantwortet werden, von der die Wahl der Architektur des Lösungsalgorithmus abhängt: Das Verschieben der Reste aus der Spenderzelle ist nur in einen und nur einen Container möglich (Single-Source) oder ist es möglich, die Reste in mehrere Containerzellen zu verschieben (Multi-Source)?
Es ist erwähnenswert, dass in der Praxis beide Formulierungen des Problems vorkommen. Im Folgenden stellen wir alle Vor- und Nachteile für jede dieser Einstellungen vor:
| Problemvariante | Vorteile der Option | Nachteile der Option |
|---|---|---|
| Einzige Quelle | Mit dieser Variante des Problems berechnete Warenbewegungsvorgänge:
|
|
| Multi-Quelle | Komprimierungen, die mit dieser Version des Problems berechnet werden, sind normalerweise 10–15 % kompakter als Komprimierungen, die mit der Option „Single-Source“ berechnet werden. Wir stellen aber auch fest, dass der Unterschied in der Kompaktheit umso geringer ist, je kleiner die Anzahl der Rückstände in den Spenderzellen ist | Mit dieser Variante des Problems berechnete Warenbewegungsvorgänge:
|
Tabelle 1. Vor- und Nachteile der Single-Source- und Multi-Source-Optionen.
Da die Single-Source-Option mehr Vorteile bietet und auch die Tatsache berücksichtigt wird, dass der Unterschied im Grad der Komprimierungskompaktheit, der für beide Varianten des Problems berechnet wird, umso geringer ist, je geringer die Anzahl der Rückstände in den Spenderzellen ist, fiel unsere Wahl auf die Single-Source-Option. Quelle.
Es ist erwähnenswert, dass auch die Lösung für die Multi-Source-Option erfolgt. Es gibt eine große Anzahl effektiver Algorithmen zu seiner Lösung, von denen die meisten darauf hinauslaufen, eine Reihe von Transportproblemen zu lösen. Es gibt auch nicht nur effiziente Algorithmen, sondern auch elegante, zum Beispiel
Eingabedaten vorbereiten
Bevor mit der Analyse und Entwicklung eines Algorithmus zur Lösung eines Problems begonnen wird, muss entschieden werden, welche Daten und in welcher Form wir sie als Eingabe bereitstellen. Es gibt keine Probleme mit dem Volumen der verbleibenden Güter in Spenderzellen und der Kapazität von Containerzellen, da dies trivial ist – solche Mengen werden in m3 gemessen, aber mit den Kosten für die Nutzung einer Containerzelle und der Umzugskostenmatrix ist das nicht alles ist so einfach!
Schauen wir uns zunächst die Berechnung an Kosten für den Warentransport von der Spenderzelle zur Containerzelle. Zunächst muss entschieden werden, in welchen Maßeinheiten wir die Transportkosten berechnen. Die beiden offensichtlichsten Optionen sind Meter und Sekunde. Es macht keinen Sinn, Fahrtkosten in „reinen“ Metern zu berechnen. Lassen Sie uns dies anhand eines Beispiels zeigen. Lass die Zelle befindet sich auf der ersten Ebene, Zelle um 30 Meter entfernt und auf der zweiten Ebene gelegen:
- Umziehen von в teurer als ein Umzug в , da der Abstieg von der zweiten Ebene (1,5 bis 2 Meter über dem Boden) einfacher ist als der Aufstieg zur zweiten, obwohl die Entfernung gleich bleibt;
- Bewegen Sie 1 Stk. Waren aus der Zelle в Es wird einfacher sein, als 10 Teile zu bewegen. das gleiche Produkt, obwohl der Abstand gleich sein wird.
Es ist besser, die Umzugskosten in Sekunden zu berücksichtigen, da Sie so sowohl den Unterschied in den Ebenen als auch den Unterschied in der Menge der bewegten Waren berücksichtigen können. Um die Bewegungskosten in Sekunden zu berücksichtigen, müssen wir den Bewegungsvorgang in Elementarkomponenten zerlegen und Zeitmessungen für die Ausführung jeder Elementarkomponente vornehmen.
Aus der Zelle lassen bewegt sich PC. Waren im Container . Lassen – die durchschnittliche Bewegungsgeschwindigkeit eines Arbeiters im Lager, gemessen in m/s. Lassen и – durchschnittliche Geschwindigkeiten der einmaligen Entnahme bzw. Lagerung von Vorgängen für ein Warenvolumen von 4 dm3 (das durchschnittliche Volumen, das ein Mitarbeiter gleichzeitig in einem Lager bei der Durchführung von Vorgängen aufnimmt). Lassen и die Höhe der Zellen, von denen aus die Take- bzw. Put-Operationen ausgeführt werden. Beispielsweise beträgt die durchschnittliche Höhe der ersten Etage (Boden) 1 m, die der zweiten Etage 2 m usw. Dann lautet die Formel zur Berechnung der Gesamtzeit zum Abschluss eines Verschiebevorgangs wie folgt:
Tabelle 2 zeigt Statistiken über die Ausführungszeit jedes Elementarvorgangs, die von Lagermitarbeitern unter Berücksichtigung der Besonderheiten der gelagerten Waren erhoben wurden.
| Name des Betriebs | Bezeichnung | Mittlere Bedeutung |
|---|---|---|
| Durchschnittliche Geschwindigkeit eines Arbeiters, der sich im Lager bewegt | |
1,5 m / s |
| Durchschnittliche Geschwindigkeit eines Arbeitsgangs (für ein Produktvolumen von 4 dm3) | |
2,4 sek |
Tabelle 2. Durchschnittliche Zeit bis zum Abschluss von Lagervorgängen
Wir haben uns für die Methode zur Berechnung der Umzugskosten entschieden. Jetzt müssen wir herausfinden, wie man berechnet Kosten für die Auswahl einer Containerzelle. Hier ist alles viel, viel komplizierter als bei den Umzugskosten, denn:
- Erstens sollten die Kosten direkt vom Volumen der Zelle abhängen – das gleiche Volumen an von Spenderzellen übertragenen Rückständen lässt sich besser in einem Behälter mit kleinerem Volumen unterbringen als in einem großen Behälter, vorausgesetzt, dass dieses Volumen vollständig in beide Behälter passt. Durch die Minimierung der Gesamtkosten für die Auswahl der Behälter streben wir danach, „knappe“ freie Lagerkapazität im Auswahlbereich einzusparen, um nachfolgende Vorgänge zum Einlagern von Waren in Zellen durchzuführen. Abbildung 4 zeigt die Möglichkeiten der Reststoffumfüllung in Groß- und Kleingebinde und die Auswirkungen dieser Umlagerungsmöglichkeiten auf den späteren Lagerbetrieb.
- Zweitens, da wir bei der Lösung des ursprünglichen Problems genau die Gesamtkosten minimieren müssen, und diese sind die Summe sowohl der Umzugskosten als auch der Kosten für die Auswahl der Container, müssen die Zellvolumina in Kubikmetern irgendwie mit Sekunden verknüpft werden. Das ist alles andere als trivial.
Reis. 4. Möglichkeiten zum Umfüllen von Resten in Behälter mit unterschiedlichem Fassungsvermögen.
Abbildung 4 zeigt in Rot die Menge an Resten, die bei der zweiten Stufe der Nachlagerung nicht mehr in den Behälter passt.
Es hilft, die Kosten in Kubikmetern für die Auswahl eines Containers mit den Kosten in Sekunden für den Umzug zu verknüpfen, um die folgenden Anforderungen an kalkulierte Lösungen für das Problem zu stellen:
- Es ist auf jeden Fall erforderlich, die Restbestände aus dem Spenderbehälter in den Behälterbehälter umzulagern, wenn sich dadurch die Gesamtzahl der Behälterbehälter mit dem Produkt verringert.
- Es ist notwendig, ein Gleichgewicht zwischen dem Volumen der Container und der für den Umzug aufgewendeten Zeit aufrechtzuerhalten: Wenn beispielsweise bei einer neuen Lösung eines Problems im Vergleich zur vorherigen Lösung der Volumengewinn groß, der Zeitverlust jedoch gering ist , dann ist es notwendig, eine neue Option zu wählen.
Beginnen wir mit der letzten Anforderung. Um das mehrdeutige Wort „Balance“ zu klären, haben wir eine Umfrage unter Lagermitarbeitern durchgeführt, um Folgendes herauszufinden. Es soll eine Containerzelle mit Volumen geben , dem die Bewegung verbleibender Güter aus Spenderzellen zugeordnet ist und die Gesamtzeit dieser Bewegung gleich ist . Es gebe mehrere alternative Möglichkeiten, die gleiche Menge an Gütern aus den gleichen Spenderzellen in andere Behälter zu platzieren, wobei für jede Platzierung ihre eigenen Schätzungen gelten Wo < и Wo >.
Es stellt sich die Frage: Was ist der minimale Lautstärkegewinn? akzeptabel, für einen gegebenen Zeitverlustwert ? Lassen Sie es uns anhand eines Beispiels erklären. Ursprünglich sollten die Überreste in einen Behälter mit einem Volumen von 1000 dm3 (1 m3) gegeben werden und die Transferzeit 70 Sekunden betragen. Es besteht die Möglichkeit, die Reststoffe in einen weiteren Behälter mit einem Volumen von 500 dm3 und einer Zeit von 130 Sekunden zu füllen. Frage: Sind wir bereit, zusätzliche 60 Sekunden der Zeit des Lagerhalters für den Warentransport aufzuwenden, um 500 dm3 freies Volumen einzusparen? Basierend auf den Ergebnissen einer Befragung von Lagermitarbeitern wurde das folgende Diagramm erstellt.
Reis. 5. Diagramm der Abhängigkeit der minimal zulässigen Volumeneinsparungen von der Zunahme der Betriebszeitdifferenz
Das heißt, wenn die zusätzlichen Zeitkosten 40 Sekunden betragen, sind wir bereit, sie erst dann auszugeben, wenn der Volumengewinn mindestens 500 dm3 beträgt. Trotz der Tatsache, dass die Abhängigkeit eine leichte Nichtlinearität aufweist, gehen wir zur Vereinfachung weiterer Berechnungen davon aus, dass die Abhängigkeit zwischen den Größen linear ist und durch die Ungleichung beschrieben wird
In der folgenden Abbildung betrachten wir die folgenden Methoden zum Platzieren von Waren in Containern.
Reis. 6. Option (a): 2 Behälter, Gesamtvolumen 400 dm3, Gesamtzeit 150 Sek.
Reis. 6. Option (b): 2 Behälter, Gesamtvolumen 600 dm3, Gesamtzeit 190 Sek.
Reis. 6. Option (c): 1 Behälter, Gesamtvolumen 400 dm3, Gesamtzeit 200 Sek.
Option (a) zur Auswahl von Containern ist besser als die ursprüngliche Option, da die Ungleichung gilt: (800-400)/10>=150-120, was 40 >= 30 impliziert. Option (b) ist weniger vorzuziehen als das Original Option , da die Ungleichung nicht gilt: (800-600)/10>=190-150, was 20 >= 40 impliziert. Aber Option (c) passt nicht in eine solche Logik! Betrachten wir diese Option genauer. Einerseits gilt die Ungleichung (800-400)/10>=200-120, was bedeutet, dass die Ungleichung 40 >= 80 nicht erfüllt ist, was darauf hindeutet, dass der Volumengewinn einen so großen Zeitverlust nicht wert ist.
Andererseits reduzieren wir bei dieser Option (c) nicht nur das gesamte belegte Volumen, sondern auch die Anzahl der belegten Zellen, was die erste von zwei wichtigen Anforderungen für berechenbare Lösungen der oben aufgeführten Probleme ist. Damit diese Anforderung erfüllt wird, ist es natürlich notwendig, auf der linken Seite der Ungleichung eine positive Konstante hinzuzufügen , und eine solche Konstante muss nur hinzugefügt werden, wenn die Anzahl der Container abnimmt. Wir möchten Sie daran erinnern ist eine Variable gleich 1, wenn der Container ausgewählt, und 0, wenn Container nicht ausgewählt. Bezeichnen wir – viele Behälter in der Ausgangslösung und – viele Container in der neuen Lösung. Im Allgemeinen wird die neue Ungleichung so aussehen:
Wenn wir die obige Ungleichung transformieren, erhalten wir
Auf dieser Grundlage haben wir eine Formel zur Berechnung der Gesamtkosten eine Lösung für das Problem:
Aber jetzt stellt sich die Frage: Welchen Wert sollte eine solche Konstante haben? ? Offensichtlich muss sein Wert groß genug sein, damit die erste Anforderung an Lösungen des Problems immer erfüllt ist. Sie können natürlich den Wert der Konstante gleich 103 oder 106 annehmen, aber ich möchte solche „magischen Zahlen“ vermeiden. Wenn wir die Besonderheiten der Durchführung von Lageroperationen berücksichtigen, können wir mehrere fundierte numerische Schätzungen des Wertes einer solchen Konstante berechnen.
Lassen – der maximale Abstand zwischen Lagerzellen einer Zone ABC, in unserem Fall 100 m. Lassen Sie – das maximale Volumen einer Containerzelle in einem Lager, in unserem Fall 1000 dm3.
Die erste Möglichkeit, den Wert zu berechnen . Stellen wir uns eine Situation vor, in der sich auf der ersten Ebene zwei Container befinden, in denen sich die Waren bereits physisch befinden, das heißt, sie selbst sind Spenderzellen, und die Kosten für den Transport der Waren in dieselben Zellen betragen natürlich 2. Es ist notwendig, um einen solchen Wert für die Konstante zu finden , wobei es von Vorteil wäre, die Reste immer von Behälter 1 in Behälter 2 zu verschieben. Ersetzen der Werte и In der oben angegebenen Ungleichung erhalten wir:
woraus folgt
Wenn wir die Werte der durchschnittlichen Zeit für die Durchführung elementarer Operationen in die obige Formel einsetzen, erhalten wir
Die zweite Möglichkeit, den Wert zu berechnen . Betrachten wir eine Situation, in der dies der Fall ist Spenderzellen, aus denen die Ware in Container 1 überführt werden soll. Bezeichnen wir – Abstand von der Spenderzelle in Container 1. Es gibt auch Container 2, der bereits Waren enthält und dessen Volumen es ermöglicht, den Rest davon unterzubringen Zellen. Der Einfachheit halber gehen wir davon aus, dass die Menge der von den Spenderzellen in die Behälter transportierten Güter gleich und gleich ist . Es ist erforderlich, einen solchen Wert der Konstante zu finden , in dem die Platzierung aller Reste aus Zellen in Container 2 zu platzieren, wäre immer rentabler, als sie in verschiedene Container zu legen:
Wir transformieren die Ungleichheit, die wir bekommen
Um den Wert der Menge zu „stärken“. , nehmen wir das mal an = 0. Die durchschnittliche Anzahl der Zellen, die normalerweise am Verfahren zur Komprimierung von Lagerbeständen beteiligt sind, beträgt 10. Wenn wir die bekannten Werte der Mengen ersetzen, erhalten wir den folgenden Wert der Konstante
Wir nehmen den größten berechneten Wert für jede Option, dies ist der Wert der Menge für die angegebenen Lagerparameter. Der Vollständigkeit halber schreiben wir nun die Formel zur Berechnung der Gesamtkosten auf für eine praktikable Lösung :
Nun ja, schließlich Titanische Bemühungen Durch die Transformation der Eingabedaten können wir sagen, dass alle Eingabedaten in die gewünschte Form umgewandelt wurden und für die Verwendung im Optimierungsalgorithmus bereit sind.
Abschluss
Wie die Praxis zeigt, wird die Komplexität und Bedeutung der Phase der Aufbereitung und Transformation von Eingabedaten für einen Algorithmus oft unterschätzt. In diesem Artikel haben wir dieser Phase besondere Aufmerksamkeit gewidmet, um zu zeigen, dass nur hochwertige und intelligent aufbereitete Eingabedaten die vom Algorithmus berechneten Entscheidungen für den Kunden wirklich wertvoll machen können. Ja, es gab viele Ableitungen von Formeln, aber wir haben Sie bereits vor der Kata gewarnt :)
Im nächsten Artikel kommen wir endlich zu dem, wofür die beiden vorherigen Veröffentlichungen gedacht waren – einem diskreten Optimierungsalgorithmus.
Habe den Artikel vorbereitet
Roman Shangin, Programmierer der Projektabteilung,
Firma First Bit, Tscheljabinsk
Source: habr.com