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:

• die Aufgabe ist NP-vollständig

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

  NP ist nicht die Abkürzung für ,,nicht polynomiell``, denn die Tiefe der Suchbäume ist eben doch polynomiell beschränkt! (N bedeutet ,,nicht- deterministisch``, ohne N wäre der Baum ein Pfad)

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

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

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

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