Up  Home


Ablaufplanung

AMS Subject Classifications: 90Bxx

Key words: Scheduling, manpower planning, Combinatorial optimization

Das Problem

Gegeben sei eine Menge von Arbeitsaufträgen und bestimmte Ressourcen mit beschränkter Kapazität. Jeder Auftrag besteht aus einer Anzahl von Aktivitäten (auch Operationen oder Task genannt), die evtl. in einer vorgegebenen Reihenfolge abzuarbeiten sind. Dabei bindet jede Operation bei ihrer Ausführung bestimmte Ressourcen. Gesucht ist ein unter betriebswirtschaftlichen Aspekten möglichst optimaler Ablaufplan.

Ausgehend von einem mathematischen Modell kann die Aufgabe als Reihenfolgeproblem formuliert werden. Idealisierte Probleme dieses Typs sind die Job-Shop-Probleme und deren Varianten. Für sie ist bekannt, dass sie NP-vollständig sind. D.h. ein Algorithmus, der eine optimale Lösung liefert muß sich exponentiell verhalten. Man wird demnach nicht eine optimale Lösung suchen, sondern sich darauf beschränken der besten Lösung (wenn es sie denn gibt) so weit wie "möglich'" anzunähern.

 

Ein einfaches Beispiel

Eine Arbeitsgruppe aus 4 Arbeitern soll die drei Arbeitsaufträge

J1={O1, O2, O3, O4}, J2={O5, O6, O7} und J3={O8, O9}

so schnell wie möglich durchführen. Jede einzelne Operation erfordert bestimmte Ressourcen (Arbeiter) und eine bestimmte Durchführungsdauer. Gefordert ist dann die Minimierung der Gesamtbearbeitungszeit für die Arbeitsaufträge, der sogenannte makespan.

j Aktion Durchführungsdauer [min] benötigte Arbeiter
1 O1 20 1
2 O2 40 2
3 O3 10 1
4 O4 80 3
5 O5 30 2
6 O6 20 1
7 O7 15 3
8 O8 60 1
9 O9 90 1

Die Aktivitäten sind nicht unabhängig voneinander ausführbar, sondern es muß eine bestimmte Reihenfolge eingehalten werden, die mittels der sogenannten Vorrangrelation gegeben ist. Der nachfolgende Graph (ein gerichteter azyklischer Graph, DAG)

definiert die Vorrangrelation für dieses Beispiel. So kann z.B. Operation O3 erst gestartet werden, wenn O2 und O5 beendet sind, während O1 und O6 unabhängig voneinander sind.
Das Optimierungsziel wird durch die Endzeiten der Operationen O4, O7 und O4 festgelegt: Ist si die Startzeit der i-ten Operation (O1 startet zum Zeitpunkt s1 usw.), dann gilt makespan = max{s4+80, s7+15, s9+90}.

Auswertung

  Arbeitsgruppe mit 4 Mitgliedern
  makespan [min] Differenz zu S0 [min]
bester Plan S0 170 -
schlechter Plan SB 220 50 (23%)
Erwartungswert 184 14 (7.6%)

 

Gegenüber einem schlechten Plan, dieser sei mit SB bezeichnet, bei dem die Arbeitsgruppe mit 4 Mitgliedern 50 Minuten(!) mehr benötigt, als wenn sie nach S0 vorgeht, ist durch die Optimierung die Leistungsfähigkeit der Gruppe um ca. 23% erhöht worden. Wird aus allen zulässigen Plänen zufällig einer ausgewählt, so ist der Erwartungswert des makespans 184 min. Ein optimaler Plan ist durchschnittlich noch 7.6% besser (siehe: Anmerkung).

Die beiden nächsten Grafiken zeigen die Ressourcenauslastung bzgl. S0 und SB. Man sieht sofort, daß ein Vorgehen nach dem zweiten Plan alles andere als gut ist, was auch an der Einfachheit des Beispiels liegt: die vorgegebene Situation ist noch recht übersichtlich.
Im Fall S0 werden die Arbeitaufträge im Zeitraum von 8:00 bis 10:50 vollständig bearbeitet und alle Mitglieder der Gruppe sind durchgehend gut beschäftigt (insgesamt 55 min "Leerlauf"). Während eine Arbeitorganisation nach SB erst um 11:40 fertig ist und immerhin 255 min "Untätigkeit" für die Arbeitgruppe erzeugt.

 


Die Arbeitsgruppe muß aus mindestens 3 Mitgliedern bestehen, da die Aktivitäten O7 und O4 in diesem Beispiel nur von 3 Mitarbeitern gemeinsam ausgeführt werden können. Wie sehen nun die Ergebnisse für eine Gruppe mit nur 3 Arbeitern aus?

  Arbeitsgruppe mit 3 Mitgliedern
  makespan [min] Differenz zu S0 [min]
bester Plan S0 245 -
schlechter Plan SB 345 100 (29%)
Erwartungswert 284 39 (13.7%)

 

Gantt-Diagramm (Arbeitsgruppe mit 3 Mitgliedern)

Die Arbeitsgruppe mit 3 Mitgliedern benötigt mindestens 245 min zur Bewältigung der Arbeitsaufträge, kann diese aber auch bei schlechter Planung 100 min später abgeschlossen haben, d.h. bzgl. des Optimierungsziels makespan, ist S0 29% besser als SB .


Anmerkung:

Für dieses einfache Beispiel ist es übrigens "schwieriger" die schlechten Pläne zu finden. Wählt man aus den 810 zulässigen Plänen zufällig einen aus, so liegen der Erwartungswert für die Bearbeitungszeit der 3 Jobs näher an der eines optimalen Plans, als an den Zeiten für die "schlechten" Pläne. Aber natürlich ist der durch die Optimierung gefundene Plan S0 einem zufällig ausgewählen Plan überlegen: durchschnittlich hat man eine Effizienzsteigerung um 7.6% bzw. 13.7%.