\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 polynomiell tief,
  d. h. exponentiell breit)

\hrule

  NP ist \emph{nicht} die Abkürzung 
  für \glqq nicht polynomiell\grqq, 
  denn die Tiefe der Suchbäume ist eben \emph{doch}
  polynomiell beschränkt!
  (N bedeutet \glqq nicht- de\-ter\-mi\-ni\-stisch\grqq,
  ohne N wäre der Baum ein Pfad)


\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}

\newcommand{\NN}{\mathbb{N}}

\begin{slide}{Open-Shop Scheduling}

als Optimierungsproblem:
\begin{itemize}\itemsep 0pt
\item \emph{Eingabe}:
  Anzahl $m \in \NN$ von Prozessoren, 
  Menge $J$ von Jobs,
  jedes $j \in J$ besteht aus $m$ Operationen $o_{i,j}$,
  für jedes $o_{i,j}$ eine Dauer $l_{i,j}$,
\item \emph{Lösung}:
  ein \emph{Open-Shop-Plan} für $J$, d. h. für jeden Prozessor $i$
  eine Funktion $f_i: J \to\NN$, 
  so daß  $f_i(j)>f_i(j') \Rightarrow f_i(j)\ge f_i(j')+l_{i,j'}$
  und für jedes $j\in J$: die halboffenen Intervalle $[f_i(j),f_i(j)+l_{i,j})$
  sind alle disjunkt.
\item \emph{Kriterium}:
  möglichst geringe Gesamtlaufzeit 
  $\displaystyle\max_{1\le i\le m, j\in J} f_i(j)+l_{i,j}$
\end{itemize}

Als Entscheidungsproblem: 

zusätzliche Eingabe: eine Zahl $T\in\NN$

Frage: gibt es einen Plan mit Gesamtlaufzeit $\le T$?


\end{slide}
