Die Ressourceneinsatzplanung basiert auf den in der Losgrößenplanung festgelegten Eckterminen der Aufträge (bezogen auf Endprodukte, Baugruppen oder Einzelteile) sowie auf den Arbeitsplänen der Erzeugnisse. Die Aufgabe der Terminplanung besteht darin, für alle Aufträge, die im aktuellen Planungszeitraum fertiggestellt werden müssen, die Start- und Endtermine ihrer Bearbeitung an den einzelnen Ressourcen zu bestimmen und die Aufträge den Ressourcen zuzuordnen, falls alternative Zuordnungsmöglichkeiten bestehen.

Die Terminplanung ermittelt nun für jeden Arbeitsgang bzw. Auftrag den frühestmöglichen und den spätestzulässigen Start- und Endtermin. Sie bedient sich dabei der Rechenregeln der Netzplantechnik. In der betrieblichen Praxis wird in zwei Schritten vorgegangen. Zunächst werden in der sog. Durchlaufterminierung die Anfangs- und Endtermine der Aufträge ohne Beachtung der Kapazitäten der Ressourcen berechnet. Erst in einem weiteren Schritt werden dann die sich aufgrund der zeitlichen Verteilung der Aufträge ergebenden Kapazitätsbelastungen den vorhandenen Kapazitäten der Ressourcen gegenübergestellt. Treten Überlastungen der Ressourcen auf, dann ist der Terminplan nicht zulässig, denn es muß zwangsläufig zu Überschreitungen der geplanten Fertigstellungstermine einzelner Aufträge kommen. Um dies zu vermeiden, versucht man im Rahmen eines anschließenden Kapazitätsbelastungsausgleichs, vorwiegend durch die zeitliche Verschiebung von Aufträgen einen zulässigen Terminplan zu erzeugen.

Ein einfaches Beispiel soll die Vorgehensweise erläutern. Betrachten wir den folgenden Netzplan:

Jeder Vorgang wird durch einen Knoten mit den Angaben (Vorgangsdauer, Ressourcennummer, Ressourcenbedarf) dargestellt. Die Vorgangsbezeichnungen sind außen neben den Knoten angegeben. Die Kapazität der Ressource beträgt 10. Die Anwendung der MPM-Netzplantechnik ohne Berücksichtigung der Kapazität führt zu folgendem Terminplan und daraus resultierenden Kapazitätsbelastungen:

Es ist deutlich erkennbar, daß dieser Terminplan nicht zulässig ist, da die Kapazität in mehreren Perioden überschritten wird. In der Praxis versucht man in solchen Fällen, durch einen Kapazitätsbelastungsausgleich, bei dem die Arbeitsgänge zeitlich verschoben werden, einen zulässigen Terminplan zu erzeugen. Dies gelingt aber in den meisten Fällen nicht.

Die Grundstruktur der betrachteten Problemstellung kann sehr einfach mit einem Modell der Mehr-Projektplanung bei begrenzt verfügbaren Ressourcen (Resource-Constrained Project Scheduling Problem; RCPSP) abgebildet werden. Eine Version dieses Modells lautet:

$\begin{eqnarray} \mathrm{Minimiere }Z=\sum_{t={FEZ}_J}^{{SEZ}_J} {t\cdot x_{Jt}}} \end{eqnarray}$

unter den Nebenbedingungen

$\begin{eqnarray} \sum_{t={FEZ}_j}^{{SEZ}_j} {x_{jt}}=1 \qquad {j=1,2,...,J} \end{eqnarray}$

$\begin{eqnarray} \sum_{t=FEZ_h}^{SEZ_h} t \cdot x_{ht} \leq \sum_{t=FEZ_j}^{SEZ_j} (t-d_j) \cdot x_{jt} \qquad {j=1,2,...,J;\;h \in V_j} \end{eqnarray}$

$\begin{eqnarray} \sum_{j=1}^J {k_{jr}}\cdot \sum_{q=t}^{t+d_j-1} {x_{jq}} \leq K_r \qquad{r=1,2,...,R;\;j=1,2,...,J;\;t=1,2,...,T} \end{eqnarray}$

$\begin{eqnarray} x_{jt} \in \left\{ {0,1} \right\} \qquad {j=1,2,...,J;\; t=1,2,...,T} \end{eqnarray}$

Es bedeuten:

Die Zielfunktion minimiert den Fertigstellungszeitpunkt des letzten Arbeitsgangs (d.h., die Zykluszeit). Die erste Nebenbedingung verlangt, daß jeder Arbeitsgang beendet und damit natürlich auch durchgeführt werden muß. Die zweite Gruppe von Nebenbedingungen beschreibt die Vorgänger-Nachfolger-Beziehungen zwischen den Produkten. Links steht der Fertigstellungszeitpunkt des Vorgangs $h$; rechts steht der Fertigstellungszeitpunkt des Nachfolgervorgangs $j$. Die nächste Gruppe von Nebenbedingungen garantiert, daß die Kapazitätsbeschränkungen eingehalten werden.

Die Kapazität der Ressource $r$ in Periode $t$ ist $K_r$. Die Beanspruchung der Ressource $r$ durch den Arbeitsgang $j$ pro Periode beträgt -- unabhängig von der Periode, in der der Arbeitsgang die Ressource belegt -- $k_{jr}$. Wir müssen nun einen Weg finden, um einen Zusammenhang zwischen den Variablen des Modells, d.h. der Fertigstellung eines Arbeitsgangs und der aus der Bearbeitung dieses Arbeitsgangs hervorgerufenen Kapazitätsbelastung in den davorliegenden Perioden herzustellen. Dazu überlegen wir uns Folgendes. Wird ein Arbeitsgang in einer Periode $q$ beendet ($x_{jq}=1$), dann muß er genau in den letzten $d_j$ Perioden vor der Periode $q$, also im Zeitabschnitt ($q-d_j+1,...,q-1,q$) bearbeitet worden sein.

Wenn wir jetzt aber eine beliebige Periode $t$ betrachten, dann kann der Arbeitsgang $j$ in dieser Periode $t$ nur dann bearbeitet worden sein, wenn er im Zeitraum mit den Perioden $q=t,t+1,...,t+d_j-1$ beendet wird. Nur in diesen Perioden kommt es zu Ressoucrenbedarf. Für jede Periode $t$ müssen wir damit nur die Fertigstellungstermine des Auftrags $j$ im Bereich von $t$ bis $t+d_j-1$ betrachten. Dies wird durch die Kapazitätsrestriktion wiedergegeben.

Zur Lösung des Modells RCPSP sind in den letzten Jahren zahlreiche Lösungsverfahren entwickelt worden sind. Die Anwendung eines heuristischen Verfahren ergibt z.B. folgenden zulässigen Plan:

Hier kommt es zu keiner Überlastung der Ressourcen.

Literatur