Branch and Bound

die t's sind ja einfach zu berechnen, bei den unteren schranken habe ich aber auch meine probleme!

Ich habe hier noch ein Problem bezüglich der Logik. In Bezug au die EA Nr. 1 vom WS 13/14 stellen sich mir folgende Fragen:

Bei Aufagbe 1 berechne ich doch die niedrigste Durchlaufzeit und komme bei X2 auf die kleinste Zahl 43. Aufgrund dessen wird S berechnet. Auf die Werte von S und X2X1 etc. komme ich zwar, aber die Logik dahinter erschließt sich mir nicht ganz. Bei S1 fange ich bei X1 A1. Den Wert (13) addiere ich mit A1 X2 und A1 X3. Dazu kommen dann A2 X2 und A3 X2. Warum werden diese Zahlen genommen und nicht A2 X1 und A3 X1? Bei der Berechnung von X2 X1 verhält es sich ähnlich.

Kann mir das vielleicht jemand Schritt für Schritt noch einmal erläutert.

Skript S. 47 f. das Beispiel: wie komme ich denn auf die T beim zweiten Knoten
z. B. (X1, X2): t1=11+3= 14
t2= t1 + min (4,1) = 15; t3= ??
bei den Schranken wollen wir erst gar nicht anfangen 😕

Abgehterderpeter! schrieb:

Skript S. 47 f. das Beispiel: wie komme ich denn auf die T beim zweiten Knoten
z. B. (X1, X2): t1=11+3= 14
t2= t1 + min (4,1) = 15; t3= ??
bei den Schranken wollen wir erst gar nicht anfangen 😕

Zum Vergrößern anklicken....

Hi Abgehtderpeter 🙂 bzgl. dem Beispiel auf Seite 47:
Ich zeichne Diagramme, um t1, t2 und t3 auszurechnen. So siehst du nämlich auf einen Blick wie lange die Bearbeitungszeiten sind. Ohne diese Balken, kann ich es nicht und versuche es auch gar nicht hehe zu kompliziert. Das Balkenzeichnen ist übrigens erlaubt.

Also bei X1,X2: Heißt, dass zuerst X1 produziert wird, danach dann X2. Und dies auf allen drei Maschinen. Siehe mein angehängtes Bild (Balkenzeichnung), um die t1, t2 und t3 zu "berechnen".
Nimmst du dann jeweils die Summe, bekommst du für t1=14, für t2=15 und t3 = 22 raus.

Das kannst du dann immer so machen, sobald 2 oder mehrere Xen produziert werden in einer bestimmten Reihenfolge.

Zu den unteren Schranken:
s1= t1 + (alle Bearbeitungszeiten, die übrig bleiben, außer X1 und X2, also die von X3 und X4) + (Die kleinste Summe aus der Reihe 2 (Maschine 2) und Reihe 3 (Maschine 3 > dabei dürfen die Spalten, die schon verwendet wurden (hier X1 und X2) nicht miteinbezogen werden)
s1= 14 + (7+10) + 14 = 45

s2=t2 + (alle Bearbeitungszeiten, die übrig bleiben, außer X1 und X2, also die von X3 und X4) + (Der kleinste Wert der 3. Reihe (Maschine 3) > dabei dürfen die Spalten, die schon verwendet wurden (hier X1 und X2) nicht miteinbezogen werden)
s2= 15 + (9+12) + 2 = 38

s3=t3+ (alle Bearbeitungszeiten, die übrig bleiben, außer X1 und X2, also die von X3 und X4)
s3=22 + (13+2)

Ich hoffe so verstehst du das

Danke. Bei mir lag der Gedankenfehler bei dem Minimum, welches ich nie berücksichtigt hatte. Daher konnte ich natrülich nie auf die Werte kommen.