Branch and Bound - Übungsaufgabe im Skript

du kannst nicht 4+2 rechnen...es ist zwar ein minimum gemeint, aber nicht so!^^
das minimum ergibt sich immer aus den beiden werten eines auftrags, es gilt also:
11+(3+7+10)+min(4+10,9+13,12+2)
11+20+min(14,22,14)
11+20+14=45

denk es dir so: wenn wir nur auftrag x2 betrachten:
t1 sagt aus, nach wieviel zeiteinheiten maschine 1 frühestens wieder frei ist...nach 11
t2 sagt aus, nach wieviel zeiteinheiten maschine 2 frühestens wieder frei ist...nach 11+1=12
t3 sagt aus, nach wieviel zeiteinheiten maschine 3 frühestens wieder frei ist...nach 11+1+5=17

für s1 gilt jetzt: maschine 1 ist mindestens 11+(3+7+10)=31 zeiteinheiten beschäftigt...
wenn mit auftrag x2 begonnen wird, ist der aber schon nach 11+1+5=17 zeiteinheiten fertig...d.h. der ist schon fertig, und maschine 1 läuft immer noch wegen den anderen aufträgen...
nach den 31 zeiteinheiten ist maschine 1 fertig
maschine 2 kann (im optimalsten fall, den wir aber noch nicht kennen) frühestens nach 31 zeiteinheiten anfangen seinen letzten auftrag zu bearbeiten...da auftrag x2 schon nach 11 Zeiteinheiten auf maschine 1 fertig ist, ist er auch nach 11+1=12 schon auf maschine 2 fertig...er ist also nicht nach 31 zeiteinheiten auf maschine 2 dran...es kann nur x1 x3 oder x4 dran sein
ist x1 als nächster dran, dauert es noch 4+10=14 einheiten zu den 31 dazu...14+31=45
ist x3 als nächster dran, dauert es noch 9+13=22, also 22+31=53
bei x4 dann 12+2=14, also 31+14=45 zeiteinheiten
s1 dauert also mindestens 45

aber! stell dir vor, x2 braucht auf maschine 2 länger, also z.B. 30 zeiteinheiten...dann kann der nächste auftrag auf a2 erst nach 11+30=41 zeiteinheiten beginnen...das muss in den klausuraufgaben berücksichtigt werden

für s2 gilt: x2 braucht 11+1=12 zeiteinheiten...die andern brauchen nochmal 4+9+12=25 bis maschine 2 fertig ist...maschine 3 ist frühestens nach 2 fertig...also 12+25+2=39

für s3 gilt: auftrag 2 ist nach 11+1+5=17 fertig...maschine 3 ist dann nach 17+(10+13+2)=42 fertig

die schranken sind dann (45,39,42)

also alles ziemlich kompliziert und im beispiel auch nicht erklärt 🙁 ich weiss auch nicht, ob meine erklärung 100pro stimmt

EMF, ich hab Deinen Beitrag noch nicht ganz nachvollzogen, bin grad noch mit was anderem beschaeftigt. Wollte aber trotzdem kurz danke sagen, dass Du das Beispiel so ausfuehrlich dargestellt hast. Leider kommt hier im Unterforum noch immer nicht so recht Diskussionsstimmung auf; deshalb find ich's total klasse, dass mal jemand 'nen Anfang macht.

Uff. Also jetzt hab ich mir heut nochmal dieses B&B reingezogen. Aber ohne Gantt-Diagramme komm ich echt nicht auf die t-Werte. Hat da jemand noch mal 'nen Tipp, wie man das schneller/simpler hinkriegt? Zwar stimmen meine Werte natuerlich alle, aber dieses Rumzeichnerei schaff ich in der Klausur ja nie und nimmer 🙁
Noch eine Frage: Hat jemand die Uebungsaufgabe 7 gerechnet? In der Loesung waehlen die beim 3. Schritt ganz entspannt die Auftragsfolge x3, x1, x4 aus. Die Auftragsfolge x3, x1, x5 hat ja aber den gleichen Schrankenwert. Woher weiss ich, was ich da waehlen darf? Muss ich dann die restlichen unteren Schranken betrachten? Und wenn dort eine niedriger ist, nehm ich dann diese Auftragsfolge her?

Merci! Caro

moechte meine Frage nochmal nach oben schubsen: Weiss jemand, wie die Auftragsfolge gewaehlt werden muss, wenn auf der vorhergehenden Stufe mehrere Knoten den gleichen (niedrigsten) Wert annehmen?

Merci! Caro

Ein Tipp: Kauft euch das Buch von Fandel! Alle bisherigen Klausuraufgaben, bei denen was auszurechnen ist, stammen aus dem Buch (teilweise mit geringen Abwandlungen). Die Lösungswege sind ausführlich erklärt.

Ich habe mir bisher sehr wenig Zusatzliteratur besorgt, aber in diesem Fall ist das Buch sein Geld wert (hoffe ich, habe die Klausur ja auch noch vor mir 🙂

Ich hätte allein mit den Unterlagen der Fernuni nicht durchgeblickt...

Caro,

die Frage habe ich mir heute auch gestellt.

Wenn ich mir die Lösung der ÜA 7 im Skript anschaue, habe ich ja für

x3, x1, x5 S= 26 (s1, s2, s3 = 26, 26, 25)
x3, x1, x4 S= 26 (s1, s1, s3 = 26, 25, 25) -->hier sind die einzelnen s-Werte kleiner, deshalb nimmt man vermutlich diesen Knoten.

Ist zwar jetzt nicht die vorherige Stufe, aber das Problem mit dem gleichen Wert tritt hier auch auf.

Falls ich total falsch liege, bitte schreien

kasmodiah,

danke fuer die Antwort!

Ich dachte zuerst auch, dass es was mit den unteren Schranken zu tun haben muesse. Aber wenn ich mir beispielsweise die Klausur Maerz2013, A2 ansehe - da trifft das nicht zu. Die Auftragsfolgen AB und AC haben beide den gleichen Schrankenwert (27), AC hat die niedrigeren s1, s2, s3-Werte .. und trotzdem wird fuer die optimale Auftragsfolge bei AB weitergerechnet (und ergibt dann zum Schluss die optimale Folge ABC).

Offen gestanden, ich hab das mit dem B&B noch nicht so ganz durchstiegen, und ich hab momentan auch nicht die Zeit, mich weiter zu vertiefen. Dazu hab ich noch zu viele andere Sachen, die ich lernen muss. Ich halte das fuer mich jetzt derzeit so, dass ich bei gleichen Schrankenwerten einfach die ERSTE Auftragsfolge nehme, die den niedrigsten Schrankenwert aufweist. Leider hab ich echt keine Erklaerung parat, aber so hab ich das fuer mich jetzt einfach mal beschlossen.

Wenn ich noch irgendeine bessere Antwort hab oder allgemein neue Erkenntnisse, meld ich mich hier im Thread wieder.

Ciao einstweilen, Caro

geloescht, Doppelpost

Ha, die Aufgabe wollte ich heute durchrechnen, bin ich noch nicht dazu gekommen. Ich schaue sie mir morgen mal an und wälze mich auch nochmal durch das entsprechende Kapitel im Buch.

Wir kommen schon noch dahinter

Okay, ich bin mal deiner Idee mit der ersten Auftragsfolge nachgegangen. Macht Sinn...so bin ich zumindest immer auf die Ergebnisse gekommen 😉

Im Buch habe ich nichts gefunden bzw. es wohl mehrfach überlesen, wenn es da steht.

Danke fuer die Rueckmeldung. Ich hab mir ueberlegt, ob vielleicht genau das mit diesem Schritt 4 (KE1, S. 54) gemeint ist: "Das Verfahren endet, wenn ein Endknoten ..erreicht wird, dessen Bound NICHT GROESSER IST ALS DER NIEDRIGSTE BOUND ... ALLER UEBRIG BLEIBENDEN KNOTEN ..."

Auf gut deutsch: Der erste Knoten, der den niedrigsten Bound hat, genau den nehm ich her und rechne mit dem weiter.

Vermutlich sollte ich, so kurz vor der Pruefung, auch erklaeren koennen, warum das so ist. 😳😕 Aber irgendwie rechne ich ohnehin nicht damit, dass Branch and Bound drankommt. Was denkt Ihr?

Kam ja letztes Mal dran, vielleicht werden wir dieses Semester verschont

Ich hoffe auch auf Johnson 🙂

Ich hab die Aufgabe zu Branch and Bound aus der letzten Klausur gerechnet und komme da für A1 A2 und A3 auf die gleichen S-Werte nämlich 52.
Ich habe dann alle möglichen weiteren Verzweigungen berechnet, also A1A2, A1A3, A2A1,A2A3, A3A1 und A3A2.
Bei mir ist dann A1A2 und A1A3 wieder minimal mit 52.
Dann habe ich wieder beide weiter verzeigt also A1A2A3 und A1A3A2.
Da habe ich wieder 52 raus.

Als "Ergebnis" habe ich dann, dass beide Auftragsfolgen optimal sind.

Wenn ich aber doch nicht alle weiterverzweige weiß ich doch gar nicht, ob vielleicht eine der anderen beiden (also angefangen mit A2 oder A3) "besser" ist.
Aber ich kann doch auch nicht in 20 Minuten (soviel Punkte gabs nämlich nur für die Aufgabe) 11 Partielle Auftragsfolgen ausrechnen!
Ich hab grob geschätzt dafür 45 Minuten gebraucht, obwohl ich die t- und s-Werte inzwischen schon ohne extra Nebenrechnung berechnen kann....

Vanessa, ich hab bei den Bounds 27. Meine Reihenfolge lautet ABC (das ist dann vermutlich A1A2A3). Die t-Werte krieg ich ohne Gantt-Charts ueberhaupt nicht gebacken; die s-Werte sind dann kein Problem mehr, aber die Zeichnerei der Charts haelt natuerlich ewig auf. Naja, wir werden sehen. Bin total platt und mach heute ueberhaupt nichts mehr. Und dann muss ich erst noch fuer 'ne andere Klausur lernen. Mit PP fang ich dann erst wieder ab Mittwoch an.

Gutes Lernen noch!

Ja, ich meine natürlich A B C.

Die t-Werte sind doch ganz einfach.
Für Auftrag A z.B. rechnest du:
t1=8
t2=8+13
t3=8+13+10

Bei der Auftragsfolge AB z.B.:
t1=8+10
t2=max. aus (8+10+9=27) oder (8+13+9=30) also 30
--> Du schaust, wie komm ich von A-M1 nach B-M2.
t3=max. aus (8+10+9+9) oder (8+13+9+9) oder (8+13+10+9)
--> hier wieder schauen wie man von A-M1 nach B-M3 kommt

Wenn du z.b. für die Auftragsfolge CB die t-Werte suchts rechnest du:

t1=11+10
t2=max. aus (11+10+9) oder (11+10+9)
t3=max aus (11+10+9+9) oder (11+10+9+9) oder (11+10+12+9)
--> Du musst also in der Tabelle schauen, wie man von C-M1 nach B-M3 kommt und dafür gibts die 3 Möglichkeiten
Möglichkeit 1: von 11 links zur 10 runter zur 9 runter zur 9
Möglichkeit 2: von 11 runter zur 10 links zur 9 runter zur 9
Möglichkeit 3: von 11 runter zur 10 runter zur 12 links zur 9

Ich hoffe das stimmt so, aber ich habe alle Aufgaben im Buch gerechnet und bin mit dem Verfahren immer auf die richtigen Ergebnisse gekommen 🙂 .

Wie kommst du auf 27?
Stimmen vielleicht deine t-Werte nicht?

Achso. Du redest von der Klausur Maerz2012, ich dachte Maerz2013. Ja, da hab ich auch 52 als Bound. Die t-Werte bei einem, vielleicht auch zwei Auftraegen geht grad noch so. Aber wenn drei Auftraege bearbeitet werden, brauch ich den Gantt. Da blick ich einfach nicht mehr durch. Aber ich seh mir das dieser Tage nochmal an, wie Du das oben beschrieben hast. Waer schon super, wenn ich mir das aufwendige Zeichnen sparen koennte.

Ups, ich meinte März 2012 ja, ich bin langsam total verwirrt 😳

Für 3 Aufträge ändert sich am Schema auch nichts.

Holen wir als Beispiel die Folge CBA

t1: 11+10+8

t2: max. aus (11+10+8+13) oder (11+10+9+13)
--> Wieder gucken wie man von C-M1 nach A-M2 kommt

t3: max. aus (11+10+12+9+10) oder (11+10+8+13+10) oder (11+10+9+9+10) oder (11+10+9+13+10) oder (11+10+9+9+10)
--> alle möglichen Wege von C-M1 nach A-M3

Das geht wirklich relativ schnell und ohne Zeichnen.
Ich hab aber gestern auch ein paar Stunden gebraucht bis ichs kapiert hab 🙁

Werd mir jetzt mal noch Alternativkalkulation und arbeitsgangweise Kalkulation anschauen...

Ogott, so einfach ist das !? Ich krieg die Krise. Was ich mir hier einen abgekaspert hab mit Diagrammen zeichnen ... unfassbar 😡 Tja, man merkt wohl, dass ich derzeit nur stumpf Sachen auswendig lern und nicht richtig kapier, sonst waer ich wohl selbst drauf gekommen. Aber ok, dann hab ich jetzt zwei Wege, wie ich das berechnen kann, und wenn ich in der Pruefung sehr viel Zeit hab (was gut passieren kann - wie kann ich mein bisschen Wissen sinnvoll auf zwei Stunden aufteilen? 😀 ), rechne ich das so, wie Du eben vorgemacht hast und pruefe mit den Gantts nach 🙂

Vielen, vielen Dank fuer die Erklaerung; hat mir gerade etliche Kronleuchter aufgesteckt!

Ich HOFFE, dass das auch so richtig ist. Aber wie gesagt bin ich damit immer auf die Lösung gekommen.
Warum und wieso das so gemacht wird weiß ich aber auch nicht 😱ops

Ne, das muss schon stimmen so, wie Du das sagst; da bin ich mir sicher. Ich mach bei der Zeichnerei ja nichts anderes. Man sieht sich einfach an, welche Maschinen in welcher Reihenfolge die Auftraege abarbeiten, und welche Auftraege demzufolge wie lange warten muessen. Der Auftrag, der schlussendlich dran ist, hat die laengste Durchlaufzeit. Und das ist dann unser t.

Bin immer noch hocherfreut ueber diesen simplen Rechenweg - vielen Dank dafuer!