Bibliographic Metadata

Heutzutage ist in großen Daten- und Rechenzentren oft nicht mehr die Rechenkapazität der Flaschenhals des Systems, sondern der Speicher oder die verfügbare Datenrate. Scheduling-Algorithmen treffen Entscheidungen, wie Jobs an einzelnen Knoten abgearbeitet werden, aber berücksichtigen meistens keine zusätzlichen Ressourceneinschränkungen in bezüglich des gesamten Rechenzentrums. In dieser Arbeit sollen solche globalen Ressourcen berücksichtigt werden.Es werden vier Modelle entsprechende eingeführt: Die ersten drei Modelle ähneln sich insofern, dass jeweils eine Ressource mit begrenzter Kapazität von mehreren Prozessoren geteilt wird, und das Ziel größtenteils darin besteht, die Gesamtabarbeitungszeit zu minimieren. Im ersten Modell liegt der Fokus auf der Zuordnung der Ressource zu den Prozessoren, während die Jobs zusammen mit ihrer Reihenfolge den Prozessoren bereits zugewiesen sind. Im zweiten Modell werden Kommunikationsanforderungen zwischen Jobs betrachtet, die auf einem gemeinsamen Kommunikationskanal erfüllt werden müssen. Das dritte Modell ist allgemeiner insofern, dass Jobs an Prozessoren verteilt werden müssen, aber auch die Ressource noch zugeteilt werden muss.Das vierte Modell erfasst dagegen mögliche Strategien für hochdynamische Systeme, in denen kontinuierlich veränderliche Beschränkungen eingehalten werden müssen. Genauer wird hier der Energieverbrauch eines einzelnen Prozessors unter dynamischen Geschwindigkeitsschranken und variablen Energiekosten minimiert.

In today's data and computing centers, the available computing power of a system often is sufficient, but memory and the data rate become the bottleneck instead. Scheduling algorithms usually deal with the assignment of jobs to processors, but without any global constraint on the computing center as a whole. In this thesis, new scheduling problems incorporating such global properties are introduced. Four (slightly) different models capturing aspects of these properties are studied.The first three models are similar in that a resource with a limited capacity is shared among multiple processors, and mostly the objective is to minimize the makespan, i.e., the time until all jobs are completed. The focus of the first model is on the assignment of the resource to the processors, where for each processor a queue of jobs is already fixed. The second model focuses on interjob communication, where given communication requirements between jobs need to be scheduled on a common communication channel. Finally, the third model is the most general case, where jobs with a certain resource requirement need to be scheduled on the different processors, but the resource has to be assigned as well.On the other hand, the fourth model captures possible strategies for highly dynamic systems, where constraints may even change continuously over time. Here, the energy consumption of a single processor is minimized while adhering to variable speed limits and incorporating fluctuating energy costs.