TY  - THES
AB  - Wir untersuchen drei Scheduling-Problemfamilien auf ihre komplexitätstheoretische Härte und zeigen, welche algorithmischen Ansätze für diese Probleme geeignet sind. Im ersten Modell, das wir neu einführe und Server Cloud Scheduling nennen, werden große Abläufe als Sammlung von Jobs mit Abhängigkeiten gegeben. Die Jobs können auf einem Server ausgeführt werden, der beschränkt, aber kostenlos ist, oder in die Cloud ausgelagert werden, die unendliche Parallelität erlaubt, aber Kosten verursacht. Das Ziel ist die Minimierung der Laufzeit unter Einhaltung eines Budgets oder Minimierung der Kosten unter Einhaltung einer Frist. Unsere Ergebnisse beinhalten unter anderem FPTAS, die auf dynamischer Programmierung basieren, für recht allgemeine Fälle des Modells, und ein starkes NP-härte Ergebnis, das sogar dann gilt, wenn alle Joblängen 1 sind. Zweitens untersuchen wir das Restricted Assignment Interval Problem, bei dem Maschinen in einer bestimmten Reihenfolge gegeben sind und jeder Job nur auf einer konsekutiven Teilmenge der Maschinen ausgeführt werden kann. Ziel ist die Minimierung der Laufzeit. Es ist uns gelungen den ersten Approximationsalgorithmus mit einem konstanten Approximationsfaktor kleiner als 2 für das Problem zu liefern. Der Algorithmus erweitert frühere Ansätze der linearen Programmierung. Zuletzt betrachten wir Many Shared Resources Scheduling. Zusätzlich zu Maschinen und Jobs erhalten wir hier Ressourcen. Jeder Job benötigt eine Ressource, und Jobs, die dieselbe Ressource benötigen, können nicht parallel ausgeführt werden. Ziel ist die Laufzeit zu minimieren. Wir stellen zwei kombinatorische Approximationsalgorithmen vor, eine einfache und elegante 5/3-Approximation und eine technisch aufwendigere 3/2-Approximation. Unser erster Algorithmus schlägt bereits den Stand der Technik.
AU  - Pukrop, Simon
CY  - Paderborn
DA  - 2023
DO  - 10.17619/UNIPB/1-1768
DP  - Universität Paderborn
LA  - eng
N1  - Tag der Verteidigung: 26.06.2023
N1  - Universität Paderborn, Dissertation, 2023
PB  - Veröffentlichungen der Universität
PY  - 2023
SP  - 1 Online-Ressource (103 Seiten)
T2  - Institut für Informatik
TI  - On Cloud Assisted, Restricted, and Resource Constrained Scheduling
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:466:2-45303
Y2  - 2026-01-20T02:20:00
ER  -