Diplomvortrag

Martin Homik

Ressourcenoptimierung von Workflow Problemen

Betreuer: Christian SchulteTobias Müller

Fahrplan

1. Motivation

2. Problemstellung

3. Modell und Heuristik

4. Implementierung

5. Ergebnisse

6. Zusammenfassung

7. Demo

Motivation: Beispiel Fertigung

Planungsoptimierung von Fertigungsanlagen:• Produktionsleistung• Invest (Maschinentypen, Anzahl)

Objekt A

Objekt B

Optimierung flexibler Produktionssysteme:• Eine Fertigungsanlage für alle Varianten!

Motivation: Beispiel Fertigung

Planungsoptimierung von Fertigungsanlagen:• Produktionsleistung• Invest (Maschinentypen, Anzahl)

Objekt A+B

Optimierung flexibler Produktionssysteme:• Eine Fertigungsanlage für alle Varianten!

Motivation

Fertigung-Problem ist übertragbar:• Industrie (Computer Integrated Manufacturing)• Baugewerbe (Hausbau)• Geschäftsleben (Kundenbetreuung)• Informatik (Verteilte Programmierung)

Abstraktion als Workflow Problem!

Workflow Abstraktion

Maschinen

Varianten

Arbeitsschritte

Workflow Teilnehmer Typen (WFT)

Abläufe

Aktivitäten

Standardisierung durch Workflow Management Coalition:• Begriffe• Workflow Definitionen• Workflow Systeme

Workflow Abstraktionsebenen

1. ProzeßlogikWelche Aktivität wird zu welchem Zeitpunkt ausgeführt?

2. OrganisationWer führt welche Aktivität aus?

3. InfrastrukturWelche WFTs sind in welcher Anzahl notwendig?

Prozeßdefinition: Eine für ein Workflow System verständlicheDatenstruktur, die Angaben zu Prozeßlogik, Organisation undInfrastruktur enthält.

Begriffe

• Attributierte Ressourcen

• Flexible Prozesse

• Kontinuierliche Versorgung und gerichteter Fluß

• Balance, Taktzeit

• Organisation, Infrastruktur

• Partitionierung

Attributierte Ressourcen

K: 400 €Rz: 200St: 95%

K: 150 €Rz: 200St: 90%

K: 250 €Rz: 200St: 95%

K = Kosten Rz = Rüstzeit St = Stabilität

Fähigkeiten sind beliebig überlappend!

Überlappung

11, 12, 15

Überlappung

12, 13, 16,19

17, 18, 19

Ablaufplan

0 12

13

15

16

17 18

19 100

11

Start Ende

Aktivität

Vorrangrelation

Jede Aktivität muß ausgeführt werden!

Flexible Prozesse

0 12

13

15

16

17 18

19 100

11

0 12

13

15

17 18

19 100

11

20

0 12

13

15

16

17

19 100

11

21 22

Kontinuierliche Versorgung

An jeder Station liegt zu jedem Zeitpunkt Arbeit vor!

Objekte werden in eine Richtung weitergegeben!

BalanceZeit

Scheduling: • min. Durchlaufzeit• Taktzeit

Kontinuierliche Versorgung: • Durchlaufzeit• min. Taktzeit

Problemstellung (Gegeben)

0 12

13

1516

17 18

19 100

11

0 12

13

15

17 18

19 100

11

20

0 12

13

1516

17

19 100

11

21 22

Problemstellung (2)

Organisation?

Infrastruktur?

Blocki

Aj

Problemstellung (2)

Organisation?

Infrastruktur?

Blocki

Aj

Prozeßlogik?

Partitionierung (Beispiel)

0 12

13

15

16

17 18

19 100

11

0 12

13

15

16

17 18

19 100

11 Partitionierung garantiert den gerichteten Datenfluß!

Partitionierung

0 12

13

15

16

17 18

19 100

11

11, 12, 15

12, 13, 16, 19

17, 18, 19

1. Regel: 15 16: 15 in 16 in verschiedene Blöcke

Partitionierung (2)

11, 12, 15

12, 13, 16, 19

17, 18, 19

0 12

13

15

16

17 18

19 100

11

2. Regel: 12 15: 12 in und 15 in derselbe Block

Partitionierung (3)

0 12

13

15

16

17 18

19 100

11

3. Regel: 16 19: 16 in 19 in und verschiedene Blöcke

11, 12, 15

12, 13, 16, 19

17, 18, 19

Grundmodell

• Datenstrukturen

• Blockbearbeitungszeit

• Infrastruktur

• Effektive Taktzeit

Modell: Datenstrukturen

Anzahl Blöcke: 0n

Menge aller Aktivitäten: ΝA

Die Menge aller Kosten: ΝK

Die Menge aller Zeitangaben: ΝTi

Die Menge der Prozentangaben: }100,...,2,1,0{Pr

Allgemeine Verlust: Prv

Maximaler Takt: TimaxT

Modell: WFT

PrTiKP(A)WFT Projektionen:

)P(AWFT:akt KWFT:kost PrWFT:stab

Modell: Datenstrukturen

Kosten:

n

1iiiG M*)kost(WK

Teilnehmertypen:

Anzahl Teilnehmertypen:

nWFTW

nΝM

Modell: Ablauf

Ein Ablauf )R,A(γ γγ ist ein gerichteter, azyklischer und

zusammenhängender Graph mit:

Knoten AAγ Kanten γγγ AAR

Projektionen:

P(A):akt

Die Menge aller Abläufe wird mit bezeichnet.

A)P(A:rel

Modell: AblaufVereinigung:

)akt(γ Azγ

u

)rel(γ Rzγ

u

) P(:union

Sei ) P(z Dann ist )R,(A) union( uuz

ji SS

iS

u

n

1ii AS

Modell: Partition

Partition von Au in: S,,S,S n21

Sei und ))akt(union(A zu ) P(z

)) rel(union(R zu

Und ...Nächste Folie

Modell: Partition(2)

akt(w)b}{a, :WFTw :Rb)(a, u

ji SbSa nji1

Sonst:

ji SbSa nji1

Eigenschaft des gerichteten Flusses:

Modell: Partition(3)

akt(w)b}{a, :WFTw :Aba, u

ji SbSa ji

Allgemeine Zuordnung:

)akt(WS ii ni1

Blockbearbeitungszeit

t

A1

U

A2

U

A3

R1 R2

RüstzeitBearbeitungszeiten

Übergangszeiten

Gesamtbearbeitungszeit / Block

TiWFTP(A):bbz

Infrastruktur

maxT*)stab(W

v)(100*)W,bbz(SM

i

iii

Anzahl WFT im Block Si (und WFT Wi)

Bbz

Anz. WFT

Infrastruktur (2)Welche Anzahl von WFT liegt bei flexiblen Prozessen vor?1. Berechne pro Block und pro Ablaufß die Anzahl2. Wähle pro Block das Maximum.3. Bilde die Summe der Maxima.

268765Summe

8701Prozeß 2

8465Prozeß 1

Taktzeit

ii

iii M*)stab(W

v)(100*)W,bbz(ST

Anzahl WFT

Takt

Taktzeit (2)

Was ist die (effektive) Taktzeit der Lösung?1. Berechne pro Block und pro Ablauf die Taktzeit.2. Die höchste Taktzeit ist die effektive Taktzeit.

Prozeß 1 489 520 531 511

Prozeß 2 500 510 525 0

Heuristik (Aufbau)

Anzahl Blöcke Die Anzahl der Blöcke ist aufsteigend

Teilnehmertyp Wähle den Block mit der geringstenAuswahl an WFTs. Weise den günstigsten WFT zu.

Aktivitäten Wähle die längste Aktivität. Weise siedem Block mit günstigstem WFT zu.

Zielgerichtete Heuristik

2. Order u. Select: Wähle längste Aktivität

1. Filter: Nichtdeterminierte Aktivitäten

3. Value: Zuweisung an Block mit günstigstem WFT

400€ 150€ 250€

Problem: Zielgerichtete Heuristik

400€ 150€ 250€

Schlecht!

Problem: Zielgerichtete Heuristik

400€ 150€ 250€

Besser!

Implementierung (Woop)

• Mozart/Oz: Constraint Programmierung• Ca. 15 000 Zeilen Code• Direkte Umsetzung des mathematischen Modells• Dynamische Skriptgenerierung• Dynamische Heuristikauswahl• Interface zu Standard-Suchmaschinen• Benutzerdefinierte Constraints

Implementierung (Woop)

• Verwaltung von Lösungen/Problemstellungen

• Export von Lösungen

• Protokollfunktion: Email/Datei

• Editor zur Erstellung von Abläufen

• Verifikation von Abläufen

• Internationalization/Localization

ErgebnisseBeispiel:• Zwei Abläufe• Jeweils 50 Akts.• 9 WFT Typen

Beste Lösung:

• 13:40 Std.

• 22.084.534 CP

• 4.74% besser

Erste Lösung:• ca. 60 Choice Points• 1Sek.8 10 10

4144

41 34.14635.002

32.527

05

101520253035404550

Blöcke WFT Kosten(Mio. €)

Vorgegeben Woop (first) Woop (best)

Präzises Modell

Werkzeuge:Reduzierte Werkzeugmagazine

Mehr Blöcke

Steigert Komplexität

Kosten:Teilnehmer, Blöcke, Werkzeuge

Präzises Modell (2)

Vermischter Datenfluß:

Lokale Zeit:

Gleichzeitige Bearbeitung verschiedener Abläufe

Exaktere Ergebnisse

Keine Verbesserung der Laufzeit!

Beitrag (Zusammenfassung)

Praxis: Erfolgreiche Anwendung von Woop in der Praxis

Abstraktion: eines Fertigungsproblems als ein ...

Workflow Problem: Definition und Untersuchung

Woop: Implementierung einer Software zur generischen Lösung; Mozart/Oz ; Technik: CP

Neue Klasse von Problemen identifiziert

Verwandte Arbeiten

Gesamtkonzept:• Workflow Management Coalition (WfMC)

www.wfmc.org• S. Bussmann, K. Schild: An agent-based approach

to the control of flexible production systems

Simulation und Verifikation:• Andreas Oberweis: Zeit- und Kostenanalyse von

Geschäftsprozessen mit höheren Petrinetzen• Scheer: ARIS Toolset

Verwandte Arbeiten(2)

Generische Approximation:• M. Gillmann: Konfiguration verteilter Workflow

Management Systeme mit Leistungsgarantien– Kein gerichteter Datenfluß

– Kontrollfluß

– WFTs sind vorgegeben

– Abschätzung des maximalen Takts

– Pessimistische Abschätzung mit Markov-Ketten

Scheduling (Brücke)

Workflow Teilnehmer:• 10 Typen• Keine Überlappung!

Aktivitäten:• 44 Aktivitäten• Kranarbeiten sind sehr zeitaufwendig

Scheduling (Brücke)

2

4

5

6

7

3

18

9

11

13

14

15

16

12

17

19

20

21

22

18

23

25

26

27

28

24

10

41

29

31

32

33

34

3036

38

39

40

35

37

42

43

44

Bagger

Ramme

Handwerker

Betonmischer

Arbeiter

Maurer

Kran

Planierraupe