Home
/
JavaForum
/
Java allgemein
Infos
|
Features
|
Gold-Edition
|
Kundenservice
java
Übersicht
Forum
-
Beginner
-
Java allgemein
-
JDBC
-
JNI
-
Networking
-
Online-Ressourcen
-
Swing + AWT
-
XML
-
Meckerecke
Mitglieder
LOGIN
User oder E-Mail
Passwort
·
Passwort vergessen
·
Kostenlos anmelden
Information
Demo
Features
Im Vergleich
Anmeldung
SUCHE
Beiträge, Foren oder Verfasser finden:
Kundenservice
Impressum
Datenschutz
AGB
Status
4.532 User online
0 User eingeloggt
Beiträge
Beginner
Java allgemein
JDBC
JNI
Networking
Online-Ressourcen
Swing + AWT
XML
Meckerecke
Antworten
Neuer Beitrag
Gesamtdarstellung
Detaildarstellung
Einzeldarstellung
Threaddarstellung
Beitrag 928 von 2212 (42%)
Autor
Gast
Datum
14.08.08, 16:53
Betreff
Job-Shop Problem mit Algorithmus
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
Diskussionsverlauf:
Job-Shop Problem mit Algorithmus
Re: Job-Shop Problem mit Algorithmus
Auf diesen Beitrag antworten
Neuen Beitrag verfassen
Impressum
·
Datenschutz
·
AGB
·
Infos
·
Presse
Ein modernes Forum:
teamturn.com