Allgemeiner Branch & Bound Algorithmus

So kommen Sie hierher:

Einstellungen:

Anzahl der Lösungen:

Der Algorithmus kann alle optimalen Pläne berechnen. Wenn Sie dies nicht wünschen oder Zeit und Speicher sparen möchten, geben Sie hier eine obere Schranke für die Anzahl der auszugebenden Pläne an, gewöhnlich 1.

Untere Schranke:

Geben Sie bekannte untere Schranken hier an. LisaBB behandelt dann jeden Plan, dessen Zielfunktionswert diesen Wert nicht überschreitet, als optimal. Falls Sie hier einen zu hohen Wert eingeben, erhalten Sie möglicherweise ein falsches Ergebenis.

Obere Schranke:

Wenn Sie bereits einen Plan kennen, geben Sie dessen Zielfunktionswert hier an. LisaBB verwirft dann alle Teilpläne mit größerem Zielfunktionswert.

Einfügereihenfolge:

Wählen Sie die Reihenfolge, in der LisaBB die Operationen berücksichtigt. Möglich sind:

LPT

geordnet nach monoton nichtsteigenden Bearbeitungszeiten

RANDOM

in zufälliger Reihenfolge

Art der unteren Schranke:

Bestimmen Sie, mit welcher Prozedur LisaBB untere Schranken für den Zielfunktionswert berechnet.

NORMAL

Zielfunktionswert des Teilplans

EXTENDED

noch nicht implementiert

Wenn LisaBB zu langsam ist:

• LisaBB ist eine Universalsolver und deshalb sehr aufwendig. Benutzen Sie einen problemspezifischen Algorithmus sofern möglich.
• Brechen Sie den Algorithmus während der Laufzeit ab, Sie erhalten eine Näherungslösung.
• Variieren Sie Art der Schranke und Einfügereihenfolge.
• Suchen Sie den optimalen Zielfunktionswert mit der Einstellung "Anzahl der Lösungen = 1" und berechnen Sie weitere Optimallösungen erst in einem zweiten Lauf.
• Wenn eine exakte Lösung nicht möglich ist, stellen Sie Fragen der Art: gibt es eine Lösung mit Zielfunktionswert im Intervall [x,y], indem Sie x und y als untere bzw. obere Schranke vorgeben. Vorsicht: eventuell berechnet LisaBB dann gar keinen Plan.