Verfahren von Ignall&Schrage / Branch&Bound

Peter,

ich hab jetzt auch mal ein bisserl geknobelt ... ganz bis zum Schluß gekommen bin ich nicht, aber vielleicht schaffen wir es ja gemeinsam ... das ganze baut m.E. auf dem kritischen Pfad auf. Sprich - für Dein Beispiel von X1, X2 oben ...
t1 = spätester Fertigstellungszeitpunkt auf A1, was sich aus den Bearbeitungszeiten auf der Maschine ergibt
t2= spätester Fertigstellungszeitpunkt auf A2
hier habe ich mir angeschaut, wann denn X2 auf A2 loslegen kann, sprich, ist X1 da schon fertig? In diesem Falle ja, da X1 in dem Moment auf A2 gestartet ist wie X2 auf A1. X2 braucht auf A1 aber länger (11), also kann X2 auf A2 starten, sobald er dort ankommt ergo:
t2=3+11+1=15
jetzt geht es auf A3 zur Berechnung von t3 - auch hier schaue ich mir wieder an, wann kann X2 auf A3 starten - und stelle fest, dass X1 insgesamt 17 ZE braucht, bis es auf A3 fertig ist. X2 kommt aber nach 15 ZE schon dort an, muss also noch 2 ZE warten, bis er überhaupt anfangen kann und dann ist der späteste Fertigstellungszeitpunkt auf A3 dann, wenn X2 dort auch noch durchgelaufen ist, sprich:
t3=15+2+5=22

Wie ich das ganze dann allerdings bei 3 oder noch mehr Aufträgen mache ist mir schleierhaft, denn dann wirds kompliziert. Aber das dürfte eigentlich mit der Logik der Netzplantechnik zu berechnen sein, oder? Muss mir das nochmal genau anschauen, nur bei der Netzplantechnik bin ich komplett ausgestiegen und kann Übungsaufgabe 3 gar nicht nachvollziehen.

Viele Grüße,
Cail

Cail,

durch deine Anregung habe ich das Problem als solches verstanden, und kann nun auch die restlichen Arbeitsschritte nachvollziehen:

Im Grunde hast Du mit der Erklärung der Abfolge X1,X2 schon alles gesagt: Es kann immer nur auf einer Maschine gearbeitet werden, und t1,t2,t3 geben die spätesten Fertigstellungszeitpunkte aller Aufträge auf der jeweiligen Maschine wieder. Um das Ganze auch für die Abfolge X1,X3,X2 darzustellen:

Die Arbeit für X1 beginnt auf A1, X2 und X3 warten solange vor A1. Im Zeitpunkt 3 ist X1 fertig und fährt mit A2 fort. Nun beginnt X2 mit A1, und ist im Zeitpunkt 10 fertig. Danach wird X3 auf A1 bearbeitet, und schließt im Zeitpunkt 21 ab, das ist gleichzeitig auch t1.

In der Zwischenzeit ist hat X1 schon lange A1 durchlaufen. Im Zeitpunkt 10 hat X3 mit A2 begonnen, und schließt diesen in Zeitpunkt 19 ab. Sobald X2 A1 im Zeitpunkt 21 beendet hat kann X2 mit A2 beginnen, da diese bereits seit Zeitpunkt 19 frei ist. X2 schließt A2 also im Zeitpunkt 22 ab, was auch t2 ist.

Bei t2 befindet sich X3 noch bei A3, und zwar noch 10 weitere Einheiten (X3 ist bei Zeitpunkt 19 mit A2 fertig geworden und zu A3 gewechselt). Diese 10 Zeiteinheiten muss X2 noch vor A3 warten, bis X2 A3 im Zeitpunkt 37 abschliesst.

Wenn man es durchschaut hat total einfach 🙂

Herzlichen Dank für deine Erklärung !

Allerbeste Grüße
Peter

P.S. und Edit: Mit der Netzplantechnik muss ich mich auch noch auseinandersetzen, aber am besten am Wochenende, die Woche steht im Zeichen der Preisbildung auf unvollkommenen Märkten

Auch wenn es schon einen neuen Thread rechtfertigen würde, hier noch etwas zur Netzplantechnik. Zu selbiger habe ich mir lange verzweifelt das Hirn zermartert, dabei habe ich die Formeln im Skript falsch verstanden bzw. nicht richtig auf die Musterlösung der Übungsaufgabe angewendet. Der folgende Link hat bei mir wesentlich zu einem besseren Verständnis der Materie beigetragen:

https:///www.tommy-todeskante.com/downloads/sonstiges/Skript Organisation - Meister.pdf

Beste Grüße
Peter

Tach Peter...
und wie berechne ich nun bei 3 Maschinen, t3... da hilft das Buch, welches empfohlen wurde, auch nicht weiter... die Aufmal-Methode von Cail bringt mir hier auch nix... Wird ja wohl kaum eine Vektorrechnung verlangt werden, bei den Taschenrechnern, welche wir benutzen dürfen.

Ich will versuchen, den Sachverhalt bei der dritten Abzweigung, also drei Aufträgen für t und s zu erklären.
Ich halte mich hierbei an die Auftragsreihenfolge X1,X3,X2 aus Seite 48 des Skripts.

tx ist der Zeitpunkt, an welchem alle Aufträge auf einer Maschine bearbeitet worden sind.

t1 ist damit der Zeitpunkt, an welchem alle Aufträge an Maschine 1 abgeschlossen sind. Die Reihenfolge der Aufträge haben wir zuvor mit X1,X3 bestimmt, und prüfen nun für X2 als drittes Element.

X1 beginnt auf Maschine 1, wird drei Zeiteinheiten lang bearbeitet, und wechselt dann zu Maschine 2. X3 wird nach Abschluss X1 auf Maschine 1 für 7 Zeiteinheiten bearbeitet. Nach insgesamt zehn Zeiteinheiten kommt X2 also an Maschine 1 und wird dort elf Zeiteinheiten lang bearbeitet. Nach nunmehr 21 Zeiteinheiten haben alle drei Aufträge Maschine 1 durchlaufen. t1 ist damit = 21

X1 hat nach den drei Zeiteinheiten zu Maschine 2 gewechselt, und diese nach vier Zeiteinheiten verlassen. Damit kann X2 bei Zeiteinheit 7 auf Maschine 2 bearbeitet werden. X2 ist aber bei Zeiteinheit 4 auf Maschine 1 gekommen und wird dort erst bei Zeiteinheit 10 fertig, Maschine 2 steht also drei Zeiteinheiten lang leer. X2 wird also ab Zeiteinheit 10 sieben Zeiteinheiten lang auf Maschine 2 bearbeitet. Nach Zeiteinheit 17 steht Maschine 2 wieder frei, und muss bis Zeiteinheit 21 warten, bis endlich X3 Maschine 2 erreicht. X3 muss aber nur eine Zeiteinheit lang bearbeitet werden, so dass t2 = 22.

Das Spiel wird für t3 genauso gespielt.


Die Schranken werden im Beispiel wie folgt berechnet: Die Werte für t kann man wie oben beschrieben errechnen. Den Formeln für die Schranken folgend errechnet sich s1 aus t1 (21) + den verbleiben Arbeitszeiten für Aufträge, also die zehn Zeiteinheiten von Auftrag 4 + der kleinsten Bearbeitungszeit eines anderen Auftrags auf den verbleibenden Maschinen, was hier im Beispiel einfach die Bearbeitungszeiten für Maschinen 2 und 3 des Auftrags 4 sind, also 12+2.

Somit errechnet sich im Beispiel s1 = t1+10+14 = 45

Analog verfährt man mit s2 und s3.

Ich hoffe, dass hilft.

Schonmal ein schönes Wochenende bzw. wir sehen uns morgen

Beste Grüße

Peter

ich rechne gerade fleißig die Aufgaben im Skript nach. Frage zu Branch & Bound: bei X3, X1, X4 ist die Schranke 26, bei X3, X1, X5 auch. Warum wird in der Beispiellösung nur mit der ersten Variante weitergerechnet und nicht auch mit der zweiten?

Das Buch gibt leider hierzu auch nichts her,

Danke!

Christina