Scheduling and Optimization for Resource Management in Novel Applications in Communication and Energy Systems

Abstract

Ressourcen-Management ist der Prozess zur Bestimmung der besten Verwendung von begrenzten Ressourcen. Typischerweise kann nicht der gesamte Bedarf an Ressourcen gedeckt werden und das Bestimmen der effizientesten Verwendung ist herausfordernd. Darüber hinaus sind viele Probleme in diesem Bereich dynamisch. Das bedeutet, dass sich die Verwendung der Resourcen und der Zustand des Systems in der Zeit ändern kann. Das zeitliche Planen der Verwendung von Ressourcen wird in der Literatur als Scheduling bezeichnet. Das Berechnen von Schedules (engl. Ablaufpläne) ist oft schwierig und erfordert eine korrekte Modellierung des zugrundeliegenden Systems.

Das Ziel dieser Arbeit ist die Entwicklung und Evaluation von Planungsalgorithmen für neuartige Anwendungen in den Bereichen Echtzeitkommunikation, Multicast Protokolle, und Energiesysteme. Im Bereich der Energiesysteme stellen wir einen Planungsalgorithmus zur Einsparung von Energiekosten in Produktionsprozessen vor, werten Vorhersagealgorithmen für Energiebedarfe in Wohnhäusern aus, und präsentieren ein Optimierungsverfahren mit dem der Eigenverbrauch von PV Energie durch Wärmepumpen optimiert werden kann. Im Bereich Echtzeitkommunikation wurde der aktuelle Forschungsstand zu Planungsalgorithmen für den sogenannten Time-Aware Shaper (TAS) zusammengefasst. Außerdem stellen wir die Ergebnisse einer quantitativen Vergleichsstudie zu mehreren Planungsalgorithmen für TAS vor. Darüber hinaus präsentieren wir einen Planungsalgorithmus, der robuste Ablaufpläne für den Fall von nicht-de\-ter\-min\-is\-tisch\-em Verhalten berechnen kann. Im Bereich von Multicast Protokollen stellen wir zuerst einen Algorithmus vor, der bnötigt wird, um Bit Indexed Explicit Replication (BIER) für große Netzwerke zu skalieren. Außerdem führen wir Segment-Encoded Explicit Trees (SEET) ein. Dabei handelt es sich um ein neuartiges Protokoll für zustandslose Multicast Kommunikation, das Tree Engineering unterstützt.

Die in dieser Arbeit vorgestellten Forschungsergebnisse wurden im Rahmen verschiedener Forschungsprojekte von der Deutschen Forschungsgemeinschaft (DFG) unter den Förderkennzeichen ME2727/1-2, dem Bundesministerium für Bildung und Forschung (BMBF) unter dem Förderkennzeichen 16KIS1161 (Verbundprojekt KITOS), und dem Bundesministerium für Wirtschaft und Energie unter Förderkennzeichen 16KN039521 (ZIM) gefördert.

Resource management is a generic term for the process of determining the most beneficial way to employ some limited set of resources. Typically, not all demands for a set of resources can be fulfilled and determining their most efficient usage is challenging. To make matters worse, many problems are not static. Instead, the state of a system changes dynamically and depends on the usage of its resources in time. Planning the usage of resources in time is denoted as scheduling in the literature. Computing schedules is hard and requires the accurate modelling of the underlying system.

The objective of this work is the development and evaluation of scheduling algorithms for novel applications in power systems, real-time communication, and multicast protocols. We contribute various research works about scheduling in power systems. We propose a scheduling algorithm to save energy costs in production processes, evaluate forecasting methods for domestic demands, and present an optimization algorithm to maximize self-consumption of roof-top PV energy with a heat pump. In the domain of real-time communication, we review the state of the art of scheduling algorithms for the so-called Time-Aware Shaper (TAS). We report results of a quantitative study comparing various scheduling algorithms for TAS. Additionally, we propose a scheduling algorithm that computes schedules robust against some sources of non-determinism. In the field of multicast protocols, we first contribute a partitioning algorithm needed to scale Bit Indexed Explicit Replication (BIER) to large networks. Then, we present Segment-Encoded Explicit Trees (SEET), a novel multicast protocol that allows tree engineering.

The research presented in this thesis has been funded by different research projects by the Deutsche Forschungsgemeinschaft (DFG) under grant ME2727/1-2, the German Federal Ministry of Education and Research (BMBF) under support code 16KIS1161 (Collaborative Project KITOS), and the German Federal Ministry for Economic Affairs and Energy 16KN039521 (ZIM).