000
14.08.2008, 16:45 Uhr
Torstinho
|
Hallo erstmal,
und zwar habe ich ein kleines Proble ich möchte ich ein Job Shop Problem mittels eines Branch&Bound Algorithmus lösen.
Das JSP könnte wie folgt aussehen 4 Maschinen 4 Jobs mit jeweils 4 tasks.
Was brauch ich jetzt alles zum Lösen reichen 3 Klassen?
Ich würde class Task, class Machine und class schedule erstellen. class Task müsste beinhalten eine tasklist für jeden task damit er weiß ob sein Vorgänger task abgeschlossen wurde, eine task id zur Identifikation des tasks, eine Zeitdauer, Anfangs- und Endzeit.
class Machine brauch nur eine id zu enthalten, welche dann an den task, wenn er auf der Maschine abgearbeitet wird, übergeben wird. Und eine Möglichkeit die Maschine zu sperren, da nur ein tasks pro Maschine bearbeitet werden kann. Am besten boole?
class schedule würde dann die abgearbeiteten tasks enthalten bzw. bräuchte ich ja dann auch eine Liste aller noch unbearbeiteten tasks class unscheduled?
Der B&B Algorithmus soll solange tasks nehmen und auf den Maschinen anordnen, dass diese möglichst mit guter Auslastung laufen.
Methoden brauch ich eine die prüft ob die Maschine frei ist, eine die tasks aus der Liste der unfertigen nimmt sie auf die Maschine bringt und gleichzeitig aus der Liste der unfertigen streicht und in die Liste der fertigen kopiert damit ich, wenn alle tasks durch sind, ich einen Plan habe an dem ich die Gesamtdauer ablesen kann.
In die main Methode würde ich eine Rekursion einbauen die immer wieder neue Pläne erstellt und sie mit der besten Gesamtdauer vergleicht also wäre das meine obere Grenze.
Der aktuell beste Plan müsste dann immer abgespeichert werden und mit dem momentan durchlaufenden Plan verglichen werden.
Wie verhindere ich jetzt, dass immerwieder der gleiche Plan probiert wird?
Ich muss ja irgendwie verhindern, dass immerwieder der gleiche Plan genommen wird oder das es irgendwann wieder von vorn losgeht. Also muss ich irgendwie abspeichern, welcher Lösungsraum schon durchlaufen ist.
Wie funktioniert das mit der unteren Grenze? Wie kann ich ein Paramter einbauen sodass ich zwischen Tiefen- und Breitensuche wechseln kann?
Grüße Torsten |
