Scheduling Signaturen

Seit der grossen Untersuchung von Graham, Lawler, Lenstra, und Rinnoy Kan (1979)[32] hat es sich zunehmend eingebürgert, Scheduling-Algorithmen mit einer $\langle \alpha \mid \beta \mid \gamma \rangle$-Signatur zu charakterisieren. Die grobe Bedeutung ist wie folgt:

$\alpha$ - Hardware-Umgebung:

Einprozessor, Multitprozessor, verteilt....

$\beta$ - Taskcharakteristik:

Präemptiv, Ressourcen, abhängig...

$\gamma$ - Optimalitätskriterien:

Minimierung von z.B. Vervollständigungszeit, Restzeit, usw. bzw. Kombinationen von verschiedenen Parametern.

Graham et al (1979) geben als Beispiele:

• $\langle1 \mid prec \mid L_{max} \rangle$ := Minimiere die maximale Restzeit auf einem einzelnen Prozessor bei Annahme von Präzedenzen