Optimized scheduling in real-time environments with column generation

Im Bereich sicherheitsrelevanter eingebetteter Systeme stellt sich der Designprozess von Anwendungen als sehr komplex dar. Entsprechend einer gegebenen Hardwarearchitektur lassen sich Steuergeräte aufrüsten, um alle bestehenden Prozesse und Signale pünktlich auszuführen. Die zeitlichen Anforderungen sind strikt und müssen in jeder periodischen Wiederkehr der Prozesse erfüllt sein, da die Sicherstellung der parallelen Ausführung von größter Bedeutung ist. Existierende Ansätze können schnell Designalternativen berechnen, aber sie gewährleisten nicht, dass die Kosten für die nötigen Hardwareänderungen minimal sind. Wir stellen einen Ansatz vor, der kostenminimale Lösungen für das Problem berechnet, die alle zeitlichen Bedingungen erfüllen. Unser Algorithmus verwendet Lineare Programmierung mit Spaltengenerierung, eingebettet in eine Baumstruktur, um untere und obere Schranken während des Optimierungsprozesses bereitzustellen. Die komplexen Randbedingungen zur Gewährleistung der periodischen Ausführung verlagern sich durch eine Zerlegung des Hauptproblems in unabhängige Unterprobleme, die als ganzzahlige lineare Programme formuliert sind. Sowohl die Analysen zur Prozessausführung als auch die Methoden zur Signalübertragung werden untersucht und linearisierte Darstellungen angegeben. Des Weiteren präsentieren wir eine neue Formulierung für die Ausführung mit fixierten Prioritäten, die zusätzlich Prozessantwortzeiten im schlimmsten anzunehmenden Fall berechnet, welche für Szenarien nötig sind, in denen zeitliche Bedingungen an Teilmengen von Prozessen und Signalen gegeben sind. Wir weisen die Anwendbarkeit unserer Methoden durch die Analyse von Instanzen nach, welche Prozessstrukturen aus realen Anwendungen enthalten. Unsere Ergebnisse zeigen, dass untere Schranken schnell berechnet werden können, um die Optimalität von heuristischen Lösungen zu beweisen. Wenn wir optimale Lösungen mit Antwortzeiten liefern, stellt sich unsere neue Formulierung in der Laufzeitanalyse vorteilhaft gegenüber anderen Ansätzen dar. Die besten Resultate werden mit einem hybriden Ansatz erzielt, der heuristische Startlösungen, eine Vorverarbeitung und eine heuristische mit einer kurzen nachfolgenden exakten Berechnungsphase verbindet.

The design process of embedded applications in safety-critical systems is very complex. With regard to the distributed hardware architecture, computing units can be upgraded to execute all existing tasks and transmit all arising messages on time. As the timing requirements are strict and have to be fulfilled in every periodic occurrence of the tasks, the guarantee of schedulability is of highest importance. Existing approaches are able to quickly generate possible design alternatives, but they come with no guarantee of minimal cost for the applied hardware modifications. We propose an approach that provides cost-minimal solutions to the distributed scheduling problem while satisfying all timing requirements. Our algorithm uses linear programming with column generation encapsulated in a branch and bound framework to hold lower and upper bounds available during the optimization process. The complex constraints which ensure the periodic schedulability are transferred to independent pricing problems by a decomposition of the master problem and are stated as integer linear programs. Both task schedulability analyses and message transmission policies are examined and linear representations are given. Additionally, we present a new formulation for a fixed priority scheduling policy, which computes worst-case response times for tasks that are necessary for scenarios, where timing restrictions are specified over subsets of tasks and messages. We prove the applicability of our methods by analysing instances with task networks containing data from real-world applications. Our results show that computed lower bounds are quickly available to prove the optimality of heuristic solutions. When providing optimal solutions with worst-case response times, our new formulation turns out to be advantageous over other approaches in terms of running times. The best results are obtained with a hybrid approach combining heuristic start solutions, non-sufficient presolving, and a heuristic phase with a small subsequent exact phase of computation.