Optimale Reihenfolgen

ISBN-13: 9783642877285 / Niemiecki / Miękka / 2012 / 228 str.

H. M. Ller-Merbach

Opis

Reihenfolgeprobleme stehen im Fachgebiet des Operations Research seit einiger Zeit im Mittelpunkt des Interesses. Nachdem bis vor wenigen Jahren fur viele Reihenfolgeprobleme noch keine brauchbaren Losungs verfahren bekannt waren, wurden seit etwa 1960 verschiedene Verfahren entwickelt, die kleine und mittelgrosse Probleme mit wirtschaftlich ver tretbarem Aufwand exakt und grossere Probleme mit hinreichender Genauigkeit zu losen gestatteten. In der vorliegenden Arbeit sollen diese Verfahren diskutiert und vor allem uber die mit ihnen an zahlreichen Beispielen gewonnenen Erfahrungen berichtet werden. Bei der Beschrei bung der Verfahren stehen algorithmische Gesichtspunkte und Fragen der Eignung zur Programmierung fur elektronische Rechenautomaten im Vordergrund. Einige neuere Verfahren wurden auf Rechenautomaten getestet. Die dabei erzielten Ergebnisse werden ausfuhrlich analysiert. Bei der Darstellung habe ich mich von der Maxime leiten lassen, ein schnell lesbares Buch hervorzubringen. Dem Leser, gleichgultig ob Theoretiker oder Praktiker, mochte ich damit die Gelegenheit bieten, sich mit einem Minimum an Zeit in die wesentlichen Strukturen der Reihenfolgeprobleme und deren Losungsverfahren einzuarbeiten. Zu diesem Zweck habe ich bei der Beschreibung der Losungsverfahren jeweils nach einfuhrenden Erorterungen Beispiele zur Demonstration herangezogen und erst abschliessend die allgemeingultigen Formulierun gen der Verfahren gegeben. Auf mathematischen Formalismus habe ich weitgehend verzichtet, soweit er nicht zum Verstandnis der Probleme und Verfahren erforderlich oder zum Lesen der wichtigsten Fachliteratur unumganglich war."

Spis treści

1 Reihenfolgeprobleme.- 2 Graphentheoretische Grundlagen.- 2.1. Grundbegriffe.- 2.2. Einige Eigenschaften von Graphen.- 3 Methoden und Modelle der linearen Planungsrechnung.- 3.1. Allgemeines.- 3.2. Das Zuordnungsproblem.- 3.3. Das Transportproblem.- 3.4. Der allgemeine Ansatz der linearen Planungsrechnung.- 3.5. Die ganzzahlige Planungsrechnung.- 4 Die wichtigsten Methoden zur Berechnung optimaler Reihenfolgen.- 4.1. Allgemeines.- 4.2. Die Vollenumeration.- 4.3. Entscheidungsbaumverfahren.- 4.3.1. Die dynamische Planungsrechnung.- 4.3.2. Das Verfahren des Branching and Bounding.- 4.3.3. Die begrenzte Enumeration.- 4.3.4. Vergleich der Entscheidungsbaumverfahren.- 4.4. Heuristische Verfahren.- 5 Optimale Wege in Netzen.- 5.1. Allgemeines.- 5.2. Optimale Wege zwischen zwei Knoten in Netzen ohne wesentliche Kreise und Schleifen.- 5.2.1. Die Berechnung kürzester Wege mit dem Dijkstra-Algorithmus.- 5.2.2. Die Berechnung längster Wege.- 5.2.3. Die Lösung mit linearer Planungsrechnung.- 5.3. Optimale Wege zwischen allen Knoten in Netzen ohne wesentliche Kreise und Schleifen.- 5.4. Optimale Wege zwischen zwei Knoten in Netzen mit wesentlichen Schleifen.- 5.4.1. Längste Wege mit Knotenrestriktion.- 5.4.2. Längste Wege mit Kantenrestriktion.- 5.5. Anwendungen.- 5.5.1. Die Bestimmung kritischer Wege in Terminplanungsnetzen.- 5.5.2. Risikominimale Wege in Netzen.- 5.5.3. Optimale Devisenarbitrage.- 6 Das Traveling Salesman Problem.- 6.1. Allgemeines.- 6.2. Geschichte der Methoden zur Lösung des Traveling Salesman Problems...- 6.3. Ein Demonstrationsbeispiel.- 6.4. Lösungsansätze mit ganzzahliger linearer Planungsrechnung.- 6.4.1. Die Formulierung des Traveling Salesman Problems als Problem der ganzzahligen linearen Planungsrechnung.- 6.4.2. Die Verwandtschaft zum Zuordnungsproblem der linearen Planungsrechnung.- 6.5. Die Lösung des Traveling Salesman Problems durch vollständige Enumeration.- 6.6. Heuristische Verfahren zur Lösung des Traveling Salesman Problems.- 6.6.1. Eröffnungsverfahren.- 6.6.2. Suboptimierende Iterationsverfahren.- 6.7. Entscheidungsbaumverfahren zur Lösung des Traveling Salesman Problems.- 6.7.1. Die dynamische Planungsrechnung.- 6.7.2. Das Verfahren des Branching and Bounding.- 6.7.3. Die begrenzte Enumeration, erste Version.- 6.7.4. Die begrenzte Enumeration, zweite Version.- 6.7.5. Die begrenzte Enumeration, dritte Version.- 6.7.6. Die begrenzte Enumeration, vierte Version.- 6.8. Numerische Erfahrungen bei der Lösung von Traveling Salesman Problemen.- 6.8.1. Untersuchte Probleme.- 6.8.2. Erfahrungen mit heuristischen Verfahren.- 6.8.3. Erfahrungen mit der begrenzten Enumeration.- 6.8.4. Empfehlungen für die Wahl eines Verfahrens.- 6.9. Rundreiseprobleme besonderer Struktur.- 7 Das Chinese Postman’s Problem.- 7.1. Allgemeines.- 7.2. Das Königsberger Brückenproblem.- 7.3. Das Chinese Postman’s Problem in ungerichteten Graphen.- 7.3.1. Das Verfahren der wesentlichen Kreise von Kwan.- 7.3.2. Der Lösungsansatz der ganzzahligen linearen Planungsrechnung...- 7.3.3. Die begrenzte Enumeration.- 7.4. Das Chinese Postman’s Problem in gerichteten Graphen.- 7.5. Varianten des Chinese Postman’s Problems.- 8 Raumzuordnungsprobleme.- 8.1. Allgemeines.- 8.2. Die Formulierung als quadratisches Zuordnungsproblem.- 8.3. Heuristische Verfahren.- 8.3.1. Eröffnungsverfahren.- 8.3.2. Suboptimierende Iterationsverfahren.- 8.4. Raumzuordnungsprobleme in der Praxis und verwandte Probleme.- 8.4.1. Die Triangulierung von Input-Output-Matrizen.- 8.4.2. Die Verwandtschaft zwischen dem Traveling Salesman Problem und Raumzuordnungsproblemen.- 9 Probleme der Maschinenbelegungsplanung.- 9.1. Allgemeines.- 9.2. Die Maschinenbelegungsplanung bei der Organisationsform der „Werkstattfertigung“.- 9.2.1. Geschichtlicher Überblick über die Lösungsansätze.- 9.2.2. Arbeitsverteilung mit Prioritätsregeln.- 9.2.3. Optimierungskriterien und Gutenbergs „Ablaufplanungsdilemma“..- 9.2.4. Das klassische Job Shop Scheduling Problem und seine Lösung mit der begrenzten Enumeration.- 9.2.5. Numerische Erfahrungen.- 9.2.6. Die Kombination von Prioritätsregeln und Enumerationsverfahren..- 9.3. Die Betriebsmitteleinsatzplanung bei netzplanmäßig zerlegten Projekten...- 9.3.1. Ein Beispiel.- 9.3.2. Die Prioritätsregelverfahren.- 9.3.3. Das Verfahren der Variationen-Enumeration.- 9.3.4. Die begrenzte Enumeration.- 9.3.5. Numerische Erfahrungen.- 10 Optimale Reihenfolge innerhalb mathematischer Algorithmen.- 10.1. Allgemeines.- 10.2. Die Reihenfolge der Pivot-Elemente bei der Inversion von Matrizen.- 10.3. Die Wahl der Pivot-Elemente bei der Simplex-Methode der linearen Planungsrechnung.- 10.4. Die Multiplikation mehrerer Matrizen.- Namenverzeichnis.