<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\begin{slide}{Scheduling-Probleme}

Die Termine für die Vorgänge sind so zu planen, daß sie
\begin{itemize}
\item
  die Abhängigkeiten (siehe Netzplan) erfüllen
\item
  mit vorgegebenen Ressourcen (Mitarbeitern, Maschinen) 
  ausgeführt werden können.
\end{itemize}

Diese Aufgabe erscheint in verschiedensten Varianten
(Stundenpläne, Raumpläne, Fahrpläne, 
Betriebssysteme, Multiprozessor-Systeme \dots).

\end{slide}

\begin{slide}{Komplexität von Scheduling-Problemen}

Mathematisch gehört Ressourcen-Scheduling 
zu Graphentheorie/Optimierung
(siehe auch entsprechende Lehrveranstaltungen)

Die algorithmische Komplexität ist gut untersucht ---
für die meisten interessanten Varianten gilt aber:
\begin{itemize}
\item
  die Aufgabe ist NP-vollständig

  (N: es ist ein Suchproblem, P: der Suchbaum ist polynomial tief,
  d. h. exponentiell breit)

\newpage

\item 
  d. h. es gibt (*) keinen Algorithmus, 
  der in vertretbarer (polynomialer) Zeit eine optimale Lösung findet
\item
  d. h. man muß Näherungs-Algorithmen finden und benutzen
\end{itemize}



Eine Liste von Scheduling-Aufgaben ist:
\url{http://www.nada.kth.se/~viggo/problemlist/compendium.html}

Lese-Übung:
Erklären Sie Unterschiede zwischen 
Open, Flow und Job Shop Scheduling.

\bigskip

(*) sehr wahrscheinlich -- das ist ein ``million dollar problem'',
\url{http://www.claymath.org/millennium/P_vs_NP/}


\end{slide}
</pre></body></html>