Das Triangle Scheduling Problem, von Dürr u.a. in [1] vorgestellt, ist ein Spezialfall von Mixed-criticility Scheduling mit Jobs in Form gleichschenkliger Dreiecke. Da es NP-schwer ist, kann der optimale Zeitplan im Allgemeinen nur mittels Brute-Force-Algorithmus gefunden werden, unter der Annahme P≠NP.

Der effiziente gierige Ansatz, jeweils das größte Dreieck in die größte Lücke im Zeitplan zu setzen, kann in vielen Fällen die optimale Lösung ermitteln, wie quantitative Tests mit gleich verteilt zufälligen Jobgrößen zeigen. An den wenigen Beispielen mit nicht optimalem Ergebnis kann man untersuchen, wann der gierige Algorithmus die falsche Entscheidung trifft.

Darüber hinaus kann mit Hilfe dynamischer Programmierung eine (1+ε)-Approximation des optimalen Zeitplans gefunden werden. Indem die Jobgrößen und Startzeiten vorher aufgerundet werden, reduziert sich die Lösung dabei auf die Lösung von O(n^log(n)) vielen Teilproblemen.

In dieser Arbeit entwerfe ich die drei Algorithmen in Pseudocode und implementiere sie in der Programmiersprache Java.

Außerdem ist das Triangle Scheduling Problem geometrisch betrachtet ein Spezialfall des Packungsproblems in einem Rechteck und ich verallgemeinere den Brute-Force-Algorithmus auf andere Figuren wie gleichseitige Dreiecke, Kreise etc.