Agentenbasierte Produktionssteuerung komplexer Produktionssysteme 9783835002494, 383500249X, 9783835090798, 3835090798 [PDF]

Zitiervorschau

Lars Monch AgentenbasierteProduktionssteuerung komplexer Produktionssysteme

WIRTSCHAFTSINFORMATIK

Lars Monch

Agentenbasierte Produktionssteuerung komplexer Produktionssysteme

Deutscher Universitats-Verlag

Bibliografische Information Der Deutschen Bibliothek Die Deutsche Bibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet uber abrufbar.

HabilitationsschriftTechnische Universitat llmenau, 2005

1.AuflageMarz2006 Alle Rechte vorbehalten © Deutscher Universitats-Verlag I GWV Fachverlage GmbH, Wiesbaden 2006 Lektorat: Ute Wrasmann / Anita Wilke Der Deutsche Universitats-Verlag ist ein Unternehmen von Springer Science+Business Media. www.duv.de Das Werk einschlieSllch aller seiner Telle ist urheberrechtlich geschiitzt. Jede Verwertung auBerhalb der engen Grenzen des Urheberrechtsgesetzes ist ohne Zustimmung des Verlags unzulassig und strafbar. Das gilt insbesondere fiir Vervielfaltigungen, Ubersetzungen, Mikroverfilmungen und die Einspeicherung und Verarbeitung in elektronischen Systemen. Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten waren und dahervon jedermann benutzt werden diirften. Umschlaggestaltung: Regine Zimmer, Dipl.-Designerin, Frankfurt/Main Druck und Buchbinder: Rosch-Buch, Schef^litz Gedruckt auf saurefreiem und chlorfrei gebleichtem Papier Printed in Germany ISBN 3-8350-0249-X

Vorwort Produktionssteuerungsprobleme konnen trotz der in den letzten Jahren voUzogenen Fortschritte in Theorie und Praxis nicht als abschliefiend gelost betrachtet werden. Eine kritische Betrachtung fiihrt zu der Erkenntnis, dass in den letzten zwei Jahrzehnten zwar grofie Fortschritte in der Hardund Softwareentwicklung stattgefunden haben, die zu besseren Informationssystemen fiir die Produktionssteuerung gefuhrt haben. Gleichzeitig haben relativ wenig moderne Algorithmen Eingang in gebrauchliche Werkstattsteuerungssysteme gefunden. Auf der anderen Seite ist es heute moglich, auf Grund der verbesserten Rechentechnik grofie Mengen an digitalen, strukturierten Daten zur Entscheidungsunterstiitznng heranzuziehen. In der vorliegenden Arbeit wird die klassische Theorie der hierarchischen Steuerung mit modernen verteilten Programmierparadigmen, insbesondere auch der Agententechnologie in Verbindung gesetzt. Dadurch wird es moghch, die Vorteile hierarchischer Ansatze wie Rechenbarkeit und Skalierbarkeit mit den Vorteilen von Softwareagenten zu verkniipfen. Als Ergebnis dieses Syntheseprozesses erhalt man Softwaresysteme, die leichter zu warten und weiterzuentwickeln sind und die Online-Anforderungen geniigen. Aufbauend auf einer griindUchen Analyse der State-of-the-Art-Situation werden in der vorliegenden Arbeit Anforderungen an moderne Steuerungssysteme fur komplexe Produktionssysteme herausgearbeitet. Auf Basis der Analyse wird ein verteiltes hierarchisches Steuerungskonzept entwickelt. Nach der Ableitung entsprechender Agenten zur softwaretechnischen Realisierung des Steuerungsframeworks werden heuristische Steuerungsalgorithmen entworfen, die zu der vorgeschlagenen hierarchischen Dekomposition passen. Die neuen Verfahren werden mit konventionellen verglichen. Die Arbeit leistet einen Beitrag zur Koordinationstheorie, indem durch die Bereitstellung einer Ontologie und einer geeigneten Contentsprache der Entwurf einer Koordinationssprache fiir verteilte hierarchische Steuerungssysteme fiir komplexe Produktionsprozesse ermogUcht wird. Es wird eine Systemarchitektur beschrieben, die in konsequenter Weise die Struktur des Steuerungssystems von den eigentUchen Steuerungsalgorithmen entkoppelt. Dadurch konnen Steuerungsverfahren leicht ausgetauscht werden. Die Leistungsbewertung des vorgeschlagenen Steuerungsframeworks erfolgt simulationsbasiert am Beispiel des FABMAS-Prototyps, eines agentenbasierten Systems zur Steuerung des Waferfertigungsprozesses. Die in dieser Arbeit dargestellten Forschungsarbeiten konnen als Ausgangspunkt fiir die Weiterentwicklung von Hard- und Softwarearchitekturen fiir CIM (Computer Integrated Manufacturing)-Anwendungen angesehen werden. Die Arbeit ist das Ergebnis von Forschungsarbeiten, die ich von 1999 bis 2004 an der Technischen Universitat Ilmenau, Institut fiir Wirtschaftsinformatik, durchgefiihrt habe.

VI

VORWORT

Der Lehrstuhlinhaber und Direktor des Instituts fiir Wirtschaftsinformatik der Technischen Universitat Ilmenau, Peter Gmilkowsky, sorgte fiir sehr gute Arbeitsbedingungen. Die durchgefiihrten Forschungsarbeiten waren gleichzeitig Ausgangspunkt einer sehr fruchtbaren Zusammenarbeit mit John W. Fowler (Arizona State University, Tempe, AZ, USA). John lenkte mein Interesse auf ScheduHngfragestellungen fiir die Halbleiterfertigung. Die in dieser Arbeit dargestellten Forschungsarbeiten wurden inhalthch und materiell durch drei Forschungsprojekte getragen, die unter meiner Leitung durchgefiihrt wurden, und mir zum Teil sehr unterschiedUche Perspektiven auf meinen Forschungsgegenstand ermoghchten: 1. „Simulationsbasierte Arbeitsvorgabe und Terminierung fiir die Waferfertigung (SimArt)" (finanziert durch X-FAB Semiconductor Foundries AG Erfurt), 2. Factory Operations Research Center (FORCe)-Projekt "ScheduUng of Semiconductor Wafer Fabrication Facihties" (finanziert durch die Semiconductor Research Corporation und SEMATECH International), 3. "FABMAS: ein System zur Steuerung des Waferfertigungsprozesses auf der Grundlage autonomer und kooperativer Softwareagenten" (finanziert durch das DFG-Schwerpunktprogramm "Intelligente Softwareagenten und betriebswirtschaftliche Anwendungsszenarien"). Eine Reihe Personen haben die hier beschriebenen Forschungsarbeiten unterstiitzt. An erster Stelle steht das aus Marcel Stehli, Jens Zimmermann und Ilka Habenicht bestehende FABMASTeam, das direkt zum Erfolg der Forschungsarbeiten beigetragen hat. Die Arbeit ware ohne die niitzliche praJctische Arbeit vieler Studenten unmoglich gewesen. Stellvertretend seien hier Rene Schabacker, Rene Driefiel, Patrick Rempel, Frank Mock und Jeannine Schmidt genannt. Oliver Rose (Technische Universitat Dresden) stand fiir viele Diskussionen iiber Halbleiterfertigung, Simulation und forschungsorganisatorische Fragestellungen zur Verfiigung. Volker Schmalfufi (X-FAB Semiconductor Foundries AG Erfurt) und Alexander Schomig (Infineon Technologies AG Munchen) ermoglichten durch Diskussionen und die Bereitstellung von Datensatzen eine standige Uberpriifung der praktischen Relevanz der durchgefiihrten Forschungsarbeiten. Peter Mertens (Universitat Erlangen-Niirnberg) verdanke ich die tJberzeugung, dass Wirtschaftsinformatik die Anwendung von Informatik- und Operations-Research-Methoden auf betriebliche Problemstellungen ist und dass es unwissenschaftlich ist, reflexartig jeder (wissenschaftlichen) Modewelle zu folgen. Ich mochte mich herzlich bei den oben genannten Personen fiir ihre Hilfe und Unterstiitzung bedanken. Lars Monch

Inhaltsverzeichnis 1 Einleitung

1

1.1 Motivation

1

1.2

2

Methodisches Vorgehen

1.3 Problemstellung

3

1.4

Ergebnisse der Arbeit

5

1.4.1

Anforderungen an Steuerungsansatze

5

1.4.2

Framework zur verteilten hierarchischen Steuerung

5

1.4.2.1

Modellsystem fiir eine verteilte hierarchische Steuerung

5

1.4.2.2

Produktionssystemsteuerungsebene

6

1.4.2.3

Produktionsbereichssteuerungsebene

6

1.4.2.4

Maschinengruppensteuerungsebene

7

1.4.2.5

Verteiltes hierarchisches Steuerungskonzept

7

1.4.2.6

Diskussion der verfolgten betriebswirtschaftlichen Ziele

8

1.4.3

Agentifizierung des Steuerungsansatzes

9

1.4.4

Steuerungsalgorithmen fiir komplexe Produktionssysteme

9

1.4.4.1

Algorithmen fur die Produktionssystemsteuerungsebene

9

1.4.4.2

Algorithmen fiir die Produktionsbereichssteuerungsebene . . . . .

1.4.4.3

Algorithmen fiir die Maschinengruppensteuerungsebene

1.4.5

10 10

Koordination in verteilten hierarchischen Steuerungssystemen

10

1.4.5.1

Koordinationsmechanismen

10

1.4.5.2

Ontologie zur Steuerung komplexer Produktionssysteme

11

1.4.5.3

Contentsprache zur Steuerung komplexer Produktionssysteme . .

11

1.4.5.4

Koordinationssprache fiir eine verteilte hierarchische Steuerung

11

.

1.4.6

Architektur eines verteilten hierarchischen Steuerungssystems

12

1.4.7

Leistungsbewertung von Steuerungsverfahren

13

VIII

INHALTSVERZEICHNIS

2 Steuerungsansatze fur komplexe Produktionssysteme

15

2.1 Komplexe Systeme und Prozesse

15

2.2

16

Komplexe Produktionssysteme und -prozesse

2.3 Steuerung komplexer Systeme

19

2.4

Steuerung komplexer Produktionssysteme

21

2.5

Steuerungsansatze des Operations Research

22

2.5.1

Prioritatsregeln und Einsteuerungsstrategien

22

2.5.1.1

Prioritatsregelbasierte Steuerung

22

2.5.1.2

Einsteuerungsstrategien fiir komplexe Produktionssysteme . . . .

23

2.6

2.5.2

Deterministische Schedulingansatze

25

2.5.3

Simulationsbasierte Ansatze

27

Steuerungsansatze der Kiinstlichen Intelligenz

30

2.6.1

Expertensysteme und wissensbasierte Systeme

30

2.6.2

Suchverfahren der Kiinstlichen Intelligenz

30

2.6.3

Constraint-Satisfaction-Techniken

31

2.6.4

Verfahren des maschinellen Lernens

33

2.6.4.1

Neuronale Netze

33

2.6.4.2

Induktive Entscheidungsbaume

34

2.6.4.3

Reinforcement-Learning

35

2.6.5

Verfahren der Verteilten Kiinstlichen InteUigenz

36

2.6.5.1

Multi-Agenten-Systeme

36

2.6.5.2

Motiviation fur agentenbasierte Produktionssteuerungssysteme . .

37

2.6.5.3

Existierende agentenbasierte Produktionssteuerungssysteme . . .

37

2.6.5.4

Funktionale Agenten

38

2.6.5.5

Adaptive Agenten

39

2.6.5.6

Kontraktnetzartige Steuerungsverfahren

40

2.6.5.7

Holonische Ansatze zur Produktionssteuerung

40

2.7 Hybride Steuerungsansatze fiir Produktionssysteme

41

2.7.1

Begriffsbestimmung und Beispiele

41

2.7.2

Hierarchische Steuerungsansatze

42

2.8 Anforderungsanalyse fiir ein Steuerungssystem

43

INHALTSVERZEICHNIS

IX

3 Verteilte hierarchische Produktionssteuerung

47

3.1

Hierarchische Steuerungsansatze

47

3.1.1

Hierarchische Strukturen

47

3.1.2

Verteilte Entscheidungsfindung in hierarchischen Systemen

48

3.1.3

Basismodell und Notationen fiir hierarchische Systeme

49

3.1.3.1

Framework fiir eine hierarchische Steuerung

49

3.1.3.2

ModelUerung von Entscheidungen

51

3.1.4

Schichtung, Stratifikation und Staffelung hierarchischer Systeme

53

3.1.5

Informationsstatus der Hierarchieebenen

55

3.2

Modellannahmen

56

3.3

tJbersicht iiber den Steuerungsansatz

58

3.4

Produktionssystemsteuerungsebene: Entscheidungsmodell

60

3.4.1

Entscheidungsvariable

60

3.4.2

Entscheidungskriterium

61

3.4.3

Alternativenraum fiir die Entscheidungen

62

3.4.4

Optimierungsmodell

63

3.4.4.1

Nicht-reaktive Antizipation

63

3.4.4.2

Imphzite reaktive Antizipation

64

3.4.4.3

Losungsverfahren

65

3.4.5 3.5

65

Produktionsbereichssteuerungsebene: Entscheidungsmodell

66

3.5.1

Entscheidungsvariable

67

3.5.2

Entscheidungskriterium

67

3.5.3

Alternativenraum fur die Entscheidungen

68

3.5.4

Optimierungsmodell zur Steuerung eines Produktionsbereichs

69

3.5.4.1

ModelUerung

69

3.5.4.2

Losungsverfgihren

73

3.5.5 3.6

Informationsstatus

Informationsstatus

73

Maschinengruppensteuerungsebene: Entscheidungsmodell

74

3.6.1

Entscheidungsvariable

74

3.6.2

Entscheidungskriterium

.

75

X

INHALTSVERZEICHNIS 3.6.3

Alternativenraum fiir die Entscheidungen

75

3.6.4

Optimierungsmodell

76

3.6.5

Informationsstatus

76

3.7

Verteiltes hierarchisches Steuerungsverfahren

78

3.8

Agentifizierung des Steuerungsansatzes

80

3.8.1

Begriffsbildungen

80

3.8.2

Ansatze zur Identifikation von Agenten

81

3.8.2.1

Gaia-Methode

81

3.8.2.2

DACS-Methode

83

3.8.2.3

PROSA-Referenzarchitektur

84

3.8.3

3.8.4

Identifikation der Agenten zur Realisierung des Steuerungsansatzes

....

85

3.8.3.1

Analyse des Steuerungsprozesses

85

3.8.3.2

Ressourcenagenten

87

3.8.3.3

Auftragsagenten

87

3.8.3.4

Produktagenten

88

3.8.3.5

Dienstagenten fur die Ressourcen- und Auftragsagenten

90

Agenteninteraktionen

90

3.8.4.1

Interaktionen zwischen Ressourcen-, Auftrags- und Produktagenten 90

3.8.4.2

Interaktionen zwischen Ressourcen-, Auftrags- und Schedulingagenten

3.8.4.3

91

Interaktionen zwischen Ressourcen-, Auftrags- und Monitoringagenten

92

4 Verfahren zur autonomen und kooperativen Steuerung

93

4.1 Losterminierung auf Produktionssystemebene

94

4.1.1

Problemformuherung

94

4.1.2

Diskussion relevanter Literatur

4.1.3

Kapazitatsorientierter Beam-Search-Algorithmus

96

4.1.3.1

Terminierungsmethode ICA

96

4.1.3.2

Beam-Search-Algorithmus

98

.

95

4.1.4

Design von Experimenten und numerische Ergebnisse

101

4.1.5

Iteratives simulationsbasiertes Verfahren zur Abschatzung von Wartezeiten

106

INHALTSVERZEICHNIS

4.2

XI

4.1.6

Softwaretechnische Umsetzung des iterativen Verfahrens

108

4.1.7

Numerische Ergebnisse fiir das iterative simulationsbasierte Verfahren . . .

109

Shifting-Bottleneck-Heuristik fiir Produktionsbereiche

Ill

4.2.1

Disjunktive Graphenformulierung

112

4.2.1.1

Bestandteile eines disjunktiven Graphen

112

4.2.1.2

Darstellung eines Ablaufplanes im disjunktiven Graphen

114

4.2.1.3

Festlegung der Kantengewichte

114

4.2.1.4

Behandlung von Batchmaschinen

116

4.2.1.5

Behandlung von reihenfolgeabhangigen Umriistzeiten

117

4.2.1.6

Behandlung von parallelen Maschinen

117

4.2.2

Shifting-Bottleneck-Heuristik

117

4.2.3

Verteilte Shifting-Bottleneck-Heuristik

119

4.2.3.1

4.2.3.2 4.2.4 4.2.5

Modifikation der disjunktiven Graphenreprasentation fiir Produktionsbereiche

119

Verfahren

120

Entwurf der durchzufiihrenden Experimente Ergebnisse numerischer Experimente mit der verteilten Shifting-BottleneckHeuristik

4.3

122

. . 123

Scheduling-Pramework fiir parallele Maschinen

127

4.3.1

Problemanalyse und Diskussion relevanter Literatur

127

4.3.2

ModeUierungs- und Entscheidungsuntersttitzungsperspektive

131

4.3.2.1

Uberblick

131

4.3.2.2

Phase I: Bildung von Schedulingentitaten (Pra-Prozessingphase) . 131

4.3.2.3

Phase H: Aufteilung der Schedulingentitaten

4.3.2.4

Phase III: Festlegung der Reihenfolge der Lose auf den Einzelmaschinen

4.3.2.5

4.3.3 4.3.4

132

135

Phase IV: Herstellen bzw. Verbesserung eines zulassigen Ablaufplanes (Post-Prozessingphase)

136

Softwaretechnische Reahsierung des Frameworks

137

Beispiel 1: Ablaufplanung fiir parallele Batchmaschinen mit dynamischen Losankiinften

138

4.3.4.1

138

Vorarbeiten

XII

INHALTSVERZEICHNIS 4.3.4.2

Problemformulierung und Notationen

139

4.3.4.3

Konkretisierung der vier Phasen

140

4.3.4.4

4.3.4.5 4.3.5

144

Numerische Experimente

145

Beispiel 2: Ablaufplanung fiir Photolithographiestepper

147

4.3.5.1

147

4.3.5.2

4.4

Methode zur simultanen Batchbildung und Festlegung der Bearbeitungsreihenfolge der Batches

Motivation und Problemstellung Modellierungs- und Entscheidungsunterstiitzung fiir das Stepperbelegungsproblem

151

4.3.5.3

Parameterwahl fur Phase II und Phase III

152

4.3.5.4

Numerische Experimente

153

Modifizierter Kontraktnetzansatz

154

4.4.1

Motivation

154

4.4.2

Kontraktnetzartige Ansatze

154

4.4.3

Maschinenstundenbasierte Budget- und Kostenbestimmung

158

4.4.3.1

Bezeichnungen

158

4.4.3.2

Definition von Maschinenstundensatzen

159

4.4.3.3

Kosten zur Herstellung eines einzelnen Loses fur ein Produkt. . . 160

4.4.3.4

Maschinenstundenbasierte Festlegung des Budgets fiir Losagenten

4.4.3.5

Maschinenstundenbasierte Festlegung der Kosten fiir Maschinen-

4.4.3.6 4.4.4

160

agenten

161

Algorithmus zur maschinenstundenbasierten Ressourcenallokation

162

Leistungsbewertung des vorgeschlagenen Ansatzes

163

4.4.4.1

Charakterisierung des untersuchten Produktionssystems

163

4.4.4.2

Design der Experimente

164

4.4.4.3

Ergebnisse

167

4.5 Integration in eine betriebliche Anwendungslandschaft

168

5 Koordination in hierarchischen Steuerungssystemen

171

5.1

Koordinationsbegriff

171

5.1.1

Motivation und Begriff

171

5.1.2

Formalisierung des Koordinationsbegriffes

172

INHALTSVERZEICHNIS

5.2

5.3

5.4

6

XIII

5.1.3

Gestaltung der Koordination im Steuerungsframework

174

5.1.4

Realisierung von Koordinationsaktivitaten

176

Ontologie zur Steuerung komplexer Produktionssysteme

177

5.2.1

Ontologiebegriff

177

5.2.2

Entwurf der Ontologie

178

Contentsprache fiir komplexe Produktionssysteme

183

5.3.1

Motivation

183

5.3.2

Grammatik der Contentsprache

184

Koordinationssprache

186

5.4.1

Begriffsbestimmung und Diskussion relevanter Literatur

186

5.4.2

Design der Koordinationssprache

187

Systemarchitektur zur Produktionssteuerung

193

6.1

Architekturmodelle fiir betriebhche Informationssysteme

193

6.2

Infrastruktur fiir das Multi-Agenten-System

195

6.3

AgentenmodeUierung

6.4

6.5

. 196

6.3.1

RoUenbasierter Ansatz .

196

6.3.2

Verhaltensmodellierung

196

6.3.3

Abbildung der hierarchischen Elemente des Steuerungsverfahrens

197

Kommunikation im Multi-Agenten-System

197

6.4.1

Technische Realisierung

197

6.4.2

Ontologieintegration

198

6.4.3

Implementierung und Integration der Contentsprache

198

Datenhaushalt des vorgeschlagenen Multi-Agenten-Systems

199

6.5.1

Prinzipien

199

6.5.2

Datenstrukturen fiir Entscheideragenten

200

6.5.2.1

Maschinengruppenagenten

200

6.5.2.2

Produktionsbereichsagenten

200

6.5.2.3

Produktionssystemagent

201

6.5.2.4

Produktagenten

202

6.5.2.5

Losagenten

6.5.2.6

Batchagenten

. 202 202

XIV

INHALTSVERZEICHNIS 6.5.2.7 6.5.3

6.5.4

Agenten fiir vorbeugende Instandhaltungsmafinahmen

Datenstrukturen fiir Dienstagenten

203

6.5.3.1

Schedulingagenten

203

6.5.3.2

Monitoringagenten

203

Datenversorgung des Steuerungssystems durch betriebliche Informationssysteme

6.6

203

Generische Architektur fiir Entscheideragenten

204

6.6.1

Funktionalitat von Entscheideragenten

204

6.6.1.1

Vorbereitung der Entscheidungsfindung

205

6.6.1.2

Treffen der Entscheidung

205

6.6.1.3

Informieren anderer Entscheideragenten

206

6.6.1.4

Starten von Dienstagenten

206

6.6.1.5

Abfrage der Berechnungsergebnisse von Dienstagenten

206

6.6.1.6

Anfordern von Diensten anderer Entscheideragenten

206

6.6.1.7

Behandlung von Ausnahmen

206

6.6.1.8

Uberpriifen der Liste gegenwartiger oder zukiinftiger Agentenaktivitaten auf Eintrage

6.6.2 6.7

203

Architektur von Entscheideragenten

206 207

Generische Architektur fiir Dienstagenten

208

6.7.1

Funktionahtat von Dienstagenten

209

6.7.1.1

Vorbereitung der Problemlosung

209

6.7.1.2

Berechnung interner Parameter des Losungsverfahrens

209

6.7.1.3

Versorgung des Losungsverfahrens mit Parametern

210

6.7.1.4

Losung des Problems

210

6.7.1.5

Abbruch eines Losungsvorganges zu bestimmten Zeitpunkten oder in Folge bestimmter Ereignisse

6.7.2

210

6.7.1.6

Informieren anderer Agenten iiber das Ergebnis der Berechnung . 210

6.7.1.7

Behandlung von Ausnahmesituationen

Datenverwaltung in Dienstagenten

211 211

6.8

Interaktion zwischen Entscheider- und Dienstagenten

211

6.9

Beschreibung des FABMAS-Prototyps

213

INHALTSVERZEICHNIS

XV

7 Leistungsbewertung von Steuerungsansatzen

217

7.1

Motivation

217

7.2

Anforderungen an die Leistungsbewertung

218

7.2.1

Modellierungsgesichtspunkte

218

7.2.2

Architekturgesichtspunkte

218

7.3 Architektur zur Leistungsbewertung

219

7.4

223

7.5

Leistungskennzahlen fiir komplexe Produktionssysteme 7.4.1

Vergleichsverfahren fiir einen zu bewertenden verteilten Steuerungsansatz . 224

7.4.2

Mafie zur Leistungsbewertung

225

7.4.3

Ansatze zur Leistungsmessung

227

7.4.4

Festlegung und Planung der durchzufiihrenden Experimente

228

Numerische Experimente

228

7.5.1

Vorgehen bei der Leistungsbewertung

229

7.5.1.1

Vergleichsverfahren

229

7.5.1.2

Festlegung der Leistungsmafie

229

7.5.1.3

Spezifikation des verwendeten Ansatzes zur Leistungsmessung . . 230

7.5.1.4

Beschreibung der verwendeten Hard- und Softwareumgebung . . . 230

7.5.1.5

Festlegung der durchzufiihrenden Experimente

7.5.2

230

Numerische Ergebnisse

231

7.5.2.1

231

7.5.2.2

Experimente zur Bewertung der Steuerungsverfahren Experimente zur Leistungsfahigkeit der technischen Realisierung des Steuerungssystems

232

8 Ausblick auf weitere Forschungsarbeiten

235

Literaturverzeichnis

239

Anhang

261

A Modellierung komplexer Produktionssysteme

261

A.l Formale Beschreibung: Basissystem

261

A.2 Formale Beschreibung: Steuerungssystem

263

XVI B Agenten fur den Steuerungsansatz

INHALTSVERZEICHNIS 267

B.l Ressourcenagenten

267

B.2 Auftragsagenten

269

B.3 Dienstagenten

270

C Verhaltensmodellierung

273

C.l Verhalten von Entscheideragenten

273

C.2 Verhalten von Dienstagenten

276

Abbildungsverzeichnis 2.1

Zusammenhang System und Prozess

16

2.2

Zielmodifikation bzw. Modifikation des internen Modells [20]

21

2.3 Aufbau eines neuronalen Netzes

34

3.1

Grundmodell der hierarchischen Steuerung [223]

50

3.2

Hierarchischen Steuerung mit zwei Steuerungsebenen [223]

52

3.3

Hierarchisches System mit Staffelung

54

3.4

Steuerungsaufgabendekomposition durch Stratifikation

55

3.5

Zeitaspekte im verteilten hierarchischen Steuerungsalgorithmus

78

3.6

Entscheideragenten und Dienstagenten fiir die Steuerung

86

3.7

Entscheideragenten zur Steuerung von Produktionssystemen

89

3.8

Dienstagenten zur Steuerung von Produktionssystemen

90

3.9

Interaktionen zwischen Ressourcen-, Auftrags- und Produktagenten

91

3.10 Interaktionen zwischen Ressourcen-, Auftrags- und ScheduUngagenten

91

3.11 Interaktionen zwischen Ressourcen-, Auftrags- und Monitoringagenten

92

4.1

Suchbaum fiir den Beam-Search-Algorithmus

99

4.2

AuiSere Schleife des Beam-Search-Algorithmus

100

4.3 Innere Schleife des Beam-Search-Algorithmus

102

4.4

Softwarearchitektur fiir das iterative simulationsbasierte Verfahren

108

4.5

Veranderung des Leistungsmafies TWT in Abhangigkeit von der Anzahl der Iterationen

Ill

4.6

Graphenreprasentation fiir Lose {1,2,3} und Maschinen {1,2,3,4}

114

4.7

Disjunktiver Graph mit den kiinstlichen Batchknoten {(2,2), (2,3)} und {(2,1)}. . 117

4.8

Modifizierte Graphenreprasentation fiir den zyklischen Durchlauf von Losen durch Produktionsbereiche

120

XVIII 4.9

ABBILDUNGSVERZEICHNIS TWT-Ergebnisse fiir Produktionssystem B

126

4.10 Belegungsproblem fiir heterogene parallele Maschinen

128

4.11 Architektur des GA-basierten Scheduling-Prameworks

138

4.12 Standardkontraktnetz

155

4.13 Kontraktnetz in der Koordinatorvariante [275]

157

4.14 Durchsatz fiir Szenario 2 und Szenario 3

168

4.15 Entwicklung der Durchlaufzeiten fiir Szenario 2

169

5.1

Ausgestaltung der Koordination im vorgeschlagenen Steuerungsframework

....

175

5.2

Datenmodell fiir komplexe Produktionssysteme

180

5.3

Konzept Aktivitat und verwandte Konzepte

181

5.4

Konzept Ressource und verwandte Konzepte

182

5.5

Konzept Ablaufplan und verwandte Konzepte

183

5.6

Interaktionsprotokoll fiir Szenario 1

188

5.7

Interaktionsprotokoll fiir Szenario 2

189

5.8

Interaktionsprotokoll fur Szenario 3

190

5.9

Interaktionsprotokoll fur Szenario 4

191

6.1

Multi-Agenten-System-Infrastruktur

196

6.2

RoUenbasierter Ansatz bei der Agentenmodellierung

197

6.3

Datenhaushalt von Produktionsbereichsagenten

201

6.4

Datenversorgung durch Fremdsysteme

204

6.5

Liste der gegenwartigen oder zukiinftigen Agentenaktivitaten (AIL)

208

6.6

Interaktionen zwischen Entscheider- und Dienstagenten: I

212

6.7

Interaktionen zwischen Entscheider- und Dienstagenten: II

213

6.8

Interaktionen zwischen Dienst- und Entscheideragenten

214

6.9

Interaktionen zwischen zwei Entscheideragenten

215

6.10 Grobarchitektur des FABMAS-Prototyps

216

7.1 Architektur zur Leistungsbewertung

220

7.2

223

Objektmodell fiir ein einzelnes Blackboard

A.l Mini-Fab-Modell als komplexes Produktionssystem

262

Tabellenverzeichnis 3.1 Funktionalitat der einzelnen Steuerungsebenen

59

3.2

78

3.3

Parameter fiir die obere und mittlere Steuerungsebene Gegeniiberstellung von verteilten hierarchischen Steuerungssystemen und MultiAgenten-Systemen

82

4.1 Details zum MIMAC-Modell 1

103

4.2 Wahl der Zeitintervalle (Szenario 1)

104

4.3

Ergebnisse fiir verschiedene Flussfaktoren (vier detailliert modellierte Maschinengruppen)

4.4

104

Ergebnisse fiir eine unterschiedliche Anzahl von detailliert modellierten Maschinengruppen (BN)(Flussfaktor FF = 1.5)

105

4.5

Wahl der Zeitintervalle (Szenario 2 und Szenario 3)

105

4.6

Ergebnisse fiir Zeitintervalle unterschiedlicher Lange (Flussfaktor FF = 1.5)

4.7

Faktorielles Design zur Leistungsbewertung des Verfahrens

110

4.8

Numerische Ergebnisse fiir das iterative Verfahren

110

4.9

Faktorielles Design zur Leistungsbewertung des Verfahrens

123

...

105

4.10 Ergebnisse fur Produktionssystem A

124

4.11 Ergebnisse fiir Produktionssystem A

125

4.12 Ergebnisse fiir Produktionssystem B

126

4.13 Ergebnisse fur Produktionssystem C

127

4.14 GaLib-Datenstrukturen fiir das Framework

137

4.15 Algorithmenkombinationen fiir die vier Phasen des Frameworks

145

4.16 Parameter fiir Phase II (Ansatz 1 und Ansatz 2)

146

4.17 Parameter der Testdaten

147

4.18 Ergebnisse fiir Ansatz 1

148

XX

TABELLENVERZEICHNIS

4.19 Ergebnisse fiir Ansatz 2

149

4.20 Niveaus der Faktoren im 2^-faktoriellen Design

152

4.21 Parameter fiir Phase II

153

4.22 Leistungswerte fiir das Framework {as = 0.0500)

153

4.23 Anzahl der benotigten vorgezogenen Siliziumscheiben

154

4.24 Produktdaten des betrachteten Produktionssystems

164

4.25 Maschinendaten des Beispiels

164

4.26 Unabhangige Variable der Simulationsstudie 4.27 Beschreibung der Vergleichsprioritatsregeln 4.28 Werte fiir die Leistungsmafie

• • • 165 166 • 167

4.29 Statische Informationen fiir die Maschinenbelegungsverfahren

169

4.30 Dynamische Informationen fiir die Maschinenbelegungsverfahren

170

5.1

Koordination im verteilten hierarchischen Steuerungssystem

176

5.2

Daten fur komplexe Produktionssysteme

179

5.3

Pradikate in der vorgeschlagenen Ontologie

184

5.4

Agentenaktivitaten in der Ontologie

185

6.1

Implementierungsdetails der Dienstagenten im FABMAS-System

215

7.1 Simulationsereignisse, die Objekte des Blackboards verandern

222

7.2

222

Moghche Zustande fiir Entitaten des Produktionssystems

7.3 Direkte Leistungsmafie

226

7.4

Indirekte Leistungsmeifie

227

7.5

Variablentypen fur Simulationsstudien

229

7.6

Faktorielles Design fiir die Leistungsbewertung von DHPCA

231

7.7

Leistungswerte fur NDSBH und DSBH-II fur unterschiedhche Horizonte

232

7.8

TWT-Werte fur Modell B bei unterschiedlichen Systembedingungen

232

7.9

Laufzeit von NDSBH unverteilt und verteilt

233

A.l Bearbeitungszeiten und Batchgrofien fiir das Mini-Fab-Modell

262

C.l Verhalten von Entscheideragenten

273

C.2 Verhaltensauspragung Prepare_Decision_Making

274

TABELLENVERZEICHNIS

XXI

C.3 Verhaltensauspragung Make_Decision

274

C.4 Verhaltensauspragung Inform_DM_Agent

274

C.5 Verhaltensauspragung Start_StafLAgent

275

C.6 Verhaltensauspragung Get_Staff_Agent_Result

275

C.7 Verhaltensauspragung Request_Decision_Making_Agent_Service

276

C.8 Verhaltensauspragung Check_AIL

276

C.9 Verhaltensauspragungen von Dienstagenten

276

C.IO Verhaltensauspragung Prepare_Solution

277

C.ll Auspragung Parameterize_Algorithm

277

C.12 Verhaltensauspragung Solve_orJnterrupt

277

C.13 Auspragung Communicate_Solution

278

Kapitel 1 Einleitung 1.1

Motivation

Die Optimierung der operationellen Ablaufe in komplexen Produktionssystemen hat in den letzten Jahren sowohl im akademischen Umfeld als auch bei Praktikern grofie Beachtung gefunden. So bezeichnet Mertens [141] die anwendungsbezogene Umsetzung von Methoden der Informatik und des Operations Research (OR) als eine der Kernaufgaben der Wirtschaftsinformatik. Neben zentralen Verfahren des Operations Research und Prioritatsregelansatzen als Beispiele fiir einfache dezentrale Verfahren werden zunehmend moderne dezentrale und hybride Verfahren eingesetzt, die u.a. Softcomputingtechniken und Verhandlungs- und Marktmechanismen zur Losung der Maschinenbelegungsprobleme verwenden. Die Verfahren mit dezentraler Philosophie erfordern die Entwicklung von Koordinationsmechanismen. In [198] wird festgestellt, "dass Unternehmen als integrierte, in sich arbeitsteilige Gebilde nur dann ein Existenzrecht haben, wenn sie in ihrem Binnenbereich die mit jeder arbeitsteiligen Leistungserstellung verbundenen Koordinationsprobleme besser losen konnen als bei einer Abwicklung mit externen Partnern iiber den Markt". Bei der Entwicklung neuartiger Steuerungsalgorithmen, die autonome und kooperative Steuerungsentscheidungen ermoglichen, miissen die erweiterten soft- und hardwaretechnischen Moglichkeiten geeignet beriicksichtigt werden. Komplexe Produktionsprozesse [188] sind u.a. durch • einen zeithch veranderUchen Produktmix, • einen Mix unterschiedhcher Prozesstypen (z.B. Batchprozesse), • vorgeschriebene Kundenendtermine, • eine hohe Komplexitat der Arbeitsplane, • reihenfolgeabhangige Umriistzeiten, • par allele Maschinen, • sekundare Ressourcen

2

KAPITEL 1.

EINLEITUNG

gekennzeichnet. Weiterhin sind externe Storungen in Form von Veranderungen von Kundenendterminen und interne Storungen durch Maschinenausfalle typisch. Ein Produktionssystem besteht aus dem Basissystem, welches durch Ressourcen gebildet wird, und aus dem Steuerungssystem. Produktionsprozesse beschreiben die Inanspruchnahme von Ressourcen des Basissystems in Folge von Entscheidungen des Steuerungssystems im zeithchen Verlauf. Demzufolge kann ein Produktionsprozess in einen Basisprozess und einen Steuerungsprozess unterteilt werden. Komplexe Systeme werden in der Systemtheorie allgemein als Systeme von Subsystemen definiert [144]. Komplexe Produktionssysteme setzen sich, einer raumlichen und arbeitsorganisatorischen Dekomposition folgend, aus Produktionsbereichen zusammen. Ein einzelner Produktionsbereich ist durch eine bestimmte Anzahl von Gruppen paralleler Maschinen gekennzeichnet. Eine Domanenanalyse fiir die Herstellung integrierter Schaltkreise als speziellen komplexen Produktionsprozess ist in [149] vorgenommen worden. Der Einsatz zentral orientierter Planungsund Steuerungsmethoden ist erschwert bzw. nicht moglich. In der Arbeit wird ein verteiltes hierarchisches Framework zur Steuerung komplexer Produktionssysteme, im Weiteren als Framework bezeichnet, vorgeschlagen, das die Vorteile dezentraler Ansatze mit den Vorteilen einer zentralen Steuerung verbindet. Mit der vorliegenden Arbeit werden drei Ziele verfolgt: 1. Es wird dargestellt, wie die Theorie der verteilten hierarchischen Entscheidungsfindung fiir die Steuerung komplexer Produktionsprozesse angewandt werden kann. Wahrend in der Literatur das Problem der Steuerung einzelner Maschinengruppen oder Produktionsbereiche eines komplexen Produktionssystems haufig untersucht wird, werden in dieser Arbeit Forschungsarbeiten beschrieben, die das Problem der Steuerung eines ganzen Produktionsunternehmens zum Gegenstand haben. 2. Es wird gezeigt, dass das vorgeschlagene hierarchische Steuerungssystem in natiirlicher Art und Weise als Multi-Agenten-System implementiert werden kann. 3. Es werden OR- und Kl-Verfahren vorgeschlagen, die optimierende und koordinierende Eigenschaften des vorgeschlagenen Steuerungsansatzes sicherstellen und als Dienstagenten im Multi-Agenten-System fungieren. Weiterhin wird eine Leistungsbewertung des vorgeschlagenen Frameworks vorgenonmien.

1.2

Methodisches Vorgehen

Die Problemstellung ist Ausgangspunkt und bedeutendes Strukturmerkmal einer Theorie (Schneider [225]). Eine Problemstellung besteht aus einer Forschungsfrage und einer Losungsidee fiir die gestellte Frage. Weitere Strukturmerkmale einer Theorie sind ein Strukturkern, der die Formulierung der Problemlosungsidee in einem Modell darstellt, sowie Musterbeispiele als Anwendungsfalle

1.3. PROBLEMSTELLUNG

3

der Problemlosungsidee [225]. Unter einer Forschungsmethodik versteht Schneider dabei ein systematisches, auf einem System von Regeln aufbauendes Verfahren zur Theoriebildung. Da Modelle auf Annahmen beruhen, die von der Realitat abweichen konnen, sind nach Ansicht von Porter [202] Frameworks besser geeignet, Praxisunterstiitzung zu geben. Unter einem Framework wird eine Rahmenstruktur verstanden, die mit dem Ziel entworfen wird, eine bestimmte Betrachtungsweise auf ein zu losendes Problem zu unterstiitzen. Eine Konstruktion von Frameworks erfolgt unter Verwendung von Modellen und Konzepten. Frameworks bieten eine breite umfassende Problembeschreibung gemeinsam mit Strukturierungsinstrumenten an, die geeignet sind, der Komplexitat in Unternehmungen gerecht zu werden [181]. In den durchgefiihrten Forschungsarbeiten wird der Frameworkgedanke aufgegriffen. In einer Analysephase wird zunachst das zu losende Steuerungsproblem untersucht und eine auf der Theorie der verteilten hierarchischen Steuerung [224] basierende Losungsidee entwickelt. In einem weiteren Schritt erfolgt die Abstraktion zu einem Framework fiir komplexe Produktionssysteme und dessen konzeptionelle softwaretechnische Umsetzung mit Softwareagenten. Das entwickelte Framework wird empirisch auf die Steuerung der Herstellung integrierter Schaltkreise angewandt, indem ein entsprechender Prototyp implementiert wird und dann simulationsbasiert die Wirkung des verfolgten Steuerungsansatzes auf eine Halbleiterfabrik untersucht wird. Dieses Vorgehen steht in Einklang mit der von Heinzl [94] geforderten Erganzung des in der Wirtschaftsinformatik vorherrschenden konstruktiven Paradigmas durch empirische Analysen.

1.3

Problemstellung

Trotz der sich in den letzten Jahren voUzogenen Entwicklungen in Theorie und Praxis sind fur komplexe Produktionssysteme die folgenden Fragen von aufierordentlichem Interesse [226, 20]: • Wann soUen wie viele Lose (vergleiche Abschnitt 3.2 fiir den zugrunde gelegten Losbegriff) als unteilbare, dynamische Systemeinheiten in das komplexe Produktionssystem eingesteuert werden? • Wie soil die Zuteilung von Losen zu alternativen Maschinen erfolgen? • In welcher Reihenfolge soUen Lose bearbeitet werden, um Ziele wie hohe Liefertermineinhaltung bei hochstmoglicher Kapazitatsauslastung zu erreichen? Gleichzeitig sind alle technologischen Restriktionen komplexer Produktionssysteme zu beriicksichtigen. In der Praxis sind zentrale Implementierungen von fast voUstandig "heterarchischen" Steuerungen, d.h. Anwendung von geeigneten Prioritatsregeln, anzutreflFen. Prioritatsregelbasierte Steuerungssysteme verwenden zur Entscheidungsfindung haufig Informationen, die sich ausschliefilich auf Lose im Warteraum vor der zu belegenden Maschine beziehen. In diesem Sinne werden Maschinenbelegungsentscheidungen auf Basis lokaler Informationen getroffen. Erfahrene, mit Produktionssteue-

4

KAPITELl.

EINLEITUNG

rungsaufgaben betraute Personen koordinieren die zeitlich und raumlich isolierten Maschinenbelegungsentscheidungen. Typische Koordinationsprobleme sind die Batch- und Riistoptimierung (vergleiche Abschnitt 3.2 fiir den in dieser Arbeit verwendeten Batchbegriff), die Steuerung von geplanten und dynamischen Engpassen, die Einbeziehung von vorbeugenden Instandhaltungsmai3nahmen in die Produktionssteuerung und die Behandlung von internen und externen Storungen [149]. Der Einsatz von Operations-Research-Methoden und Methoden der Kiinstlichen Intelligenz (KI) befindet sich z.B. in der Fertigung integrierter Schaltkreise erst am Anfang (vergleiche dazu Uzsoy, Lee und Martin-Vega [249, 250] und Schomig und Fowler [226]). Diese Situation wird insbesondere unter dem Aspekt einer zunehmenden Automatisierung der Produktionssysteme als unbefriedigend empfunden. Die Steuerung komplexer Produktionsprozesse kann durch Losung einer Folge von Entscheidungsproblemen im zeitlichen Ablauf beschrieben werden. In komplexen Produktionssystemen findet die Losung von Entscheidungsproblemen raumlich und zeitlich verteilt statt. Die verteilten Entscheidungen haben unterschiedlichen Stellenwert im System der Produktionssteuerung, aus diesem Grund erscheint eine hierarchische, asymmetrische Strukturierung der zu losenden Entscheidungsprobleme als angemessen. Die Steuerung komplexer Produktionsprozesse kann folglich als Design und Koordinierung von miteinander verbundenen Entscheidungen aufgefasst werden [224]. Die Defizite vorhandener hierarchischer Steuerungsansatze fiir komplexe Produktionssysteme [238, 254, 255] bestehen in einer fehlenden Beriicksichtigung terminorientierter Steuerungsziele und der fehlenden Moglichkeit, die auftretenden Steuerungsprobleme nebenlaufig zu losen. Hierarchische Steuerungssysteme konnen agentenbasiert implementiert werden [223]. Agenten sind Softwareeinheiten, die autonom Entscheidungen treffen konnen und iiber Kommunikationsmoglichkeiten verfiigen [113, 72]. Auf Grund dieser Eigenschaften sind aus Agenten bestehende Softwaresysteme ("Multi-Agenten-Systeme") zur Implementierung von verteilten hierarchischen Steuerungssystemen in natiirlicher Art und Weise geeignet, wenn es gelingt, die Optimierungs- und Koordinationsfahigkeiten von Multi-Agenten-Systemen durch Ergebnisse der Theorie verteilter hierarchischer Entscheidungen und durch OR- und Kl-Verfahren anzureichern. Auf diese Art und Weise kann die Liicke zwischen der Theorie hierarchischer Entscheidungen [143, 144, 224] und deren fehlender softwaretechnischer Umsetzung geschlossen werden und ein Beitrag zur Fundierung von Multi-Agenten-Systemen geleistet werden. Aufbauend auf der durchgefiihrten Domanenanalyse wurden die folgenden Thesen aufgestellt: 1. Ein Verzicht auf jede Form von Hierarchie liefert keine besseren Ergebnisse als die derzeit dominierenden prioritatsregelbasierten Ansatze. Um ein unter globalen Gesichtspunkten giinstiges Verhalten des Produktionssystems zu gewahrleisten, sind zentrale Elemente in die Steuerung einzubeziehen. Entscheidungen iibergeordneter Ebenen stellen lediglich einen Rahmen fiir die Entscheidungen untergeordneter Steuerungsebenen dar. 2. Die in klassischen hierarchischen Steuerungsansatzen vorhandene Stratifikation, Staffelung und zeitliche Dekomposition der entscheidungsfahigen Einheiten konnen als Basis fiir die Verteilung der SteuerungsfunktionaHtat benutzt werden.

1.4. ERGEBNISSE DER ARBEIT

5

3. Die Theorie der Koordination muss weiterentwickelt werden. Es ist eine Koordinationssprache zu entwickeln, welche die im Zuge der Stratifikation und Staffelung entstandenen Entscheidungseinheiten informationstechnisch miteinander verbindet. 4. Neben entscheidungsfahigen Einheiten ("Entscheideragenten") miissen Softwareeinheiten ("Dienstagenten") betrachtet werden, die geeignet weiterzuentwickelnde OR- und KIMethoden fiir komplexe Produktionssysteme kapseln.

1.4 1.4.1

Ergebnisse der Arbeit Anforderungen an Steuerungsansatze

In der Arbeit werden zunachst Steuerungsansatze des Operations Research und der Kiinstlichen Intelligenz diskutiert. Zentrale Verfahren des Operations Research haben den Vorteil, dass sie in Richtung der Erreichung eines global giinstigen Systemverhaltens wirken. AUerdings sind die Laufzeit und der Aufwand zur Datenbereitstellung haufig zu hoch. Prioritatsregeln als Beispiel fiir dezentrale Operations-Research-Verfahren haben den entscheidenden Nachteil, dass sie haufig Entscheidungen ausschliefilich unter Verwendung von lokalen Informationen treffen. Verfahren der Kiinstlichen Intelligenz konnen gewohnlich besser als Operations-ResearchVerfahren mit unsicheren Informationen, dynamisch veranderlichen Prozessbedingungen und der Problemkomplexitat umgehen. Verfahren der Kiinstlichen Intelligenz unterstiitzen besser die Erreichung eines adaptiven Systemverhaltens. Probleme bereitet aber der Verzicht auf die Forderung, optimale Losungen bereitzustellen. Verfahren der Kiinstlichen InteUigenz erfordern als heuristische Verfahren haufig einen grol3en Parametrisierungsaufwand. Fiir die Steuerung komplexer Produktionssysteme miissen Verfahren entwickelt werden, die globale Ziele in die Entscheidungsfindung einbeziehen. Eine raumliche und zeitliche Dekomposition des zu losenden Steuerungsproblems muss vorgenommen werden. Die Dekomposition hat die Aufgabe, fiir eine Rechenbarkeit des Steuerungsproblems bei einer hinreichenden Losungsqualitat zu sorgen. Rechenbarkeit wird durch Aggregation und durch Verteilung der Berechnungen auf mehrere Prozessoren erreicht. Aggregation und Verteilung fiihren zu einem verteilten hierarchischen S teuerungsansatz.

1.4.2

Framework zur verteilten hierarchischen Steuerung

1.4.2.1

Modellsystem fur eine verteilte hierarchische Steuerung

Hierarchische Steuerungssysteme ordnen die zu losenden Entscheidungsaufgaben unterschiedlichen Ebenen zu, die in einer Feedback- und gegebenenfalls Feedforwardbeziehung stehen. Dabei gilt, dass in der Hierarchic iibergeordnete Ebenen zur Beeinflussung von umfangreicheren Teilen des Gesamtprozesses dienen. Ubergeordnete Ebenen haben langere Entscheidungsperioden

6

KAPITEL 1.

EINLEITUNG

und beschaftigen sich mit „langsameren" Aspekten des zu steuernden Prozesses. Somit steht auf ubergeordneten Ebenen haufig mehr Zeit zur Entscheidungsfindung zur Verfiigung. Die Entscheidungsprobleme iibergeordneter Ebenen sind weniger strukturiert, enthalten in starkerem Mafie Unsicherheiten und sind schwieriger quantitativ zu formalisieren [143]. Jede Hierarchieebene wird durch • ein Modell des zu steuernden Prozesssegmentes, • eine Menge von Entscheidungskriterien, • einen Alternativenraum, • einen bestimmten Informationsstatus beschrieben. Die Ebenen sind durch Kopplungsgleichungen verbunden. Fiir komplexe Produktionssysteme wird ein aus drei Ebenen bestehendes Steuerungssystem vorgeschlagen. Die einzelnen Ebenen dienen in dieser Reihenfolge der Terminierung von Losen, der detaillierten Maschinenbelegungsplanung auf Basis der Terminierungsvorgaben sowie der Implementierung der ermittelten Ablaufplane auf der untersten Hierarchieebene. 1.4.2.2

Produktionssystemsteuerungsebene

Die obere Ebene der vorgeschlagenen Hierarchic verwendet zur Entscheidungsfindung ein aggregiertes Modell. Die Aggregation wird erreicht, indem aufeinanderfolgende in einem Produktionsbereich auszufiihrende Arbeitsgange (im Folgenden synonym als Prozess-Schritte bezeichnet) zu Makroarbeitsgangen (synonym auch Operationen genannt) zusammengefasst werden. Das Terminierungsproblem kann als Optimierungsproblem mit binaren Variablen und periodengenauer Auflosung zur Minimierung der gewichteten Verspatung der Lose formuliert werden. Die obere Ebene des hierarchischen Ansatzes liefert Vorgaben fiir den zeitlichen Durchlauf der Lose durch das komplexe Produktionssystem entsprechend der Segmentierung des Produktionssystems in Produktionsbereiche. Es wird ein Modell des (geplanten) Engpassproduktionsbereichs bei der Entscheidungsfindung der oberen Ebene beriicksichtigt. 1.4.2.3

Produktionsbereichssteuerungsebene

Die mittlere Steuerungsebene dient der Steuerung einzelner Produktionsbereiche. Dafiir werden disjunktive Graphenmodelle fiir die einzelnen Produktionsbereiche beschrieben. In diesen Modellen werden die Starttermine und die geplanten Endtermine fiir die Lose aus den Terminvorgaben der oberen Ebene ermittelt. Ein ganzzahfiges Optimierungsmodell zur Minimierung der gewichteten Verspatung der Lose innerhalb eines Produktionsbereichs bezuglich der Vorgaben der Produktionssystemsteuerungsebene wird beschrieben. Durch die Terminvorgaben der Produktionssystemsteuerungsebene wird der Alternativenraum des Entscheidungsproblems fiir eine einzelne Steuerungseinheit der Produktionsbereichssteuerungsebene eingeschrankt. Dieses Vorgehen ermoglicht die

1.4. ERGEBNISSE DER ARBEIT

7

Losung von Koordinationsproblemen der Batch- und Riistoptimierung. Eine Losung des Problems einer koordinierten Steuerung von Engpassmaschinengruppen wird durch die maschinengruppenubergreifende Betrachtungsweise ebenfalls betrachtlich erleichtert. Die Schedulingprobleme fur die Produktionsbereiche werden verteilt gelost, da die Vorgaben der oberen Steuerungsebene in Form von Start- und Endterminen fiir eine Entkopplung der zu losenden Probleme sorgen. Es findet eine produktionsbereichsiibergreifende Koordination statt, indem die durch die Ablaufplane bereitgestellten frlihesten Verfiigbarkeitstermine der Lose zwischen den Produktionsbereichen ausgetauscht werden und so auf iterative Weise giinstigere Maschinenbelegungen beziigUch der absoluten gewichteten Verspatung der Lose des Produktionsbereichs ermittelt werden. Die obere und mittlere Steuerungsebene steuern zusammen das komplexe Produktionssystem in kooperativer Art und Weise. Die Steuerung der einzelnen Produktionsbereiche erfolgt autonom, da die Berechnung der Ablaufplane lediglich grobe terminliche Vorgaben der oberen Steuerungsschicht beriicksichtigen muss.

1.4.2.4

Maschinengruppensteuerungsebene

Die untere Steuerungsebene dient der Implementierung der Ablaufplane durch Maschinengruppen. Es wird ein ereignis-diskretes Modell angenommen, das wesentliche, fiir das komplexe Produktionssystem charakteristische Ereignisse (Statusanderungen von Losen und Maschinen) enthalt. Das Modell wird in regelmafiigen Abstanden aktualisiert. Es werden Vorgaben der mittleren Ebene in Form von detaillierten Ablaufplanen zur Maschinenbelegung verwendet. Falls diese Ablaufplane nicht giiltig sind, wird alternativ ein kontraktnetzartiges AUokationsverfahren zur Maschinenbelegung verwendet. Dieses Verfahren beriicksichtigt nur zeitlich und ortlich lokale Daten bei der Entscheidungsfindung. Auf dieser Steuerungsebene wird ebenfalls die Wahrung der Autonomic der entscheidungsfahigen Einheiten deutlich. Den Ablaufplanen der Produktionsbereiche wird nur solange gefolgt, wie diese giiltig sind. In der gegenteiligen Situation werden autonom Maschinenbelegungsentscheidungen getroffen.

1.4.2.5

Verteiltes hierarchisches Steuerungskonzept

Das vorgeschlagene Steuerungskonzept kann wie folgt beschrieben werden: 1. Terminierung der im Produktionssystem befindlichen bzw. der innerhalb des Terminierungszeitraums eintreffenden Lose entsprechend einer fest gewahlten Strategic, 2. Antizipation des Verhaltens des Engpassproduktionsbereichs unter dem Einfluss der Terminierungsstrategie, 3. Falls das antizipierte Verhalten des Engpassproduktionsbereichs nicht akzeptabel ist, wird in Schritt 1 die Terminierungsstrategie verandert. Andernfalls wird zu Schritt 4 verzweigt,

8

KAPITELl.

EINLEITUNG

4. Ubermittlung der Terminvorgaben fiir die Lose an die Produktionsbereichssteuerungsebene. Berechnung von detaillierten Ablaufplanen fiir die Lose aller Produktionsbereiche, 5. Ubermittlung der durch die Ablaufplane bereitgestellten Termine an die anderen Entscheidungseinheiten der Produktionsbereichssteuerungsebene. Berechnung neuer Ablaufplane unter Beriicksichtigung der modifizierten Termine, 6. Ubermittlung der zu implementierenden Ablaufplane an die Maschinengruppensteuerungsebene, 7. Implementierung dieser Ablaufplane im Produktionsprozess. Falls die Ablaufplane ungiiltig sind, wird verhandlungsbasiert zwischen Losen und Maschinen eine Maschinenbelegung ausgehandelt. Der gewahlte Ansatz unterscheidet sich von anderen bereits untersuchten hierarchischen Ansatzen dadurch, dass Koordination zwischen den Entscheidungseinheiten der mittleren Steuerungsebene stattfindet, dass terminorientierte Entscheidungskriterien verwendet werden und dass ein verteiltes Losen der auftretenden Entscheidungsprobleme moglich ist. 1.4.2.6

Diskussion der verfolgten betriebswirtschaftlichen Ziele

In der Kegel ist es auf Grund von Operationalisierungsproblemen nicht moglich, die Auswirkungen einzelner ScheduHngentscheidungen auf die Kosten zu bestimmen [41]. Aus diesem Grund erfolgt typischerweise eine Substitution der Kosten durch entsprechende ZeitgroBen. In der Arbeit werden Produktionssysteme untersucht, in denen auf Grund von Kundenanforderungen Lose mit unterschiedlicher Prioritat (auch als Losgewicht bezeichnet) vorhanden sind. Es wird das Ziel verfolgt, die totale gewichtete Verspatung (Terminiiberschreitung) der eingesteuerten Lose zu minimieren. Die totale gewichtete Verspatung der Lose ergibt sich durch Summation der gewichteten Verspatung der einzelnen Lose. Diese Zielgrofie stellt ein spezielles terminorientiertes Ziel dar [51]. Die terminorientierten Ziele werden als Ersatzgr6i3en fiir erfolgsorientierte Ziele verwendet, da diese haufig schwierig zu interpretieren sind. Es ist aber moglich, die totale gewichtete Verspatung als Kostenziel zu betrachten. Die Gewichte der einzelnen Lose stellen dann z.B. die Strafkosten fiir verspatete Lose dar. Gleichzeitig werden in dieser Arbeit die prozessokonomischen Zielgrofien („Ingenieurziele") Durchlaufzeit und Durchsatz (Anzahl fertiggestellter Lose) beobachtet, die aber nicht die primaren Steuerungsziele darstellen. Ausgehend von dem Ziel, die gewichtete Verspatung der Lose zu minimieren, werden Ziele fiir die untergeordneten Hierarchieebenen abgeleitet. Fiir die Produktionsbereichssteuerungsebene fiihrt das zu dem Ziel, die totale gewichtete Verspatung der Lose beziiglich der geplanten Fertigstellungstermine fiir den jeweiHgen Produktionsbereich zu minimieren. Dieses Ziel wirkt in Richtung der Erfiillung des Zieles, die gewichtete Verspatung der Lose beziiglich der geplanten Fertigstellungstermine (auf der Ebene des Produktionssystems) zu minimieren. Auf der Maschinengruppensteuerungsebene wird das Ziel verfolgt, den Ablaufplanen der mittleren Hierarchieebene so weit

1.4. ERGEBNISSE DER ARBEIT

9

wie moglich zu folgen. Falls das nicht moglich ist, werden losbezogene Zielfunktionen betrachtet, die einen Kompromiss zwischen terminlicher Dringlichkeit und Auslastung der Maschinen suchen.

1.4.3

Agentifizierung des Steuerungsansatzes

Unter Benutzung der PROSA-Referenzarchitektur fiir holonische Produktionssysteme [251] wird die zur (softwaretechnischen) Realisierung des geforderten Steuerungsverhaltens notwendige Agentenhierarchie abgeleitet. Entscheideragenten werden den Stratifikations- und Staffelungselementen zugeordnet und sind fiir die Entscheidungsfindung der durch sie reprasentierten dynamischen und statischen Systembestandteile zustandig. Produktionssystemagenten, Produktionsbereichsagenten, Maschinengruppenagenten, Losagenten, Batchagenten und Agenten zur Reprasentation von vorbeugenden Instandhaltungsauftragen werden verwendet. Die Identifikation der Agenten erfolgt unter Beriicksichtigung des zu losenden Steuerungsproblems. Jeder Agent kann unterschiedliche Rollen einnehmen [177]. Dabei wird einzelnes Verhalten durch eine Zustandsmenge und Zustandstransitionen beschrieben. Bei der Losung der Entscheidungsprobleme werden die Entscheideragenten durch Dienstagenten unterstiitzt, welche die notwendige Scheduling- und Monitoringfunktionalitat kapseln. WesentUcher Vorteil der Betrachtung von Entscheider- und Dienstagenten ist eine Entkopplung der Struktur des Steuerungssystems von den Steuerungsalgorithmen. Die Dienstagenten dienen als generische Container fiir OR- und KI-Algorithmen. Eine prototypische agentenbasierte Implementierung des hierarchisch organisierten Steuerungssystems unter Verwendung der Programmiersprachen C-l-l- und C # sowie der .NET-Middleware wurde in [167] beschrieben.

1.4.4

Steuerungsalgorithmen fiir komplexe Produktionssysteme

1.4.4.1

Algorithmen fiir die Produktionssystemsteuerungsebene

Die Produktionssystemsteuerungsebene arbeitet auf einem aggregierten Modell. Das verwendete Modell beriicksichtigt ledigUch Kapazitaten von Maschinengruppen anstelle von Kapgtzitaten fur einzelne Maschinen. Es werden Start- und Endtermine fiir Operationen bestimmt. Operationen entstehen durch Zusammenfassung von aufeinanderfolgenden Prozess-Schritten entsprechend der raumhchen Unterteilung des komplexen Produktionssystems in Produktionsbereiche. Ein BeamSearch-Algorithmus wird zur Terminierung der Lose vorgeschlagen. Alternativ wird ein iteratives simulationsbasiertes Verfahren beschrieben, das Abschatzungen fiir die Wartezeiten der Lose auf Bearbeitung ermittelt. Beide Verfahren haben den Vorteil, dass sie die endlichen Kapazitaten des Produktionssystems beriicksichtigen.

10

KAPITELl.

1.4.4.2

EINLEITUNG

Algorithmen fiir die Produktionsbereichssteuerungsebene

Die Produktionsbereichssteuerungsebene stellt detaillierte Ablaufplane fur die einzelnen Produktionsbereiche bereit. Zur Ermittlung der Ablaufplane wird die Shifting-Bottleneck-Heuristik verwendet. Die Shifting-Bottleneck-Heuristik ist ein Dekompositionsverfahren, das das zu losende Maschinenbelegungsproblem in Belegungsprobleme fiir Maschinengruppen aufteilt. Die Sicht auf das zu losende Gesamtproblem bleibt durch die Verwendung eines disjunktiven Graphen (vergleiche [51, 199] fiir das Konzept disjunktiver Graphen in der Maschinenbelegungsplanung) erhalten, der zur Berechnung von geplanten Fertigstellungsterminen und Ankunftszeiten fiir die Lose an den Maschinengruppen verwendet wird. In der Arbeit wird eine verteilte Variante der Shifting-Bottleneck-Heuristik entwickelt. Die Verteilung wird durch die Terminvorgaben der Produktionssystemsteuerungsebene ermoglicht. Zwischen den einzelnen Produktionsbereichen werden Informationen iiber die tatsachUch notwendigen Start- und Endtermine der Lose auf iterative Art und Weise ausgetauscht. Die vorgeschlagene verteilte Shifting-Bottleneck-Heuristik hat gegeniiber der herkommlichen Shifting-Bottleneck-Heuristik den Vorteil, dass auf Grund des hierarchischen Ansatzes giinstigere Ankunftszeiten und geplante Fertigstellungszeiten ermittelt werden als bei alleiniger Anwendung des disjunktiven Graphen. Aufierdem kann die neuartige Heuristik auf mehrere Prozessoren verteilt werden.

1.4.4.3

Algorithmen fur die Maschinengruppensteuerungsebene

Falls die durch die Produktionsbereichssteuerungsebene ermittelten Ablaufplane nicht giiltig sind, wird das in [162] beschriebene kontraktnetzartige AUokationsverfahren zur Maschinenbelegung verwendet. Das vorgeschlagene Verfahren ordnet jedem Los ein auf Basis von Maschinenstundensatzen ermitteltes Budget zu. Bei der Ausfiihrung eines bestimmten Prozess-Schrittes auf einer Maschine wird das Budget des Loses una die fiir die Bearbeitung auf der Maschine anfallenden Kosten reduziert. In Simulationsstudien [163] konnte gezeigt werden, dass sich das AUokationsverfahren besonders in Produktionssystemen mit Storungen besser beziiglich terminorientierter Leistungsmafie verhalt als Prioritatsregeln.

1.4.5 1.4.5.1

Koordination in verteilten hierarchischen Steuerungssystemen Koordinationsmechanismen

Unter Koordination wird in dieser Arbeit eine direkte Einflussnahme auf unterschiedhche Systembestandteile mit dem Ziel eines integrierten, harmonischen Zusammenwirkens verstanden [143]. Entsprechend der Unterteilung von Steuerungsansatzen wird zwischen zentraler, hierarchischer und dezentraler Koordination unterschieden. Zentrale Koordination bedeutet, dass Teilprobleme zu einem Gesamtproblem zusammengefasst werden und dieses dann gelost wird. Hierarchische Koordination umfasst Koordination durch

1.4. ERGEBNISSE DER ARBEIT

11

Vorgaben, Koordination durch Rtickkopplung sowie Koordination durch wechselseitige (iterative) Abstimmung. Dezentrale Koordination ist eng verwandt mit der wechselseitigen Abstimmung. Es wird zwischen direkter und indirekter dezentraler Koordination unterschieden. Vertreter der direkten Koordination sind Kontraktnetzverfahren. Eine indirekte Koordination liegt zum Beispiel bei der Anwendung von Marktmechanismen vor. In dieser Arbeit werden als Koordinationsmechanismen hierarchische Koordination mit Riickkopplung bzw. hierarchische Koordination durch wechselseitige Abstimmung verwendet. In Ausnahmesituationen findet direkte dezentrale Koordination Anwendung.

1.4.5.2

Ontologie zur Steuerung komplexer Produktionssysteme

Die fiir verteilte hierarchische Steuerungssysteme typischen Feedforward- und Feedbackzyklen zwischen den stratifizierten Entscheidungseinheiten und die Koordinationsaktivitaten zwischen den gestaffelten Entscheidungseinheiten erfordern eine rechneriibergreifende Kommunikation auf Basis von Middleware. Auf Grund der Aufteilung der Steuerungsfunktionalitat auf mehrere Rechner ist eine nachrichtenbasierte Kommunikation erforderlich. Dazu ist in einem ersten Schritt die Festlegung einer Ontologie notwendig, die eine fiir alle Kommunikationspartner verfiigbare Interpretationsvorschrift fiir iibermittelte Daten zur Verfugung stellt. Der Entwurf einer domanendedizierten Ontologie fiir die Domane der Fertigung integrierter Schaltkreise wurde in [164] beschrieben. Die Ontologie enthalt Domanenkonzepte wie beispielsweise Ressourcen in unterschiedlichem Aggregationsgrad, Produkte und Ablaufplane. Neben den Domanenkonzepten wurden Agentenaktivitaten und Pradikate in die Ontologie aufgenommen.

1.4.5.3

Contentsprache zur Steuerung komplexer Produktionssysteme

Auf semantischer Ebene ist die Entwicklung einer Contentsprache erforderlich, die semantisch sinnvoUe Kommunikationsinhalte unter Verwendung des durch die Ontologie bereitgestellten Vokabulars beschreibt. Eine Contentsprache wurde in [165] beschrieben. Die grundlegende Idee dieser Sprache besteht darin, eine kontextfreie Grammatik zu entwickeln. Die Grammatik verwendet die in XML-Objekte konvertierten Instanzen der Ontologieklassen.

1.4.5.4

Koordinationssprache fur eine verteilte hierarchische Steuerung

Im letzten Schritt muss das dynamische Verhalten der an der Kommunikation beteiUgten Einheiten durch InteraktionsprotokoUe beschrieben werden. Das Tripel (O, C , / P ) , bestehend aus einer Ontologie O, einer Contentsprache C und einer Menge IP von InteraktionsprotokoUen fiir die Einheiten des Steuerungssystems, wird als Koordinationssprache bezeichnet. Unter einem InteraktionsprotokoU wird eine Menge von auf Sprechakten beruhenden Konversationen verstanden,

12

KAPITELl.

EINLEITUNG

die in einer wohldefinierten Ordnung durchlaufen werden. Jeder Sprechakt besitzt einen Contentausdruck, der entsprechend der Grammatik aufgebaut ist. Mit Hilfe der Koordinationssprache konnen die Entscheideragenten unter Verwendung der Monitoringagenten Ausnahmesituationen erkennen und ein geeignetes verteiltes Scheduling- und Reschedulingverhalten realisieren.

1.4.6

Architektur eines verteilten hierarchischen Steuerungssystems

Es wurde ein agentenbasierter Prototyp geschaffen, der den verteilten hierarchischen Steuerungsansatz implementiert. Die Systemarchitektur umfasst: • eine Architektur fiir Einzelagenten, • eine Infrastruktur zur Abbildung hierarchisch organisierter Multi-Agenten-Systeme, • Moglichkeiten zur Implementierung von Kommunikation und Koordination, • eine generische Architektur fiir Entscheider- und Dienstagenten. Entscheideragenten zur Realisierung des Steuerungsansatzes haben die folgenden Aufgaben zu

• Vorbereiten

von Entscheidungen

(z.B. situationsabhangige

Wahl von

Parametern

fiir die Nutzung von Dienstagentenfunktionalitat, Auswahl einer geeigneten Dienstagentenfunktionalitat), • Entscheidungsfindung, • Ausfiihren von der Entscheidungsfindung nachgelagerten Aktivitaten (z.B. Informieren anderer Agenten liber das Entscheidungsergebnis), • sachgerechte Behandlung von Problemen und Ausnahmen, die wahrend des Entscheidungsfindungsprozesses auftreten. Dienstagenten haben die nachfolgenden Aufgaben zu losen: • Problemlosung vorbereiten (Berechnung interner Parameter des Losungsverfahrens, Versorgung des Losungsverfahrens mit Daten und Parametern), • Losung des Problems, • Abbruch eines Losungsvorganges zu bestimmten Zeitpunkten oder in Folge bestimmter Ereignisse, • Information anderer Agenten iiber das Ergebnis der Berechnung.

1.4. ERGEBNISSE DER ARBEIT

1.4.7

13

Leistungsbewertung von Steuerungsverfahren

Eine generische Architektur fiir eine Leistungsbewertung des Frameworks durch simulationsbasierte Emulation des zu steuernden komplexen Produktionsprozesses wurde in [163] vorgeschlagen. Kernidee dieses Ansatzes ist die Verwendung eines diskreten ereignis-orientierten Simulationsmodells zur Identifikation des zu steuernden Produktionsprozesses. Ein derartiges Vorgehen hat den Vorteil, dass zum einen das Basissystem des zu steuernden Produktionssystems in hinreichendem Detaillierungsgrad modelliert werden kann. Andererseits konnen auch dynamische Aspekte des Produktionsprozesses, die im Wesentlichen durch Arbeitsplane beschrieben werden, gut modeUiert werden. Es ist mogUch, das stochastische Verhalten des Produktionssystems in die Leistungsbewertung einzubeziehen. Zur ReaUsierung des Leistungsbewertungsansatzes wurde eine objektorientierte blackboardartige Datenschicht in der Programmiersprache C + + implementiert, die alle relevanten Entitaten des Produktionssystems im Hauptspeicher des Computers vorhalt. Es wird sichergestellt, dass existierende Steuerungsverfahren (z.B. Prioritatsregeln) zu Vergleichszwecken softwaretechnisch effizient in die Leistungsbewertung einbezogen werden konnen. Die Architektur wird zur simulationsbasierten Leistungsbewertung des in der Arbeit beschriebenen hieraxchischen Steuerungsframeworks verwendet. In diesem Buch beziehen sich alle Untersuchungen und alle vorgeschlagenen Verfahren auf komplexe Produktionssysteme. Wenn im Weiteren nur von Produktionssystemen gesprochen wird, sind somit auch komplexe Produktionssysteme gemeint. Die Spezifikation des verteilten Steuerungssystems erfolgt in dieser Arbeit unter Benutzung der Unified-Modelhng-Language (UML) in der in [67] dargestellten Version.

Kapitel 2 Steuerungsansatze fur komplexe Produktionssysteme In diesem Kapitel wird ein allgemeiner System- und Prozessbegriff auf Produktionssysteme und -prozesse angewandt. Anschliefiend werden komplexe Produktionssysteme charakterisiert. Der Begriff der Steuerung von Produktionsprozessen wird eingefiihrt. Steuerungsansatze des Operations Research, der Kiinstlichen Intelligenz und der Regelungstheorie fiir komplexe Produktionssysteme werden erlautert. Darauf aufbauend werden hybride Steuerungsansatze diskutiert. Das Kapitel endet mit der Ableitung von Anforderungen an ein Steuerungssystem fiir komplexe Produktionsprozesse.

2.1

Komplexe Systeme und Prozesse

Ein System wird in der abstrakten Systemtheorie als eine Relation auf Mengen definiert. Ein komplexes System ist definiert als ein System von Systemen, d.h. eine Relation auf einer Menge von Systemen [144]. Prozesse werden in [56] als Abbildungen zwischen Eingangsgrofien X, Ausgangsgrofien Y und Zustanden Z definiert. Analog zum Begriff des komplexen Systems wird der Begriff des komplexen Prozesses eingefiihrt, indem die einen Prozess beschreibende Abbildung auf Familien von Eingangsgrofien, Ausgangsgrofien und Zustanden ausgedehnt wird. Mit einer Aufgabenlosung betraute Systeme werden als zielsuchende Systeme bezeichnet. Zielsuchende Systeme lassen sich in natiirlicher Weise in das Regelkreisparadigma [208, 252] einbetten. Dazu wird zunachst eine Dekomposition des zielsuchenden Systems S in zwei Subsysteme vorgenommen. C bezeichnet das Steuerungssystem und B das Basissystem. Mit M := {m} wird die Menge der moglichen Steuerungsanweisungen, die C an B ubermittelt, bezeichnet. Formal wird das zielsuchende System S durch die beiden Abbildungen C und B beschrieben: C :X xY -^M,

B:MxX-^Y.

16

KAPITEL 2. STEUERUNGSANSATZE

FUR KOMPLEXE

PRODUKTIONSSYSTEME

Die Abbildungen C und B miissen dabei die folgende Konsistenzbedingung mit dem System S erfiillen: es gilt (x, y) E S genau dann, wenn em m e M derart existiert, dass (m, x,y) e B und (x, y,m) eC gilt. In dieser Arbeit wird neben dem Basissystem B und dem Steuerungssystem C jeweils der dazugehorige Basisprozess BP und der dazugehorige Steuerungsprozess PC betrachtet. Der Zusammenhang zwischen den vier Kategorien B, C, PB und PC ist in Abbildung 2.1 dargestellt.

Steuerungssystem C

Basissystem B

Abbildung 2.1: Zusammenhang System und Prozess

2.2

Komplexe Produktionssysteme und -prozesse

In diesem Abschnitt werden die bisher fiir abstrakte komplexe Systeme bzw. Prozesse getatigten Aussagen fiir komplexe Produktionssysteme bzw. Produktionsprozesse konkretisiert. Ziel eines Produktionsprozesses ist die Herstellung von Giitern mit vorgegebenen Eigenschaften zur Deckung eines Verbrauches [41]. Es wird zunachst eine Beschreibung des Basissystems und des Basisprozesses fiir die Produktion vorgenommen. Die Menge der vom Produktionssystem prinzipiell auszufiihrenden Prozess-Schritte wird mit O bezeichnet. Jedem auszufiihrenden Prozess-Schritt muss mindestens eine Maschine, auf der die Bearbeitung stattfinden kann, zugeordnet sein. Weiterhin wird jedem Prozess-Schritt der Erwartungswert der Bearbeitungsdauer auf einer bestimmten Maschine zugeordnet. Die zu bearbeitenden Gegenstande werden als Bearbeitungsobjekte CD bezeichnet. Auf der Menge der auszufiihrenden Prozess-Schritte und der Bearbeitungsobjekte kann die Direkt-Vorganger-Relation RDVCOxOxOD angegeben werden. Es gilt (01,02,0) e RDV fiir die Prozess-Schritte oi und 02 sowie fur das Bearbeitungsobjekt o genau dann, wenn

2.2. KOMPLEXE PRODUKTIONSSYSTEME

UND -PROZESSE

17

1. zur Herstellung von Beaxbeitungsobjekt o die Prozess-Schritte Oi und 02 notwendig sind und 2. Prozess-Schritt oi direkter Vorganger von Prozess-Schritt 02 ist. Bearbeitungsobjekte werden in dieser Arbeit synonym als Lose oder Jobs bezeichnet. Die Struktur des realisierenden Produktionssystems ist durch die Menge der Systemobjekte OP gegeben. In Produktionssystemen sind die wichtigsten Systemobjekte 1. Maschinen, 2. sekundare Ressourcen, d.h. Werkzeuge und andere Hilfsmittel, die zur Bearbeitung von Bearbeitungsobjekten notwendig sind. Die Systemobjekte des Produktionssystems seien durch die Familie von Maschinen {rrii \ i = 1 , . . . , n} gegeben. Maschine rrii ist in der Lage, die Prozess-Schritte {on,..., Oifc.} auszuftihren. Auf der Menge der Systemobjekte und der Bearbeitungsobjekte wird die Direkt-Uberfiihrungsrelation

RDT

COPxOPxOD

eingefiihrt. Fiir die Systemeinheiten mi und m2 sowie fiir das Bearbeitungsobjekt o gilt (mi,7712,0) e RDT genau dann, wenn Systemeinheit mi das Bearbeitungsobjekt o direkt an Systemeinheit m2 iibergibt. Fiir die Beschreibung des Basissystems ist die Angabe der Menge der Arbeitsplane ausreichend. Im Sinne der in Abschnitt 2.1 gegebenen Definition werden die Arbeitsplane als Relationen iiber den Prozess-Schritten, denen andererseits eine nichtleere Menge von Systemobjekten (Maschinen) zugeordnet sind, betrachtet. Es wird angenommen, dass die maximale Lange eines Arbeitsplanes rio betragt. Dann ist die Menge aller Arbeitsplane AP als Relation iiber {X^i{O,0}}

aufzufassen.

Es gilt somit AP C {Xgi{O,0}}. Ein Produktionsprozess besteht aus Elementarprozessen, die auf der Direkt-Vorganger-Relation RDV fiir Prozess-Schritte aufbauen. Ein Elementarprozess fiir ein Bearbeitungsobjekt 0 wird durch die Abbildung Po'.OoXZo^ZoX

Oo

(2.1)

beschrieben. Dabei bezeichnet Oo die Menge der Prozess-Schritte, die fiir das Bearbeitungsobjekt o auszuftihren sind. Mit Zo sei die Menge der Zustande von Bearbeitungsobjekt 0 bezeichnet. Es sind die folgenden Zustande z moglich: Ze

{WoJo^Po}

mit Wo'. Prozess-Schritt wartet auf Bearbeitung, fo'. Prozess-Schritt wurde bearbeitet, po'. Prozess-Schritt befindet sich in Bearbeitung.

18

KAPITEL 2. STEUERUNGSANSATZE

FUR KOMPLEXE

PRODUKTIONSSYSTEME

Umgekehrt kann durch die Abbildung Po,m :OPxZm-^ZmXOP

(2.2)

ein Elementarprozess fiir das Bearbeitungsobjekt o aus Sicht des Systemelements m beschrieben werden. Die folgenden Zustande z e Zm konnen auftreten: ^mi '^mi *m) ^771/

mit Prn'- Systemeinheit m bearbeitet einen auszufiihrenden Prozess-Schritt fiir o, Sjn'- Systemeinheit m fiihrt einen Riistwechsel durch, um einen Prozess-Schritt fiir o auszufiihren, Im'- Systemeinheit m fiihrt einen Beladevorgang durch, um einen Prozess-Schritt fiir o auszufiihren, Um'- Systemeinheit m fiihrt einen Entladevorgang durch, um einen Prozess-Schritt fur o zu beenden, bm'- Systemeinheit m ist ausgefallen und steht fiir die Bearbeitung eines Prozess-Schrittes von o nicht zur Verfugung. Produktionssysteme konnen als zielsuchende Systeme aufgefasst werden, da sie versuchen, Aufgaben zu losen. Entsprechend der in Abschnitt 2.1 erfolgten Darstellung besteht jedes zielsuchende System aus einem Basissystem und dem dazugehorigen Steuerungssystem. Das Steuerungssystem besteht aus Systemobjekten, die im Fall von Produktionssystemen durch die Hard- und Software zur Realisierung von Steuerungsfunktionalitat gebildet werden. Analog zu den Bearbeitungsobjekten im Basissystem werden zwischen den Systemobjekten im Steuerungssystem Steuerungsinformationen ausgetauscht. Der Steuerungsprozess wird in Abschnitt 2.3 untersucht. In dieser Arbeit werden Produktionssysteme als spezielle zielsuchende Systeme aufgefasst. Daraus folgt, dass fur eine Charakterisierung komplexer Produktionssysteme sowohl das Basis- als auch das Steuerungssystem untersucht werden miissen. Da Produktionssysteme keine statischen Aufgaben losen, sondern die Aufgaben zeitabhangig sind, ist es sinnvoU, parallel zum realisierenden Produktionssystem (d.h. parallel zum Basis- und Steuerungssystem) auch den Produktionsprozess (realisiert durch den Basis- und Steuerungsprozess) zu untersuchen. Das Basissystem eines Produktionssystems wurde als Menge aller Arbeitsplane AP, die als Relation iiber {Xgi{O,j0}} interpretiert werden, beschrieben. Weiterhin wurde bereits darauf hingewiesen, dass jedem Prozess-Schritt mindestens eine Maschine zugeordnet ist, auf der die Bearbeitung des Prozess-Schrittes erfolgen kann. Eine Einschrankung der Relation AP auf einzelne Arbeitsplane ergibt Basissysteme, die nur aus den Prozess-Schritten und denjenigen Maschinen bestehen, die zur Realisierung von Bearbeitungsobjekten notwendig sind, die dem speziellen Arbeitsplan folgen. Falls die Anzahl der Arbeitsplane card{AP) grofi ist, folgt daraus, dass auch

2.3. STEUERUNG KOMPLEXER SYSTEME

19

die Anzahl der so gebildeten Systeme groB ist. Folglich liegt ein komplexes Produktionssystem vor. Entsprechend dieser Betrachtungsweise sind komplexe Produktionssysteme durch eine grofie Produktvielfalt und einen zeitlich veranderlichen Produktmix gekennzeichnet. Eine Bildung von Systemen kann unter ausschliefilicher Betrachtung der Systemobjekte des Basissystems erfolgen. Wenn die Menge der Systemeinheiten in disjunkte Untermengen zerfallt, wird dadurch auch eine entsprechende Zerlegung der Relation AP garaniert, die daraus resultiert, dass jedem Prozess-Schritt mindestens eine Maschine zur Ausfiihrung zur Verfiigung steht. Durch diese Dekomposition der Menge der Arbeitsplane entsteht somit auch eine Menge von Systemen, die miteinander in Beziehung stehen. Entsprechend dieser Betrachtungsweise sind Produktionssysteme, fiir die eine Aggregation von Maschinen zu Maschinengruppen bzw. eine Zusammenfassung von Maschinengruppen zu Produktionsbereichen erfolgt, komplexe Produktionssysteme. Im nachsten Schritt werden aus dem Studium des Basisprozesses Eigenschaften komplexer Produktionssysteme abgeleitet. Ein komplexer Prozess ist dadurch gekennzeichnet, dass eine Zerlegung in eine Vielzahl von Unterprozessen moglich ist. Es wurde der Begriff des Elementarprozesses aus Sicht des Bearbeitungsobjektes und aus Sicht der Systemeinheit eingefiihrt. Falls die Anzahl dieser Elementarprozesse grofi ist, wird der zu realisierende Produktionsprozess als komplex bezeichnet. Das ist immer dann der Fall, wenn die zu realisierenden Arbeitsplane eine grofie Anzahl von Prozess-Schritten umfassen. Zusammenfassend kann festgehalten werden, dass komplexe Produktionssysteme durch • die Komplexitat des Basissystems in Form einer grofien Anzahl von Maschinen, • die Vielfalt und Anzahl der Arbeitsplane sowie der Bearbeitungsobjekte gekennzeichnet sind. Der Begriff einer komplexen Werkstattfertigung wurde in [134] fiir Halbleiterfertigungssysteme verwendet. In [188] werden Produktionssysteme des Testbereichs von Halbleiterfabriken als komplexe Produktionssysteme bezeichnet. Ein aus drei Subsystemen bestehendes einfaches komplexes Produktionssystem ist in Anhang A.l beschrieben.

2.3

Steuerung komplexer Systeme

Im Vergleich zur Steuerung von gewohnlichen Systemen [208, 252, 20] kann bei der Steuerung komplexer Systeme ausgenutzt werden, dass diese aus unterschiedlichen Subsystemen bestehen. Es wird zunachst auf die Moglichkeiten der Steuerung eines einzelnen Subsystems eingegangen. Um sich an den zu steuernden Prozess anzupassen, ist es vorteilhaft, wenn ein zu steuerndes System iiber ein internes Modell des zu steuernden Prozesses verfiigt. Das interne Modell wird als dynamisches Prozessmodell bezeichnet. Dieses interne Modell ermoglicht das Studium der Wirkung von parametrisierbaren Steuerungsprozessen auf den Basisprozess. Auf Grund dieser Eigenschaften gibt es prinzipiell zwei Moglichkeiten, auf die Elemente eines Steuerungssystems zuzugreifen [20]:

20

KAPITEL 2. STEUERUNGSANSATZE

FUR KOMPLEXE

PRODUKTIONSSYSTEME

1. Zielmodifikation: Unter Zielmodifikation versteht man, dass ein zweites intervenierendes System eine Zielvorgabe in Form von Fiihrungsgrofien erhalt. Das intervenierende System hat die nachfolgenden Moglichkeiten, diese Zielvorgabe zu verandern: • Direkte Veranderung der Auspragungen von Fiihrungsgrofien. Darunter versteht man, dass numerische Werte fiir eine Fiihrungsgrofie verandert werden. Beispielsweise kann durch Verandern der Strategie zur Bestimmung von geplanten Fertigstellungsterminen die Liefertermintreue eines Produktionssystems verandert werden. Das intervenierende System erhalt eine Ex-Ante-Riickkopplung durch Experimente am Prozessmodell. • Das intervenierende System schrankt den Entscheidungsraum M (vergleiche dazu Abschnitt 2.1) ein oder erweitert diesen geeignet. Beispielsweise fiihrt die Anwendung einer riistzeitminimierenden Prioritatsregel dazu, dass die Menge der moglichen Maschinenbelegungsalternativen wesentlich reduziert wird. 2. Modifikation des internen Modells (Bildmodifikation): Das intervenierende System hat die Moglichkeit, das interne Modell des Steuerungssystems zu beeinflussen. Zum Beispiel ist es sinnvoU, eine detaillierte Modellierung von Maschinenkapazitaten fiir den in Abschnitt Abschnitt 4.1 dargestellten Beam-Search-Algorithmus nur fiir dynamische Engpasse im System vorzunehmen. Durch das intervenierende System kann in dieser Situation festgestellt werden, welche Maschinengruppen dynamische Engpasse verursachen. Im Gegensatz zur Zielmodifikation ist es fiir das intervenierende System nicht direkt moglich, die Auswirkungen der Modellanderung zu bewerten. Die Modifikation des internen Modells entspricht in der Organisationstheorie einem "Managment By Exception" [201]. Komplexe Produktionssysteme sind durch viele bei der Modellbildung zu beriicksichtigende Nebenbedingungen gekennzeichnet. Bei der Modellbildung muss stets gefragt werden, welcher Detaillierungsgrad des Modells fiir die zu losende Aufgabe angemessen ist. Abbildung 2.2 dient der Veranschaulichung der beiden Moglichkeiten zur Beeinflussung von Systemen. Die Dekomposition eines komplexen Systems in Subsysteme fiihrt dazu, dass an Stelle eines internen Modells eine Familie von internen Modellen betrachtet werden muss. Jedes dieser internen Modelle beschaftigt sich mit unterschiedlichen Aspekten des komplexen Systems. Ein komplexes System kann als dezentralisiertes System aufgefasst werden, da es per Definition unterschiedliche Subsysteme enthalt, die in Interaktion stehen, um ein gemeinsames Ziel zu erreichen. Verschiedene Dezentralisationsgrade konnen unterschieden werden, die in den eingesetzten Steuerstrategien zum Ausdruck kommen. Auf der einen Seite ist eine fast voUstandig zentrale Steuerung moghch, die den beteiligten Subsystemen nur einen geringen Grad an Autonomie einraumt. Im Gegensatz zur fast voUstandigen zentralen Steuerung befinden sich voUstandig dezentralisierte Systeme, die dadurch gekennzeichnet sind, dass jedes Subsystem eigenstandig fiir seine Steuerung verantwortlich ist. Als Kompromiss zwischen diesen beiden Auspragungen konnen

2.4. STEUERUNG KOMPLEXER FuhrungsgroBen Intervenierendes System

Ex-Ante Ruckkopplungl

Fuhnmgsgrdfien Zielmodifikation

Stellsignale

Ausgangssignal

21

PRODUKTIONSSYSTEME

Eingangssignale, Stoning

Stellsignale

Ausgangssignal

Eingangssignale, Stoning

Abbildung 2.2: Zielmodifikation bzw. Modifikation des internen Modells [20]

verteilte Systeme mit zentraler Steuerung oder mit einer verteilten hierarchischen Steuerung angesehen werden. AUe dezentralisierten Systeme sind dadurch gekennzeichnet, dass die Subsysteme koordiniert werden mussen, um die gemeinsamen Systemziele zu erreichen. In Anhang A.2 wird ein Beispiel fiir die Steuerung eines aus drei Subsystemen bestehenden einfachen komplexen Produktionssystems gegeben.

2.4

Steuerung komplexer Produktionssysteme

Der zu realisierende Steuerungsprozess fiir Produktionssysteme kann in Elementarprozesse unterteilt werden, die sich an der Dekomposition des Basissystems orientieren konnen. Beispielsweise kann die Belegung einer einzelnen Maschine mit Losen als Form einer lokalen Steuerung aufgefasst werden. Ahnliches gilt fiir die Steuerung von Produktionsbereichen. Umgekehrt wird eine Dekompositon des Steuerungsprozesses in Unterprozesse aus der Kompliziertheit von Prozessbedingungen abgeleitet. Ein Vorschreiben von geplanten Kundenendterminen fiihrt beispielsweise dazu, dass interne Termine fiir die Bearbeitungsobjekte vorgegeben werden. Eine Batchfertigung oder das Vorhandensein von reihenfolgeabhangigen Umriistzeiten bewirken ebenfalls eine Dekomposition des Steuerungsprozesses. Externe und interne Storungen (in Form von Maschinenausfallen bzw. Anderung der Prioritaten von Kundenauftragen) erfordern Reschedulingaktivitaten, die neue Steuerungsprozesse notwendig machen. Die Steuerung komplexer Produktionssysteme ist somit durch eine hohe Komplexitat des Steuerungsprozesses, die sich aus

22

KAPITEL 2. STEUERUNGSANSATZE

FUR KOMPLEXE

PRODUKTIONSSYSTEME

• komplizierten Produktionsbedingungen und • der Komplexitat des Basisprozesses ableitet, gekennzeichnet.

2.5

Steuerungsansatze des Operations Research

2.5.1

Prioritatsregeln und Einsteuerungsstrategien

2.5.1.1

Prioritatsregelbasierte Steuerung

Auf Grund der Komplexitat der betrachteten Produktionssysteme stellen Prioritatsregeln den in der Praxis am weitesten verbreiteten Steuerungsansatz dar. Prioritatsregeln werden dazu verwendet, zu entscheiden, welches Los auf einer freien Maschine als nachstes bearbeitet werden soil. In der Literatur werden Prioritatsregeln ausfiihrlich in [22, 92] diskutiert. In den Arbeiten [215, 216, 217] werden speziell fiir Halbleiterfabriken entworfene Prioritatsregeln auf ihre Leistungsfahigkeit hin untersucht. Einfache Prioritatsregeln sind zum Beispiel die FIFO (First-In, First-Out)-Regel, die gewichtete kiirzeste Bearbeitungszeitregel und die Schlupfzeitregel. Neben den einfachen Regeln existieren • zusammengesetzte Prioritatsregeln, • bedingte Prioritatsregeln, • Multi-Level-Prioritatsregeln. Zusammengesetzte Prioritatsregeln fassen mehrere Regeln zu einer einzigen zusammen. Ein Beispiel fur diesen Ansatz ist die ATC (Apparent-Tardiness-Cost)-Regel [199], die die gewichtete kiirzeste Bearbeitungszeit und den Schlupf eines Loses miteinander kombiniert. Die grundsatzliche Idee bedingter Prioritatsregeln besteht darin, dass eine Menge von Prioritatsregeln vorliegt und in Abhangigkeit vom Zustand des Produktionssystems eine dieser Regeln ausgewahlt wird. Beispielsweise kann in Abhangigkeit von der Auslastung des Produktionssystems zwischen der gewichteten kiirzesten Bearbeitungszeitregel und der Schlupfzeitregel gewechselt werden. Multi-Level-Regeln sortieren die Lose nach unterschiedlichen Kriterien. Zum Beispiel konnen in einem ersten Schritt alle Lose ausgewahlt werden, die geringe Riistkosten verursachen, wahrend in einem zweiten Schritt die Lose dieser Menge nach der Schlupfzeitregel sortiert werden. MultiLevel-Prioritatsregeln fiir den Einsatz in einer Halbleiterfabrik sind in [245] untersucht worden. Prioritatsregeln sind relativ leicht zu implementieren und aus diesem Grund u.a. in den meisten Manufacturing Execution Systems (MES) (vergleiche McClellan [137] fiir eine Definition des

2.5. STEUERUNGSANSATZE

DES OPERATIONS RESEARCH

23

MES-Begriffs) anzutreffen. Aufierdem konnen Prioritatsregeln leicht an die aktuelle Situation im betrachteten Produktionssystem angepasst werden. Der Hauptvorteil von Prioritatsregeln besteht in ihrer geringen Redienzeit, die sie fiir einen Online-Ansatz besonders geeignet erscheinen lassen. Aufierdem ist ihre Leistungsbewertung mit Hilfe von Simulationsmodellen relativ leicht moglich. Der wesentliche Nachteil von Prioritatsregeln besteht darin, dass in die Entscheidungsfindung lediglich zeitlich und raumlich lokale Informationen einbezogen werden. Die einzelnen Lose werden isoliert voneinander betrachtet. Es ist nur schwer moglich, mehrere Ziele in die Entscheidungsfindung einzubeziehen.

2.5.1.2

Einsteuerungsstrategien fiir komplexe Produktionssysteme

Eng verbunden mit der Prage der Auswahl einer oder mehrerer Prioritatsregeln fiir ein bestimmtes Produktionssystem ist die Prage einer geeigneten Einsteuerungsstrategie fiir das betrefFende Produktionssystem. Einsteuerungsstrategien versuchen, kiirzere Durchlaufzeiten zu erreichen, indem die Lose in einer kontroUierten Art und Weise in das Produktionssystem eingelastet werden. Der Mittelwert und die Varianz der Durchlaufzeit werden verringert. Die Termintreue verschlechtert sich aber unter Umstanden, da die Lose langer auf die Einlastung warten miissen. Pragen der Einsteuerung von Losen bei Werkstattfertigung werden in [19] diskutiert. In [63] wird eine Ubersicht iiber (moderne) Einsteuerungsstrategien fur komplexe Produktionssysteme (am Beispiel der Halbleiterindustrie) gegeben. Bei der Einsteuerung von Losen wird zwischen Push- und PuU-Konzepten unterschieden. PushAnsatze steuern Lose entsprechend von Vorgaben aus dem Enterprise-Resource-Planning-(ERP)System in das Produktionssystem ein. Da heutige ERP-Systeme nach wie vor nur unzureichend endliche Kapazitaten bei der Entscheidungsfindung beriicksichtigen [52], fiihrt die Anwendung von Push-Methoden fiir die Einsteuerung zu langen Durchlaufzeiten und hohen Bestanden in den Produktionssystemen. PuU-Methoden wurden stark durch die Einfiihrung von Just-In-Time- und engpassorientierten Steuerungskonzepten wie OPT (Optimized-Production-Technique) [81] beeinflusst. PuU-Ansatze beriicksichtigen die kapazitiven Moglichkeiten des Produktionssystems. In der Literatur wird iiber die Uberlegenheit von PuU-Ansatzen in Vergleich zu Push-Ansatzen berichtet [212]. Es wurden Anstrengungen unternommen, Kanban-artige Steuerungsansatze in Produktionssystemen zu implementieren [147]. CONWIP [237] kann als Verallgemeinerung des Kanban-Ansatzes angesehen werden. Der CONWIP-Ansatz kontroUiert die Anzahl von Halbfabrikaten (Work in Process (WIP)) in einem Produktionssystem. Fiir den Einsatz von CONWIP ist die Kenntnis des Zusammenhanges zwischen der Anzahl von Halbfabrikaten und dem Durchsatz, der durch eine charakteristische Kennlinie [175] beschrieben wird, notwendig. Unter Verwendung dieser Kennlinie wird dann eine bestimmte Zielanzahl an Halbfabrikaten fiir einen bestimmten Durchsatz angegeben. Es wird angestrebt, die WIP unter dieser Zielgrofie zu halten. Gleichzeitig wird der Durchsatz bestimmt.

24

KAPITEL 2. STEUERUNGSANSATZE

FUR KOMPLEXE

PRODUKTIONSSYSTEME

Falls dieser von den Vorgaben abweicht, werden die WIP-Ziele angepasst. In der Literatur wird CONWIP als leistungsfahiger PuU-Ansatz beschrieben [212]. Entsprechende Modifikationen und Erweiterungen des CONWIP-Ansatzes fiir Halbleiterfabriken werden in [214] diskutiert und mit Hilfe von Simulation untersucht. Fiir den Frontendbereich von Halbleiterfabriken als Beispiel fiir ein komplexes Produktionssystem entsprechend der in Abschnitt 2.2 gegebenenen Definition konnen die folgenden wichtigen Einsteuerungsmethoden genannt werden [63]:

1. Starvation-Avoidance-Ansatz (SA),

2. Workload-Regulation-Ansatz (WR),

3. Flow-Rate-Control-Ansatz (FRC).

Die Grundidee des Starvation-Avoidance-Ansatzes besteht darin, fiir eine einzelne Engpassmaschinengruppe einen virtuellen Bestand zu berechnen, der, auf eine bestimmte Durchlaufzeit bezogen, zur Festlegung der Anzahl einzusteuernder Lose verwendet wird [75]. Als Durchlaufzeit wird die Zeit gewahlt, die Lose benotigen, um die betrachtete Engpassmaschinengruppe das erste Mai zu erreichen. Der Ansatz wurde in [78] auf den Fall mehrerer Engpassmaschinengruppen ausgedehnt. Die Grundidee des Workload-Regulation-Ansatzes besteht darin, eine bestimmte Last fiir die dominierende Engpassmaschinengruppe zu berechnen. In der grundlegenden Arbeit von Wein [265] wird dazu die Auslastung der fiihrenden Engpassmaschinengruppe in Stunden angegeben. Weiterhin werden unterschiedliche Erweiterungen von Prioritatsregeln betrachtet, die zu einer Balancierung der Belastung des Produktionssystems dienen. Der Work-Load-Regulation-Ansatz ist konzeptuell dem OPT-Ansatz ahnlich. Der Workload-Regulation-Ansatz wurde in [78] auf den Fall mehrerer Engpassmaschinengruppen ausgedehnt. Der Flow-Rate-Control-Ansatz wurde von Lou und Kager [127] vorgeschlagen. Die Kernidee dieses Ansatzes besteht darin, zunachst eine maximale Flussrate zu berechnen. Auf Basis dieser Rate wird dann die Anzahl einzusteuernder Lose reduziert oder es werden neue Lose in das Produktionssystem eingesteuert. Durch Einfiihrung von virtuellen Maschinen wird der zyklische Fluss der Lose aus Steuerungssicht aufgebrochen. Der Starvation-Avoidance-Ansatz, der Workload-Regulation-Ansatz und CONWIP werden in [76] mit dynamischer Optimierung gekoppelt. Eine lineare KontroUregel wird verwendet. Der Ansatz wird in ein hybrides Simulations- und Optimierungsframework eingebettet. Wahrend in der Vergangenheit liberwiegend Einsteuerungsstrategien im Zusammenhang mit einer prioritatsregelbasierten Durchsteuerung der Lose untersucht wurden, erscheint es sinnvoU, in Zukunft Einsteuerungsfragen im Kontext von deterministischen Schedulingansatzen fiir Produktionssysteme zu untersuchen.

2.5. STEUERUNGSANSATZE

2.5.2

DES OPERATIONS RESEARCH

25

Deterministische Schedulingansatze

Scheduling (Maschinenbelegungsplanung) beschaftigt sich mit der Zuteilung von Prozess-Schritten der Lose (Bearbeitungsobjekte) zu Maschinen (Systemeinheiten). Nach erfolgter Zuteilung zu den Maschinen erfolgt weiterhin eine Festlegung der Bearbeitungsreihenfolge auf den einzelnen Maschinen [199]. Deterministische Schedulingprobleme sind dadurch gekennzeichnet, dass alle Daten diskret, deterministisch und vorab bekannt sind. Prinzipiell kann bei deterministischen Schedulingansatzen zwischen zwei Auspragungen unterschieden werden: • Anwendung von Schedulingansatzen auf einzelne Maschinengruppen (Gruppen paralleler Maschinen), • Anwendung von Schedulingansatzen auf das gesamte Produktionssystem. Schedulingansatze fiir einzelne Maschinengruppen in Produktionssystemen sind Gegenstand von umfangreichen Untersuchungen. Eine detaillierte Abbildung bzw. Modellierung unterschiedlicher Prozessbedingungen wird vorgenommen. Zur Losung werden u.a. lokale Suchverfahren, gemischtganzzahlige Optimierung und Prioritatsregeln eingesetzt. Eine ausfiihrlichere Darstellung und Bewertung von entsprechenden Losungsverfahren findet in Abschnitt 4.3 statt. Es ist festzustellen, dass viele akademische Arbeiten zum deterministischen Scheduling auf der Ebene von Einzel- und parallelen Maschinen existieren. Dabei wird in den meisten Fallen von der Annahme ausgegangen, dass alle Lose, fiir die ein Ablaufplan erstellt werden soil, bereits vor der Einzelmaschine bzw. der Maschinengruppe auf Bearbeitung warten. Oft werden aber die entwickelten Verfahren nicht in der Praxis angewandt, weil praktische Problemstellungen dynamischer Natur sind, d.h., es liegen dynamische Losankiinfte vor. Andererseits ist es komphziert, die entsprechenden Daten, die erst einen Einsatz der „akademischen" Algorithmen ermoglichen, in Produktionsunternehmen bereitzustellen. Auf Grund der Komplexitat der zu losenden Schedulingprobleme werden deterministische Scheduhngansatze fiir das gesamte Produktionssystem in der Literatur seltener diskutiert. Im Folgenden werden zwei Ansatze zur Losung des Schedulingproblems auf Gesamtsystemebene beschrieben. Beiden Ansatzen ist gemeinsam, dass Graphen zur Modellierung der Abhangigkeiten der auf unterschiedlichen Maschinengruppen zu bearbeitenden Lose benutzt werden. Ein prominenter Vertreter fiir einen deterministischen Schedulingansatz auf Gesamtproduktionssystemebene ist die Shifting-Bottleneck-Heuristik von Adams, Balas und Zawack [2]. Die Shifting-Bottleneck-Heuristik wurde in [187] zur Erzeugung von Ablaufplanen fiir den Testbereich von Halbleiterfabriken angewandt. In [134] werden Erweiterungen vorgestellt, die eine Anwendung der Shifting-Bottleneck-Heuristik im Frontendbereich von Halbleiterfabriken ermoglichen. Die Shifting-Bottleneck-Heuristik kann grob wie folgt beschrieben werden: 1. Aufteilung des Produktionssystems, fiir das ein Ablaufplan bestimmt werden soil, in einzelne Gruppen paralleler Maschinen,

26

KAPITEL 2. STEUERUNGSANSATZE

FUR KOMPLEXE

PRODUKTIONSSYSTEME

2. Uberfuhrung des zu losenden Schedulingproblems in einen disjunktiven Graphen, 3. Bestimmung eines Ablaufplans fiir diejenigen Maschinengruppen, fiir die noch kein Ablaufplan ermittelt wurde, 4. Festlegung der Reihenfolge der Maschinengruppen auf Basis eines Mafies, das bestimmt, wie kritisch eine Maschinengruppe ist, 5. Anwendung der disjunktiven Graphenformulierung, um die Abhangigkeit zwischen Maschinengruppen, fiir die bereits ein Ablaufplan ermittelt wurde und diejenigen, fiir die das noch aussteht, abzubilden, 6. (optionale) Berechnung eines neuen Ablaufplans fiir die Maschinengruppen, fiir die bereits ein Ablaufplan berechnet wurde, unter Verwendung der Informationen aus Schritt 5. Der Algorithmus wird beendet, wenn fiir alle Maschinengruppen ein Ablaufplan berechnet wurde. Ansonsten wird der Algorithmus in Schritt 3 fortgesetzt. In [187, 134, 46, 158] wird gezeigt, dass die Shifting-Bottleneck-Heuristik traditionellen Prioritatsregelansatzen iiberlegen ist. Probleme bereiten aber • die grofie Laufzeit der Heuristik, • der hohe Speicherbedarf auch bei effizienten softwaretechnischen Implementierungen, der einen Schedulinghorizont grol3er als eine Schicht unmogUch macht, • der hohe Parametrisierungsaufwand fiir den erfolgreichen Einsatz der Shifting-BottleneckHeuristik, • die fiir komplexe Produktionssysteme typischen Storungen, die ein deterministisches Scheduling erschweren. Die inharente Nebenlaufigkeit

der auf dem Dekompositionsprinzip beruhenden

Shifting-

Bottleneck-Heuristik wurde bisher nicht ausgenutzt. Ein zweiter Verfahrensrahmen zur Losung von Maschinenbelegungsproblemen auf Ebene des gesamten Produktionssystems ist durch das ressourcenbeschrankte ProjektscheduUng gegeben. Auf den Ubersichtsartikel von Brucker, Drexl, Mohring, Neumann und Pesch [29] wird fiir eine Diskussion der relevanten Literatur verwiesen. Spezielle Modellformulierungen fiir die Prozessindustrie sind beispielsweise in [228] zu finden. Im Grundmodell wird die Menge V

:={0,l,...,n,n-\-l}

von Aktivitaten betrachtet, die Ressourcen benotigen. Es konnen maximale und minimale Liegezeiten zwischen Anfang und Ende von Aktivitaten i,j G V auftreten. Jeder Aktivitat ist eine bestimmte Dauer zugeordnet. Eine Operation identifiziert genau eine reale Aktivitat i e { 1 , . . . , n}

2.5. STEUERUNGSANSATZE

DES OPERATIONS RESEARCH

27

des Projektes. Jeder Operation ist ein Startereignis z*, das zum Zeitpunkt Si eintritt, und ein Fertigstellungsereignis f, das zum Zeitpunkt Q > Si stattfindet, zugeordnet. Die Hilfsaktivitat 0 dient zur Modellierung des Produktionsanfangs, wahrend die Hilfsaktivitat n + 1 das Produktionsende abbildet. Die Menge K : = { 0 , l ^ l ^ . . . , n ^ r ^ ^ n + l} stellt alle Ereignisse dar. Der Vektor T := {So, 5 i , . . . , 5„, C i , . . . , Cn, Cn+i) wird als Ablaufplan bezeichnet. Das zu untersuchende Projekt wird im ressourcenbeschrankten Projektscheduling als Graph

{V,E,S) mit V

: Menge der Ereignisse,

E

: Menge der Kanten des Graphen,

S

:

Kantengewichte

dargestellt. Fiir jedes Ereignis e € V wird ein Knoten in den Graphen eingefiigt. Die (gerichteten) Kanten des Graphen dienen zur Reprasentation von maximalen und minimalen Liegezeiten zwischen Ereignissen, d.h., es gilt fiir e,feV

die Beziehung (e,/> 6 E, falls die

Ereignisse e und / durch eine vorgeschriebene maximale bzw. minimale Liegezeitbedingung miteinander verkniipft sind. Die Kanten werden mit Gewichten versehen, deren GroBe von der vorgeschriebenen Liegezeit abhangig ist. Zur Losung des Projektschedulingproblems werden zunachst Ressourcenconstraints relaxiert. Ahnhch wie im Fall der Shifting-Bottleneck-Heuristik werden langste Wege im Graphen berechnet, die zur Minimierung des spatesten Fertigstellungstermines der Aktivitaten dienen. Auf Basis des erhaltenen Ablaufplanes, der gegebenenfalls Ressourcenconstraints verletzt, werden im Modell sukzessive disjunktive Vorrangbeziehungen zwischen Start- und Fertigstellungsereignissen eingefiihrt, die die Erfiillung von Ressourcenconstraints sicherstellen. Die Berechnung von Ablaufplanen und die Erzeugung von entsprechenden Vorrangbeziehungen werden iterativ wiederholt.

2.5.3

Simulationsbasierte Ansatze

Simulationsbasierte Ansatze in der Produktionssteuerung zeichnen sich dadurch aus, dass ein Simulationsmodell als Modell des zu steuernden Produktionssystems verwendet wird und anhand dieses Modells das Verhalten des realen Systems in Abhangigkeit von der Zeit untersucht wird [119]. Fiir die in dieser Arbeit untersuchten Produktionssysteme eignen sich besonders diskrete ereignis-orientierte Simulationsansatze. Zu den Vorteilen von Simulationsansatzen gehort (vergleiche hierzu [119]) die Moglichkeit der Erprobung neuer Strategien und Entscheidungsregeln ohne den laufenden Betrieb des Produktionsprozesses zu unterbrechen. Zu den bekannten Nachteilen

28

KAPITEL 2. STEUERUNGSANSATZE

FUR KOMPLEXE

PRODUKTIONSSYSTEME

der diskreten ereignis-orientierten Simulation zahlen der hohe Aufwand fiir die Daten- und Modellbereitstellung und die schwierige Interpretation von Ergebnisdaten der Simulation. Fiir die simulationsbasierte Steuerung von Produktionssystemen kann zwischen den folgenden Verfahrensauspragungen unterschieden werden: • Erzeugen von Ablaufplanen durch Simulation (simulationsbasiertes Scheduling), • simulationsbasierte Auswertung von Zielfunktionen im Rahmen von Optimierungsansatzen (simulationsbasierte Optimierung), • simulative Bewertung von Einsteuerstrategien und Prioritatsregeln. In jlingerer Zeit sind eine Reihe von Schedulingsystemen entwickelt worden, die ein Simulationstool zur Bereitstellung von Ablaufplanen benutzen. Die Simulationsmodelle werden datengetrieben aus Informationen in betrieblichen Informationssystemen generiert. Die Systeme unterstiitzen die Einsteuerung von neuen Losen in das Produktionssystem und erzeugen detaillierte Ablaufplane unter Verwendung von Prioritatsregeln in einer roUierenden Art und Weise. Das bedeutet, dass vor jeder Erzeugung neuer Ablaufplane zunachst ein neues aktuelles Simulationsmodell generiert werden muss und anschliefiend dann der Ablaufplan berechnet wird. Die Ereignisdateien des verwendeten Simulationstools werden im nachsten Schritt in Ganttcharts konvertiert. Ein derartiges System fiir den Backendbereich einer Halbleiterfertigung ist in [203] beschrieben worden. Ein weiteres dieser Philosophie folgendes System wurde von Sivakumar [232] vorgestellt. Im Vergleich zu herkommlichen Prioritatsregelansatzen fallt auf, dass eine bessere Beriicksichtigung mehrerer Zielkriterien moglich ist und dass in starkerem Mafie globale Zielsetzungen bei der Auswahl des im Produktionssystems zu implementierenden Ablaufplanes beachtet werden konnen. Die beschriebenen Ansatze sind in einem betrieblichen Kontext allerdings nur dann erfolgreich, wenn die mit der Simulation verbundenen Probleme wie Aufwand fiir die Datenbereitstellung, hoher Modellierungsaufwand sowie hohe Laufzeit fiir die Ausfiihrung der Simulationsmodelle beseitigt werden konnen. Bei der simulationsbasierten Optimierung (vergleiche [73] fiir eine detailliertere Beschreibung des Konzeptes) besteht die Aufgabe darin, eine vektorwertige reelle Funktion

unter Anwendung des Simulationsmodells auszuwerten. Mit 0 wird dabei die Menge zulassiger Losungen der Optimierungsaufgabe bezeichnet. Die Nebenbedingungen der Optimierungsaufgabe werden impHzit durch das Simulationsmodell abgebildet. Entscheidungsvariable werden mit 9 bezeichnet. Es gilt 6 € B. Die Auswertung des Zielfunktionswertes f{9) erfordert eine gewisse Anzahl von Simulationslaufen. Der Einsatz der simulationsbasierten Optimierung bietet sich an, wenn eine explizite Beschreibung der Nebenbedingungen nicht moglich oder zu kompliziert ist. Zur Steuerung der Suche nach einer optimalen Losung der zu losenden Optimierungsaufgabe werden haufig Metaheuristiken herangezogen. Da Metalieuristiken iterativ arbeiten, ist eine

2.5. STEUERUNGSANSATZE

DES OPERATIONS RESEARCH

29

grofie Anzahl von Zielfunktionsauswertungen, d.h. Simulationslaufen, notig. Auf Grund der h o hen Laufzeit heutiger Simulationstools ist ein Einsatz der simulationsbasierten Optimierung unter Echtzeitbedingungen mit Problemen verbunden. Die Losung dieser Probleme verlangt erweiterte Modellierungsansatze. Beispielhaft werden an dieser Stelle reduzierte Simulationsmodelle und Methoden der ressourcengetriebenen Simulation betrachtet. Fiir viele Pragestellungen kann auf eine detaillierte Modellierung verzichtet werden. Ansatze fiir die Simulation von Halbleiterfabriken mit vereinfachten Modellen sind durch Rose [213, 214] untersucht worden. Rose zeigt, dass das Verhalten einer Halbleiterfabrik nach einem Ausfall einer wichtigen Engpassmaschine durch ein reduziertes Simulationsmodell mit ausreichender Genauigkeit vorausgesagt werden kann [213]. Das von Volker und Gmilkowsky [258] vorgeschlagene Konzept der Modellreduktion geht davon aus, dass nur eine Teilmenge aller planungsrelevanten Prozess-Schritte explizit in die Simulation einbezogen wird, die iibrigen Prozess-Schritte werden im Simulationsmodell nur implizit abgebildet. Das wird durch Einfiihrung von Zeitpuffern, welche neben den Bearbeitungszeiten fiir die nicht exakt modellierten Prozess-Schritte auch die geschatzten Wartezeiten beinhalten, erreicht. Der Weg zum reduzierten Simulationsmodell fiihrt fiber die drei Schritte

• Zerlegen der Menge der Prozess-Schritte, • Berechnung der Zeitpuffer, • Berechnung von Kapazitatsreservierungen.

Wesentliche Bedeutung hat dabei die Ermittlung von Siebfunktionen zur Auswahl der nicht exakt modellierten Prozess-Schritte. Uber diese sukzessiv angewandten Siebfunktionen werden nichtquantifizierbare Grofien, die Einfluss auf die Prozess-Schritte haben, durch Indikatoren operationalisiert. Grundlage dafiir sind messbare GroBen, die Aussagen iiber die Relevanz von ProzessSchritten fiir das Simulationsmodell zulassen. Als erfolgversprechend sind weiterhin Arbeiten anzusehen, die versuchen, das iibliche jobgetriebene Simulationsparadigma zu vermeiden. An Stelle einer detaillierten ModeUierung wird beim ressourcengetriebenen Ansatz auf die exphzite Abbildung von dynamischen Entitaten (Losen, Jobs) verzichtet, es werden an den Ressourcen lediglich Zahlvariable gehalten, die zur Aufnahme der Anzahl der vor der jeweiligen Ressource wartenden dynamischen Entitaten dienen. Dadurch kommt es zu betrachtlichen Beschleunigungseffekten. Durch Roder, Fischbein, Janakiram und Schruben [211] konnte gezeigt werden, dass sich ressourcengetriebene Simulationsmodelle fiir Halbleiterfabriken beziiglich wichtiger Leistungsmafie wie die langsameren jobgetriebenen Modelle verhalten. Forschungsbedarf besteht aber noch fiir hybride Ansatze, die die Vorteile job- und ressourcengetriebener Simulationsmodelle vereinen. Weiterhin erscheint es sinnvoU, ressourcengetriebene Ansatze und simulationsbasierte Optimierung zu kombinieren.

30

KAPITEL 2. STEUERUNGSANSATZE

2.6

FUR KOMPLEXE

PRODUKTIONSSYSTEME

Steuerungsansatze der Kiinstlichen Intelligenz

2.6.1

Expertensysteme und wissensbasierte Systeme

Expertensysteme bzw. wissensbasierte Systeme bestehen aus den Hauptbestandteilen Wissensbasis und Inferenzmaschine. Die Inferenzmaschine operiert auf der Wissensbasis. In der Wissensbasis wird formalisiertes Wissen menschlicher Experten in Form von Regeln, Prozeduren und Heuristiken abgelegt. Es werden die folgenden drei Arten von Wissen unterschieden. Prozedurales Wissen ist problemspezifisches Problemlosungswissen. Deklaratives Wissen liefert die Eingabedaten zur Beschreibung der Problemdomane. Metawissen dient dazu, zu entscheiden, wie das prozedurale und deklarative Wissen zur Losung eines konkreten Problems verwendet werden kann. Es werden spezielle Datenstrukturen zur Representation des Wissens verwendet. Die Inferenzmaschine wahlt eine Strategie zur Losung eines konkreten Problems aus. Datengetriebene Vorwartsstrategien und zielgetriebene Riickwartsstrategien werden unterschieden. Expertensysteme bzw. wissensbasierte Systeme wurden auf Steuerungsprobleme in komplexen Produktionssystemen angewandt. Exemplarisch wird auf die Systeme ISIS [68], OPIS [234] und SONIA [123] verwiesen. In [227] werden Expertensystemansatze mit anderen ScheduUngtechniken verglichen. Ein Expertensystem fiir die Steuerung einer Halbleiterfabrik ist in [220] beschrieben. Expertensysteme haben den Nachteil, dass es schwierig ist, das existierende Wissen der mit Produktionssteuerungsaufgaben betrauten Personen zu formalisieren. Im Falle von komplexen Produktionssystemen ist das Wissen weiterhin haufig auf eine Vielzahl von Entscheidungstragern verteilt. Diese Tatsache steht einer weiteren Verbreitung des Einsatzes von Expertensystemen zur Steuerung komplexer Produktionssysteme im Weg.

2.6.2

Suchverfahren der Kiinstlichen Intelligenz

Lokale Suchverfahren sind Verbesserungsverfahren. Sie gehen von einem voUstandigen Ablaufplan aus und versuchen, in der Nachbarschaft des gegebenen Ablaufplanes einen beziiglich einer vorgegebenen Zielfunktion besseren Ablaufplan zu finden (vergleiche beispielsweise [1] fiir Informationen zu lokalen Suchverfahren). Zwei Ablaufplane werden als benachbart bezeichnet, wenn sie durch eine Transformation ineinander iiberfiihrt werden konnen. In jeder Iteration eines lokalen Suchverfahrens wird eine Suche und Bewertung der Nachbarschaftsablaufplane durchgefiihrt. Das Suchverfahren akzeptiert einen Nachbarschaftsablaufplan als aktuell besten Ablaufplan oder weist ihn auf Basis bestimmter Kriterien zuriick. Lokale Suchverfahren werden nach den folgenden vier Kriterien unterschieden: 1. gewahlte Darstellungform des Ablaufplanes, die im jeweiligen lokalen Suchverfahren benotigt wird, 2. Struktur der gewahlten Nachbarschaft fiir einen gegebenen Ablaufplan,

2.6. STEUERUNGSANSATZE

DER KUNSTLICHENINTELLIGENZ

31

3. Suchverfahren in der jeweiligen Nachbarschaft des Ablaufplanes, 4. verwendetes Kriterium zur Annahme bzw. Zuriickweisung eines Nachbarschaftsablaufplanes. Die drei wesentlichen Verfahrensgruppen fiir lokale Suchverfahren zur Losung von ScheduUngproblemen sind: • Tabu-Search (vergleiche u.a. [79] fiir Anwendungen von Tabu-Search auf ScheduUngprobleme), • Simulated-Anneahng (vergleiche [253] fiir Anwendungen von Simulated-Annealing auf JobShop-ScheduHngprobleme), • genetische Algorithmen (vergleiche [50, 10] fiir Anwendungen von genetischen Algorithmen auf Schedulingprobleme).

Der Einsatz von lokalen Suchverfahren wird auf Grund des hohen Parametrisierungsaufwandes und auf Grund der komplizierten Bewertung der Giite problemspezifischer Heuristiken erheblich erschwert. Neben lokalen Suchverfahren spielen Beam-Search-Algorithmen [199] eine grofie RoUe. BeamSearch-Algorithmen sind von klassischen Branch&Bound-Algorithmen abgeleitete Verfahren. Im Gegensatz zu Branch&Bound-Algorithmen werden aber auf einer gegebenen Ebene des Suchbaumes nur bestimmte, erfolgversprechende Knoten zum Verzweigen ausgewahlt. Die iibrigen Knoten werden von der weiteren Verzweigung ausgeschlossen. Falls auf Ebene k des Suchbaumes keine Verzweigungen mehr moglich sind, wird ein Backtrackingschritt auf Ebene A; - 1 durchgefiihrt und in weitere erfolgversprechende Knoten verzweigt. Beam-Search-Algorithmen unterscheiden sich in der maximal erlaubten Anzahl von erfolgversprechenden Knoten pro Ebene des Baumes. Diese Anzahl wird als Beam-Breite bezeichnet. Die Auswahl von erfolgversprechenden Knoten auf einer Ebene kann durch unterschiedliche Algorithmen erfolgen. Beam-Search-Algorithmen haben den Nachteil, dass fiir bestimmte Probleminstanzen auf Grund von vielen Backtrackingschritten der Zeitaufwand sehr hoch ist. Das ist insbesondere bei niedriger Beam-Breite der Fall. Umgekehrt fiihrt eine grofie Beam-Breite dazu, dass ein ahnlicher Suchbaum wie bei Branch&Bound-Verfahren aufgebaut wird. Das ergibt ebenfalls einen hohen zeitlichen Aufwand.

2.6.3

Constraint-Satisfaction-Techniken

Constraint-Satisfaction-Probleme werden in der Form {V,D,C) dargestellt, wobei gilt: • V := {\4,..., V^} bezeichnet eine endliche Variablenmenge.

32

KAPITEL 2. STEUERUNGSANSATZE

FUR KOMPLEXE

PRODUKTIONSSYSTEME

• D := { D i , . . . , Dn} ist eine endliche Menge von Wertebereichen. Jede Variable Vi eV nimmt nur Werte aus Di an. Es wird vorausgesetzt, dass card{Di) < oo gilt. • C ist eine endliche Menge von Constraints, die zwischen den Variablen bestehen. Ein Constraint zwischen den Variablen Vi^,..., V^^ G V^ ist eine Teilmenge des kartesischen Produktes A i X . . . X Di„ d.h., es gilt C{Vi,,...,

K J C A , X ... X A,-

Ein Constraint-Satisfaction-Problem ist gelost, wenn fiir alle Vi e V eine Belegung mit Werten aus Di e D gefunden wurde. Eine Variable kann Bestandteil mehrerer Constraints sein, d.h., die Constraints sind abhangig voneinander. Fiir die Modellformulierung bedeutet das, dass Constraint-Netzwerke betrachtet werden miissen. Die Knoten des Netzwerkes sind Variable, wahrend die Kanten des Netzwerkes durch Constraints, die die Variablen verbinden, gebildet werden. Die Graphstruktur hat den Vorteil, dass Werte bzw. Wertebereiche instanziierter Variablen innerhalb des Graphen propagiert werden konnen. Unter Propagierung versteht man, dass die Einschrankung des Wertebereichs einer bestimmten Variablen durch die mit ihr in Relation stehenden Constraints an andere Variable weitergeleitet wird und diese entsprechend eingeschrankt werden. Losungsverfahren fiir Constraint-Satisfaction-Probleme werden unterteilt in Verfahren, welche die Constraints lediglich passiv zur Aufdeckung von Inkonsistenzen verwenden, und Verfahren, die die Constraints aktiv zur Einschrankung des Suchraums vor Beginn der eigentlichen Suche verwenden. Beispiele fur passive Verfahren sind Algorithmen mit Backtracking. Bei diesem Typ von Algorithmen werden sukzessive Belegungen von Variablen mit Werten aus dem korrespondierenden Wertebereich derart erzeugt, dass die Belegung der zuletzt betrachteten Variablen mit der vorausgegangenen Belegung der iibrigen Variablen konsistent ist. Kann eine Variable einen bestimmten Constraint nicht erfuUen, wird die zuletzt vorgenommene Belegung in einem Backtrackingschritt zuriickgenommen. Auf diese Art und Weise werden alle Variablen nacheinander mit Werten belegt und die Constraints erfuUt. Bei ungeschickter Traversierung der Variablen kann dieses Verfahren auf Grund der Backtrackingschritte sehr aufwendig sein. Ein zweites Beispiel fiir ein passives Verfahren ist das "generate and test"-Verfahren. Dieses Verfahren lasst sich in zwei Phasen unterteilen. In der ersten Phase werden Belegungen fiir die Variablen Vi e V erzeugt. In der zweiten Phase wird gepriift, ob die gewahlten Variablenbelegungen Constraints verletzen. Falls die in der ersten Phase erzeugte Losung nicht zulassig ist, wird eine andere Belegung bestimmt. Aktive Verfahren schranken den durch die Wertebereiche der Variablen gegebenen Suchraum durch die Propagierung von Constraints ein. Bei der Belegung einer noch nicht traversierten Variablen werden die Wertebereiche aller noch nicht belegten Variablen, die von einem Constraint betroffen sind, eingeschrankt. Die reduzierten Wertebereiche fiir die noch nicht belegten Variablen sind mit den bereits belegten Variablen konsistent. Falls ein reduzierter Wertebereich keine Variablen mehr enthalt, wird durch einen Backtrackingschritt eine andere Belegung gesucht. Der Grundalgorithmus besteht aus den drei aufeinander folgenden Phasen Variablenauswahl, Belegung der Variablen und Propagierung der Constraints. Verfahren zur Losung von Constraint-Satisfaction-

2.6. STEUERUNGSANSATZE

DER KUNSTLICHENINTELLIGENZ

33

Problemen sind in u.a. in [261] beschrieben. Entsprechende Losungsansatze haben auch Eingang in kommerzielle Systeme wie zum Beispiel ILOG [16, 122, 173] gefunden. Ansatze fiir verteilte Constraint-Satisfaction-Probleme sind im Kontext von Multi-Agenten-Systemen in [274, 90] beschrieben. Ein Nachteil der beschriebenen Verfahren zur Losung von Constraint-Satisfaction-Problemen besteht darin, dass in bestimmten Fallen keine Losung gefunden werden kann, die alien Constraints geniigt. In dieser Situation miissen dann Constraints relaxiert und ein neues ConstraintSatisfaction-Problem gelost werden.

2.6.4

Verfahren des maschinellen Lernens

An dieser Stelle werden neuronale Netze, induktive Entscheidungsbaume und ReinforcementLearning-Ansatze sowie ihre Anwendung auf Produktionssteuerungsprobleme diskutiert. Fiir weiterfiihrende Literatur zu Anwendungen des maschinellen Lernens auf ScheduUngprobleme sei auf [8] verwiesen.

2.6.4.1

Neuronale Netze

Ein neuronales Netz [146, 183] besteht aus einer Knotenmenge, den Neuronen. Die Neuronen konnen auf unterschiedliche Art und Weise miteinander verbunden sein. Jedes Neuron dient zur Realisierung einer Schwellenwertfunktion T n

yi'==T{J2wj,iUj), die festlegt, ob das Neuron schaltet, d.h. seinen berechneten Ausgangswert weitergibt, oder nicht. Mit Uj, j = 1 , . . . , n wird der Eingangswert und mit Wj^i, j = 1 , . . . , n, i = 1 , . . . , m das zugehorige Gewicht bezeichnet. Die Ausgangswerte werden fiir i = 1 , . . . , m mit yi bezeichnet. Die Neuronen sind in Schichten angeordnet. Neben einer Eingabe- und einer Ausgabeschicht existieren interne Schichten. Fiir den Anwender neuronaler Netze sind nur die Eingangs- und die Ausgangsschicht sichtbar. Das neuronale Netz realisiert eine IVansformation von Eingabewerten in Ausgabewerte unter Verwendung der gewichteten Eingabefunktionen und der Schwellenwertfunktionen. Das Basisvorgehen in einem neuronalen Netz ist in Abbildung 2.3 veranschaulicht, Zu den Vorteilen neuronaler Netze gehoren die Lernfahigkeit durch Anpassung der Gewichtsfunktionen in den Neuronen sowie ein robustes Verhalten bei mit Fehlern behafteten, verrauschten Eingabedaten. Es konnen nichthneare, komplexe Punktionen gut durch neuronale Netze abgebildet werden. Eine wesentliche Schwache neuronaler Netze besteht darin, dass bei leicht veranderten Situationen jeweils neue neuronale Netze konstruiert werden miissen. Das macht neuronale Netze fiir Anderungen des Produktmixes oder der Einsteuerungsstrategie empfindlich. Das bedeutet.

34

KAPITEL 2. STEUERUNGSANSATZE Eingabeschicht

Interne Schicht

FUR KOMPLEXE Interne Schicht

PRODUKTIONSSYSTEME Ausgabeschicht

Abbildung 2.3: Aufbau eines neuronalen Netzes

dass neuronale Netze auf Grund der wenig flexiblen Struktur beziiglich Ein- und Ausgabe im Wesentlichen fiir statische Probleme geeignet sind. In Produktionssystemen mit Dynamik und Turbulenzen stehen haufig keine Lerndaten zur Verfiigung, da historische Daten fiir die aktuelle Situation fehlen. Auf Grund der hohen Komplexitat der Netze werden diese in vielen Fallen nur fiir Schedulingprobleme geringer Komplexitat benutzt. Die Anwendung neuronaler Netze auf Job-Shop-Schedulingprobleme ist beispielsweise in [105] beschrieben worden. Andere Anwendungen sind in [277] diskutiert worden. In [191, 157] werden neuronale Netze zur Festlegung von verfahrensspezifischen Parametern der Apparent-TardinessCost-Prioritatsregel und der Batched-Apparent-Tardiness-Cost-Prioritatsregel verwendet.

2.6.4.2

Induktive Entscheidungsbaume

Induktives Lernen ist ein Zustandsklassifikationsprozess. Der Zustandsraum kann als Hyperebene aufgefasst werden. Die Trainingsdaten umfassen • Situationsbeschreibungen in Form von Bedingungen, • Entscheidungen, die unter den vorliegenden Bedingungen getroffen worden sind. Der induktive Lernalgorithmus nimmt eine Segmentierung des durch die Hyperebene reprasentierten Zustandsraumes in Segmente (Teilhyperebenen) vor. Jeder Teilhyperebene ist eindeutig eine bestimmte Entscheidung zugeordnet. Falls ein durch eine bestimmte Situationsbeschreibung gegebenes Problem gelost werden soil, wird zunachst ein entsprechender Punkt in der Hyperebene berechnet. Dann wird diejenige Teilhyperebene ermittelt, die den Punkt enthalt. Anschhefiend

2.6. STEUERUNGSANSATZE

DER KUNSTLICHENINTELLIGENZ

35

wild die zur Teilhyperebene zugehorige Entscheidungsregel angewandt [184]. Ein Beispiel fiir einen induktiven Lernalgorithmus ist durch den IDS (Iterative Dichotomister)-Algorithmus und dessen Weiterentwicklungen gegeben [207]. IDS verwendet Testfalle, um Wenn-Dann-Regeln abzuleiten, aus denen ein Entscheidungsbaum abgeleitet wird. Mit Hilfe des Entscheidungsbaumes konnen Objekte auf Grund ihrer Attributwerte klassifiziert werden. Die Knoten des Entscheidungsbaumes enthalten Attribute der zu klassifizierenden Objekte. Die Zweige des Baumes reprasentieren unterschiedliche Werte fiir das durch den Vaterknoten dargestellte Attribut. Die Blatter des Baumes bestimmen Klassen, zu denen die Objekte gehoren. Zur Berechnung von giinstigen Attributmengen fiir die Einteilung der Objektmenge in Klassen wird der Entropiebegriff verwendet. Es wird die Entropie zur Messung des Informationsgehaltes fiir jedes einzelne Attribut angewandt. Anschliefiend werden durch einen iterativen Dekompositionsprozess, der die Minimierung der Gesamtentropie zum Ziel hat, Regeln berechnet. Dieses Verfahren wird in [185] verfeinert, indem Fuzzy-Methoden zur Beschreibung der Klassengrenzen angewandt werden. Induktive Entscheidungsbaume werden in [157] zur Festlegung von verfahrensspezifischen Parametern der Appaxtent-Tardiness-Cost-Prioritatsregel und der Batched-Apparent-Tardiness-CostPrioritatsregel verwendet.

2.6.4.3

Reinforcement-Learning

Das wesentliche Element von Reinforcement-Learning-Ansatzen [24S, 45] ist eine Strategic IT zur Auswahl von Aktionen aus dem Problemraum. Die Strategic TT definiert Aktionen, die in Abhangigkeit von bestimmten Zustanden ausgefuhrt werden. Es gilt: 7r:S

xA-^[0,l],

wobei mit S die Zustandsmenge und mit A die Menge der moglichen Aktionen bezeichnet werden. 7r(s, a) ist die Wahrscheinhchkeit, dass bei Vorhegen des Zustands s 6 5 die Aktion a e A ausgefiihrt wird. Einem Paar (TT, S) wird durch

V^{s):=EJf:^'n^,^,\st \fc=0

= s) /

ein Wert zugewiesen. Eine Strategic, der vom Initialzustand s ausgehend gefolgt wird, kann somit bewertet werden. Die Grofie 7 stellt einen Diskontierungsfaktor dar. Die Bezeichnung r^ wird fiir den Nutzen verwendet, den man bei Ausfiihrung der Aktion at zum Zeitpunkt t erzielt. Anstelle einer optimalen Strategic n* wird versucht, cine optimalc Wertfunktion V*{s):=max^V''{s) zu lerncn. Temporal-Differcnce-Learning wird dafiir angewandt. Die Wertfunktion V* wird durch die Approximation / ( s , w) ersetzt. Die Groi^c w stellt einen Vcktor dar, der Parameter der Punktionsapproximation (z.B. Gewichte cines neuronalen Netzes) enthalt. Falls eine feste Strategic

36

KAPITEL 2. STEUERUNGSANSATZE

FUR KOMPLEXE

PRODUKTIONSSYSTEME

eriernt werden soil, kann wie folgt vorgegangen werden. Im Schritt t -\- 1 wird der Fehler 5t des Temporal-Difference-Learnings aus Schritt t berechnet: 6t := n+i -\-rff(st+u w) - f{st, w). Anschliei3end wird ein geglatteter Gradient e^ := grad^ f{st, w) + \et-i berechnet. Mit A wird ein Glattungsparameter bezeichnet, der den Gradienten aus Schritt ^ - 1 mit dem aktuellen Gradienten verkniipft. Der Gradient wird zur Berechnung korregierter Parameterwerte Ait; := adtet verwendet. Die Grofie a bezeichnet die Lernrate. Zur Ermittlung optimaler Strategien wird das Verfahren der Wertiteration eingesetzt [243, 45]. Reinforcment-Lerning-Ansatze sind zur Losung von Schedulingproblemen u.a. in [278, 26, 45] angewandt worden.

2.6.5

Verfahren der Verteilten Kiinstlichen Intelligenz

Verfahren der Verteilten Kiinstlichen Intelligenz (VKI) [266] sind in den letzten 15 Jahren in den Mittelpunkt des Interesses fur Produktionssteuerungsprobleme geriickt [218]. Dafiir gibt es im Wesentlichen zwei Griinde. Zum einen wurden in den letzten Jahren bedeutende Fortschritte bei der theoretischen Fundierung und experimentellen Untersuchung von Systemen der Verteilten Kiinstlichen Intelligenz erreicht. Gleichzeitig erlaubt die Entwicklung von entsprechender Middleware (RMI, CORE A, .NET) und der Java- und C#-Programmiersprache eine vergleichsweise bequeme Entwicklung von derartigen Systemen. Das Wissenschaftsgebiet der Verteilten Kiinstlichen Intelligenz besteht aus den nachfolgenden Teilgebieten [113]: • Parallele Kiinstliche Intelligenz, • verteiltes Problemlosen in den Auspragungen blackboard-basierte Systeme [42] und kooperatives verteiltes Problemlosen [174], • Multi-Agenten-Systeme. Verfahren der Parallelen Kiinstlichen Intelligenz oder des verteilten Problemlosens werden an dieser Stelle nicht diskutiert. In dieser Arbeit soil der Schwerpunkt auf Multi-Agenten-Systemen liegen, da diese besonders gut zur Losung von dynamischen Problemstellungen in einem turbulenten Umfeld geeignet sind. 2.6.5.1

Multi-Agenten-Systeme

Multi-Agenten-Systeme dienen der Beschreibung von Beziehungen zwischen verschiedenen Agenten, die Entscheidungen treffen. Ausgehend von einem komplexen Problem wird in einem MultiAgenten-System eine zu losende Aufgabe zunachst in Teilaufgaben zerlegt, diese werden dann

2.6. STEUERUNGSANSATZE

DER KUNSTLICHENINTELLIGENZ

37

einzelnen Agenten zugeordnet und von diesen gelost. Im letzten Schritt werden die Teillosungen zur Losung des Ausgangsproblems zusammengesetzt [266, 113]. Ein Agent besteht aus einer administrativen Komponente, die fiir den Kommunikationsprozess verantwortlich ist. Weiterhin besitzt ein Agent eine Koordinations- bzw. Optimierungskomponente, die die Regeln und das Vorgehen zur Problemlosung zur Verfligung stellt. Es bestehen vielfaltige Ausgestaltungsmoglichkeiten fiir Agentenarchitekturen. Fiir eine Beschreibung wichtiger Architekturen fiir Einzelagenten wird auf [266] verwiesen.

2.6.5.2

Motiviation fiir agentenbasierte Produktionssteuerungssysteme

Agentenbasierte Systeme spielen in der Produktionssteuerung aus folgenden Griinden eine grol3e RoUe [193, 178]: 1. Aufbauend auf der physischen Dekomposition des Basissystems eines Produktionssystems kann haufig eine Modularisierung des Steuerungssystems vorgenommen werden. Agenten sind gut fiir die Modellierung modularer Systeme geeignet, da sie Objekte sind. 2. Produktionsprozesse sind haufig in natiirlicher Art und Weise dezentral organisiert. Da Agenten proaktive Objekte sind, sind sie gut geeignet, dezentrale Entscheidungen vorzunehmen. Agenten haben dabei den Vorteil, dass sie nur lokale Daten benotigen. Auf diese Weise erscheint es moglich, die heute vorherrschenden zentralen betrieblichen Informationssysteme, die im Wesentlichen durch zentrale Steuerungsrechner und zentrale Datenbanken gebildet werden, durch agentenbasierte Steuerungssysteme mit lokaler Datenhaltung zu ersetzen. 3. Produktionsprozesse sind zeitUchen Veranderungen unterworfen. Die Veranderungen betreffen das Basissystem, den Basisprozess, das Steuerungssystem und den Steuerungsprozess. Agentenbasierte Architekturen haben den Vorteil, dass auf derartigen Architekturen basierende Steuerungssysteme leicht an die Veranderungen in den Produktionssystemen angepasst werden konnen. Dazu kann es notwendig sein, dass neue Agenten zum agentenbasierten Steuerungssystem hinzugefiigt oder nicht mehr benotigte Agenten entfernt werden. Das kann, im Gegensatz zu traditionellen Systemen, zur Laufzeit des Systems erfolgen. Die Software fiir einzelne Agenten ist von geringerer Komplexitat und folgUch leichter zu entwickeln und zu warten als das bei den entsprechenden zentralen Ansatzen der Fall ist. Es wird deutlich, dass die Einfiihrung agentenbasierter Systeme durch softwaretechnische Gesichtspunkte und durch Datenhaltungsgesichtspunkte motiviert wird. Algorithmische Aspekte spielen eine untergeordnetere RoUe. 2.6.5.3

Existierende agentenbasierte Produktionssteuerungssysteme

Die meisten der existierenden agentenbasierten Produktionssteuerungssysteme sind lediglich prototypisch realisiert worden. Als Steuerungsmethode werden iiberwiegend Varianten des Kontrakt-

38

KAPITEL 2. STEUERUNGSANSATZE

FUR KOMPLEXE

PRODUKTIONSSYSTEME

netzansatzes eingesetzt. Die nachfolgenden Defizite sind festzustellen: • Die Systeme werden iiberwiegend zur Steuerung von Produktionssystemen niedriger Komplexitat eingesetzt. • Es wird nicht umfassend und systematisch nachgewiesen, dass die entwickelten Systeme eine bessere Steuerung der jeweiligen Produktionssysteme ermoglichen [109]. • Die Systeme sind voUstandig heterarchisch organisiert. In komplexen Produktionssystemen erscheint aber der Einsatz von hierarchischen Steuerungselementen in gewissem Umfang giinstig zu sein [60]. • Die eingesetzten Steuerungsverfahren, die im Wesentlichen auf dem Kontraktnetzansatz basieren, sind nur unzureichend geeignet, um Maschinenbelegungsprobleme in komplexen Produktionssystemen zu losen. Wie in [224] diskutiert, erscheint eine starkere Einbeziehung von Verfahren des Operations Research und der Kiinstlichen Intelligenz bei der Ausgestaltung von Multi-Agenten-Systemen fiir die Produktionssteuerung sinnvoU zu sein. Diese These wird in Anfangen durch die Arbeiten von Weigelt [264] bestatigt, der Prioritatsregeln und Eckterminverschiebungsmechanismen zur agentenbasierten Feinplanung einsetzt. Eine umfassende Beschreibung verschiedener existierender agentenbasierter Produktionssteuerungssysteme ist u.a. in [229] zu finden. Industrielle Anwendungen der Agententechnologie werden von Parunak in [194] diskutiert. Multi-Agenten-Systeme fiir die Produktionssteuerung konnen aus funktionalen oder adaptiven Agenten bestehen. Andere Auspragungen von Agentenarchitekturen werden in Kapitel 6 diskutiert. Kontraktnetzartige Steuerungsansatze sind fiir die Maschinenbelegungsplanung weit verbreitet. Sie sind aber fiir den Einsatz in komplexen Produktionssystemen nur mit Einschrankungen geeignet. Holonische Produktionssteuerungssysteme erlauben in einem starkeren Mafie die Einbeziehung von hierarchischen Strukturierungsinstrumenten als heterarchische Multi-Agenten-Systeme, sind aber traditionell starker auf die unmittelbare Maschinensteuerung ausgerichtet als auf die Losung von Maschinenbelegungsproblemen. Aus diesen Griinden werden anschliefiend funktionale und adaptive Agenten, Kontraktnetze sowie holonische Produktionssteuerungssysteme studiert.

2.6.5.4

Funktionale Agenten

Funktionale Agenten in der Produktionssteuerung reprasentieren eine funktionale Fahigkeit eines Steuerungssystems. Typischerweise wird eine funktionale Dekomposition des Steuerungssystems durchgefiihrt und jeder zu realisierenden Funktion ein Agent zugeordnet. Funktionale Agenten kommunizieren direkt miteinander, indem eine Funktion andere Funktionen aufruft und bestimmte

2.6. STEUERUNGSANSATZE

DER KUNSTLICHENINTELLIGENZ

39

Ergebnisse erwartet [14]. Komplexe agentenbasierte Steuerungssysteme aus funktionalen Agenten sind beispielsweise in [279] beschrieben worden. Agentensysteme, die aus funktionalen Agenten bestehen, erfiillen nur unzureichend die in Abschnitt 2.6.5.2 genannten Griinde fiir agentenbasierte Steuerungssysteme.

2.6.5.5

Adaptive Agenten

In vielen Produktionssystemen treten zeitabhangig Veranderungen ein. Auf diese Veranderungen kann wie in Abschnitt 2.3 dargestellt durch Zielmodifikation oder Modifikation des internen M o dells reagiert werden. Agenten besitzen als entscheidungsfahige Einheiten eigene Ziele, diese werden bei adaptiven Agenten in situationsabhangiger Art und Weise angepasst. Umgekehrt verfiigen Agenten haufig iiber eine eigene Reprasentation der Umwelt, die durch geeignete interne Modelle realisiert werden kann. Anderungen in der Umwelt, d.h. des Basisprozesses bzw. des Basissystems, fiihren zu Anderungen des internen Modells. In [129] werden evolutionare Algorithmen (vergleiche [145] fiir Details zu dieser Verfahrensklasse) zur Adaption von Prioritatsregeln in Flexiblen Fertigungssystemen benutzt. Die Anzahl der Lose in der Warteschlange vor der Maschine und die Anzahl der notwendigen Umriistoperationen werden durch Maschinenagenten minimiert. Auftragsagenten sind daran interessiert, die Durchlaufzeit des ihnen zugeordneten Loses durch das Produktionssystem zu minimieren. Den Auftragsagenten sind Regeln zugeordnet, nach denen die Auswahl derjenigen Maschine erfolgt, auf welcher der nachste Prozess-Schritt ausgefiihrt werden soil. Den Maschinenagenten sind umgekehrt Prioritatsregeln zugeordnet, nach denen die Auswahl der Lose, die als nachste zu bearbeiten sind, vorgenommen wird. Der evolutionare Algorithmus legt Gewichte fest, welche die Zuordnungs- bzw. Prioritatsregeln in einer kombinierten Kegel gewichten. In [20] wird ein Verfahren vorgeschlagen, das adaptive Agenten zur Maschinenbelegungsplanung in automatisierten Produktionssystemen verwendet. In Echtzeit erfolgt eine Adaption einer Population aus Losprioritatsmustern durch einen genetischen Algorithmus. Die Populationselemente werden in Abhangigkeit von der Situation im Basisprozess bzw. Basissystem aktualisiert. In [26] wird ein Verfahren zur Ablaufplanung von Losen in einer Fliefifertigung vorgestellt, das die Auswahl einer giinstigen Maschine in jeder Stufe des Fliefifertigungsprozesses ermoglicht. Mit Hilfe des Reinforcement-Learning-Ansatzes werden Abschatzungen iiber die noch notwendige Zeit bis zur Fertigstellung der Lose ermittelt. Die vorgeschlagenen Lernverfahren ermoglichen eine Anpassung des jeweiligen Steuerungssystems an Anderungen im Basissystem bzw. Basisprozess. Eine derartige situationsabhangige Anpassung wird in derzeitigen Produktionssteuerungssystemen von Menschen durchgefiihrt. Eine automatische Anpassung erscheint zur Zeit nur fiir einfache Steuerungsalgorithmen moglich zu sein.

40

KAPITEL 2. STEUERUNGSANSATZE

2.6.5.6

FUR KOMPLEXE

PRODUKTIONSSYSTEME

Kontraktnetzartige Steuerungsverfahren

Agentenbasierte Systeme zur Produktionssteuerung benutzen haufig Varianten des Kontraktnetzansatzes [233] zur Losung der Maschinenbelegungsprobleme. Ausgehend von einer physischen Dekomposition des Basissystems und des Basisprozesses werden Maschinenagenten, die Maschinen reprasentieren, und Auftragsagenten, die Lose abbilden, betrachtet (vergleiche auch die Ausfiihrungen in Abschnitt 4.4). Weiterhin werden Koordinationsagenten, die Anfragen von Auftragsagenten und Angebote von Maschinenagenten in Einklang bringen, eingefiihrt [275]. In den Arbeiten [128, 182, 186, 196, 218, 247] werden beispielsweise derartige Ansatze in unterschiedlicher Ausgestaltung angewandt. Haufig werden aber ausschliefilich Produktionssysteme niedriger Komplexitat (zum Beispiel Flexible Fertigungszellen) betrachtet. Eine Leistungsanalyse erfolgt, indem die agentenbasierten Steuerungsansatze mit prioritatsregelbasierten Steuerungsansatzen verglichen werden. Stabilitatsfragen der vorgeschlagenen Ansatze werden nicht diskutiert. Weiterhin bleibt unklar, warum und wie eine Steuerung in Richtung eines global giinstigen Systemverhaltens erfolgen soil. Die vorgeschlagenen Ansatze sind mit vielen Parametern behaftet, deren situationsabhangige Wahl umfangreiche Simulationsstudien erfordert. Einen umfassenden Uberblick zu verhandlungsbasierten Losungsansatzen in Multi-AgentenSystemen gibt Kraus in der Monographic [115]. Uber Erfahrung mit einem agentenbasierten Steuerungsansatz auf Basis eines Kontraktnetzsystems in einem Industrieunternehmen wird in [242, 32] berichtet. Insgesamt erscheint eine Steuerung komplexer Produktionssysteme unter globalen Gesichtspunkten mit Varianten des Kontraktnetzansatzes im Vergleich zu konventionellen Prioritatsregeln neben der Moglichkeit der Verteilung auf mehrere Rechner keine grofien Vorteile zu versprechen.

2.6.5.7

Holonische Ansatze zur Produktionssteuerung

Ein Holon wird definiert als eine autonome und kooperative Einheit eines Produktionssystems, die zur Transformation, dem Transport und dem Speichern von physikalischen und Informationsobjekten dient [138]. Holonen bestehen aus einem Steuerungsteil und einem (optionalen) Teil zum Ausfiihren von physischen Operationen [139]. Ein Holon kann selber aus anderen Holonen bestehen. Unter einer Holarchie wird ein aus Holonen bestehendes System verstanden, in dem die Holonen kooperieren, um ein bestimmtes Ziel zu erreichen. Multi-Agenten-Systeme sind eine geeignete Technologic, um holonische Produktionssteuerungssysteme softwaretechnisch zu realisieren [130, 61, 62]. Holonische Produktionssteuerungssysteme konnen unter Verwendung der PROSA (ProductResource-Order-Staff-Architecture)-Referenzarchitektur [251, 273, 23] entwickelt werden. Eine Referenzarchitektur ist definiert als eine Menge von Designprinzipien, die fiir einen bestimmten Problembereich auf Grund einer identischen Tiefenstruktur genutzt werden konnen. Eine Referenzarchitektur schlagt eine Aufteilung des Systems in Einzelbestandteile vor, legt die Aufgaben der Systembestandteile fest und spezifiziert das Zusammenwirken der in der Referenzarchitektur fest-

2.7. HYBRIDE STEUERUNGSANSATZE

FUR PRODUKTIONSSYSTEME

41

gelegten Systembestandteile. In der PROSA-Referenzarchitektur werden die folgenden Bestandteile von holonischen Produktionssteuerungssystemen identifiziert: • Auftragsagenten: Auftragsagenten reprasentieren einen festen Fertigungsauftrag in einem Produktionssystem. Sie dienen der Verwaltung der relevanten Informationen und kapseln die zur Maschinenbelegungsplanung aus Auftragssicht notwendige Entscheidungslogik. Auftragsagenten entscheiden, auf welchen Maschinen die Fertigungsauftrage ausgefiihrt werden soUen. • Ressourcenagenten: Ressourcenagenten dienen der Modellierung von Ressourcen in Produktionssystemen. Sie verwalten die zur Maschinenbelegung notwendigen Informationen und enthalten die zur Maschinenbelegung notwendige Entscheidungslogik. • Produktagenten: Produktagenten kapseln Produktwissen. Produktwissen liegt in Form von Arbeitsplanen und Qualitatsvorschriften vor. Auftrags-, Ressourcen- und Produktagenten werden als Entscheideragenten bezeichnet. Entscheideragenten werden bei der Entscheidungsfindung durch Dienstagenten unterstiitzt. Dienstagenten kapseln beispielsweise Algorithmen zur Maschinenbelegungsplanung. Durch die Unterteilung in Entscheider- und Dienstagenten wird eine Entkopplung zwischen der Struktur des Steuerungssystems und den Steuerungsalgorithmen vorgenommen. Holonische Produktionssteuerungssysteme haben im Vergleich zu rein heterarchisch organisierten Multi-Agenten-Systemen den entscheidenden Vorteil, dass durch den rekursiven Aufbau von Holonen hierarchische Elemente in den Steuerungsprozess einbezogen werden konnen und dass zur Laufzeit des Steuerungssystems dynamisch, d.h. situationsabhangig, zwischen unterschiedlichen Steuerungsparadigmen gewahlt werden kann. Forschungsbedarf besteht aber bei Anwendung der Theorie verteilter Entscheidungen zur hierarchischen Strukturierung von holonischen Produktionssteuerungssystemen und beim Einsatz hoherwertiger Steuerungsverfahren.

2.7 2.7.1

Hybride Steuerungsansatze fur Produktionssysteme Begriffsbestimmung und Beispiele

Neben Verfahren des Operations Research und der Kiinstlichen Intelligenz werden Verfahren der optimalen KontroUtheorie zur Steuerung von Produktionssystemen vorgeschlagen. Entsprechende Ansatze sind u.a. in [117, 265, 82] beschrieben worden. Ansatze der KontroUtheorie wurden mit Fluid-Modellen in [21] kombiniert. In der vorliegenden Arbeit wird auf eine weitere Darstellung verzichtet, da derartige Verfahren nur bedingt fiir Produktionssysteme mit terminorientierten Produktionszielen geeignet sind.

42

KAPITEL 2. STEUERUNGSANSATZE

FUR KOMPLEXE

PRODUKTIONSSYSTEME

Unter einem hybriden Steuerungsansatz fiir komplexe Produktionssysteme wird in dieser Arbeit ein Steuerungssatz verstanden, der sowohl unterschiedliche Verfahren des Operations Research als auch der Kiinstlichen Intelligenz umfasst und geeignet kombiniert. Ein Beispiel fiir einen hybriden Ansatz ist durch das Logistics Management System (LMS) von IBM gegeben [241]. Das System enthalt Dispatchentscheidungseinheiten, die KontroUzonen um bestimmte Maschinengruppen aufbauen. Die Zonen werden unter Verwendung von Kanbanartigen Mechanismen separat gesteuert. Dazu werden fiir die einzelnen Waferebenen der Produkte Kanbans eingefiihrt. Jede Zone enthalt eine Bewertungseinheit, die auf Basis unterschiedlicher Bewertungskriterien Maschinenbelegungsentscheidungen trifft. Die Kanbans dienen zur Implementierung von OR- und KI-Konzepten. Ein weiteres Beispiel ist ein bei INTEL entwickeltes ScheduUngsystem [108]. In diesem System werden prioritatsregelbasierte Ansatze mit Simulationstechniken verbunden.

2.7.2

Hierarchische Steuerungsansatze

Hierarchische Steuerungsalgorithmen werden im Detail in Kapitel 3 untersucht. An dieser Stelle der Arbeit soUen hierarchische Steuerungsalgorithmen als spezielle hybride Steuerungsansatze dargestellt werden. Srivatsan, Bai und Gershwin beschreiben in [238] ein Framework, das fiir eine Entscheidungsfindung unter Echtzeitbedingungen geeignet ist. Es wird eine Aufteilung der Steuerungshierarchie in eine Menge von Ebenen vorgeschlagen. Den Ebenen sind Ereignisse zugeordnet, die mit unterschiedlicher Haufigkeit auftreten. Dieses ereignisbasierte Konzept wird in [74] weiter verfeinert und auf eine grofiere Klasse von hierarchischen Systemen angewandt. Auf jeder Steuerungsebene werden Entscheidungen getroffen, die der Erfiillung der Vorgaben hoherer Steuerungsebenen dienen und Kapazitatsrestriktionen der jeweiligen Steuerungsebene geniigen. Entscheidungen werden in Form von • Aktionen, • Vorgaben fiir untergeordnete Ebenen getroffen. Eine pyramidenformige Hierarchic wird aufgebaut, die das Ergebnis einer sowohl zeitlichen, d.h. ereignis-orientierten Dekomposition des Basisprozesses als auch einer raumlichorientierten Dekomposition des Basissystems ist. Die moglichen Ereignisse werden entsprechend der Haufigkeit ihres Auftretens, als charakteristische Frequenz bezeichnet, klassifiziert. Auf den oberen Ebenen der Hierarchic wird auf Ereignisse reagiert, die eine kleine charakteristische Frequenz haben, d.h. selten auftreten. Auf den unteren Ebenen werden entsprechende Ereignisse mit einer hoheren Frequenz behandelt. Auszufiihrende Prozess-Schritte auf den Maschinen sind diejenigen Ereignisse mit der hochsten Frequenz in komplexen Produktionssystemen. Jeder Ebene wird eine stochastische Kapazitatsmenge zugeordnet. Die Kapazitat muss stochastisch modelliert werden, da Schwankungen im

2.8. ANFORDERUNGSANALYSE

FUR EIN STEUERUNGSSYSTEM

43

Kapazitatsangebot, z.B. durch Maschinenausfalle, beriicksichtigt werden miissen. Neben der zeitlichen wird eine raumliche Dekomposition eingefiihrt, die sicherstellt, dass gewisse Annahmen iiber die zeitliche Dekomposition erfiillt sind. Zwischen den einzelnen Segmenten des zu steuernden Produktionssystems werden Lager eingefiihrt, deren Bestand dezentral gesteuert wird. Eine segmentiibergreifende Koordination erfolgt iiber die Bestandshohe in den einzelnen Lagern. In [238] wird eine funktionale Vier-Ebenen-Hierarchie fiir eine Halbleiterfabrik niedriger Komplexitat vorgeschlagen. Terminliche Aspekte werden in [238] nicht beriicksichtigt. In der Arbeit [254] wird eine hierarchische Zwei-Ebenen-Steuerung fiir den Frontendbereich einer Halbleiterfabrik beschrieben. Ein Optimierungsverfahren, das in Echtzeit arbeitet, bildet die obere Ebene der Hierarchic. Die obere Steuerungsebene ermittelt schichtweise Vorgaben fiir die untere Ebene. Dabei wird durch die obere Steuerungsebene das Ziel verfolgt, die Vorgaben hoherer Planungsebenen zu erfiillen. Die Maximierung des Durchsatzes und eine mogUchst geringe Abweichung des Bestandes zu Vorgaben hoherer Planungsebenen bilden die verfolgten Optimierungsziele. Auf der unteren Steuerungsebene wird eine Prioritatsregel verwendet, die derart angepasst wird, dass die langfristigeren Vorgaben der oberen Ebene erfiillt werden. Terminziele werden nicht beriicksichtigt. Es ist notwendig, hoherwertige Algorithmen auf den unteren Ebenen der Hierarchic einzusetzen. In [255] wird der Zwei-Ebenen-Ansatz aus [254] um eine dritte Ebene erweitert, die zur Parameterschatzung fiir das Optimierungsverfahren der mittleren Ebene dient.

2.8

Anforderungsanalyse fiir ein Steuerungssystem

Die in den Abschnitten 2.5 und 2.6 beschriebenen Steuerungsverfahren haben die naxihfolgenden Nachteile: 1. Dezentrale Verfahren, d.h. prioritatsregelbasierte Verfahren bzw. kontraktnetzartige Verfahren treffen Steuerungsentscheidungen unter Verwendung von raumhch bzw. zeitlich isoUerten Informationen. Es sind intensive Simulationsexperimente zur Bewertung der Leistungsfahigkeit des jeweiligen dezentralen Verfahrens notwendig. Eine Anpassung an veranderte Bedingungen ist kaum moglich. 2. Zentrale Verfahren, d.h. gemischt-ganzzahlige Optimierungsformuherungen, constraintbasierte Techniken bzw. lokale Suchverfahren haben den Nachteil, dass die fiir den Algorithmus notwendigen Daten zentral bereitgestellt werden miissen. Da eine grofie Klasse von Maschinenbelegungsproblemen NP-schwer ist [83], miissen geeignete Heuristiken zur Losung der Probleme entworfen werden. Die Rechenzeit fur derartige Heuristiken ist auf Grund der vorliegenden Problemgrofie fiir komplexe Produktionssysteme haufig trotz leistungsfahiger Rechentechnik zu hoch. Probleme werden dadurch verursacht, dass keine zulassigen Losungen fur das jeweilige Optimierungsproblem existieren und folglich Restriktionen relaxiert werden mussen. Im AUgemeinen sind zentrale Verfahren so ausgelegt, dass eine (zulassige) Losung

44

KAPITEL 2. STEUERUNGSANSATZE

FUR KOMPLEXE

PRODUKTIONSSYSTEME

fur das jeweilige Problem erst nach Beendigung der Berechnungen vorliegt. Die Verfahren sind somit nicht als Verbesserungsverfahren konzipiert, die zulassige Losungen iterativ in optimale Losungen umwandeln. In Produktionssystemen liegen dynamische und stochastische Prozessbedingungen vor. Aus diesem Grund sind Reschedulingmafinahmen haufig unvermeidlich. Dadurch wird das Problem zu langer Rechenzeiten weiter verscharft. Zusatzlich sind Stabilitatsprobleme fiir die gefundenen Losungen typisch, die zu einer groBen Nervositat des Produktionssystems fuhren. Die Beriicksichtigung unterschiedlicher, zum Teil gegenlaufiger Ziele ist schwierig zu realisieren. In der Praxis verwendete Werkstattsteuerungssysteme verfiigen iiber die folgenden Schwachen [236]: L Die Softwaresysteme basieren auf dem softwaretechnischen Stand Anfang der 90er Jahre bzw. haben in Anfangen eine Client-Server-Architektur. 2. Eine funktionale Erweiterung der Systeme ist nur schwer moglich. 3. Die Kommunikation bzw. der Informationsaustausch mit anderen informationsverarbeitenden Systemen ist nur kompliziert und umstandlich zu realisieren. 4. In den Systemen sind keine modernen Steuerungsalgorithmen enthalten. 5. Die Moglichkeit zum verteilten Losen von Problemen wird konzeptionell nicht ausgenutzt und ist softwaretechnisch schwer zu realisieren. Auf Grund einer zentralen Datenhaltung ist die Datenbereitstellung aufwendig. 6. Sie sind in erster Linie Systeme zur umfassenden Verwaltung von Produkt- und Produktionsdaten, unter dem Aspekt der Steuerung wirken sie iiberwiegend „passiv". Ein zu konzipierender neuartiger Steuerungsansatz muss folgenden Anforderungen geniigen: 1. Der Steuerungsansatz muss in der Lage sein, globale Ziele in die Entscheidungsfindung einzubeziehen. Dabei muss ein Kompromiss zwischen der dazu notwendigen Rechenzeit und der Losungsqualitat gefunden werden. Eine raumliche und zeitliche Dekomposition des zu losenden Steuerungsproblems muss vorgenommen werden, die zum einen Rechenbarkeit sicherstellt, andererseits aber zu einer hinreichenden Losungsqualitat fiihrt. Rechenbarkeit kann durch • Verteilung der Berechnungen auf mehrere Rechner, • Verringerung der Problemgrofie durch Aggregation erreicht werden. Die angestrebte Verteilung und Aggregation fiihrt zu einem verteilten hierarchischen Ansatz. Auf Grund der Verteilung der zu losenden Maschinenbelegungsprobleme

2.S. ANFORDERUNGSANALYSE

FUR EIN STEUERUNGSSYSTEM

45

kann gut mit dynamischen und stochastischen Prozessbedingungen umgegangen werden. Da von den Reschedulingaktivitaten stets nur partielle Telle des Basissystems unmlttelbar betroffen sind, 1st die Nervosltat innerhalb des komplexen Produktlonssysteras nledrlger. 2. Der Steuerungsansatz muss „any-time"-Algorlthmen umfassen. Ein „any-time"-Algorithmus zelchnet slch dadurch aus, dass zu jedem Zeltpunkt t > 0 die bis zu diesem Zeltpunkt gefundene beste Losung zur Verfiigung steht. „ Any-time"-Algorlthmen slnd Verbesserungsverfahren. Die „any-tlme"-Elgenschaft unterstiitzt Insbesondere die von Kirn [113] geforderte Online-Fahlgkelt moderner Planungs- und Steuerungsalgorlthmen in Multl-AgentenSystemen. 3. Der Steuerungsansatz muss mit lokalen Daten arbeiten. Dieses Vorgehen hat den Vorteil, dass der betrachtllche zeitllche Aufwand zur Bereitstellung der Daten aus zentralen Informatlonssystemen entfallt und die Daten dort verarbeitet werden, wo sie bereltgestellt werden. 4. Der Steuerungsansatz muss eine situatlonsabhangige Parametrisierung der Steuerungsalgorlthmen ermoglichen. 5. Die Steuerungsalgorlthmen miissen lelcht austauschbar sein. Helm Design des Steuerungsansatzes 1st deshalb darauf zu achten, dass eine Trennung zwischen Steuerungssystem und Steuerungsalgorlthmen stattfindet. 6. Die Steuerungsalgorlthmen miissen in der Lage sein, gegenlaufige Steuerungsziele geeignet zu beriickslchtlgen. Der zu entwlckelnde Steuerungsansatz muss in ein neuartiges Steuerungssystem eingebettet werden. An dieses Steuerungssystem miissen die nachfolgenden Anforderungen gestellt werden: 1. Das Steuerungssystem muss ofFen sein, d.h., eine funktionale Erwelterung des Systems muss zur Laufzelt des Systems mogllch sein. 2. Das System muss in der Lage sein, mit anderen Systemen zu kommunlzieren und Informatlonen auszutauschen. 3. Das System muss den Elnsatz vertellter Steuerungsalgorlthmen unterstiitzen. Das bedeutet Insbesondere, dass die Steuerungsalgorlthmen ausschliefilich auf lokalen Daten arbeiten. Eine geelgnete Synchronisierung der vertellten Problemlosungselnhelten muss durch das Steuerungssystem slchergestellt werden. 4. Das Steuerungssystem muss skaherbar sein, d.h., mit zunehmender Komplexltat des Basisprozesses und des Basissystems darf slch die Leistungsfahigkelt des Steuerungsansatzes unter Berechenbarkeltsgesichtspunkten nlcht in starkem Mafie verrlngern.

46

KAPITEL 2. STEUERUNGSANSATZE

FUR KOMPLEXE

PRODUKTIONSSYSTEME

5. Die Architektur des Steuerungssystem muss eine Trennung zwischen Struktur des Systems und den Steuerungsalgorithmen vornehmen. Dadurch ist insbesondere auch eine leichte Austauschbarkeit von Steuerungsalgorithmen zur Laufzeit des Systems gewahrleistet. 6. Die Architektur des Systems muss den Einsatz von diskreter ereignis-orientierter Simulation zur Leistungsbewertung des Steuerungssystems unabhangig vom realen Produktionsprozess ermoghchen. In Kapitel 3 werden strukturelle Aspekte eines verteilten hierarchischen Steuerungsansatzes herausgearbeitet. Das daran anschliefiende Kapitel 4 beschaftigt sich mit der Gestaltung von an die Struktur des verteilten hierarchischen Steuerungssystems angepassten Steuerungsalgorithmen. Pragen der konzeptionellen Realisierung von Koordinationsmechanismen werden in Kapitel 5 diskutiert. Kapitel 6 entwickelt eine Softwarearchitektur fiir das neuartige Steuerungssystem. Das anschhefiende Kapitel 7 dient der Leistungsbewertung des vorgeschlagenen Steuerungssystems.

Kapitel 3 Verteilte hierarchische Produktionssteuerung Verteilte hierarchische Steuerungssysteme sind ein Kompromiss zwischen dezentralen und zentralen Ansatzen. Die Einfiihrung von Hierarchien dient dazu, komplexe Probleme raumUch und zeithch zu dekomponieren und auf diese Art und Weise Losungen fiir das untersuchte Problem zu ermoglichen. In diesem Kapitel wird ein hierarchisches Steuerungsverfahren fiir komplexe Produktionssysteme vorgeschlagen. Dafur werden die Hierarchieebenen Produktionssystemsteuerungsebene, Produktionsbereichssteuerungsebene und Maschinengruppensteuerungsebene betrachtet. Fiir jede dieser Hierarchieebenen werden entsprechende Entscheidungsmodelle entwickelt. AnschUe6end wird eine Agentifizierung des vorgeschlagenen Steuerungsansatzes vorgenommen.

3.1 3.1.1

Hierarchische Steuerungsansatze Hierarchische Strukturen

Hierarchische Systeme werden u.a. in [223, 59, 144, 143] untersucht. Unter einem hierarchischen System wird ein System verstanden, das aus Objekten besteht, die in einer asymmetrischen Beziehung beziiglich • ihrer Entscheidungsrechte, • ihres Informationszustands, • des Zeitpunkts der Entscheidungsfindung stehen. Es wird zwischen konstruktiven und organisatorischen Hierarchien unterschieden. Konstruktive Hierarchien sind dadurch charakterisiert, dass ein symmetrischer Informationszustand vorliegt, d.h., es gibt genau eine entscheidungsfindende Einheit fiir alle Ebenen des hierar-

48

KAPITEL 3. VERTEILTE HIERARCHISCHE

PRODUKTIONSSTEUERUNG

chischen Systems, die zu bestimmten Zeitpunkten unter Beriicksichtigung der vorliegenden Informationen Entscheidungen trifft. Organisatorische Hierarchien besitzen als wesentliches Merkmal einen asymmetrischen Informationszustand. Organisatorische Hierarchien treten in den Auspragungen Entscheidungszeitpunkthierarchien und Fiihrungshierarchien auf. Von einer Entscheidungszeitpunkthierarchie wird gesprochen, falls genau eine entscheidungsfindende Einheit vorliegt. Entscheidungszeitpunkthierarchien bestehen aus Ebenen, die Entscheidungen zu unterschiedlichen Zeitpunkten treffen. Die Entscheidungen basieren auf Grund der Zeitabhangigkeit auf unterschiedlichen Informationen. Angenommen, die iibergeordnete Hierarchieebene trifft eine Entscheidung zum Zeitpunkt t = to und die untergeordnete Ebene eine Entscheidung zum Zeitpunkt t = ti mit ^i > ^o, dann basieren die Entscheidungen der iibergeordneten Hierarchieebene lediglich auf den Informationen, die zum Zeitpunkt ^ = ^o zur Verfiigung stehen. Die veranderte Situation zum Zeitpunkt t = ti wird nicht beriicksichtigt. Hierarchische Systeme, welche die Ermittlung eines Planes und dessen Implementierung sicherstellen, sind typische Beispiele fiir Entscheidungszeitpunkthierarchien. In diesem Fall werden bei der Berechnung eines Planes Storungssituationen nur naherungsweise beriicksichtigt, so dass zum Zeitpunkt der Planimplementierung haufig eine von den Planungsannahmen abweichende Situation im zu beeinflussenden System vorUegt. Fiihrungshierarchien sind dadurch gekennzeichnet, dass jede Ebene ihre eigene entscheidungsfindende Einheit besitzt, die iiber private Informationen und Ziele verfiigt. Ein typisches Beispiel fiir eine Fiihrungshierarchie ist ein hierarchisches System mit einer Koordinationsinstanz.

3.1.2

Verteilte Entscheidungsfindung in hierarchischen Systemen

Verteilte Entscheidungsfindung beschaftigt sich mit den Entscheidungen, die in unterschiedlichen Teilen eines Systems getroffen werden. Demzufolge besteht eine wesentliche Aufgabe der verteilten Entscheidungsfindung darin, die unterschiedlichen Entscheidungen zu koordinieren. Es werden in Anlehnung an Schneeweifi [223, 224] vier unterschiedliche Koordinationsgrade unterschieden: 1. Datenintegration, 2. Integration unterschiedlicher Systeme durch reaktive Verhandlungen, 3. Integration unterschiedlicher Systeme durch Planungsaktivitaten, 4. Integration unterschiedlicher Systeme durch Fiihrungsaktivitaten. Die Koordinationsgrade unterscheiden sich in der Kompliziertheit der Kommunikation und der Integration. Die Datenintegration stellt den niedrigsten, die Integration durch Fiihrungsaktivitaten umgekehrt den hochsten Koordinationsgrad dar. Hierarchische Strukturen und verteilte Entscheidungsfindung stehen in engem Zusammenhang. Das wird im Wesentlichen dadurch verursacht,

3.1. HIERARCHISCHE STEUERUNGSANSATZE

49

dass die verschiedenen Entscheidungen koordiniert werden mussen, dazu haufig aber eine Selbstkoordination nicht ausreichend ist. Es ist deshalb notwendig, hierarchische Strukturen einzufiihren, die das Recht haben, direkt zu koordinieren oder Regeln fiir die Koordination festzulegen. Entscheidungsprobleme in praktischen Anwendungen werden durch die beiden nachfolgenden trivialen Fakten beeinflusst: • Wenn eine Entscheidung ansteht, muss diese getroffen werden. Die Entscheidung kann nicht verzogert werden, da dies dazu fiihrt, dass keine Aktion ausgewahlt und implementiert wird. • Die Unsicherheit iiber die Folgen der Implementierung einer gewahlten Aktion im Rahmen der Entscheidungsfindung fiihrt dazu, dass eine formale Situationsbeschreibung, Voraussetzung fiir die rationale Auswahl einer Aktion aus einer Menge von moghchen Aktionen, nicht vorgenommen wird. Diese beiden Tatsachen fiihren zum Dilemma der Entscheidungsfindung [223]. Auf der einen Seite miissen Entscheidungen ohne zeitliche Verzogerung getroffen werden, andererseits ist Zeit notwendig, um die vorliegende Situation, in der die Entscheidung getroffen werden muss, besser zu verstehen. In komplexen Entscheidungssituationen wird versucht, dieses Dilemma durch einen hierarchischen Ansatz zu vermeiden. Es wird im Wesentlichen eine FamiUe von Entscheidungsproblemen definiert, deren Losung in einer sequentiellen oder falls moglich in einer nebenlaufigen Art und Weise vorgenommen wird. Die Losung der iibergeordneten Entscheidungsprobleme dient zur Parameterfestlegung bzw. Parameterauswahl fiir die in der sequentiellen Abarbeitung nachgeordneten Entscheidungsprobleme. Dieses Vorgehen entspricht der in Abschnitt 2.3 dargestellten Zielmodifikation durch ein intervenierendes System. Das Gesamtproblem ist gelost, wenn alle auf diese Art und Weise erhaltenen Entscheidungsprobleme gelost sind.

3.1.3

BsLsismodell und Notationen fiir hierarchische Systeme

3.1.3.1

Framework fur eine hierarchische Steuerung

Ohne Einschrankung der AUgemeinheit wird zunachst die Situation betrachtet, dass genau zwei Ebenen im hierarchischen Steuerungssystem vorhanden sind. Die beiden Ebenen werden als iibergeordnete und untergeordnete Ebene des Steuerungssystems bezeichnet. Unter einer Anweisung (s3monym als Vorgabe bezeichnet) soil im Folgenden die Beeinflussung der untergeordneten Ebene durch die libergeordnete Ebene verstanden werden. Die libergeordnete Ebene des Steuerungssystems hat das Ziel, eine (beziiglich einer fest gewahlten Zielfunktion) optimale Entscheidung zu treffen. Dazu versucht die libergeordnete Ebene, das Verhalten der untergeordneten Ebene zu antizipieren. Die libergeordnete Steuerungsebene enthalt neben einem Modell fiir diese Ebene auch ein antizipiertes Modell der untergeordneten Steuerungsebene. Es werden hypothetisch Anweisungen IN an das antizipierte Modell der untergeordneten

50

KAPITEL 3. VERTEILTE HIERARCHISCHE

PRODUKTIONSSTEUERUNG

Ebene libergeben. Das antizipierte Modell der untergeordneten Ebene sendet umgekehrt hypothetische Reaktionen RE an das Modell der iibergeordneten Steuerungsebene. Die iibergeordnete Steuerungsebene fallt danach eine endgiiltige Entscheidung, die in Form einer Anweisung IN* an die untergeordnete Steuerungsebene iibergeben wird. Die untergeordnete Steuerungsebene beriicksichtigt die Anweisung IN* und berechnet eine optimale Reaktion RE*, die an die iibergeordnete Steuerungsebene iibermittelt wird. Nach einer endlichen Anzahl von Verhandlungsrunden wird die endgiiltige Steuerungsentscheidung IN** ermittelt und an den zu beeinflussenden Basisprozess iibergeben. Das beschriebene Vorgehen ist in Abbildung 3.1 schematisch dargestellt.

i^l2SS3IIZSZ

TZH^

Antizipiertes Modell der untergeordneten Steuerungsebene U

IN*

Implementierung

Zu Ex-Post Riickkopplmig Abbildung 3.1: Grundmodell der hierarchischen Steuerung [223]

Die folgenden Eigenschaften des beschriebenen Steuerungssystems soUen detaillierter untersucht werden [223]:

1. AusschlieBlich die iibergeordnete Steuerungsebene antizipiert das (erwartete) Verhalten der untergeordneten Ebene. Lediglich die optimale Anweisung IN* verlasst die iibergeordnete Steuerungsebene. 2. Die iibermittelte Anweisung IN* ermoglicht einen Kommunikationsprozess innerhalb der unterschiedlichen Ebenen des Steuerungssystems. 3. Lediglich die endgiiltige Entscheidung IN** wird als Anweisung des hierarchischen Steuerungssystems an den Basisprozess iibergeben.

3.1. HIERARCHISCHE STEUERUNGSANSATZE 3.1.3.2

51

Modellierung von Entscheidungen

Mit t wild im Folgenden der Zeitpunkt bezeichnet, zu dem eine Entscheidung getroffen wird. Ein beliebiges Entscheidungsmodell kann in der Form M:=M{C,A,It)

(3.1)

mit C: Entscheidungskriterium (Zielfunktion), A: Alternativenraum (Entscheidungsfeld), It'. Informationsstatus zum Zeitpunkt t dargestellt werden [223]. Der Alternativenraum A stellt die Menge der zulassigen Entscheidungen dar. Die Giite einer Entscheidung wird mit Hilfe von Zielfunktionen bewertet. Die Entscheidungen basieren auf Daten, die zum Entscheidungszeitpunkt t zur Verfugung stehen und mit Hilfe des Informationsstatus It beschrieben werden. Das Entscheidungsmodell der iibergeordneten Ebene wird mit M^:=M^(C^,>1^,/,^)

(3.2)

bezeichnet. Fur das Entscheidungsmodell der untergeordneten Ebene wird die Bezeichnung M^:=M^{C^,A^jf)

(3.3)

verwendet. Die Entscheidung der iibergeordneten Ebene wird mit aF bezeichnet. Es gilt a^ e A^. Eine optimale Entscheidung beziiglich des Entscheidungskriteriums C^ wird mit aF* bezeichnet. Das von der iibergeordneten Ebene erwartete Verhalten der untergeordneten Ebene wird durch das Entscheidungsmodell

beschrieben. Im Folgenden wird genauer auf die Antizipationsfunktion AF{IN) eingegangen. Die Antizipationsfunktion wird von der iibergeordneten Ebene dazu verwendet, das erwartete Verhalten der untergeordneten Ebene bei der Entscheidungsfindung zu beriicksichtigen. Die Antizipationsfunktion beschreibt das erwartete Verhalten der untergeordneten Ebene als Reaktion auf die Anweisung IN. Das Entscheidungskriterium C^ der iibergeordneten Ebene setzt sich aus zwei Bestandteilen zusammen, einem privaten und einem offentlichen Kriterium. Das private Kriterium C'^ dient zur Bewertung der Entscheidung der iibergeordneten Ebene. Das ofTentliche Kriterium C^^ beriicksichtigt die erwartete Entscheidung der untergeordneten Ebene als Ergebnis der Anweisung IN. Unter Verwendung der Antizipationsfunktion kann C^^ als C^^ := C^^ (AF) geschrieben werden.

52

KAPITEL 3. VERTEILTE HIERARCHISCHE

PRODUKTIONSSTEUERUNG

Ubergeordnete Steuerungsebene ^ .„ •;

r>

MUC\A^,/J

)

•V

:-:mm:i'- •.:-. -'-•-'^'r--]:^:mjM^u^-vJ-'• M^(C^

^

,A^ ,if

• !j

)

y.c^ ^•^;gi^^^vaT"'.T^?'!^"ri^:5v^""""f^'^v:—......,y.„.,^™,MM^,.,M,,;^.,^,j._ ,.^,^ ^ . ^ j . ^ . , ; _ ^,_,., ^.,; j

1

/A^*= /ivra^*;

Untergeordnete Steuerungsebene Abbildung 3.2: Hieraxchischen Steuerung mit zwei Steuerungsebenen [223]

AUgemein kann das Entscheidungskriterium C^ wie folgt dargestellt werden: ^^{J)

:= C^ (C"^(a^), C^^ [AF {IN (J))))

.

(3.4)

Ein Entscheidungsproblem kann als Optimierung des Entscheidungskriteriums iiber dem Alternativenraum aufgefasst werden. Formal wird dieser Optimierungsprozess wie folgt dargestellt: a^- := an, opt^r^^rE {C^ {Cf"(a^), C™ [AF {IN ( a ^ ) ) ) ) | / ^ } .

(3.5)

Es wird zur Abkiirzung die Notation argf{x) = x verwendet. Die Entscheidung der unteren Ebene wird durch die nachfolgende Gleichung abgebildet: a^' := an, opt„B,^a^.£{C« {cf^^.i^^Cf^.

(a^) | / f ; , . „ ) } .

(3.6)

In Gleichung (3.6) wird mit C^^ das private und mit C^^ das offentliche Kriterium der untergeordneten Ebene bezeichnet. Die Vorgabe der iibergeordneten Ebene an die untergeordnete Ebene wird durch die nachfolgende Gleichung beschrieben: IN := IN (oF) .

(3.7)

Die Antizipationsfunktion AF ist durch die folgende Gleichung gegeben: AF{IN) := arg opt^s^f.^

{Cf^ (a^) UFN} •

(3.8)

Mit / ^ wird die Information bezeichnet, welche fiir die untergeordnete Ebene zum Zeitpunkt ^i durch die iibergeordnete Ebene zum Zeitpunkt ^o vorausgesetzt wird. Durch die Entscheidung a^ der iibergeordneten Ebene findet an dieser Stelle eine Beeinflussung des Entscheidungskriteriums und des Alternativenraums der untergeordneten Ebene statt. Diesem Sachverhalt wird durch die Verwendung eines tief gestellten IN in der Bezeichnung fiir den Alternativenraum und

3.1. HIERARCHISCHE STEUERUNGSANSATZE

53

im Entscheidungskriterium Rechnung getragen. Die Gleichungen (3.5), (3.6), (3.7), (3.8) werden als Kopplungsgleichungen bezeichnet. Die folgenden Arten von Antizipationsfunktionen werden unterschieden: • Exakte explizite reaktive Antizipation: In diesem Fall wird eine Antizipation vorausgesetzt, die der Gleichung (3.8) folgt. Es liegt eine exakte Antizipation vor, da exakte Informationen iiber das Verhalten der untergeordneten Ebene an die ubergeordnete Ebene iibermittelt werden. Die Antizipation ist explizit, da das aktuelle Verhalten der untergeordneten Ebene antizipiert wird. Diese Form der Antizipation wird als perfekte Antizipation bezeichnet. • Approximative explizite reaktive Antizipation: Im Gegensatz zur perfekten Antizipation werden bei der approximativen expliziten reaktiven Antizipation Schatzwerte fiir die Parameter des Modells der untergeordneten Ebene verwendet. • Implizite reaktive Antizipation: In diesem Fall werden ledighch bestimmte Telle des Modells der untergeordneten Ebene antizipiert. Implizite reaktive Antizipation wird dadurch realisiert, dass der Entscheidungsraum (Alternativenraum) der iibergeordneten Ebene durch die Antizipation eingeschrankt wird. • Nicht-reaktive Antizipation: Es existiert keine Antizipationsfunktion. Die ubergeordnete Ebene beriicksichtigt bei der Entscheidungsfindung keine Entscheidungen einer antizipierten untergeordneten Ebene. Eigenschaften der untergeordneten Ebene konnen in die Gleichung (3.4) der iibergeordneten Ebene aufgenommen werden. Die betrachteten Eigenschaften der untergeordneten Ebene sind aber nicht von einer Anweisung IN abhangig.

3.1.4

Schichtung, Stratifikation und StafFelung hierarchischer Systeme

In der Literatur werden drei Sichten auf hierarchische Systeme unterschieden [144, 56]: 1. Staffelung, 2. Stratifikation, 3. Schichtung. Die Sicht der Staffelung wird zur Abbildung organisatorischer Gegebenheiten innerhalb des hierarchischen Systems verwendet. Eine einzelne Staffel wird durch das Niveau der Entscheidungsprioritat charakterisiert. Die unterschiedlichen Elemente einer Staffel besitzen prinzipiell die gleiche Entscheidungsprioritat. Die Staffelung ist ein Spezialfall einer organisatorischen Hierarchie im Sinne von Schneeweifi [224]. Entscheidungseinheiten auf iibergeordneten Staffeln erzeugen Rahmenbedingungen fiir die Entscheidungen der untergeordneten Staffeln. Die Entscheidungseinheiten

54

KAPITEL 3. VERTEILTE HIERARCHISCHE

PRODUKTIONSSTEUERUNG

der untergeordneten Staffeln verfiigen aber iiber einen gewissen Graxi an Autonomie. Die Staffelung ist fiir hierarchische Steuerungssysteme von besonderer Bedeutung, da sie Voraussetzung fiir eine funktional und raumlich verteilte Steuerung im Sinne einer zeitlich parallelen Steuerung von unterschiedlichen Elementen des Basisprozesses schafft. Durch eine Staffelung treten Koordinationsprobleme zwischen Entscheidungseinheiten unterschiedlicher Staffeln sowie zwischen den Entscheidungseinheiten einer Staffel auf. Der Staffelungsansatz wird zur Abbildung von Beziehungen zwischen Entscheidungseinheiten, die ein System bilden, verwendet. Ein aus drei Staffeln bestehendes hierarchisches System ist in Abbildung 3.3 dargestellt. Entscheidungshierarchie Staffel 3

Entscheidungseinheit Staffel 2

Koordination Informationsruckkopplung

Staffel 1 Steuerung Prozessriickkopplung

i

1

^' Prozess

Abbildung 3.3: Hierarchisches System mit Staffelung

Unter Stratifikation versteht man das Abstraktionsniveau in der Beschreibung des Systemverhaltens. Man verwendet den Begriff der stratifizierten Beschreibung. Das zu untersuchende System wird durch eine Familie von Modellen beschrieben, die das Verhalten des Systems mit unterschiedlichem Abstraktionsniveau abbilden. Das Konzept der Stratifikation dient somit in erster Linie ModeUierungszwecken. Jede durch Stratifikation gewonnene Steuerungseinheit hat eigene Begriffe, Konzepte und Prinzipien. Das Systemverstandnis wird grofier, wenn die unterschiedlichen Stratifikationsebenen durchlaufen werden. Falls man die Ebenen von oben nach unten durchlauft, erhalt man eine starker detaillierte Beschreibung des Systems. Umgekehrt fiihrt ein Durchlaufen der Hierarchic von unten nach oben zu einem besseren Verstandnis fiir das Systemverhalten, da umfangreichere Subsysteme und langere Zeitperioden in die Beschreibung einbezogen werden. Stratifikation dient zur Zerlegung einer gewiinschten Funktion in eine Menge von Unterfunktionen. Die Unterfunktionen werden weiter zerlegt, bis einfach realisierbare Funktionen erscheinen. Da die Erfiillung von Funktionen bzw. Unterfunktionen zeitabhangig ist, spielen bei der Stratifikation Fragen der Synchronisation eine grofie RoUe. Neben der Staffelung ist die Stratifikation

3.1. HIERARCHISCHE

55

STEUERUNGSANSATZE

Voraussetzung fiir eine funktional und raumlich verteilte Steuerung im Sinne einer zeitlich parallelen Steuerung von unterschiedlichen Elementen des Basisprozesses. Ein Beispiel fiir eine Zerlegung von Steuerungsaufgaben durch Stratifikation ist durch Abbildung 3.4 gegeben. Darstellungsniveau 1

Steuerung 11

Darstellungsniveau 3

f-^V- ^ f: :--'-"i'

r Abbildung 3.4: Steuerungsaufgabendekomposition durch Stratifikation

Der Sicht der Schichtung wird zur Abbildung unterschiedlicher Entscheidungskomplexitat verwendet. Eine einzelne Schicht wird dabei durch das Niveau der durch die Schicht betrachteten Entscheidungskomplexitat charakterisiert. Das Grundprinzip der Schichtung besteht darin, dass das zu losende Entscheidungsproblem D in eine Folge Di,...,Dk

von Unterentscheidungsproble-

men zerlegt wird, die in einer sequentiellen Art und Weise gelost werden. Dabei gilt, dass die Losung des Enscheidungsproblems Di dazu fiihrt, dass Eingangsgrofien bzw. Parameter des untergeordneten Entscheidungsproblems Di_i bestimmt werden. Das urspriingliche Entscheidungsproblem D ist gelost, wenn alle Unterentscheidungsprobleme Di gelost sind. Das Konzept der Schichtung wird somit zur vertikalen Strukturierung von Entscheidungsproblemen benutzt. Beispielsweise ist es moghch, die Produktionssteuerung in die Schichten Grobplanung, Feinplanung und operative Steuerung der Produktion einzuteilen. In dieser Arbeit wird allgemein von Hierarchieebene gesprochen, wenn keine der drei moglichen Sichten besonders ausdriicklich eingenommen werden soil.

3.1.5

Informationsstatus der Hierarchieebenen

Der Informationsstatus der Elemente einer Ebene, d.h. der Elemente einer Staffel, in verteilten hierarchischen Systemen kann in die folgenden Kategorien unterteilt werden [224]: 1. Informationen iiber die eigene interne und externe Situation,

56

KAPITEL 3. VERTEILTE HIERARCHISCHE

PRODUKTIONSSTEUERUNG

2. Informationen iiber die interne und externe Situation anderer Systemeinheiten des verteilten hierarchischen Systems, 3. Informationen iiber den Informationsstatus anderer Systemeinheiten des hierarchischen Systems. Unter der internen Situation werden diejenigen Informationen verstanden, iiber die die betrachtete Entscheidungseinheit einer Hierarchieebene verfiigt. Zur Beschreibung der externen Situation dienen Informationen, die aus der Umgebung des hierarchischen Systems der Entscheidungseinheit zur Verfiigung stehen. Insbesondere werden hier auch Informationen iiber den Status des Basisprozesses beriicksichtigt. Informationen iiber die interne und externe Situation anderer Systemeinheiten werden in Form von antizipierten Modellen anderer Hierarchieebenen beriicksichtigt. Informationen iiber den Informationsstatus anderer Systemelemente des hierarchischen Systems hegen in Form von Wissen uber die vorhandenen Informationen der Entscheidungseinheiten einer anderen Hierarchieebene vor. Zur Strukturierung der Informationen, die die interne bzw. externe Situation beschreiben, werden Informationen beziigUch des Basissystems und des Basisprozesses unterschieden. Es wird von Informationssymmetrie zwischen zwei Ebenen gesprochen, wenn beide Ebenen iiber identische Informationen verfiigen. Man spricht von asymmetrischen Informationen, falls beide Ebenen des hierarchischen Systems iiber unterschiedhche Informationen verfiigen. Der Fall asymmetrischer Informationen liegt insbesondere vor, wenn die betrachteten Ebenen zu unterschiedlichen Zeitpunkten ^o und ti Entscheidungen treffen. Falls ein gestaflFeltes hierarchisches System vorHegt, muss neben dem Informationszustand der Staffel der Informationszustand der Entscheidungseinheiten, welche die Staffel bilden, beschrieben werden.

3.2

Modellannahmen

Den nachfolgenden Ausfiihrungen liegen die folgenden Modellannahmen zugrunde: 1. Die zu bearbeitenden Lose gehoren zu unterschiedlichen Produkten. 2. Jedes Los besitzt einen geplanten Aussteuertermin. Dieser ergibt sich aus dem vom Kunden gewiinschten Endtermin, wenn das Los einem Kundenauftrag zugeordnet ist. Im Fall einer anonymen Fertigung wird der geplante Aussteuertermin unter Beriicksichtigung kapazitiver Gegebenheiten und dem Erreichen des Ziels einer ausbalancierten Linie mit einem geplanten Aussteuertermin versehen. Weiterhin wird die okonomisch motivierte Verhinderung der Uberschreitung eines bestimmten maximalen Bestandes an Halbfabrikaten (Losen) innerhalb des Produktionssystems bei der Bestimmung des geplanten Aussteuertermins beriicksichtigt. 3. Jedes Los besitzt einen Einsteuertermin. Dieser wird unter Beriicksichtigung des geplanten Aussteuertermins, der aktuellen und zukiinftigen Auslastung des Produktionssystems sowie

3.2. MODELLANNAHMEN

57

unter Bestandsannahmen festgelegt. Fiir eine Darstellung moglicher Methoden wird auf die Arbeit von Fowler, Hogg und Mason [63] bzw. auf die AusfQhrungen in Abschnitt 2.5.1.2 verwiesen. 4. Jedes Los besitzt ein Attribut zur Beschreibung seiner Wichtigkeit (auch als Gewicht oder statische Prioritat bezeichnet). Das Gewicht wird fiir Lose, die zur Realisierung von Kundenauftragen dienen, entsprechend einer Klassifizierung der Kunden festgelegt. Fiir Lose, die nicht zur Realisierung von Kundenauftragen verwendet werden, wird das Gewicht w = 1 gewahlt. 5. Transportzeiten fiir die Lose sind in den Bearbeitungszeiten fiir die Prozess-Schritte enthalten. Es wird kein separates Transportsystem in das Modell aufgenommen. 6. Es werden deterministische Bearbeitungszeiten vorausgesetzt. 7. Das untersuchte Produktionssystem wird als einstufig angenommen, d.h., es liegt genau eine Fertigungsstufe vor. Diese Annahme bewirkt, dass Produkte eindeutig durch den Arbeitsplan beschrieben werden und das Stiicklisten nicht notwendig sind. 8. Es wird angenommen, dass Lose unteilbare Einheiten darstellen. Ein Aufteilen der Bestandteile eines Lose auf mehrere Lose ist somit nicht zulassig. 9. Es wird angenommen, dass Lose nicht angehalten werden konnen. 10. Im betrachteten Produktionssystem existieren Batchmaschinen. Die Menge derjenigen Lose, deren Bearbeitung auf eine Maschine denselben Riistzustand und gegebenenfalls eine gleichartige sekundare Ressource erfordert, wird als Losfamilie bezeichnet. Falls mehr als eine Losfamilie vorliegt, wird von inkompatiblen Familien gesprochen. Die Lose einer Losfamilie konnen auf Grund des gleichen Riistzustandes gegebenenfalls gruppiert werden. Ein Batch stellt die Gruppierung von Losen einer Losfamilie dar [259]. Die maximal mogliche Anzahl von Losen in einem Batch wird als maximale Batchgrofie bezeichnet. Entsprechend der von Potts und Kovalyov [204] vorgeschlagenen Klassifizierung wird zwischen simultaner und sequentieller Abarbeitung der Lose eines Batches unterschieden. Die simultane Abarbeitung erfolgt auf Batchmaschinen, die mehrere Lose gleichzeitig bearbeiten konnen. Im Fall der sequentiellen Abarbeitung lassen sich nach Potts und Kovalyov [204] zwei Varianten unterscheiden. Bei Batch-Verfiigbarkeit ist die Weiterbearbeitung der den Batch bildenden Lose erst dann moglich, wenn die Bearbeitung aller Lose abgeschlossen ist. Bei Los-Verfiigbarkeit konnen die einzelnen den Batch bildenden Lose unmittelbar nach ihrer Fertigstellung ihre Weiterbearbeitung auf nachfolgenden Maschinen fortsetzen. Wenn in dieser Arbeit lediglich von Batching gesprochen wird, wird Batching mit simultaner Abarbeitung gemeint. Batching mit sequentieller Abarbeitung wird explizit als solches gekennzeichnet.

58

KAPITEL 3. VERTEILTE HIERARCHISCHE

PRODUKTIONSSTEUERUNG

11. Die Maschinen verlangen fiir die Ausfuhrung von Prozess-Schritten eines Loses einen bestimmten Riistzustand. Die fur einen Rustvorgang notwendige Riistzeit hangt vom ausgefuhrten Vorganger-Prozess-Schritt auf der Maschine ab. Die Riistzeiten sind somit reihenfolgeabhangig. 12. Das betrachtete komplexe Produktionssystem besteht aus Produktionsbereichen. Ein einzelner Produktionsbereich umfasst Gruppen funktionsgleicher, d.h. paralleler Maschinen. Diese konnen sich in den Fertigungs- oder Maschinengeschwindigkeiten und in den Fahigkeiten zur Bearbeitung bestimmter Produkte unterscheiden [51]. Falls die Fertigungsgeschwindigkeiten fiir alle Maschinen identisch sind, spricht man von identischen parallelen Maschinen. Falls sich lediglich Fertigungs- oder Maschinengeschwindigkeiten unterscheiden, verwendet man den Begriff uniformer paralleler Maschinen. Heterogene parallele Maschinen liegen vor, wenn die Maschinen unabhangig voneinander sind. Die Fertigungsgeschwindigkeiten sind in diesem Fall sowohl maschinen- als auch losabhangig. 13. Es wird vorausgesetzt, dass im betrachteten Produktionssystem ein Produktionsbereich vorliegt, der einen geplanten Engpass darstellt. Diese Annahme ist sinnvoU, da in Praxissituationen haufig Maschinen existieren, die im Vergleich zu den anderen Maschinen des Produktionssystems extrem teuer sind. Aus diesem Grund wird die Kapazitat dieser Maschinen knapp kalkuliert.

3.3

Ubersicht iiber den Steuerungsansatz

Die Steuerung komplexer Produktionsprozesse kann durch Losen einer Folge von Entscheidungsproblemen im zeithchen Ablauf beschrieben werden. In Produktionssystemen findet die Losung von Entscheidungsproblemen raumlich und zeitlich verteilt statt. Die verteilten Entscheidungen haben unterschiedlichen Stellenwert im System der Produktionssteuerung, aus diesem Grund erscheint eine hierarchische, asymmetrische Strukturierung der zu losenden Entscheidungsprobleme als angemessen. Die Steuerung von Produktionssystemen kann folglich als Design und Koordinierung von miteinander verbundenen Entscheidungen aufgefasst werden [224]. Aus diesem Grund wird ein verteilter hierarchischer Steuerungsansatz fiir komplexe Produktionssysteme entwickelt, der die in den Modellannahmen in Abschnitt 3.2 postuherte Dekomposition des Produktionssystems in Produktionsbereiche ausnutzt. Der Steuerungsansatz umfasst die S t euerungsebenen: • Produktionssystemsteuerungsebene, • Produktionsbereichssteuerungsebene, • Maschinengruppensteuerungsebene.

3.3. UBERSICHT UBER DEN

59

STEUERUNGSANSATZ

In der Hierarchie iibergeordnete Ebenen dienen zur Beeinflussung von umfangreicheren Teilen des Gesamtprozesses. Ubergeordnete Ebenen haben langere Entscheidungsperioden und beschaftigen sich mit „langsameren" Aspekten des zu steuernden Prozesses. Die Entscheidungsprobleme ubergeordneter Ebenen sind weniger strukturiert, enthalten in starkerem Mafie Unsicherheiten und sind schwieriger quantitativ zu formalisieren. Die drei vorgeschlagenen Steuerungsebenen unterscheiden sich im Detaillierungsgrad der Optimierungsmodelle, die der Steuerung zugrunde liegen, und in der Lange der Terminierungs- und Schedulinghorizonte. Im Sinne der Nomenklatur von Schneeweifi [223, 224] liegt eine Entscheidungszeitpunkthierarchie vor. Da die Produktionsbereichssteuerungsebene aus mehreren entscheidungsfahigen Einheiten besteht, ist es notwendig, die Entscheidungen dieser Ebene durch die Produktionssystemsteuerungsebene zu koordinieren. Somit besitzt das hierarchische System gleichzeitig den Charakter einer Fiihrungshierarchie. Auf Grund der unterschiedlichen Entscheidungseinheiten auf den Steuerungsebenen liegt eine aus drei Ebenen bestehende Staffelung vor. Gleichzeitig kann den drei gewahlten Steuerungsebenen unterschiedliche Steuerungsfunktionalitat im Sinne einer Stratifikation zugewiesen werden. In Tabelle 3.1 ist die durch die einzelnen Steuerungsebenen zu realisierende Punktionalitat zusammengefasst. In den folgenden Abschnitten wird zur Bezeichnung der Produktionssystemsteuerungsebene ein hochgestelltes „T", fiir die Produktionsbereichssteuerungsebene ein hochgestelltes „M" und fiir die Maschinengruppensteuerungsebene ein hochgestelltes „B" verwendet.

Tabelle 3.1: Funktionalitat der einzelnen Steuerungsebenen Steuerungsebene

Funktionalitat

Anzahl Entscheidungseinheiten

Produktionssystem-

1

Grobterminierung der Lose

1...*

prozess-schritt-genaue Feinplanung der Lose, die

steuerungsebene Produktionsbereichssteuerungsebene

sich innerhalb des Schedulinghorizontes im Produktionsbereich aufhalten

Maschinengruppensteuerungsebene

1...*

Maschinenbelegung fiir die Maschinen der Maschinengruppe

60

KAPITEL 3. VERTEILTE HIERARCHISCHE

3.4

PRODUKTIONSSTEUERUNG

Produktionssystemsteuerungsebene: Entscheidungsmodell

Die Aufgabe der Produktionssptemsteuemngsebene besteht darin, Starttermine fur die Bearbeitung der Lose in einzelnen Produktionsbereichen des Produktionssystems festzulegen. Dazu wird eine roUierende und ereignisgetriebene Terminierung durchgefiihrt. Das Steuerungsziel der P r o duktionssystemsteuerungsebene besteht in der ErfuUung von Produktionsvorgaben (Mengen- und Terminvorgaben), die in der operativen bzw. mittelfristigen Planung festgelegt werden. Das Entscheidungsmodell fiir die Produktionssystemsteuerungsebene wird durch Angabe des Entscheidungskriteriums, der Entscheidungsvariablen, des Alternativenraums sowie des Optimierungsmodells voUstandig beschrieben. Auf Ebene des Produktionssystems wird eine Aggregation von im Arbeitsplan unmittelbar aufeinanderfolgenden Prozess-Schritten zu Operationen durchgefiihrt. Die Zusammenfassung von Prozess-Schritten zu Operationen wird dabei so vorgenommen, dass alle Prozess-Schritte einer Operation auf den Maschinen eines einzelnen Produktionsbereiches ausgefiihrt werden konnen. Im Folgenden wird Operation j von Los i mit ij bezeichnet. Die Operation ij wird durch die Prozess-Schritte j i , . . . ,jk gebildet, es gilt: k

1=1

Die verwendete Aggregation spiegelt die physische Dekomposition des Produktionssystems in einzelne Produktionsbereiche wider.

3.4.1

Entscheidungsvariable

In dieser Arbeit wird der realisierte Fertigstellungstermin fiir Operation j von Los i mit Cij bezeichnet. Indirekte Entscheidungsvariable sind durch die Menge {cij} gegeben. Direkte Entscheidungsvariable werden aus indirekten abgeleitet und dienen zur Berechnung des Zielfunktionswertes. Im Fall der Produktionssystemsteuerungsebene wird die Menge der Entscheidungsvariablen durch die Menge der realisierten Fertigstellungstermine { Q } gebildet. Geplante Fertigstellungstermine fiir die Lose in Produktionsbereichen und die realisierten Fertigstellungstermine stehen in folgender Beziehung zueinander: Cij+i

:=

Ci :=

Cij-hpij-hwtij, c,„,

(3.9) (3.10)

Mit Pij wird dabei die Bearbeitungszeit der Operation j fiir Los i bezeichnet. Die Grofie Pij erhalt man, indem die Bearbeitungszeiten der Prozess-Schritte, welche die Operation bilden, addiert werden. Ife gilt somit: k

Pij '= T,Pjr 1=1

3.4. PRODUKTIONSSYSTEMSTEUERUNGSEBENE:

ENTSCHEIDUNGSMODELL

61

Die Wartezeit, die vor der Bearbeitung der Prozess-Schritte von Operation ij auftritt, wird mit wUj bezeichnet. Diejenige Operation von Los i, die entsprechend dem Arbeitsplan vor der Fertigstellung von Los i abschliefiend auszufuhren ist, wird mit n^ bezeichnet. Der aggregierte Arbeitsplan umfasst rii Operationen.

3.4.2

Entscheidungskriterium

Ein terminorientiertes Entscheidungskriterium wird betrachtet. Die obere Steuerungsebene minimiert die gewichtete Verspatung der Lose. Es wird das folgende private Kriterium C " ' verwendet: C^:=±wj{cj-djr

(3.11)

mit n: Anzahl der Lose, die im Terminierungszeitraum T fertig gestellt werden, wf Gewicht von Los j , df geplanter Fertigstellungstermin fiir Los j . Zur Abkiirzung wird x"*" := max(a:, 0) in dieser Arbeit verwendet. Die Produktionssystemsteuerungsebene iibergibt die folgende Anweisung an die Produktionsbereichssteuerungsebene: IN^ := IN^{{c,j}),

(3.12)

d.h., die geplanten Fertigstellungstermine fiir die Operationen der Lose werden der Produktionsbereichssteuerungsebene mitgeteilt. Die Produktionssystemsteuerungsebene antizipiert das erwartete Verhalten der untergeordneten Ebene durch das Kriterium C ^ ^ . Es wird die gewichtete Verspatung der Lose im geplanten Engpassproduktionsbereich innerhalb eines Horizontes der Lange T bezogen auf die Fertigstellungsterminvorgaben der Produktionsbereichsebene in die Entscheidungsfindung der iibergeordneten Ebene einbezogen. Es gilt: C™:=

2

Wi{c,j-Ciif

(3.13)

to PfXfg +

E

'^efXef " M(l - Xfg),

eeOs,e^f

"^/T^gJ^ge 0„ o{e) = o{f) = o{g) = leG',

(3.40)

Xfg + X9fPfXfh+

XI

tlJefXef-M{l-l3h),

\/heBJ eh,

(3.46)

V/ € Ob,

(3.47)

^heB,

(3.48)

\/heB,

(3.49)

eeOa,e¥^f

E Xfh = 1,

heB

Y^Xfh = Phcard{h), Yl

Xhg = (3hcard{h),

geOaUOb

y9-rh>ShXh9+

Y.

Xehi^eh-M{l-(3h),

\/heBJeh,if,g)€A,

(3.50)

eeB,e^h

Ti-Th>

Sh (Xhi - 1 + A ) +

Y

'^ehXeh " M (1 - Xhi) ,

eeB,e^h

^h,ieB,hni Xih + Xw < 1, E X/.i < 1,

^h,ieB,hni

= ili,oj{'y{h)) = uj{^ii)) ^leG^,

(3.51)

= 0,u;(7(/i)) = uj{j{i)) = leG\

(3.52)

Vz € B, /i n z = 0, a;(7(/i)) = uj{l{i)) = I € G\

(3.53)

heB

E Xhi < 1,

^heB,hni

= i/i, a;(7(/i)) = uMi))

= I e G\

(3.54)

ieB

1 - E X/.i < Oi,

Vi G B, /i n 2 = 0, u(^{h)) = u{j{i)) = leG\

(3.55)

heB

E ^h < rnu

Va;(7(/i)) = / € G'^

(3.56)

heB

Oh < Ph,

V/i G B.

(3.57)

Bedingung (3.46) stellt sicher, dass die Startzeit des Batches h, welcher Lose mit dem ProzessSchritt / enthalt, mindestens yf-^PfXfh-^YleeOs,e^f'^efXef

betragt. Bedingung (3.47) sorgt dafiir,

dass jeder Prozess-Schritt eines Loses in hochstens einem Batch enthalten ist, d.h. eine gleichzeitige Bearbeitung von zwei Batches auf einer Batchmachine vermieden wird. Bedingung (3.48) stellt sicher, dass genau card{h) Lose im Batch h enthalten sind. Durch Bedingung (3.49) wird

3.5. PRODUKTIONSBEREICHSSTEUERUNGSEBENE:

ENTSCHEIDUNGSMODELL

73

modelliert, dass der Batchknoten h fiir jedes Los, das Bestandteil des Batches ist, genau einen Nachfolgerknoten hat. Bedingung (3.50) stellt sicher, dass der Nachfolger / des Prozess-Schrittes g, der Bestandteil des Batches ist, friihestens nach ^htphg +

Y. '^ehXeh

eeB,e-^h

Zeiteinheiten beginnt. Die Nebenbedingungen (3.52), (3.53), (3.54), (3.55), (3.56) bilden das Analogon zu den Bedingungen (3.41), (3.42), (3.43), (3.44) und (3.45) fiir Nicht-Batchmaschinen. Bedingung (3.57) erzwingt die Bildung des Batches vor seiner Verwendung als Startknoten.

3.5.4.2

LOsungsverfahren

Obwohl es moglich ist, das Entscheidungsproblem der Produktionsbereichssteuerungsebene als ganzzahhges Optimierungsproblem zu formulieren, soUte dieser Ansatz aus Performancegriinden nicht angewendet werden. In Abschnitt 4.2 wird eine verteilte Shifting-Bottleneck-Heuristik zur Losung des Entscheidungsproblems fiir die Produktionsbereichssteuerungsebene vorgeschlagen. Die Shifting-Bottleneck-Heuristik liefert mit akzeptablem Zeitaufwand gute Losungen fiir die betrachteten Maschinenbelegungsprobleme.

3.5.5

Informationsstatus

Die Produktionsbereichssteuerungsebene besteht aus n Entscheidungseinheiten. Die eigene interne Entscheidungssituation eines fest gewahlten Produktionsbereiches k wird durch die folgenden Informationen beschrieben: • Informationen iiber die Dekomposition des Produktionsbereichs k in Maschinengruppen, • Arbeitsplane fiir diejenigen Lose, die zum Zeitpunkt ti im Produktionsbereich k bearbeitet werden, • Informationen iiber reihenfolgeabhangige Riistzeiten fiir die Maschinen des Produktionsbereichs, • Informationen iiber den Status des Ablaufplanes fiir den Produktionsbereich k. Die Statusinformationen werden dazu verwendet, zu entscheiden, ob ein neuer Ablaufplan fiir den Produktionsbereich k bestimmt werden muss. Die eigene externe Entscheidungssituation einer fest gewahlten Entscheidungseinheit der Produktionsbereichssteuerungsebene wird durch die nachfolgenden Informationen beschrieben: • Arbeitsplane fiir diejenigen Lose, die im Zeitraum {ti,ti -f r) den Produktionsbereich k erreichen und dort bearbeitet werden soUen,

74

KAPITEL 3. VERTEILTE HIERARCHISCHE

PRODUKTIONSSTEUERUNG

• Anaxbeitungsgrad der sich zum Zeitpunkt ti im Produktionsbereich k befindlichen Lose, • Informationen iiber den Beginn und die voraussichtliche Dauer eines Maschinenausfalls im Produktionsbereich k. Da die Produktionsbereichssteuerungsebene gestafFelt ist, ist die Beschreibung der internen und externen Situation anderer Entscheidungseinheiten neben der Betrachtung der internen und externen Situation der Entscheidungseinheit fiir den Produktionsbereich k bedeutsam. Zur Beschreibung der internen und externen Situation der anderen Entscheidungseinheiten werden die folgenden Informationen benotigt: • Informationen iiber den Beginn und die voraussichtHche Dauer eines Maschinenausfalls im Produktionsbereich I ^^ k, • Ablaufplan fiir den Produktionsbereich I ^ k, • Informationen iiber den Status des Ablaufplanes fiir den Produktionsbereich I ^ k. Die Informationen iiber die interne und externe Situation anderer Entscheidungseinheiten ermoghchen eine produktionsbereichsiibergreifende Koordination. Informationen iiber den Informationszustand anderer Systemelemente des hierarchischen Systems spielen im hier betrachteten Fall keine RoUe, da von kooperativem Verhalten ausgegangen wird, d.h., es wird angenommen, dass alle Systemeinheiten vollstandige und wahre Informationen zur Verfiigung stellen.

3.6

Maschinengruppensteuerungsebene: Entscheidungsmodell

Die Aufgabe der Maschinengruppensteuerungsebene besteht darin, die von der Produktionsbereichssteuerungsebene ermittelten Ablaufplane im Produktionssystem zu implementieren. Auf Grund von Storungen im Produktionssystem konnen die Ablaufplane der Produktionsbereichssteuerungsebene ungiiltig sein, d.h., die laut Ablaufplan zu bearbeitenden Lose befinden sich nicht im Warteraum vor der zu belegenden Maschinengruppe. In dieser Situation werden durch die Maschinengruppensteuerungsebene autonom Maschinenbelegungsentscheidungen getroffen. Fiir die fest gewahlte Max^hinengruppe r aus Produktionsbereich k wird im Folgenden die Bezeichnung {k,r) gewahlt.

3.6.1

Entscheidungs veiriable

Die Entscheidungsvariablen der Maschinengruppensteuerungsebene sind durch die Starttermine der Prozess-Schritte der Lose auf den Maschinen der fest gewahlten Maschinengruppe r aus dem

3.6. MASCHINENGRUPPENSTEUERUNGSEBENE:

ENTSCHEIDUNGSMODELL

75

Produktionsbereich k gegeben. Es wird die folgende Bezeichnung eingefiihrt: Sji: realisierter Staxttermin fiir Prozess-Schritt i von Los j auf {k, r). In den verwendeten Entscheidungsvariablen ist implizit auch die Entscheidung enthalten, auf welcher Maschine der Maschinengruppe die Bearbeitung stattfindet und in welchem Batch das jeweilige Los enthalten ist.

3.6.2

Entscheidungskriterium

Die Maschinengruppensteuerungsebene versucht, dem durch die Produktionsbereichssteuerungsebene vorgegebenen Ablaufplan so weit wie mogUch zu folgen. Das verwendete Entscheidungskriterium fiir die Steuerung von Maschinengruppe r im Produktionsbereich k kann wie folgt angegeben werden:

,, E

^K4-4).

P.58)

wobei mit Wj das Gewicht von Los j und mit sj'^ der durch den Ablaufplan festgelegte Starttermin von Prozess-Schritt i bezeichnet werden.

3.6.3

Alternativenraum fiir die Entscheidungen

Der Alternativenraum umfasst die Belegungsmoglichkeiten einer Maschine, auf der die Bearbeitung eines Loses oder eines Batches zum Zeitpunkt ^2 mogUch ist. Alternativenraum ^4^-*='^: Maschinenbelegung einer Maschine der Maschinengruppe {k,r): Die Aufgabe der Maschinengruppensteuerungsebene besteht in der Belegung einer Maschine, die zur Bearbeitung bereit ist, mit einem Los oder einem Batch. Der Alternativenraum kann wie wie folgt beschrieben werden:

1. Menge der Lose, die im Warteraum der Maschinengruppe (k, r) zum Zeitpunkt ^2 auf Bearbeitung warten, 2. Riistzustand der zu belegenden Maschine zum Zeitpunkt t2, 3. zukunftige Losankiinfte an der Maschinengruppe (A;, r) innerhalb eines Zeitfensters (^2, ^2 + At), um Batchentscheidungen und Umriistentscheidungen treffen zu konnen.

76

KAPITEL 3. VERTEILTE HIERARCHISCHE

3.6.4

PRODUKTIONSSTEUERUNG

Optimierungsmodell

Im Gegensatz zur Produktionssystemsteuerungsebene und zur Produktionsbereichssteuerungsebene wird durch die Maschinengruppensteuerungsebene eine direkte Belegung von Maschinen vorgenommen. Es existiert somit kein echter Schedulinghorizont. Die direkte Verwendung eines Optimierungsverfahrens ist somit nicht moglich. Es sind zwei Falle zu unterscheiden. 1. Im ersten Fall liegt ein giiltiger Ablaufplan vor. Das Steuerungsziel besteht darin, diesem Ablaufplan zu folgen, da bei der Erstellung des Ablaufplanes durch die Produktionsbereichssteuerungsebene globale Gesichtspunkte beriicksichtigt wurden. 2. Im zweiten Fall ist der durch die Produktionsbereichssteuerungsebene ermittelte Ablaufplan zum Zeitpunkt ^2 ungiiltig. Die Auswahl des als nachstes zu bearbeitenden Loses/Batches wird aus der nachfolgenden Menge durchgefuhrt: {I e I\mini^i {aiTPi + aiSQ + as (1 - UMi))} , 0 < a^, ai 4- as + ag = 1,

(3.59)

mit /

: Menge der Indizes von Losen oder bereits gebildeten Batches im Warteraum

TPi

: (mittlere) terminliche Dringlichkeit von Batch I als Quotient aus der verblei-

von Maschinengruppe {k,r), benden (mittleren) Zeit bis zum Aussteuertermin des Loses bzw. der Lose des Batches und der verbleibenden (mittleren) Restbearbeitungszeit des Loses bzw. der Lose des Batches, SQ

: normierte Riistkosten,

UMi

: normierte Auslastung von Batch I (im Fall eines Loses wird UMi = 1 gewahlt),

ai

: Gewichte, die zur Abbildung von Praferenzen zwischen terminorientierten Zielen, Riistzielen und Batchauslastungszielen dienen.

3.6.5

Informationsstatus

Fur die Maschinengruppensteuerungsebene liegen mehrere Entscheidungseinheiten vor. Da die Maschinengruppensteuerungsebene insbesondere die Aufgabe hat, die Maschinenbelegung auf Basis der von der Produktionsbereichssteuerungsebene ermittelten Ablaufplane vorzunehmen, ist es notwendig, dass die Maschinengruppensteuerungsebene als einzige Steuerungsebene direkt Informationen iiber den zu steuernden Produktionsprozess bezieht. Die eigene interne Situation einer Maschinengruppensteuerungseinheit wird durch die nachfolgenden Informationen beschrieben: • Informationen iiber die Dekomposition der Maschinengruppe in Maschinen,

3.6. MASCHINENGRUPPENSTEUERUNGSEBENE:

ENTSCHEIDUNGSMODELL

77

• Informationen iiber die Fahigkeiten der Maschinen, d.h. welche Prozess-Schritte auf einer konkreten Maschinen ausgefiihrt werden konnen und welchen Riistzustand sie verlangen, • Informationen iiber den Status des Ablaufplanes ftir die Maschinengruppe, • Informationen iiber das Budget der Lose, die im Rahmen des maschinenstundenbasierten Ressourcenallokationsverfahrens den Maschinen zugeteilt werden soUen, • Informationen iiber die Maschinenstundensatze fur Maschinen der Maschinengruppe. Die eigenen externe Situation einer Maschinengruppe wird durch die folgenden Informationen beschrieben: • Informationen iiber die zum Zeitpunkt ^2 im Warteraum der Maschinengruppe befindlichen Lose, • Informationen iiber die zum Zeitpunkt ^2 auf den Maschinen der Maschinengruppe in Bearbeitung befindlichen Lose, • Informationen daruber, ob eine Maschine der Maschinengruppe zum Zeitpunkt ^2 ausgefallen ist, • Informationen daruber, wie lange der Ausfall einer bestimmten Maschine dauern wird, • Informationen iiber den aktuell gultigen Riistzustand der Maschinen der Maschinengruppe, • Informationen daruber, welche Lose innerhalb eines bestimmten Zeitfensters im Warteraum der Maschinengruppe eintreffen werden. Da die Maschinengruppensteuerungsebene gestaffelt ist, ist die Beschreibung der internen und externen Situation von Entscheidungseinheiten, die sich von Maschinengruppe {k, r) unterscheiden, bedeutsam. Die folgenden Informationen sind dazu notwendig: • Informationen iiber den Status der Ablaufplane fur Maschinengruppen {I, s) mit I ^ k oder s 7^ r, • Informationen iiber den Beginn und die Dauer eines Maschinenausfalls in einer Maschinengruppe (/, s) mit / 7^ k oder s ^ r. Informationen uber den Informationszustand anderer Entscheidungseinheiten der Maschinengruppensteuerungsebene spielen auf Grund des vorausgesetzten kooperativen Verhaltens der Steuerungseinheiten des hierarchischen Systems keine RoUe.

78

KAPITEL 3. VERTEILTE HIERARCHISCHE

3.7

PRODUKTIONSSTEUERUNG

Verteiltes hierarchisches Steuerungsverfahren

Die in den Abschnitten 3.4, 3.5 und 3.6 beschriebenen Entscheidungen werden in diesem Abschnitt zu einem verteilten hierarchischen Steuerungsalgorithmus zusammengefasst. Es wird im Weiteren mit PBgf die Menge der Produktionsbereichssteuerungseinheiten bezeichnet, fiir die ein Ablaufplan bestimmt wurde, der als Vorgabe IN^

an die Maschinengruppensteuerungsebene iibergeben

wird. Die Bezeichnung PB wird fiir die Menge aller Produktionsbereichssteuerungseinheiten gewahlt. Fiir die Terminiemngs- und Schedulingalgorithmen der Produktionssystem- und der Produktionsbereichssteuerungsebene ist festzulegen, wann die Terminierung bzw, die Maschinenbelegungsplanung durchzufiihren ist. Das Schedulingverfahren der Produktionsbereichssteuerungsebene wird fiir einen Horizont der Lange r angewandt. Es gilt r = TA+TO/I, wobei mit r^ die Lange des Aufrufintervalls fiir das Schedulingverfahren und mit Tah die Lange des Uberlappungshorizontes bezeichnet werden. Fiir das Terminierungsverfahren wird ein Horizont der Lange T gewahlt. Das Verfahren wird roUierend alle Prnox^A Zeiteinheiten aufgerufen, d.h., die Aufrufhaufigkeit des Terminierungsverfahrens ist ein ganzzahliges Vielfaches der Aufrufhaufigkeit des Schedulingverfahrens. Die Parameter der beiden Verfahren sind in Tabelle 3.2 zusammengefasst. Abbildung 3.5 dient der Darstellung von Zeitaspekten im verteilten hierarchischen Steuerungsansatz. Tabelle 3.2: Parameter fiir die obere und mittlere Steuerungsebene Steuerungsebene

Aufrufintervall

Uberlappungshorizont

Produktionssystem

Pmax'^A

T - PmaxTA

Produktionsbereich

TA

Tah

Aufrufintervall des Terminierungsverfahrens

Produktionssystemsteuerungsebene

Aufrufintervall des Schedulers •^

H4

III'

Produktionsbereichssteuerungsebene

Maschinengruppensteuerungsebene

Abbildung 3.5: Zeitaspekte im verteilten hierarchischen Steuerungsalgorithmus

3.7. VERTEILTES HIERARCHISCHES STEUERUNGSVERFAHREN

79

Das verteilte hieraxchische Steuerungsverfahren (Distributed Hierarchical Production Control Algorithm (DHPCA)) wird wie folgt beschrieben: Verteilter hierarchischer Steuerungsalgorithmus (DHPCA) 1. Terminiere die im Produktionssystem zum Zeitpunkt ^o befindhchen bzw. innerhalb des Terminierungszeitraums (^o, ^o + T) eintreffenden Lose. 2.

Antizipiere das Verhalten des geplanten Engpassproduktionsbereichs, indem ein Ablaufplan fur diesen Produktionsbereich mit Scheduhnghorizont {to,to + r) berechnet wird.

3.

Falls der in Schritt 2 ermittelte Ablaufplan zu einer hinreichend kleinen (antizipierten) gewichteten Verspatung der Lose fiihrt, verzweige zu Schritt 4. Andernfalls verzweige zu Schritt 1 und andere die Losterminierungsstrategie.

4.

Initialisiere PBgf : = 0 .

5.

Iteration iiber alle Produktionsbereiche k e PB \ PB^f. Berechne fiir jeden Produktionsbereich k einen Ablaufplan fiir den Schedulinghorizont (^i, h -h r) unter Verwendung der Vorgaben fur friiheste Starttermine und geplante Fertigstellungstermine aus Schritt 1 bzw. Schritt 5. Es gilt: ^i = t^+pr^ mit p = 0,.. .,Pmax - 1-

6.

Wahle einen Produktionsbereich k € PB \ PBgf unter Verwendung bestimmter Kriterien aus. Setze PB^j := PBgf U {k}. Teile die tatsachlich notwendigen Start- und Endtermine der Lose, die fiir die Implementierung des Ablaufplanes erforderlich sind, den Produktionsbereichen PB\PBsf

mit. Falls PB = PBgf gilt, verzweige zu Schritt

7, andernfalls verzweige zu Schritt 5. 7.

Nehme eine Maschinenbelegung zum Zeitpunkt ti 0}. Die verwendeten Leistungsmafie bewerten die Verspatung, die Durchlaufzeit und den Durchsatz. In der Praxis ist speziell der fiir einfache ProduktioUssysteme durch das Gesetz von Little (vergleiche Law und Kelton [119]) gegebene Zusammenhang von Durchsatz und Durchlaufzeit von Interesse. In alien Experimenten wurden nach beendeter Einschwingphase Simulationslaufe mit einer Lange von drei Monaten betrachtet. Es wurde somit ein Produktionssystem im stationaren Zustand untersucht. Fiir jeden Simulationslauf wurden fiinf unabhangige Wiederholungen durchgefuhrt, um statistisch signifikante Werte fiir die Leistungsmafie zu erhalten. Die Leistungsmafie wurden als Durchschnitt der Leistungsmafie ftir die Einzellaufe berechnet. In Tabelle 4.27 sind Prioritatsregeln beschrieben, mit denen der maschinenstundenbasierte Allokationsmechanismus verglichen wird. In den benutzten Formeln werden die Bezeichnungen aus Abschnitt 4.4.3 verwendet. Die folgenden zusatzlichen Bezeichnungen werden eingefiihrt: t : Zeitpunkt, zu dem eine Maschinenbelegungsentscheidung getroffen werden muss, Pji

Bearbeitungszeit fiir den aktuellen Prozess-Schritt von Los j ,

Pji'. Bearbeitungszeit fiir Prozess-Schritt i von Los j , p : durchschnittliche Bearbeitungszeit der noch wartenden Lose zum Entscheidungszeitpunkt t, K:

Vorausschauparameter in der ATC-Regel.

Tabelle 4.27: Beschreibung der Vergleichsprioritatsregeln Kegel

Prioritat

Definition

FIFO

First-In-First-Out

min(rj)

ATC

Apparent-Tardiness-Cost

»-(^exp{-i^i^^))

SLSS

Slack-and-Same-Setup

min{dj -t-^pji),

falls der Riistzustand der Maschine

beibehalten werden kann, andernfalls wird diejenige freie Maschine ausgewahlt, die die geringste Zeit zum Umriisten benotigt SPT

Shortest-Processing-Time

i mm{pj)

4.4. MODIFIZIERTER 4.4.4.3

167

KONTRAKTNETZANSATZ

Ergebnisse

In Tabelle 4.28 sind numerische Werte fiir die untersuchten Leistungsmafie fiir den maschinenstundenbasierten Ressourcenallokationsansatz und die vier Vergleichsprioritatsregein zusammengefasst. Ungiiltige Ablaufplane werden nach der SLSS-Strategie aus Tabelle 4.27 behandelt. Im Folgenden wird dieser Ansatz mit MAS abgekiirzt. AUe numerischen Werte in Tabelle 4.28 werden relativ zu dem jeweiligen Ergebnis mit dem MAS angegeben, d.h. sind der Quotient aus dem MAS-Ergebnis und dem Ergebnis mit der entsprechenden Prioritatsregel. Tabelle 4.28: Werte fiir die Leistungsmafie Szenario 1

MAS

FIFO

SLSS

ATC

AWT

1.0000

1.2621 2.9650

2.2490

1.7981

AT

1.0000

1.0060 2.3691

1.7471 1.5890

ACT

1.0000

1.0640

TP

1.0000

1.0481 0.8220

SPT

1.0680

1.1551 1.1390 0.9321

0.9100

Szenario 2 AWT

1.0000

1.1910 2.6351

1.9810

1.1880

AT

1.0000

1.1242 2.1781

1.7422

1.3570

ACT

1.0000

1.1000

TP

1.0000

1.0320 0.8400

0.9602

1.0581

AWT

1.0000

1.5900 2.1441

1.7880

1.7080

AT

1.0000

1.3250

1.9830

1.5750

1.5991

AC

1.0000

1.1071 1.0440

TP

1.0000 0.9251

1.0370

1.1771 1.1340 1

Szenario 3

0.8051

1.1332

1.1500

0.9251

0.9170

Aus Tabelle 4.28 ist zu erkennen, dass MAS fiir das untersuchte Produktionssystem den prioritatsregelbasierten Ansatzen fiir die termin- und durchlaufzeitorientierten Leistungsmafie iiberlegen ist. Bei der Zuteilung des Budgets fliefien globale Informationen iiber das Produktionssystem in die Entscheidungsfindung ein. Bei einer prioritatsregelbasierten Steuerung des Systems ist das nur eingeschrankt moglich. Wahrend fiir das Szenario 1 und 2 mit einem nach FIFO gesteuerten System noch ein gr6i3erer Durchsatz als bei einer Steuerung mit dem maschinenstundenbasierten AUokationsansatz erreicht wird, erzielt fiir Szenario 3 auch der maschinenstundenbasierte AUokationsansatz den grofiten Durchsatz. Ursache dafiir ist die Beriicksichtigung von globalen Informationen bei der Budgetzuteilung. In Abbildung 4.14 werden die ermittelten Werte fiir den Durchsatz TP fur ein Produktionssystem mit haufigen, kurzen Maschinenausfallen (Szenario 2) und ein Produktionssystem mit seltenen, langen Maschinenausfallen (Szenario 3) zusatzHch in Form eines Balkendiagramms veranschaulicht. In Abbildung 4.15 werden Ergebnisse fiir das Leistungsmafi ACT fur ein Produktionssystem mit vielen, kurzen Maschinenausfallen (Szenario 2)

168 KAPITEL 4. VERFAHREN ZUR AUTONOMEN

UND KOOPERATIVEN

STEUERUNG

Durchsatz (TP) 00

85,0

90

82.4

80

•^ pi in H^'^'-' •

70 60 ^ 0 40 30 20 10

H75,0

79^

•

69,4

87,2

H 69.2

r

•69,4

•60.4

B n

•68.8

•n •

P: 1 1 1 K:;: 1 1 I 1 Imi 11 11 11 11 Ji i L L .11.

MASmitSLSS

•

SLSS

Szenario2

•-n •

SPT

FIFO

ATC

|~3 Szenario3

Abbildung 4.14: Durchsatz fiir Szenario 2 und Szenario 3

gezeigt. Dabei wird die Durchlaufzeit im zeitlichen Verlauf betrachtet, indem jeweils nach einer bestimmten Anzahl fertiggestellter Lose die mittlere Durchlaufzeit gemessen wird. Offensichtlich erreicht MAS die geringste mittlere Durchlaufzeit, wahrend die mittlere Durchlaufzeit bei den prioritatsregelbasierten Ansatzen teilweise im zeitlichen Verlauf leicht ansteigt. AUe Experimente wurden auf einem PC mit einem Pentium-4-Prozessor mit 2,4 GHz Taktfrequenz und 256 MB Arbeitsspeicher durchgefiihrt. Die Laufzeit fiir einen Simulationslauf betrug fiir das betrachtete Produktionssystem weniger als fiinf Minuten. Zusammenfassend kann auf Basis der durchgefiihrten Experimente festgestellt werden, dass der maschinenstundenbasierte Ressourcenallokationsmechanismus besser als Prioritatsregeln zur Reaktion auf ungiiltige Ablaufplane im verteilten hierarchischen Steuerungsansatz geeignet ist. Durch die Kombination der verteilten Schedulingansatze mit dem maschinenstundenbasierten Ressourcenallokationsmechanismus wird sichergestellt, dass zu jedem Zeitpunkt eine Maschinenbelegungsentscheidung getroffen werden kann.

4.5

Integration in eine betriebliche Anwendungslandschaft

In diesem Abschnitt wird beschrieben, wie die in den Abschnitten 4.1, 4.2, 4.3, 4.4 beschriebenen Algorithmen in eine vorhandene betriebliche Anwendungslandschaft integriert werden konnen. Dazu wird im Wesentlichen dargestellt, in welchen Informationssystemen sich die Informationen

4.5. INTEGRATION

IN EINE BETRIEBLICHE

ANWENDUNGSLANDSCHAFT

169

Mittlere Durchlaufzeit (ACT) 8000 xxxxxxxxxxxx