Konzeption und Realisierung eines Terminplaners für ein radiologisches Informationssystem (RIS) unter Berücksichtigung softwareergonomischer Aspekte

Inhaltsverzeichnis

1 Einführung

2 Bisherige und geforderte Funktionalität
2.1 Funktionalität des bisherigen Terminplaners
2.2 Anforderungen an den neuen Terminplaner
2.2.1 Mehrfachtermine
2.2.2 Geschwindigkeit

3 Theorie der Ablaufplanung
3.1 Planungsprobleme
3.1.1 Auftragsmodelle
3.1.2 Prozessormodelle
3.1.3 Optimierungskriterien
3.1.4 Beispiele
3.1.5 Erweiterungen
3.2 Lösung von Planungsproblemen
3.3 Mehrere Prozessoren pro Operation
3.4 Terminplanung in der Radiologie
3.4.1 Das Modell für Serientermine
3.4.2 Das Modell für Profiltermine

4 Algorithmen zur Terminvergabe
4.1 Der Algorithmus zur Profilterminvergabe
4.1.1 Komplexität
4.2 Der Algorithmus zur Serienterminvergabe

5 Implementierung
5.1 Schichten bei Anwendungsarchitekturen .
5.1.1 2-Schicht-Modell
5.1.2 3-Schicht-Modell
5.2 Verwendete Softwareprodukte
5.2.1 Java
5.2.2 J2EE und EJB
5.2.3 Orion
5.2.4 Forte
5.2.5 SourceSafe
5.2.6 Oracle 8.06
5.2.7 JFCSuite
5.3 Benutzeroberfläche
5.3.1 Steuerungsleiste
5.3.2 Monatsübersicht
5.3.3 Multifunktionsleiste
5.3.4 Weitere Termine / Abwesenheitsliste
5.3.5 Terminübersicht
5.3.6 Termindialog
5.4 Architektur der Benutzerschicht
5.5 Architektur der Vorgangsbearbeitung
5.5.1 Session-Beans
5.5.2 Entity-Beans
5.6 Stand des Projektes

6 Fazit und Ausblick

Stichwortverzeichnis

Kapitel 1

1. Einführung

Die Firma GE Medical Systems Information Technologies¹ in Dornstadt bei Ulm ist einer der führenden Hersteller von Radiologie-Informationssystemen (RIS ) in Europa. Das Hauptprodukt der Firma ist das Programmpaket Medora, welches eine vollständige RIS-Lösung für radiologische Kliniken und Praxen darstellt.

Ein RIS dient dazu, Radiologiepatienten und Patientenakten, Materiallager, Befundungen sowie Belegungen von Geräten, Arbeitsplätzen und Mitarbeitern zu verwalten. Eng verwandt mit dem Begriff des RIS ist der des Krankenhaus-Informationssystems (KIS ). Ein KIS ist eine Software, die zentral alle Patienten des Krankenhauses erfaßt und verwaltet. RIS und KIS kommunizieren über den sogenannten HL7 -Standard², welcher ein Protokoll zur elektronischen Kommunikation im Gesundheitswesen darstellt. Die Kommunikation zwi-

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1.1: KIS und RIS

schen KIS und RIS verläuft dabei in beiden Richtungen. Eine typische HL7-Nachricht vom KIS an das RIS wäre etwa die Anforderung einer CT-Aufnahme für einen Patienten an einem bestimmten Tag. Das RIS sendet daraufhin z. B. eine Terminbestätigung an das KIS zurück. HL7-Nachrichten können auch von anderen Krankenhausabteilungen an das RIS gesandt werden.

Das Radiologie-Informationssystem Medora wurde bisher vollständig mit der Program- mierumgebung Oracle Forms entwickelt³⁴, welches auf die Erstellung von Datenbankanwen- dungen mit graphischer Oberfläche zugeschnitten ist. Forms ermöglicht es auf relativ einfache Weise, dialogbasierte Anwendungen zu erstellen, die an eine Datenbank gekoppelt sind. Ein großes Manko von Forms ist allerdings, daß der Entwickler die Oberfläche nur aus einem sehr beschränkten Satz von Komponenten zusammenbauen kann. Daher lassen die damit erzeugten Applikationen in puncto Benutzerfreundlichkeit eher zu wünschen übrig und sind bezüglich Benutzeroberfläche nicht auf dem aktuellen Stand der Technik. So ist es in einer Forms-Applikation für den Benutzer nicht möglich, die Größe von Fenstern oder von Un- terkomponenten wie Tabellenspalten zu verändern oder Objekte zu verschieben ( ”Dragand Drop“ ). Auch gibt es für viele der Elemente einer modernen Benutzeroberfläche wie Kontextmenüs, Baumansichten usw. in Forms keine Entsprechung.

Eine weitere Problematik resultiert aus der Tatsache, daß, um in Forms eine bestimmte Reaktion auf ein semantisches Ereignis (Mausklick, Tastatureingabe, Nachricht überÄnderung eines Datensatzes, usw.) zu programmieren, im Regelfall eine ganze Reihe von Behandlungsroutinen für sog. Trigger bemüht werden müssen. Die Mengen von Triggern, die für semantische Ereignisse benötigt werden, überschneiden sich untereinander, so daß mit steigender Größe des Projekts die Abhängigkeiten zwischen Behandlungsroutinen untereinander zunehmen und es immer schwieriger wird, Änderungen am Code vorzunehmen und dabei unbeabsichtigte Seiteneffekte im Griff zu behalten.

Zu der genannten Unübersichtlichkeit steuert auch die fehlende Objektorientierung von Forms bei, die ebenfalls mit zunehmender Projektgroße immer stärker ins Gewicht fällt. Aus diesen Gründen beschloß man Mitte 2001, als Technologiestudie - mit Option auf Fortführung als Produkt - ein einzelnes Modul von Medora auf eine Plattform umzustellen, die die erwähnten Mängel nicht aufweisen, aber gleichzeitig eine effektive Datenbankanbin-dung erlauben würde. Die Plattformwahl fiel auf Java⁵, da es zum einen auf einfache, aber dennoch flexible Weise gestattet, graphische Benutzeroberflächen zu implementieren und zum anderen durch die J2EE -Erweiterung 3-Schicht-Architekturen unterstützt werden, somit also eine Anbindung der objektorientierten Programmiersprache an eine relationale Datenbank gegeben ist.

Als Objekt der Technologiestudie war das Terminplanungsmodul am geeignetsten, da bei ihm erstens die geringste Abhängigkeit zu anderen Medora-Komponenten besteht, es also das am einfachsten austauschbare Modul ist, und zweitens bei der Terminplanung der Bedarf nach ei- ner verbesserten Version am größten war. Außerdem hätte bei einer Forms-Implementierung die erwähnte Zunahme der Unübersichtlichkeit und der Seiteneffekte bei den für die neue Version geplanten Funktionen wand bereitet.

”Serientermine“und ”Profiltermine“entsprechendenMehrauf Die vorliegende Diplomarbeit beschäftigt sich mit der Konzeption und Realisierung der Tech nologiestudie ”NeueTerminplanung“.

Kapitel 2

Bisherige und geforderte Funktionalität

2.1 Funktionalität des bisherigen Terminplaners

Der bisherige Terminplaner verwaltet Termine auf der Basis von Terminbüchern. Ein Ter- minbuch ist eine Übersicht über die Termine einer Ressource (Mitarbeiter oder Gerät). Jeder Ressource ist ein Terminraster zugeordnet, welches je nach Tag verschieden sein kann. Es gibt drei Hauptdialoge, von denen mehrere gleichzeitig geöffnet werden können:

- Tagesübersicht (Stellt ein Terminbuch für eine Ressource an einem Tag dar; siehe Abb. 2.1)
- Jahresübersicht (Stellt einen Jahreskalender für eine Ressource dar; Mausklick auf einen Tag öffnet die Tagesübersicht für diese Ressource; siehe Abb. 2.1)
- Terminauskunft (Suche nach existierenden Terminen)

Zur Anzeige einer Tages- und Jahresübersicht einer Ressource muß der Benutzer diese erst im Ressourcenauswahl-Dialog auswählen (siehe Abb. 2.2). Um einen neuen Termin anzulegen, klickt man in der Tagesübersicht auf eine freie Rasterzeile, worauf sich ein Patientenauswahl- Dialog öffnet (siehe Abb. 2.3). Nachdem der Patient, für den der Termin reserviert werden soll, ausgewählt ist, öffnet sich der eigentliche Terminvergabe-Dialog (Siehe Abb. 2.4).

2.2 Anforderungen an den neuen Terminplaner

Unter Berücksichtigung von Prinzipien modernen GUI-Designs sowie Kommentaren und Wünschen seitens von Kunden wurde ein Pflichtenheft für die neue Version des Terminplaners erarbeitet. Es spezifiziert u. a. folgende Anforderungen:

- Die neue Terminplanung soll die gesamte Funktionalität der alten Version beherrschen
- Die Größe jedes Fensters und abgetrennten Fensterbereichs soll veränderbar sein
- Termine sollen sowohl innerhalb eines Terminbuchs als auch zwischen Terminbüchern verschoben werden können ( ”DragandDrop“)
- Es sollen Mehrfachtermine unterstützt werden (siehe Abschn.2.2.1)

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1: Jahresübersicht (links oben) und Tagesübersicht (rechts unten)

- Mitarbeiter und Geräte sollen in Mitarbeitergruppen bzw. Gerätegruppen eingeteilt werden können
- Es soll eine Zwischenablage für Termine geben
- Die Zeitdauer für die Ausführung der wichtigsten Operationen soll ein bestimmtes Maß nicht überschreiten (siehe Abschn. 2.2.2)

2.2.1 Mehrfachtermine

Mit der neuen Version des Terminplaners wurden Mehrfachtermine eingeführt. Es werden zwei Arten von Mehrfachterminen unterstützt: Serientermine und Profiltermine. Mehr dazu findet sich in Abschnitt 3.4.

2.2.2 Geschwindigkeit

Ein vorrangiges Kriterium beim neuen Terminkalender war, daß das System für das Eintragen eines neuen Termines und das Ändern eines bereits existierenden Termines nicht länger als eine Sekunde benötigen sollte.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.2: Der Ressourcenauswahl-Dialog

Aufgrund früherer Betrachtungen [Hieber 96] wurde bisher davon ausgegangen, daß zum Er- stellen von Profilterminen ein Backtracking-Algorithmus notwendig ist, der den Zeitaufwand pro einzelnem Termin stark erhöhen würde. Daher wurde die Zeitspanne, die bei Profiltermi- nen pro einzelnem Termin nicht überschritten werden sollte, auf zehn Sekunden festgesetzt. In Kap. 4 wird ein neuer Ansatz vorgestellt werden, der ohne den Einsatz von Backtracking- Algorithmen auskommt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.3: Der Patientenauswahl-Dialog

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.4: Der Terminvergabe-Dialog

Kapitel 3

Theorie der Ablaufplanung

Die Ablaufplanung ist ein Untergebiet der Unternehmensforschung (auch unter der englischen Bezeichnung Operations Research bekannt). Die Anfänge der Planungstheorie datieren um die Jahrhundertwende, als man begann, sich wissenschaftlich mit Problemen wie der Maschinenbelegung in Fertigungsanlagen zu befassen (Siehe [Pinedo 95]). Der wichtigste Pionier auf diesem Gebiet war Henry Gantt (1861-1919). Die ersten Resultate in Form von wissenschaftlichen Veröffentlichungen wurden jedoch erst in den 50er Jahren erarbeitet.

Die Ablaufplanung beschäftigt sich mit der

”VergabevonRessourcenübereinenZeitraumhinwegmitdemZiel,eineAnzahl von Aufträgen zu erledigen“ (Übersetzt nach [Baker 74]).

Es geht also darum, zu entscheiden, in welcher Reihenfolge eine vorhandene Anzahl Ressour- cen (im terminus technicus Prozessoren genannt) eingesetzt werden soll, um eine gegebene Anzahl von Aufträgen gemäß einem Optimaierungskriterium zu bearbeiten. Die Aufträge (engl. Jobs) setzen sich dabei aus elementaren Operationen (engl. Operations oder Tasks) zusammen, von denen jede von einem anderen Prozessor bearbeitet werden kann. Es gibt unterschiedliche Optimalitätskriterien, die dabei zum Einsatz kommen können, oft ist bei- spielsweise die Minimierung der mittleren oder maximalen Bearbeitungszeit von Bedeutung, oder die Minimierung von Kosten.

Zur graphischen Darstellung einer Belegung verwendet man Gantt-Diagramme. Es gibt pro- zessororientierte (Abb. 3.1) und aufgabenorientierte (Abb. 3.2) Gantt-Diagramme. Auf der waagrechten Achse ist immer die Zeit abgetragen, auf der senkrechten die Prozessoren bzw. Aufgaben.

3.1 Planungsprobleme

Je nachdem, welche Arten von Prozessoren und Aufgaben vorliegen, d. h., welcher Prozessor welche Operationen in welcher Zeit bearbeiten kann und unter welchen Bedingungen die zu einem Auftrag gehörenden Operationen abgearbeitet werden müssen, entstehen mehrere grundlegend verschiedene Kategorien von Planungsproblemen. Zur Beschreibung von Planungsproblemen gibt es in der Ablaufplanung verschiedene Modelle. Ein solches Modell setzt sich aus drei Teilen zusammen (vgl. [Brucker 95], [Blazewicz 96]):

- Dem Auftragsmodell
- Dem Prozessormodell und

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.1: Prozessororientiertes Gantt-Diagramm

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.2: Gleiche Belegung wie in Abb. 3.1, jedoch als aufgabenorientiertes Diagramm

- Dem Optimierungskriterium.

Zur kompakten Beschreibung von Planungsproblemen wird eine mathematische Notation benutzt, die auf [Graham 79] zurückgeht. Sie hat die Form α | β | γ, wobei α die Beschreibung des Prozessormodells, β die Beschreibung des Auftragsmodells und γ die des Optimierungskriteriums ist. Eine genauere Erläuterung der drei Teile dieser Notation und deren Bedeutung findet sich in den folgenden Abschnitten. Soweit nicht anders angegeben, liegen diesen Abschnitten die Bücher [Brucker 95] und [Blazewicz 96] zugrunde.

3.1.1 Auftragsmodelle

Bei jedem Planungsproblem ist eine Menge {A1, . . . , An} von Aufträgen zu bearbeiten. Jeder Auftrag Ai besteht aus einer Menge von Operationen Oi1, . . . , Oini . Besteht der Auftrag nur aus einer Operation, so schreibt man Ai statt Ai1.

Der Parameter β eines Planungsproblems beschreibt dessen Auftragsmodell und hat die Form β1β2β3β4β5. Jeder der fünf Einzelparameter kann entweder leer sein oder einen der Werte, die im folgenden aufgeführt sind, haben: listii

- β1 gibtan,obdieOperationenteilbar (präemptiv)sind.

β1 leer: Die Operationen sind unteilbar, können also nur als Ganzes ausgeführt werden.

β1 = pmtn: Die Operationen sind teilbar, können also in mehreren Etappen auf verschiedenen Prozessoren bearbeitet werden.

- β2 spezifiziert Abhängigkeitsbeziehungen unter den Aufträgen. Ein Satz von Abhän- gigkeitsbeziehungen eines Planungsproblems wird durch einen gerichteten Graphen G dargestellt.

β2 leer: Die Aufträge können in beliebiger Reihenfolge ausgeführt werden.

β2 = prec: G ist ein beliebiger gerichteter Graph.

β2 = uan: G ist ein einfach verbundenes Aktivitätsnetzwerk , d. h., ein gerichte ter Graph, bei dem für jedes Paar von Knoten (u, v) genau ein Pfad p existiert, so daß p u und v verbindet oder umgekehrt.

β2 = intree: G ist ein Einwärtsbaum, also ein Baum, bei dem jeder Knoten höch- stens eine wegführende Kante besitzt.

β2 = outtree: G ist ein Auswärtsbaum, also ein Baum, bei dem jeder Knoten höch- stens eine herführende Kante besitzt.

β2 = tree: G ist entweder ein Einwärtsbaum oder ein Auswärtsbaum.

β2 = chains: G ist eine Vereinigung von Kettengraphen, d. h. ein Baum, bei dem jeder Knoten höchstens eine herführende und höchstens eine wegführende Kante besitzt.

- β3 gibt Auskunft über Bereitstellungszeiten (engl. ready times oder release dates) von Aufträgen.

β3 leer: Alle Aufträge müssen zum Zeitpunkt 0 zur Bearbeitung bereitstehen.

β3 = rj: Für jeden Auftrag ist ein Zeitpunkt angegeben, ab dem er zur Bearbei- tung bereitstehen muß.

- β4 steht für die Bearbeitungszeiten der einzelnen Operationen.

β4 leer: Für jede Operation ist eine Bearbeitungszeit angegeben.

β4 = (pj = 1) bzw.

β4 = (pij = 1): Alle Aufträge haben die gleiche Bearbeitungszeit.

Daneben gibt es noch eine Reihe anderer Charakteristika, auf die man in der Literatur gelegentlich trifft, wie z. B. β4 = (pij ∈ {1, 2}) oder β4 = (p ≤ pij ≤ p).

- β5 schließlich enthält Informationen darüber, ob bei der Auftragsbearbeitung Stichtermine beachtet werden müssen.

β5 leer: Es sind keine Stichtermine festgelegt.

β5 = di: Jeder Auftrag hat einen Stichtermin, bis zu dem der Auftrag spätestens fertig sein muß.

Es gibt darüberhinaus eine Vielzahl von Spezialfällen von Planungsproblemen; bei diesen können zusätzlich zu β1, . . . , β5 auch noch weitere Bedingungen in β enthalten sein.

3.1.2 Prozessormodelle

Bei einem konkreten Planungsproblem ist stets eine Menge P = {P1, . . . , Pm} von Prozessoren gegeben. sk ist die Geschwindigkeit des Prozessors Pk. Jedem Auftrag ist eine Bearbeitungszeit pik zugeordnet. pik ist die Bearbeitungszeit des Auftrags i auf dem Prozessor k unter der Annahme, daß der Auftrag ausschließlich von diesem einen Prozessor bearbeitet wird, d. h., keine Präemption auftritt.

Jeder Operation Oij eines Auftrags Ai ist eine Menge µij ⊆ P von Prozessoren, die diese Operation bearbeiten können, zugeordnet.

Je nach Art der Prozessoren und der Aufträge teilt man Prozessormodelle in drei Kategorien ein:

- Einprozessorsysteme
- Parallele Prozessoren
- Spezialisierte Prozessoren (In der engl. Literatur Dedicated Processors genannt)

Diese Klassen enthalten jeweils Prozessormodelle, von denen jedes durch einen Parameter α bezeichnet wird. Dieser Parameter ist gemäß α = α1α2 zusammengesetzt, wobei α1 den Prozessortyp angibt und α2 die Anzahl der Prozessoren.

Im folgenden werden die verschiedenen Prozessormodelle genauer beschrieben. Dabei gelten für alle Modelle folgende allgemeine Regeln:

- Operationen, die zu verschiedenen Aufträgen gehören, können in beliebiger Reihenfolge ausgeführt werden.
- Jeder Prozessor kann höchstens einen Auftrag gleichzeitig bearbeiten.
- Jeder Auftrag kann nur auf einem Prozessor gleichzeitig laufen. Einprozessorsysteme

Wenn der Parameter α leer ist, liegt ein Einprozessorsystem vor, d. h. alle Aufträge werden von einem einzelnen Prozessor bearbeitet.

Parallele Prozessoren

Der Begriff ”parallel“istnachAnsichtdesAutorsetwasunglücklichgewählt,dennerbezeich- net nicht etwa die Eigenschaft einer Gruppe von Prozessoren, mehrere Aufträge gleichzeitig bearbeiten zu können (welche selbstverständlich auch bei spezialisierten Prozessoren gegeben ist), sondern bedeutet vielmehr, daß die Menge von Operationen, die ein Prozessor ausführen kann, für alle Prozessoren gleich ist. ”Parallel“bezeichnetalsodenUmstand,daßalleProzes- soren bezüglich Auftragsbearbeitung die gleichen Fähigkeiten haben. Beim Modell mit parallelen Prozessoren enthält grundsätzlich jeder Auftrag genau eine Ope- ration.

Parallele Prozessoren können sich in ihren Bearbeitungsgeschwindigkeiten unterscheiden. Man unterscheidet daher³ Unterklassen von parallelen Prozessoren:

1. Wenn α1 = P ist, handelt es sich um identische Prozessoren. Das bedeutet, daß die Bearbeitungszeit für alle Operationen eines Auftrags gleich ist, unabhängig vom Pro- zessor. Die Bearbeitungszeit hängt also nur vom Auftrag ab. Mathematisch ausgedrückt bedeutet dies pik = pi, 1 ≤ k ≤ n.

2. Bei α1 = Q spricht man von gleichartigen Prozessoren. Hier unterscheiden sich die Bearbeitungszeiten für einen Auftrag um einen konstanten Geschwindigkeitsfaktor, der von Prozessor zu Prozessor verschieden sein kann. Es gilt also pik = pi/sk, wobei pi die Bearbeitungszeit des Auftrags auf einem Prozessor mit Geschwindigkeit 1 ist.

3. Ist α1 = R, so sind die Prozessoren unverwandt, d. h., die Bearbeitungszeit hängt sowohl vom Prozessor, als auch von der auszuführenden Operation ab. Im Gegensatz zu gleich- artigen Prozessoren gibt es hier also keinen konstanten Faktor, durch den sich die Bear- beitungszeiten für eine gegebene Operation von Prozessor zu Prozessor unterscheiden, sondern für jedes Paar (P rozessor, Operation) ist eine eigene Bearbeitungsgeschwin- digkeit definiert. Die Bearbeitungszeit ergibt sich also gemäß pij = pi/sij , wobei pi die Bearbeitungszeit auf dem Standardprozessor ist.

Spezialisierte Prozessoren

Im Gegensatz zu Szenarien mit parallelen Prozessoren, wo alle Operationen, die ein Prozessor ausführen kann, auch von jedem anderen Prozessor ausgeführt werden können, ist dies bei spezialisierten Prozessoren nicht gegeben. Vielmehr ist jedem Prozessor eine Menge von Operationen zugeordnet, die er durchführen kann.

Jeder Operation Oij ist eindeutig ein Prozessor zugeordnet. In anderen Worten, [Abbildung in dieser Leseprobe nicht enthalten]. Prozessormodelle mit spezialisierten Prozessoren werden in 3 Kategorien eingeteilt:

1. Das Job-Shop-Modell (α1 = J ). Hier liegen n Aufträge und m Prozessoren vor. Jedem Auftrag ist eine Abarbeitungsreihenfolge der Operationen zugeordnet.

2. Beim Flow-Shop-Modell (α1 = F ) hat jeder Auftrag eine Anzahl n von Operationen, die gleich der Zahl der Prozessoren ist. Die Abarbeitungsreihenfolge der Operationen innerhalb eines Auftrags ist festgelegt. Die i-te Operation muß vom Prozessor i be- arbeitet werden. Der Flow-Shop ist ein Spezialfall des Job-Shops mit ni [Abbildung in dieser Leseprobe nicht enthalten].

3. Das Open-Shop-Modell (α1 = O) ist mit dem Flow-Shop-Modell identisch, bis auf den Unterschied, daß die Operationen eines Auftrags in beliebiger Reihenfolge bearbeitet werden können.

Anzahl der Prozessoren

Wie schon erwähnt, gibt der Parameter α2 die Prozessorzahl im System an. Wenn α2 leer ist, ist die Anzahl variabel. Ist nur ein Prozessor vorhanden, so wird α2 weggelassen.

3.1.3 Optimierungskriterien

Bei einem Planungsproblem gilt es, eine optimale Planung zu finden, d. h., eine Planung, die eine Kostenfunktion minimiert.

Eine Kostenfunktion F für ein Optimierungsproblem besteht aus zwei Funktionen, die miteinander verkettet sind:

[Abbildung in dieser Leseprobe nicht enthalten]

Die fi geben die Kosten für den Auftrag Ai an, abhängig von dem Zeit Zeitpunkt Ci der Fertigstellung des Auftrages. Die Funktion fges bildet die n Werte für die Kosten der Aufträge auf einen einzigen Wert ab. Dieser Wert ist ein Maß für die Gesamtkosten der Planung. Die Kostenfunktion F ergibt sich wie folgt:

Abbildung in dieser Leseprobe nicht enthalten

Von fges gibt es im Wesentlichen vier Varianten:

Abbildung in dieser Leseprobe nicht enthalten

Beispiele für fi sind:

Abbildung in dieser Leseprobe nicht enthalten

Der Parameter γ gibt das Optimalitätskriterium des Planungsproblems an, also die Kostenfunktion. Die am häufigsten verwendeten Kostenfunktionen sind die folgenden:

Abbildung in dieser Leseprobe nicht enthalten

3.1.4 Beispiele

Hier nun einige ausgewählte Klassen von Planungsproblemen:

[Abbildung in dieser Leseprobe nicht enthalten] Ti bezeichnet das Problem, die durchschnittliche Fristüberschreitung in einer

Anlage mit k Prozessoren und einheitlichen Bearbeitungszeiten zu minimieren.

[Abbildung in dieser Leseprobe nicht enthalten] Cmax ist die Klasse von Planungsproblemen, bei denen Aufträge, deren Operationen un- teilbar sind und beliebige Bearbeitungszeiten haben können, auf identische Prozessoren verteilt werden sollen. Die Aufgaben sind alle vom Zeitpunkt 0 an zur Bearbeitung verfügbar, und es soll die Dauer bis zur Fertigstellung des letzten Auftrags minimiert werden.

[Abbildung in dieser Leseprobe nicht enthalten] Ci steht für ein Open-Shop-Modell mit 3 Prozessoren, bei dem Aufträge zu verschiedenen Zeiten beim System eingehen und Operationen beliebige Bearbeitungszeiten haben. Ziel ist es, die mittlere Bearbeitungszeit zu minimieren.

3.1.5 Erweiterungen

Zusätzlich zum hier vorgestellten Grundmodell der Planungsprobleme sind im Laufe der Zeit auch zahlreiche Erweiterungen untersucht worden. Dazu zählen die Berücksichtigung von Transportzeiten und -wegen, Signallaufzeiten, Materialverbrauch, stochastische Modelle für Auftragsankunftszeiten und Prozessorausfallzeiten, sog. für verschiedene Aufgaben umgerüstet werden können, usw.

”flexible“Prozessoren,die ([Brucker [95]], [Pinedo [95]],

[Blazewicz [96]]). Diese Modelle sollen hier nicht näher erläutert werden, jedoch wird in Abschnitt³.³ das Modell dahingehend erweitert werden, daß eine Operation mehrere Prozessoren gleichzeitig benötigen kann.

3.2 Lösung von Planungsproblemen

Für viele Klassen von Planungsproblemen existieren Algorithmen, die das Problem effizient, d. h. in polynomieller Zeit lösen. Bei anderen Klassen hingegen ist bekannt, daß sie NP-hart sind, also aller Wahrscheinlichkeit nach nicht effizient zu lösen sind. Viele Problemklassen sind auch noch offen und es ist nicht bekannt, ob das Problem effizient lösbar ist.

Effizient zu lösen sind im allgemeinen die spezielleren Planungsprobleme, während ab ei- nem bestimmten Grad von Allgemeinheit der Problemstellung das Problem NP-hart wird. So ist das Problem O2||Cmax in linearer Zeit lösbar [Gonzales et al. 76], doch wenn man beliebi- ge Auftrags-Ankunftszeiten zuläßt (O2|ri|Cmax), entsteht ein NP-hartes Problem [Lawler 81]. Wenn die Bearbeitungszeit aller Operationenen gleich ist, liegt das Problem wieder in P , selbst mit beliebiger Prozessorzahl und mit beliebigen Ankunftszeiten (O|pij = 1, ri|Cmax ∈ P [Horn 74].

Mit steigender Prozessorzahl werden Planungsprobleme ebenfalls schwieriger: Das schon er- wähnte Problem O2||Cmax ∈ P ist bei 3 Prozessoren (O3||Cmax) NP-hart [Gonzales et al. 76]. Beim Job-Shop-Modell ist bereits der überwiegende Teil der Probleme mit fester Prozessor- zahl NP-hart. So sind J 3|n = 3| ∑Ci und J3|n = 3|Cmax NP-hart [Sotskov 95], ebenso wie J 2|pij = 1| ∑Ti [Lenstra 79]. Bei in der Praxis auftretenden Typen von Job-Shop-Problemen ist es nach dem heutigen Stand bereits bei Problemgrößen, die 20 Aufträge und 10 Maschi- nen übersteigen, praktisch nicht mehr möglich, eine optimale Lösung zu finden [Jain 98]. Eine ÜbersichtderKomplexitätsklassen findet sich unter [Univ. Osnabrück 02].

Der Augenmerk gilt daher seit längerer Zeit Approximationsalgorithmen, unter denen sich Tabusuche, Engpaßverschiebung (Shifting Bottleneck Procedure), Lokale Genetische Suche und Simulated Annealing sowie Kombinationen dieser Methoden als die erfolgreichsten erwiesen haben [Jain 98].

3.3 Mehrere Prozessoren pro Operation

Wir wollen nun das Modell dahingehend erweitern, daß zur Bearbeitung einer Operation mehrere Prozessoren gleichzeitig benötigt werden können. Dabei beziehen wir uns im Wesentlichen auf [Brucker 95], Kap. 10. Dieses Modell ist nicht mit parallelen Systemen zu verwechseln, bei denen parallelisierbare Operationen (engl. divisible tasks) auf mehrere Prozessoren aufgeteilt werden können ([Blazewicz 96], Kap. 6).

Bei unserem Modell geht es vielmehr darum, daß jeder Operation Oij eines Auftrags Ai eine Menge µij ⊆ P zugeordnet ist. Während der gesamten Ausführung der Operation werden alle Prozessoren aus µij für die Operation benötigt.

[...]

---

¹ http://www.gemedical.de/

² http://www.hl7.org/

³ http://otn.oracle.com/products/forms/content.html

⁴ Zum Zeitpunkt der Drucklegung wurde die Version 4.5 verwendet; es wird im Folgenden, soweit nicht anders angegeben, auf diese Version Bezug genommen

⁵ http://java.sun.com/