2023-06-252023-06-25https://tore.tuhh.de/handle/11420/15842Scheduling- und Planungsprobleme gehören zu den grundlegenden Fragestellungen der Algorithmik. Viele dieser Probleme erlauben höchstwahrscheinlich keine Verfahren, welche garantiert eine optimale Lösung in polynomieller Zeit berechnet. Daher wurden in den letzten Dekaden hunderte Approximationsalgorithmen für diese Probleme entwickelt. In diesem Projekt beschäftigen wir uns mit einem alternativen Lösungsansatz für Schedulingprobleme mit hoher Multiplizität, in denen eine große Menge von Jobs geplant werden müssen welche in wenige Kategorien klassifizierbar sind. Derartige Probleme treten beispielsweise beim Planen von Landesequenzen für Flugzeuge auf, deren Sicherheitsabstände vor allem von ihrer Bauart entsprechend weniger Typen abhängen. Unser Ziel ist die Entwicklung von Fest-Parameter Algorithmen, welche optimale Lösungen liefern in einer Zeit die polynomiell von der Eingabegröße ist und superpolynomiell nur in der kleinen Anzahl der Kategorien. Auf diese Weise verallgemeinern wir polynomielle Algorithmen für Spezialfälle dieser Probleme mit konstant vielen Kategorien auf realistischere Modelle, und verbessern gleichzeitig die Laufzeiten von Fest-Parameter Algorithmen welche bisher eine verschwenderische Auflistung jedes einzelnen Jobs verlangen.Scheduling and planning problems belong to the fundamental questions in algorithms. Many of those problems are highly unlikely to admit procedures that guarantee to deliver an optimal solution in polynomial time. Therefore, hundreds of approximation algorithms have been developed for such problems in the past decades.In this project we deal with an alternative approach for scheduling problems with high multiplicity, in which a large number of jobs must be planned which can be categorized into few categories. Such problems arise in, for instance, sequencing of landing aircraft, whose safety separation distances mainly depend on which of few aircraft type the respective planes belong to. Our goal is the development of fixed-parameter algorithms, which deliver optimal solutions in time that depends polynomially on the input size and superpolynomially only in the small number of categories. This way, we generalize polynomial-time algorithms for special cases of those problems with only constantly many job categories to more realistic models, and simultaneously improve the run times of fixed-parameter algorithms which so far require a lavish encoding of every single job.