Optimierung der Arbeitsverteilung durch eindimensionalen Bin-Packing-Algorithmus_3.Implementierung (1)

3. Implementierung des Bin-Packing-Algorithmus

Eine Entwicklungsumgebung ist erforderlich, um die Liste der Elemente und Einschränkungen einzugeben, den Algorithmus zu implementieren und die Ergebnisse zu überprüfen. Es gibt mehrere Entwicklungsumgebungen wie Excel VBA, Python und R. Unter anderem hat Excel VBA keine offene Bibliothek, sodass Sie den größten Teil des Quellcodes selbst schreiben müssen. Python und R können den Bin-Packing-Algorithmus direkt implementieren oder ein bereits bereitgestelltes Paket verwenden. Hier werde ich mir ansehen, wie ich das Tool verwende, das den Algorithmus selbst mit Excel VBA und dem in Python bereitgestellten Paket implementiert.

3.1. Excel VBA-basiertes Tool

Ein Tool oder eine Sprache, die einen Algorithmus implementiert, erhält normalerweise eine Datendatei als Eingabe getrennt vom Quellcode des Programms. Excel VBA hat die Eigenschaft, Programmquellcode und Daten in einer Datei verwalten und separat verwalten zu können. Hier werden Programmquellcode und Daten in einer Datei verwaltet.

Die Konfiguration und der Quellcode des Tools, das die Liste der Artikel durch Eingabe in ein Excel-Sheet verwaltet und den eindimensionalen Bin-Packing-Algorithmus mit VBA implementiert, werden im Folgenden kurz vorgestellt. Der gesamte Quellcode wird als Anhang bereitgestellt. https://github.com/DAToolset/1D-bin-packing kann auch überprüft werden.

**Hinweis: Dieser Artikel behandelt nicht das Konzept oder die Syntax von Excel VBA, sondern wird in Zukunft in einem separaten Artikel ausführlich beschrieben.

Der Gesamtaufbau des Tools ist in der folgenden Abbildung dargestellt. Geben Sie Daten in das Blatt „Run“ ein, legen Sie Optionen fest und klicken Sie auf die Schaltfläche „Run Bin Packing“, um das Ausführungsergebnis zu überprüfen.

Einzelheiten zu den vier Bereichen in der obigen Abbildung werden im folgenden Inhaltsverzeichnis erläutert.

3.1.1. Eingabematerialkonfiguration

Geben Sie in der Artikelliste Name und Größe im folgenden Format ein.

Hier ist der Behälterartikelname ein Name zum Identifizieren des Typs eines Artikels, und er kann gemäß dem Artikeltyp geeignet bezeichnet werden. Zum Beispiel:

• Wenn das Element eine Datenbanktabelle ist, der Tabellenname
• Wenn das Element ein Job ist, der Name des Jobs
• Zusätzlich eine zur Identifizierung des jeweiligen Artikels geeignete Bezeichnung (Bestellnummer etc. ist ebenfalls möglich)

Beachten Sie, dass es keine doppelten Namen in der Artikelliste geben sollte. Denn selbst wenn die Größe gleich ist, muss man wissen, dass es sich um unterschiedliche Objekte handelt, um zu bestimmen, welches Objekt in den Behälter gefüllt werden soll.

Geben Sie unter Größe die Größe jedes Artikels ein. Für die Größe kann bei einer Tabelle die Anzahl der Zeilen und Bytes verwendet werden und bei einem Job die Ausführungszeit in Minuten oder Sekunden angegeben werden. Die erforderliche Zeit sollte im Auftragsausführungsprotokoll überprüft werden, es wird jedoch empfohlen, den Durchschnittswert ohne die Höchst- und Mindestwerte der letzten 5 oder mehr erforderlichen Zeiten zu berechnen und zu verwenden.

Wenn Sie verschiedene Datensätze benötigen, können Sie das Blatt „Run“ kopieren und eingeben. Der Name des Blattes kann ein beliebiger Name sein, Es ist gut, es in Form von anzugeben, um es von anderen Blättern unterscheiden zu können. Weisen Sie beispielsweise „Run_Org“ zu, wie in der folgenden Abbildung gezeigt.

Bin Packing kann ausgeführt werden, indem mehrere Datensätze erstellt und unterschiedliche Daten oder unterschiedliche Optionen in jedem Datensatzblatt eingestellt werden. Das Blatt, auf dem das Ausführungsergebnis angezeigt wird, wird nicht für jeden Datensatz erstellt, sondern dauerhaft verwendet. Wenn Sie die Ergebnisse jedes Datensatzes behalten möchten, können Sie die Excel-Datei unter einem anderen Namen speichern und eine separate Datei erstellen.

3.1.2. Optionseinstellung

Die maximale Größe des Bins, die eine Beschränkung darstellt, und ob die Referenzspalte in absteigender Reihenfolge sortiert werden soll, werden im folgenden Format eingegeben.

Max. Bin-Größe ist die maximale Größe, die einem Bin zugewiesen werden kann. Mit anderen Worten, wenn mehrere Artikel in einen Behälter gefüllt werden, ist dies eine Einschränkung für die Summe der Artikelgrößen.

Die Standardspalte Artikelgröße ist eine Spalte, die angibt, welcher Wert verwendet werden soll, wenn mehrere Größenwerte in einem Lagerplatzartikel vorhanden sind. Angenommen, es ist beispielsweise so konfiguriert, dass mehrere Größen wie folgt in ein Element eingegeben werden können.

Spalten, die als Größenwerte verwendet werden können, sind C bis I. Geben Sie den Spaltennamen ein, um auszuwählen, welche Spalte als Eingabewert für die Größe verwendet werden soll. Um durch Erstellen eines Zufallswerts in Größe zu simulieren, kopieren Sie den von der Formel generierten Wert in die Spalte J (Rando Size), fügen Sie ihn als Wert in die Spalte I (Simulation) ein und führen Sie ihn dann aus, indem Sie die Referenzspalte als I festlegen . . Der Grund, warum Sie die J-Spalte nicht angeben sollten, liegt darin, dass in der J-Spalte eine Formel verwendet wird und bei jeder Berechnung ein neuer Wert erstellt wird, sodass nicht bekannt ist, welcher Wert als Eingabewert verwendet wurde.

Wenn die Option zum absteigenden Sortieren nach Artikelgröße ausgewählt (aktiviert) ist, wird zuerst die Artikelgröße in absteigender Reihenfolge sortiert und der Bin-Packing-Algorithmus angewendet.

3.1.3. Führen Sie Bin Packing aus

Wenn die Eingabedatenkonfiguration und die Optionseinstellungen abgeschlossen sind, klicken Sie zum Ausführen auf die Schaltfläche „Run BinPacking“.

Beim Ausführen kann ein Fehler auftreten, wenn ein Duplikat in „Bin Item Name“ vorhanden ist. Überprüfen und entfernen Sie das Duplikat vor dem Ausführen.

3.1.4. Überprüfen Sie das Ausführungsergebnis

Das Ausführungsergebnis besteht aus 5 Blättern. Die Gesamtzusammenfassung wird im Ergebnisübersichtsblatt überprüft, das die Ausführungsergebnisse jedes Algorithmus sammelt, und die detaillierten Ergebnisse jedes Algorithmus werden in jedem Blatt überprüft.

• Ergebniszusammenfassung: Ein Blatt, in dem die Ergebnisse der Ausführung jedes Algorithmus auf einen Blick zu sehen sind
• Next Fit: Das Ergebnisblatt der Ausführung des Next-Fit-Algorithmus
• First Fit: Das Ergebnisblatt der Ausführung des First-Fit-Algorithmus
• Worst Fit: Das Ergebnisblatt der Ausführung des Worst-Fit-Algorithmus
• Best Fit: Das Ergebnisblatt der Ausführung des Best-Fit-Algorithmus

Der Inhalt des Ergebnisübersichtsblatts ist wie folgt.

Referenzinformationen für die in den Optionen festgelegte maximale Bin-Größe werden oben angezeigt, und ein Diagramm mit den Ergebnissen der Ausführung jedes der vier Algorithmen wird unten angezeigt.

Die Zusammensetzung der auf dem Ergebnisblatt angezeigten Informationen nach Ausführung jedes Algorithmus ist wie folgt.

Artikel	Inhalt
① Ergebnisliste	Als Ergebnis der Ausführung des Behälterpackalgorithmus können Sie überprüfen, welche Artikel in welche Behälter gefüllt werden. Hier wird der Bin-Name mit der Regel „Bin_“ + Sequenznummer (5-stellig) im Prozess der Programmabarbeitung erstellt.
② Behälter insgesamt	Dies ist eine Pivot-Tabelle zur Berechnung der Summe der Artikelgrößen in Behältereinheiten. <④ Bin Sum Chart> wird mit dieser Pivot-Tabelle als Datenquelle erstellt.
③ Ausführungsinformationen	Es zeigt die für die Verarbeitung des Algorithmus benötigte Zeit, die Summe des verbleibenden Platzes in allen Behältern, den Gesamtplatz und die Informationen zur Platzineffizienz an. Die Raumineffizienz wird berechnet als (Bin-Gesamtrestraumsumme)/(Gesamtraumsumme).
④ Bin-Gesamtdiagramm	Dies ist eine Visualisierung von <② Bin Sum Pivot Table> als vertikales Balkendiagramm.

▼ Ausführungsergebnisse der nächsten Anpassung

▼ Ergebnisse des ersten Anpassungslaufs

▼ Worst-Fit-Ausführungsergebnisse

▼ Best-Fit-Laufergebnisse

3.1.5. VBA-Code-Konfiguration

Der Quellcode, der Bin Packing mit VBA implementiert, wird kurz beschrieben. Die Gesamtzusammensetzung des VBA-Projekts ist wie folgt.

• Sheet (Excel-Benutzeroberfläche) verwaltet die Liste der Eingabedaten und zeigt die Eingabe und Ausgabe des Algorithmusverarbeitungsergebnisses an.
• Ein Modul ist verantwortlich für die Handhabung und Steuerung des gesamten Verarbeitungsprozesses, das Erstellen von Instanzen von Klassen und gemeinsamen Funktionen.
• Die Klasse ist für Funktionen wie das Laden von Eingabedaten in den Speicher, das Implementieren von Algorithmen und das Ausgeben von Ergebnisdaten verantwortlich.

Der Zweck der detaillierten Punkte ist wie folgt.

• Blech
  • Jedes Blatt: Eingabedaten/Optionseinstellung, Ausführungsergebnisausgabe
• Modul
  • modControl: Verwaltet den gesamten Prozess der Objektivierung einer Klasse, des Ladens von Eingabedaten, der Implementierung jedes Bin-Packing-Algorithmus und der Ausgabe von Ergebnissen
  • modFactory: Instanziierung von Klassen verwalten
    • Die VBA-Klasse kann den Eingabeparameter des Konstruktors nicht angeben, daher ist sie so konfiguriert, dass sie ein Objekt mit dem Factory-Muster erstellt.
  • modUtil: Verwalten Sie Funktionen wie das Protokollieren und das Festlegen des Formats der erforderlichen Zeitzeichenfolge
    • Hier hinterlässt die Protokollierung keine Datei, sondern ist so konfiguriert, dass Protokollmeldungen im Debugger mit OutputDebugString unter den Windows-APIs überprüft werden können.
    • Debugger empfiehlt die Verwendung von DebugView
• Klasse
  • CBin: Klasse von 1 Behälter
    • Hauptmethoden: AddBinItem, IsAbleToAdd
  • CBinItem: Klasse von 1 Artikel, der in den Bin gelegt werden soll
    • Das heißt, eine Klasse, die einer Zeile von Eingabedaten entspricht.
    • Hauptmethode: CompareTo
  • CBinItemCollection: Eine Sammlungsklasse, die eine Liste mehrerer BinItems verwaltet.
    • Hauptmethoden: Add, Sort, GetString
  • CPacker: Eine Klasse, die eine Liste von Behältern als Sammlung verwaltet.
    • Implementieren Sie einen Algorithmus, der die Eingabedaten an einer geeigneten Stelle in der vorhandenen Bin-Liste füllt oder einen neuen Bin erstellt, um sie zu füllen
    • Hauptmethoden: DoPacking, Add, GetNewBin, GetBinNextFit, GetBinFirstBit, GetBinWorstFit, GetBinBestFit, PackToBin, DoOutput, GetRemainSizeSum
  • CTimer: Eine Klasse zum Messen der aufgewendeten Zeit
    • Verwenden von Windows-API QueryPerformanceCounter, QueryPerformanceFrequency
    • Hauptmethoden: StartCounter, TimeElasped

Um das OOP-Konzept richtig anzuwenden, ist es Standard, öffentliche Eigenschaften verfügbar zu machen, die aus Getter/Setter ohne öffentliche Member-Variablen in der Klasse bestehen. In diesem Tool werden öffentliche Eigenschaften jedoch nicht zur Vereinfachung der Implementierung verwendet. Member-Variablen, Funktionen und Prozeduren, auf die von außen zugegriffen werden kann, werden jedoch als öffentlich deklariert, und Objekte, auf die von außen zugegriffen werden soll, werden als privat deklariert.

Die Beziehung zwischen den im VBA-Quellcode definierten Klassen wird wie folgt kurz als UML-Klassendiagramm ausgedrückt.

Die Beziehung zwischen Klassen im obigen Klassendiagramm ist eine hat eine Beziehung. Das heißt, in der zwischen den beiden Klassen definierten Zusammensetzungsbeziehung ist die gefüllte Raute (♦) der Behälter.

 Von rechts nach links ist zu erkennen, dass die Unterschicht mit der Oberschicht verbunden ist. Ein Eingabedatum wird von der CBinItem-Klasse verwaltet, und die CBinItemCollection-Klasse verwaltet die gesamten Eingabedaten als Sammlung von CBinItems. Die CBin-Klasse verwaltet einzelne Behälterobjekte und verwaltet die Liste der in jeden Behälter gefüllten Elemente als ein Objekt der CBinItemCollection-Klasse. Die CPacker-Klasse implementiert den Algorithmus und verwaltet das gesamte Ergebnis-Bin-Objekt als Sammlung der CBin-Klasse. Jede Klasse hat eine Kompositionsbeziehung, sodass beim Entfernen des Containerobjekts alle Unterobjekte entfernt werden. Die CTimer-Klasse wird in der CPacker-Klasse verwendet, um die Ausführungszeit des Algorithmus zu messen.

Hier wird die CBinItemCollection-Klasse verwendet, um die gesamten Eingabedaten und auch die Liste der in jeden Behälter gefüllten Elemente zu verwalten. Angenommen, 100 Artikel sind beispielsweise mit 10 Artikeln in 10 Behältern gefüllt, ist das Objekt, das alle 100 Artikel verwaltet, ebenfalls vom Klassentyp CBinItemCollection, und das Objekt, das 10 Artikel verwaltet, die in jeden Behälter gefüllt sind, ist ebenfalls vom Klassentyp CBinItemCollection. sein.

Den Quellcode jeder Klasse finden Sie im Anhang. Der Pseudocode von modControl, einem Modul, das den gesamten Prozess des Ladens von Eingabedaten, der Ausführung des Algorithmus und der Ausgabe von Ergebnisdaten steuert, lautet wie folgt.

Public Sub RunBinPacking()
    입력자료를 읽어들여 CBinItemCollection type의 oInputItemCol 변수에 적재
    입력자료의 정렬 실행을 선택했으면 oInputItemCol 내림차순 정렬
    각 알고리즘의 실행결과를 담을 변수 선언
    각 변수에 최대 Bin 크기와 PackingType을 설정하여 개체 생성
    각 변수에 입력자료 채우기
    결과출력
    각 변수 메모리에서 삭제하여 정리
End Sub

---

Im nächsten Artikel sehen wir uns den mit dem Python Bin Packing-Paket implementierten Quellcode und das Ausführungsergebnis an.

---

<< Liste verwandter Artikel >>

• Optimierung der Arbeitsverteilung durch eindimensionalen Bin-Packing-Algorithmus_1.Überblick
• Optimierung der Arbeitsverteilung durch eindimensionalen Bin-Packing-Algorithmus_2.Algorithmus (1)
• Optimierung der Arbeitsverteilung mit eindimensionalem Bin-Packing-Algorithmus_2.Algorithmus(2)
• Optimierung der Arbeitsverteilung durch eindimensionalen Bin-Packing-Algorithmus_3.Implementierung (1)
• Optimierung der Arbeitsverteilung durch eindimensionalen Bin-Packing-Algorithmus_3.Implementierung (2)
• Optimierung der Arbeitsverteilung durch eindimensionalen Bin-Packing-Algorithmus_4.Attachment
• Letzte Änderungen am eindimensionalen Bin-Packing-Tool (Stand: 21. März 2021)
• Tool zur Optimierung der Arbeitsverteilung mit eindimensionalem Bin-Packing-Algorithmus Vollständiger Inhalt, Download