Precedence Constraint Scheduling

Precedence Constraint Scheduling (PCS) zählt zu den Optimierungsproblemen der Informatik. Ziel von PCS ist es, einen optimalen Schedule (d. h. Terminplan) zu erstellen. Einen Schedule kann man sich als Tabelle vorstellen. Der Schedule weist jeder Aufgabe eine Periode zu, in der sie abgearbeitet wird. In jeder Periode können nur begrenzt viele Aufgaben abgearbeitet werden. Außerdem sind die Aufgaben voneinander abhängig, d. h., dass einige Aufgaben erst abgeschlossen werden können, wenn alle ihnen vorliegende Aufgaben abgeschlossen wurden. Ein Schedule ist dann optimal, wenn er nur so viele Perioden benötigt wie unbedingt nötig ist.