Algorithmus zur Prozessnetzerstellung

Wissenschaft Informatik
#1

Hallo Alle,

ich habe ein kleines Problem. Ich habe einen Algorithmus entwickelt, der mir aus einer Auswahl definierter Prozesse mit Eingangs und Ausgangsgrößen eine Liste der möglichen Kombinationen in Form von Prozessketten ausgibt.

Zur besseren Veranschaulichung folgendes Beispiel:

Prozess1: Wasser kochen
Input: 1 liter Wasser
Output: 1 liter kochendes Wasser

Prozess2: Tee aufkochen
Input: 0,2l kochendes Wasser + 1 Teebeutel
Output: 0,2l Tee

Prozess3: Tee trinken
Input: 0,2l Tee

Daraus kann ich nun also die möglichen Prozessketten ermitteln, die da wären:

Prozesskette 1: Prozess1
Prozesskette 2: Prozess1 + (5 x Prozess2)
Prozesskette 3: Prozess1 + (5 x Prozess2) + 5 x (Prozess3)

Die Mögliche Ausführunganzahl eines Folgeprozesses berechne ich zu

n = Min (Input_FolgeProzess/ Output_Folgeprozess) für alle Inputs des Folgeprozesses.

Das ganze gehe ich rekursiv für alle Prozesse und neu gebildeten Prozessketten durch, so dass ich die Prozessketten wie oben erhalte. Bei gegebenem Inputbestand und gewünschtem Outputbedarf kann ich hiernach durch lineare Programmierung ermitteln, wie oft ich welche Prozesskette ausführen sollte.

Soweit so gut. Funktioniert auch alles bestens. Jetzt möchte ich aber möglichst Prozessnetze generieren können.

Gehen wir von zwei weiteren Prozessen aus, die da wären:

Prozess 4: Kekse backen
Input: 300g Back Mischung
Output: 10 Kekse

Prozess 5: Keks in Tee tunken
Input: 1 Keks + 0,2 l Tee

Hierfür fehlt es mir momentan an einem tragfähigen Ansatz. Hat jemand vielleicht eine Idee, die er gerne mit mir teilen würde?

Wäre für jede Anregung sehr dankbar, da ich schnellstens zu einem Ansatz kommen muss.

Beste Grüße
HG

#2

Hallo HG,

Prozess 5: Keks in Tee tunken
Input: 1 Keks + 0,2 l Tee

Hierfür fehlt es mir momentan an einem tragfähigen Ansatz. Hat
jemand vielleicht eine Idee, die er gerne mit mir teilen
würde?

Die Prozessbeschreibung ist unvollständig: :wink:
Prozess 5: Keks in Tee tunken
Input: 1 Keks + 0,2 l Tee
Output: 0,19 l Tee

MfG Peter(TOO)

#3

Hallo Peter,

danke fürs Vervollständigen. :smile:
Sagt, ist die Fragestellung unverständlich?

Grüße
HG

#4

Hallo HG,

danke fürs Vervollständigen. :smile:
Sagt, ist die Fragestellung unverständlich?

Die Frage ist, wie soll die Prozesskette für (5xTee trinken) und (5xKeks tunken) aussehen ??
Benötigt man dazu 1l oder 2l Tee ?

Ohne den Output benötigst du 2l Tee.

MfG Peter(TOO)

#5

Hi Peter,

Die Frage ist, wie soll die Prozesskette für (5xTee trinken)
und (5xKeks tunken) aussehen ??
Benötigt man dazu 1l oder 2l Tee ?:
Ohne den Output benötigst du 2l Tee.

Sicherlich, Du hast vollkommen recht. Allerdings kam es mir eher auf die Prozesskettenbildung vor dem „Keks tunken“ an.

Schließlich brauche ich dafür Kekse und Tee, also zwei Inputs, die von verschiedenen Prozessen erzeugt werden. In diesem Fall wäre es ja kein Problem, schwieriger wirds allerdings, wenn mehrere Prozesse (teilweise) die gleichen Outputs haben.

Es geht bei mir um folgendes: Ich habe eine Reihe von Prozessen, deren Input- und Outputgrößen ich in einer Inputoutputmatrix darstelle. Zum Beispiel folgende:

Prozess -> P1 P2 P3 P4 P5
Güter
|
v

G1 -1 -1
G2 +1 -1
G3 +1 -1
G4 -1 +1
G5 +2 -1
G6 +1

Wobei P die Prozesse und G die Güter darstellen. So, jetzt verknüpfe ich diese Daten mit den Kosten für die entsprechenden Prozesse und dem Betriebsmittelbedarf.

Im nächsten Schritt bilde ich Prozessketten, wobei ich jede mögliche Kombination der Prozesse als Prozesskette akzeptiere. Zum Beispiel könnte ich im obigen Fall die Prozesskette P1+P2 bilden, da P1 ein G3 erzeugt, das wiederrum P2 als Input verwendet. Dementsprechend wäre auch die Prozesskette P1+P2+(2*P3) möglich.

Entsprechend der gebildeten Prozessketten ergänze ich meine Inputoutputmatrix um die entsprechenden Einträge:

Prozess -> P1+P2 P1+P2+P3
Güter
|
v

G1 -1 -1
G2 +2
G3
G4
G5 +2

Diese Daten und entsprechende Restriktionen zum Beispiel bzgl. der Betriebsmittelkapazitäten verwende ich, um durch lineare Programmierung, die optimale Anzahl der durchzuführenden Prozesse in einer Periode zu ermitteln. Soweit so gut, funktioniert alles bestens.

Nun kommt aber das Problem, dass zum Beispiel P4 sowohl G2 als auch G4 als Input benötigt. Hierfür müssten aber erst die Prozesse P1+P2+P3 als auch P5 ausgeführt worden sein. In meinem Fall bedeutet das, dass ich eine entsprechende Kette nicht bilden kann, sondern eine Periode warten muss, bis ich P4 einplanen kann.

Ich würde gerne anstelle der Prozessketten komplexere Prozessnetze bilden, die zum Beispiel wie folgt aussehen könnten:

P1+P2+P3 --|
|–> P4
P5 --|

Kompliziert wie gesagt, wird das bei mir auf dem Papier, wenn mehrere Prozesse teilweise den gleichen Output haben, ich also schon beim Prozessnetzbilden anfangen muss zu optimieren.

So kompliziert kann das doch nicht sein, oder? Es gibt doch sicherlich viele ähnliche Probleme in der Optimierung von Produktionsabläufen, Routenplanung etc.

Wäre super, mal auf die richtige Fährte zu kommen…

Viele Grüße
HG

#6

Verdammte Naht,

im Browser sind jetzt die ganzen blanks weg. Hier die Inputoutputmatrix mal mit Punkten statt Leerzeichen.

…Prozess ->…P1…P2…P3…P4…P5…
…----------------------------------
Güter…|…
.|…|…

.v… …
G1… …-1…-1…
------- ---------------------------------------
G2… …+1…-1…
------- ---------------------------------------
G3… …+1…-1…
------- ---------------------------------------
G4… …-1…+1…
------- ---------------------------------------
G5… …+2…-1…
------- ---------------------------------------
G6… …+1…
------- ---------------------------------------

Sorry, sieht schrecklich aus, aber was besseres ist mir nicht eingefallen auf die schnelle… :smile:

Viele GRüße
HG

#7

Hallo HG,

Die Darstellung bekommst du mit dem Tag hin :wink:

Die Frage ist, wie soll die Prozesskette für (5xTee trinken)
und (5xKeks tunken) aussehen ??
Benötigt man dazu 1l oder 2l Tee ?:
Ohne den Output benötigst du 2l Tee.

Sicherlich, Du hast vollkommen recht. Allerdings kam es mir
eher auf die Prozesskettenbildung vor dem „Keks tunken“ an.

Schließlich brauche ich dafür Kekse und Tee, also zwei Inputs,
die von verschiedenen Prozessen erzeugt werden. In diesem Fall
wäre es ja kein Problem, schwieriger wirds allerdings, wenn
mehrere Prozesse (teilweise) die gleichen Outputs haben.

Es geht bei mir um folgendes: Ich habe eine Reihe von
Prozessen, deren Input- und Outputgrößen ich in einer
Inputoutputmatrix darstelle. Zum Beispiel folgende:

> Prozess -\> P1 P2 P3 P4 P5  
> Güter  
> |  
> v  
>   
> G1 -1 -1  
> G2 +1 -1  
> G3 +1 -1  
> G4 -1 +1  
> G5 +2 -1  
> G6 +1

Wobei P die Prozesse und G die Güter darstellen. So, jetzt
verknüpfe ich diese Daten mit den Kosten für die
entsprechenden Prozesse und dem Betriebsmittelbedarf.

Im nächsten Schritt bilde ich Prozessketten, wobei ich jede
mögliche Kombination der Prozesse als Prozesskette akzeptiere.
Zum Beispiel könnte ich im obigen Fall die Prozesskette P1+P2
bilden, da P1 ein G3 erzeugt, das wiederrum P2 als Input
verwendet. Dementsprechend wäre auch die Prozesskette
P1+P2+(2*P3) möglich.

Entsprechend der gebildeten Prozessketten ergänze ich meine
Inputoutputmatrix um die entsprechenden Einträge:

> Prozess -\> P1+P2 P1+P2+P3  
> Güter  
> |  
> v  
>   
> G1 -1 -1  
> G2 +2  
> G3  
> G4  
> G5 +2

Diese Daten und entsprechende Restriktionen zum Beispiel bzgl.
der Betriebsmittelkapazitäten verwende ich, um durch lineare
Programmierung, die optimale Anzahl der durchzuführenden
Prozesse in einer Periode zu ermitteln. Soweit so gut,
funktioniert alles bestens.

Nun kommt aber das Problem, dass zum Beispiel P4 sowohl G2 als
auch G4 als Input benötigt. Hierfür müssten aber erst die
Prozesse P1+P2+P3 als auch P5 ausgeführt worden sein. In
meinem Fall bedeutet das, dass ich eine entsprechende Kette
nicht bilden kann, sondern eine Periode warten muss, bis ich
P4 einplanen kann.

Ich würde gerne anstelle der Prozessketten komplexere
Prozessnetze bilden, die zum Beispiel wie folgt aussehen
könnten:

> P1+P2+P3 --|  
> |--\> P4  
> P5 --|

Sollte das nicht so aussehen:

 P1+P2+P3 --|
 |--\> **P5**
**P4** --|

Kompliziert wie gesagt, wird das bei mir auf dem Papier, wenn
mehrere Prozesse teilweise den gleichen Output haben, ich also
schon beim Prozessnetzbilden anfangen muss zu optimieren.

So kompliziert kann das doch nicht sein, oder? Es gibt doch
sicherlich viele ähnliche Probleme in der Optimierung von
Produktionsabläufen, Routenplanung etc.

Also praktisch würde ich das mit verschachtelten Bäumen lösen.
Dann musst du für eine gültige Lösung nur noch den Baum zurückverfolgen.

MfG Peter(TOO)