Rolf Felter

Decision Support Assistant

Rail Felter

Decision Support Assistant Ein Konzept fiir ein Software-Verwaltunas­IYltem, mit dem vorhandene Software effizient zu leistunasfiihiaen Entlcheidunasunter­Itiitzenden Systemen zusammenaestellt werden kann

f[)fll.\n DeutscherUniversitatsVerlag ~ GABLER 'VIEWEG ·WESTDEUTSCHER VERLAG

ClP-Titelaufnahme der Deutschen Bibliothek

Feiter, Ralf: Decision support assistant: ein Konzept für ein Software­Verwaltungssystem, mit dem vorhandene Software effizient zu leistungsfähigen Entscheidungsunterstützenden Systemen zusammengestellt werden kann I Ralf Feiter. - Wiesbaden: Dt. Univ.-Verl., 1989

(DUV : Datenverarbeitung) Zugl.: Passau, Univ., Diss., 1989 ISBN 978-3-8244-2008-7 ISBN 978-3-322-91018-9 (eBook) DOI 10.1007/978-3-322-91018-9

Der Deutsche Universitäts-Verlag ist ein Unternehmen der Verlagsgruppe Bertelsmann International.

© Deutscher Universitäts-Verlag GmbH, Wiesbaden 1989

Das Werk einschließlich aller seiner Teile ist urheberrechtfich ge­schützt. Jede Verwertung außerhalb der engen Grenzen des Ur­heberrechtsgesetzes ist ohne Zustimmung des Verlags unzulässig und strafbar. Das gilt insbesondere für Vervielföltigungen, Über­setzungen, Mikroverfilmungen und die Einspeicherung und Ver­arbeitung in elektronischen Systemen.

ISBN 978-3-8244-2008-7

5

Vorwort

Diese Arbeit entstand wiihrend meiner Tatigkeit als wissenschaftIicher Mitarbeiter am Lehrstuhl fur Informatik und Operation Research der Universitat Passau im Rahmen eines langfristigen Forschungsprojektes zur Realisierung leistungsfahiger Entscheidungsunterstiitzender Systeme ftir komplexe Anwendungen (wie z.B. das Scheduling von Projekten). Gegenstand der vorliegenden Arbeit ist die Konzep­tion eines Verwaltungssystemes, mit dem die in einem Rechnersystem verftigbare Software problem- und anwenderspezifisch zu effizient arbeitenden Entschei­dungsunterstiitzenden Systemen zusammengestellt werden kann.

Auf einer SUN-Workstation wurden verschiedene Moglichkeiten zur Implemen­tie rung eines derartigen Verwaltungssystemes untersucht. 1m einzelnen wurden eine Realisierung tiber PROLOG, eine Realisierung tiber trickreiche PASCAL­Pointerstrukturen und eine Realsierung tiber die relationale Datenbank INGRES betrachtet. Der Datenbank-Ansatz, bei dem die Datenbank mit Hilfe der Datenbank-Anfragesprache QUEL aus C-Programmen heraus gesteuert wurde, erwies sich dabei den anderen Ansatzen gegentiber sowohl von der Performance als auch yom Programmieraufwand her als tiberlegen.

Zur Zeit wird nach den in dieser Arbeit entwickelten Konzepten ein Verwaltungs­system fur ein Entscheidungsuntersttitzendes System im Bereich der Projekt­planung aufgebaut. Dabei sind Standard-Software und an verschiedenen Universitaten entwickelte Spezial-Software zu einem leistungsfahigen Gesamt­system zu integrieren.

Ftir die langfristige Forderung dieser Arbeit und seine zahlreichen Anregungen und Verbesserungsvorschlagen gilt mein besonderer Dank Herrn Professor Dr. Dr. Radermacher, ebenso Herrn Professor Dr. Jarke, dessen konstruktive Kritik mir bei meiner Arbeit entscheidend weitergeholfen hat. Ftir ihre Anregungen und Diskussionen danke ich Herrn W. Effner, Herm J. Plagwitz, Herrn B. Schmid und meiner Frau Stephanie. SchlieBlich mochte ich auch noch allen Professoren der Fakultat ftir Mathematik und Informatik an der Universitat Passau danken, daB mir auch nach dem Weggang von Herrn Professor Dr. Dr. Radermacher weiterhin optimale Forschungsbedingungen zur Verfugung standen.

Passau, im Mai 1989

Ralf Felter

6 Inhaltsverzeichnis

Inhaltsverzeichnis

Vorwort

Inhaltsverzeichnis

Notation, Abkurzungen, Verweise

Uberblick

Kapitel1: Der Decision Support Assistant: Ein allgemeines Konzept fur ein Software tool, mit dem sich vorhandene Software effizient zu Systemen fur die Entscheidungsunterstutzung zusammenstellen laBt.

(1.1) Der DSA als Generator fiir Entscheidungsunterstiitzende Systeme

(1.2) Der DSA als Hilfsmittel zur kostengunstigen Realisierung von Entscheidungsunterstiitzenden Systemen durch den massiven Einsatz von Standard-Software

(1.3) Der DSA als VerwaltungsprozeB

(1.4) Der DSA als Reason-Maintenance-System

(1.5) Der DSA als Stratege

Kapitel 2: Die Methode: Ein Beschreibungskonzept fiir Algorithmen, bei dem neben der eigentlichen Algorithmenbeschreibung zusatzl­iche Informationen tiber das Algorithmenverhalten abgelegt werden, die es sowohl dem Entscheider als auch dem DSA ermoglichen, die Algorithmen im Hinblick auf ein globales Ziel sinnvoll einzusetzen.

(2.1) Darstellung der Infobank

(2.2) Darstellung von Methoden

(2.3) Darstellung der kritischen Faktenmengen

(2.4) Schlitzen von Methodenergebnissen

(2.5) Erklarungsfunktion fiir eine Methode

S. 5

S. 6

S. 8

S. 9

S. 12

S. 21

S.26

S. 35

S.49

S.57

S.65

S. 71

S.82

S.95

Inhaltsverzeichnis

Kapite13: Die Politik: Ein Ansatz flir ein Beschreibungskonzept. bei dem die Vorstellungen des Entscheiders tiber den sinnvollen Einsatz der Methodenauf vergleichsweise einfache Weise unabhlingig von tatsachlich vorhandenen Methoden formuliert werden konnen.

(3.1) Darstellung von Politiken

(3.2) RETE-Verfahren

(3.3) Auswahl der Methodenaufrufe

Kapite14: Integration der bisherigen Funktionen zu einem Gesamtsystem

(4.1) Ablauf des DSA

(4.2) Realisierung des DSA tiber Datenbankfunktionen

Kapite15: Die Beraterfunktionen: Eine Supervisor-Funktion. tiber die der Entscheider den Ablauf des Entscheidungsprozesses auf einfache und komfortable Weise kontrollieren und steuem kann.

Zusammenfassung

Literatur

Index

7

S.lOO

S.107

S.120

S.l33

S.l40

S.l45

S.156

S.l59

S.l65

8 Notation

Notation

In dieser Arbeit werden fur Mengen und Folgen teilweise spezielle Schreibweisen verwendet:

Menge: 'Ober den Il-Operator bzw. O-Operator kann man das kleinste bzw. groBte Element einer Menge M bzg. einer Funktion f: 0 -> R bestimmen, wenn Meine Teilmenge von 0, f eine injektive Funktion und Reine Menge mit einer ~-Relation ist

J..lr(x){x E: M} = Y :<=> y E: M und 'V x E: M gilt: f(y):S; f(x)

!lr(x){x E: M} = Y :<=> y E: M und'V x E: M gilt: f(x):S; f(y)

z.B. J...lid(s){S E: M } = a und nid(s){S E: M } = f

Dabei steht id ftir die Identitatsfunktion, ~ fUr die alphabetische Reihenfolge und M fiir {a,b,c,d,e,f}

Folge: Eine Folge wird dadurch dargestellt, daB man ihre einzelnen Elemente in ronde Klammem schreibt: z.B. F:= (a,b,c,a,e,b). 1m Gegensatz zur Menge ist bei der Folge die Reihenfolge der Elemente wichtig. Insbesondere konnen Elemente auch doppelt vorkommen.

Uber den #-Operator wird die Lange einer Folge beschrieben. z.B. #F=5

Durch F[i] konnen die einzelnen Elemente einer Folge bezeichnet werden. z.B. F[3]=c

Ftir Folgen gibt es noch eine alternative Schreibweise tiber den o-Operator z.B. F:= (a,b,c,a,e,b) = a 0 b 0 c 0 a 0 e 0 b

Der o-Operator kann auch zur Erweiterung von Folgen verwendet werden z.B. a 0 F = (a,a,b,c,a,e,b) oder Fog = (a,b,c,a,e,b,g)

Abkiirzung

o.B.d.A. ohne Beschriinkung der Allgemeinheit

Verweise

[Willi 87] (KapiteI3) (3.4) (1) (a) (A)

(3.1.2) (4.2.a)

ist ein Literaturhinweis ist ein Verweis auf ein ganzes Kapitel ist ein Verweis auf ein Unterkapitel sind Verweise innerhalb eines Unterkapitels sind Verweise auf Stellen in anderen Kapiteln oder Unterkapiteln

Uberblick 9

Uberblick

In diesem Buch wird unabhlingig von speziellen Problembereichen ein Konzept zur Realisierung eines Verwaltungssystemes vorgestellt, uber das die in einem Rechnersystem verfUgbaren Algorithmen auf vergleichsweise einfache Weise problem- und anwenderspezifisch zu effizient arbeitenden Systemen der Entschei­dungsunterstutzung zusammengestellt werden konnen. Da sich ein solches Verwaltungssystem am Beratungsmodell eines personiichen Assistenten orientiert, wird es in diesem Buch als Decision SUlW0rt Assistant (DSA) bezeichnet.

Fur die Erstellung von komplexen Software-Systemen aus bereits vorhandener Software stehen mit den Betriebssystem-Shells (z.B. C-Shell in Unix [Gulbins 84]), den Methodenbanken im Sinne von [Dittrich, Huber, Lockemann 79] und den 4GL­Sprachen [Martin 85/86] bereits bewahrte Entwickiungs-Toois zur Verfugung. GroBe Probleme tauchen jedoch auf, wenn man versucht, mit diesen Tools Systeme zu entwickeln, auf die die folgenden Eigenschaften zutreffen:

(a) Es gibt kein allgemein anerkanntes Verfahren, mit dem mit akzeptablem Zeitaufwand festgelegt werden kann, wann welcher Algorithmus wie anzuwen­den ist, damit das Gesamtsystem seine Aufgabe zufriedenstellend erfiillt.

(b) Welche Algorithmen zur Losung eines Problems wie eingesetzt werden sollen, hangt nicht nur yom Problem seIber ab, sondem auch von den intuitiven Vorstellungen des Entscheiders und von der verfugbaren Zeit.

(c) Ein iterativer Autbau des zu entwickelnden Systems ist erwiinscht.

Speziell fiir Systeme mit derartigen Eigenschaften ist der DSA konzipiert worden. Bei ihm werden Entscheidungsunterstutzende Systeme durch die Angabe von sogenannten Methoden (KapiteI2) und Politiken (KapiteI3) beschrieben. Nach den Ausfiihrungen in (1.1) ist dies die am besten geeignete Form, Systeme zu beschreiben, bei deren Entwicklung, die in (a) aufgefiihrten Schwierigkeiten auftauchen. Unter einer Methode versteht man die urn einige zusatzliche Angaben erglinzte Beschreibung eines Algorithmus. Bei den zusatzlichen Angaben handelt es sich in erster Linie urn schnell berechenbare Schlitzfunktionen, mit denen schon vor der Ausfiihrung eines Algorithmus angenlihert berechnet werden kann, aus welchen Informationen (2.3) er wie schnell welche Informationen erzeugt (2.4). Durch eine statistische Verfolgung des AlgorithmenverhaItens besteht sogar die Moglichkeit, die Vorab-Schatzfunktionen im Sinne einer On-Line Systemadaption permament an das tatsachliche Verhalten der Algorithmen anzupassen.

10 Uberblick

In den Politiken (Kapitel 3) wird festgelegt, nach welchen Kriterien die Methoden einzusetzen sind. Dazu gehOren die Beschreibung des angestrebten Ziels, die daflir verfUgbare Zeit und das Vorschlagen von Algorithrnen, die flir das Erreichen des angestrebten Ziels besonders geeignet sind. Damit konnen uber Politiken intuitive Vorstellungen uber den Einsatz der Algorithrnen und die flir die Losung der Probleme verfUgbare Zeit auf naheliegende Weise angegeben werden (vgl. (b)).

Aus der Sieht des DSA konnen Methoden und Politiken unabhlingig von anderen Methoden oder Politiken entwickelt werden. Diese Eigenschaft bildet zusammen mit dem in (1.2) beschriebenen Konzept der Brucken-Algorithmen, das eine schnelle Anpassung an eine veranderte Software-Umgebung ennoglicht, die Grundlage fur einen iterativen Autbau des zu entwiekelnden Systems (vgl. (c)).

Daruber hinaus erfUllen Systeme, die uber den DSA realisiert werden, automatisch noch zwei weitere Eigenschaften: Sie sind Reason-Maintenance-Systeme im Sinne von [Reinfrank 86] (1.4), wodurch gewahrleistet ist, daB Anfragen des Entscheiders im Sinne von (1.4.1) korrekt und vollstandig beantwortet werden, und sie verfugen uber komfortable Beraterfunktionen (Kapitel 5), mit denen der Entscheider das Verhalten des Systems vollstlindig uberwachen und steuem kann.

Ein uber Methoden und Politiken spezifiziertes System realisiert der DSA dadurch, daB er die Methoden aufgrund der Anweisungen in einer aktuellen Politik einsetzt und die dabei erzeugten Infonnationen in einer zentralen Speicherstruktur sammelt. Der DSA fiihrt die Methoden nicht seIber durch, sondem deligiert sie an parallel arbeitende Hilfsprozesse, die die Methodenergebnisse an den DSA zuriickschicken, sobald sie ennittelt wurden. Auf diese Weise konnen in einer entsprechenden Hard- und Software-Umgebung mehrere Methoden gleichzeitig ausgeflihrt werden und die Zeit, in der die Methoden ausgeflihrt werden, kann ausgenutzt werden, urn neue Methoden zur Ausflihrung auszuwahlen (1.3). Fur eine derartige Organisation des DSA sprechen zwei Griinde: Zum einen handelt es sich bei den in der Entscheidungsunterstiitzung verwendeten Methoden in der Regel urn zeitaufwendige Algorithmen, so daB viel Zeit bleibt, urn den Einsatz der nachfolgenden Methoden sorgfaltig zu planen. Zum anderen lassen sich die Aufgaben der Entscheidungsunterstiitzung in der Regel sehr leicht parallelisieren, so daB eine parallele Ausflihrung der Methode mit gro8er Wahrscheinlichkeit zu erheblichen Verbesserungen bei der computerunterstiitzenden Entscheidungsfin­dung fiihren wird.

Uberblick 11

Der DSA hat also im wesentlichen drei Aufgaben zu erfiillen:

(I) Die von den Methoden erzeugten Ergebnisse so zu verwalten, daB die Eigenschafien eines Reason-Maintenance-Systems erhalten bleiben. Dazu werden in (1.4) die theoretischen Grundlagen gelegt, wahrend in (2.3) ein effizient arbeitendes Verfahren dargestellt wird.

(II) Aufgrund der Angaben in der Politik geeignete Methoden auszuwahlen. In (1.5) wird die grundsatzliche Vorgehensweise skizziert, die im wesentlichen dem Vorgehen bei Computerspielen entspricht. In Kapitel 3 wird gezeigt, wie man bei dieser Vorgehensweise Prazision und Schnelligkeit miteinander verbinden kann.

(III) Beraterfunktionen bereitzustellen und die tiber Beraterfunktionen gemachten Anweisungen des Entscheiders zu bearbeiten. In Kapitel 5 wird gezeigt, wie man mit wenig Programmieraufwand Beraterfunktionen erstellen kann, die so komfortabel und leistungsfahig sind, daB sie flir die meisten Anwendungen ausreichen werden.

Das Leistungspotential des DSA-Konzeptes drtickt sich im wesentlichen in der Laufzeit der vom DSA bereitgestellten Funktionen aus. Denn der GroBenordnung nach hangt diese nur logarithmisch vom Umfang der insgesamt im System enthaltenen Information und hOchstens quadratisch (2.3.12) vom Umfang der zu berechnenden Information abo Die praktische Umsetzung der Konzeption erfolgt am besten tiber Datenbanken. Denn alle wichtigen Funktionen des DSA konnen mit geringem Programmieraufwand auf typische Datenbankfunktionen zurtickgeflihrt werden, ohne daB sich die Gesamtperformance des DSA dadurch wesentlich verschlechtert.