No label defined (Q3838010)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1183280
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 1183280

      Statements

      0 references
      3 August 1998
      0 references
      packing patterns
      0 references
      interval graphs
      0 references
      asymptotic worst case performance
      0 references
      orthogonal knapsack problem
      0 references
      Im zweiten Kapitel haben wir \(d\)-dimensionale Packmuster mit Hilfe von Intervallgraphen charakterisiert und so den Begriff der Packmusterklasse eingeführt. Die daraus im vierten Kapitel abgeleitete enumerative Methode für das orthogonale Entscheidungsproblem besitzt zwei Vorteile: Erstens erreichen wir eine gewisse Symmetriereduktion, da wir statt Packmustern ganze Packmusterklassen enumerieren. Zweitens beschleunigen die starken Struktureigenschaften der Intervallgraphen den Suchprozeß, indem sie effektive Kriterien zum Abschneiden von Ästen des Suchbaums liefern. Wir konnten zudem das Überprüfen dieser Kriterien durch effiziente Algorithmen auf perfekten Graphen realisieren. Im dritten Kapitel haben wir mit den Volumenbilanzen bezüglich konservativer Skalierungen eine allgemeine Methode gefunden, Relaxierungen und Schranken für orthogonale Packungsprobleme zu konstruieren. Eine einfache Herleitung mehrdimensionaler Schranken ermöglicht insbesondere unsere Erkenntnis, daß man eine konservative Skalierung erhält, wenn man auf jede Komponente der Größenfunktion eine beliebige dual zulässige Funktion anwendet. Wir haben drei Klassen dual zulässiger Funktionen angegeben, aus denen sich so in linearer Zeit berechenbare konservative Skalierungen konstruieren lassen. In diesem Rahmen haben wir für bekannte Schranken vereinfachte und systematisierte Darstellungen gefunden, die zudem preiswerte Verbesserungsmöglichkeiten offenbarten. Weiterhin haben wir gezeigt, wie man dual zulässige Funktionen zur heuristischen Verbesserung beliebiger unterer Schranken für das eindimsionale BPP benutzen kann. Mit dieser Technik konnten wir sowohl die asymptotische Worst-Case-Performance als auch die ``empirische'' Performance der bisher besten ``billigen'' unteren Schranke für das BPP erheblich steigern. Im fünften Kapitel haben wir die in den vorigen Kapiteln entwickelten Methoden als Bausteine für neue exakte Algorithmen für \(d\)-dimensionale orthogonale Packungsprobleme verwendet. Das Verfahren für das orthogonale Knapsackproblem wurde implementiert und auf zwei- und dreidimensionalen Instanzen getestet. Unsere numerischen Resultate belegen, daß das neue Verfahren einen deutlichen Fortschritt darstellt: Für jede öffentlich zugängliche OKP-2-Testinstanz konnte in weniger als 0.4 Sekunden eine Optimallösung berechnet werden. Die maximale Anzahl der Boxen einer exakt gelösten OKP-2-Instanz wurde von 22 auf 80 gesteigert, die maximale Anzahl der Boxtypen von 15 auf 40. Diese Größen geben keine singulären Extremfälle wieder, sondern beziehen sich jeweils auf ganze Klassen nichttrivialer Testinstanzen. Anders als bei den bisher existierenden Verfahren stellt die Containergröße keinen limitierenden Faktor dar. In dieser Arbeit werden nach unserem Wissen zum ersten Mal experimentelle Resultate für ein OKP-3-Verfahren veröffentlicht. Bei einem geringen Anteil kleiner Boxen konnten hier ebenso große Instanzen bearbeitet werden wie beim OKP-2. Doch selbst bei einem 60\%-Anteil kleiner Boxen konnten immerhin noch OKP-3-Instanzen mit 20 Boxen zuverläßig exakt gelöst werden. Die in dieser Arbeit erzielten Ergebnisse ermutigen dazu, exakte Verfahren auf geeignete Praxisprobleme anzuwenden. Die hier beschriebenen Algorithmen bieten dafür einen guten Ausgangspunkt. Aussichtsreich erscheint etwa ein hybrider Ansatz, bei dem zunächst die sperrigen Objekte mit exakten Verfahren gepackt, und später die kleinen Objekte mit einer Heuristik in die Lücken geschoben werden. Dazu würde sich die Push-Straight-Insert-Heuristik eignen. Auch könnten gewisse praktische Nebenbedingungen, wie z.B. die vorgeschriebene räumliche Trennung verschiedener Gefahrgutbehälter innerhalb eines Frachtcontainers direkt in den Ansatz integriert werden, indem mit ihnen ein Teil der Packmusterklasse a priori bestimmt wird. Die Erzeugung von Schranken mit Hilfe konservativer Skalierungen ist als eine allgemeine Technik sicherlich auch außerhalb des Kontexts dieser Arbeit verwertbar. Eine naheliegende und praktisch relevante Anwendung wäre zum Beispiel die Integration dieser Schranken in Guillotinenschnittverfahren.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references