Hallo,
ich habe ein Projekt in der Arbeit, bei dem ich keine Lösung des Problems finden kann. Es ist eine Maschine, die ich programmieren muß. Es ist eine Maschine mit 14 Becken. In jedem Becken ist eine andere Flüssigkeit, in die die Körbe eingetaucht werden müssen. Die Reihenfolge und die Eintauchzeit wird von einem Programmablauf festgelegt. Wäre super, wenn mir jemand helfen könnte.

---- VORGABE ------------------------------------------------------------

Es gibt die Becken B1 – B14.

Ein Korb soll je nach Ablauf von einem Becken ins nächste gelegt werden.
Der Programmablauf kann wie folgt aussehen:

1.Schritt: B1 – 10s
2.Schritt: B2 – 20s
3.Schritt: B4 – 10s
4.Schritt: B5 – 30s
5.Schritt: B10 – 60s
6.Schritt: B2 – 30s
7.Schritt: B3 – 10s
8.Schritt: B4 – 10s
9.Schritt: B14 – Ende


Ablauf:
Der erste Korb wird ins Becken(Schritt 1) gelegt. Jetzt soll berechnet werden, wann der nächste Korb ins erste Becken gelegt werden kann, ohne das der erste Korb mit dem zweiten Korb kollidiert. Zusätzlich müssen die Zeiten der Körbe im Becken eingehalten werden. Ein weiterer Parameter, der berücksichtigt werden muss, ist die Zeit, die benötigt wird, um den Korb von einem Becken ins nächste zu bringen. Die Zeit ist wiederum abhängig davon, ob der Korb von B1 zu B2 oder von B1 zu B3, usw. …. gebracht wird. Nach Programmende wird der Korb noch in ein vorgegebenes Becken abgelegt und von einer Person genommen.


Das Programm müsste so flexibel sein, dass der Programmablauf jederzeit geändert werden kann, allerdings nicht mitten im Ablauf.




Vielen Dank.

Stefan

Worin genau besteht jetzt dein Problem

Hätt ich ne Stunde Zeit, könnt ich dir das sogar noch toll animiert geben...ABER ich bin schwer beschäftigt

Ist doch einfach:

Der erste Korb kommt und hängt 10 Sekunden im ersten Becken.
Da im zweiten nichts ist, kann er sofort in dieses.
Also Korb wandert ein Becken weiter.
Erstes Becken ist wieder frei und somit kann der zweite Korb ins erste Becken.
Nach zehn Sekunden ist Korb 2 in Becken 1 fertig und könnte in Becken 2, wäre da nicht Korb 1 in Becken 2 mit einer Zeit von 20 Sekunden.
Da aber beide, sprich Korb 1 und Korb 2 zeitgleich mit dem Bad beginnen, muss Korb 2 noch warten.

Wie lang?

Wartezeit Korb 2 = Badezeit Korb 1 - Badezeit Korb 2
= 20 - 10
10 Sekunden muss Korb 2 also noch warten, bis er ins Becken 2 kann.

Ist diese Zeit herum Wartezeit Korb2/Badezeit Korb 1 kann Korb 1 in Becken 3 und Korb 2 in Becken 2 und Korb 3 in Becken 1.
Nach 10 Sekunden kann Korb 1 ungehindert in Becken 4, da es frei ist. Korb 3 wartet wieder wie Korb 2 auf Korb 1 (10 Sekunden) und wandert dann weiter..

Und so weiter..

LG
Stefan

PS Timer sollten helfen!

Danke für die Antwort, aber das Problem ist das, daß die Körbe sofort ins nächste Becken müssen, ohne Wartezeit.

Jetzt seh ichs..beliebige Reihenfolge..
Das wird lustig

Ich schlage vor: Genetischer Algorithmus

Ist fast mit dem Problem des Handlungsreisenden zu vergleichen.

LG
Stefan

Danke, aber der Handlungsreisende besucht jeden Ort nur einmal. Ich möchte jedes Becken auch mehrmals benutzen können. Hat vielleicht noch jemand eine Idee?

Für sowas verwendet man im allgemeinen Netzplantechnik.
Dafür wird die früheste/späteste Anfangszeit und die früheste/späteste Endzeit für
jedes Becken berechnet.
Damit solltest du eigentlich das Problem lösen können.

Ich glaub du findest im Netz aber nicht so viel darüber. :-/

Hm, kleine Frage: was genau meinst du mit kollidieren?

Dürfen nur nicht 2 gleichzeitig in einem Becken sein, oder können die Körbe auch auf dem Transportweg zusammenstoßen? Wenn das nicht der Fall ist, könnte man einen binären genetischen Algorithmus nehmen... Keine Ahnung, obs sowas gibt, wenn nicht, habe ich den grade erfunden

Die maximale Wartezeit ist ja logischerweise die gesamte Prozesszeit. Jetzt versuche ich einfach, immer kürzere Zeiten (binäre suche, daher der Name) zu verwenden. Wenn ich ne Kollision hab, war es zu kurz. Wenn nicht, ist alles i.O, dann kann ich weiter verkürzen.
Das ganze solange, bis man einen stabilen Wert erreicht hat. KA wie schnell das ist, führt aber definitiv zum Ziel...

Erfordert aber eine Echtzeit-Simulation (mit wahrscheinlich mehreren Eimern), um halt genau zu wissen obs knallt oder nicht...

Eventuell versuch ich das ja mal

Ist zwar mit Sicherheit keine optimale Lösung, aber wie wäre es damit:

1. Fall: Dein Ablauf hat keine Doppelbelegung der Becken (B(i) <> B(j) für alle 1 <= i,j <= max. Schrittzahl Ablaufplan und i <> j)

Dann bestimme den Schritt mit der maximalen Zeit ( Zeit = Zeit im Becken + Transportzeit zu nächstem Becken!). Wenn Du die Körbe dann in genau diesem Abstand in das Erste Becken einsetzt, sollten keine Kollisionen entstehen.

2. Fall: es gibt Doppelbelegung der Becken. Dann den längsten Zyklus finden (Zyklus: erste Belegung bis letzte Belegung des Beckens. Diesen als Pseudobecken auffassen mit seiner max. Zeit und dann wie in Fall (1) die Zeit berechnen.


Grüße,
Uli

stefan.gayr hat folgendes geschrieben:

Danke für die Antwort, aber das Problem ist das, daß die Körbe sofort ins nächste Becken müssen, ohne Wartezeit.

Na und?
Jeder Korb besucht das Becken doch auch nur einmal...

Korb = Handlungsreisender
Becken = Stadt

Du kannst das jez so durchspielen, dass beide Reisen aber nich in der selben Stadt sein dürfen

Nein, Spass beiseite:

Du hast 14 Becken, dürfen alle Becken zeitgleich belegt sein?

Also beim Start gehen 14 Körbe in 14 Becken baden.
Badezeit ist unterschiedlich.
Danach sind sagen wir 2 Becken mit gleicher Badezeit (10s) fertig, dann diese beiden tauschen.
Nach wird ein Becken mit Badezeit 20 Sekunden fertig. Dieses wandert in ein 10s Becken und der Korb aus einem 10s Becken in das 20s Becken...usw..

Hm, ich habe grade ein Brute-Force Programm geschrieben, was dein Beispiel-Programm in gefühlten weniger als 100ms löst...

Reicht das? Dann bau ich mal noch ein GUI dazu

Weniger als 100ms hört sich schon mal unheimlich an. Kannst Du mir mal zeigen wie Du das gemacht hast.