Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-9526
For citation please use:
Main Title: On the modeling and control of extended timed event graphs in dioids
Translated Title: Modellierung und Regelung von erweiterten Synchronisationsgraphen in Dioiden
Author(s): Trunk, Johannes
Advisor(s): Raisch, Jörg
Cottenceau, Bertrand
Hardouin, Laurent
Referee(s): Raisch, Jörg
Hardouin, Laurent
Moor, Thomas
Gaubert, Stephane
Granting Institution: Technische Universität Berlin
Type: Doctoral Thesis
Language Code: en
Abstract: Various kinds of manufacturing systems can be modeled and analyzed by Timed Event Graphs (TEGs). These TEGs are a particular class of timed Discrete Event Systems (DESs), whose dynamic behavior is characterized only by synchronization and saturation phenomena. A major advantage of TEGs over many other timed DES models is that their earliest behavior can be described by linear equations in some tropical algebra structures called dioids. This has led to a broad theory for linear systems over dioids where many concepts of standard systems theory were introduced for TEGs. For instance, with the (max,+)-algebra linear state-space models for TEGs were established. These linear models provide an elegant way to do performance evaluation for TEGs. Moreover, based on transfer functions in dioids several control problems for TEGs were addressed. However, the properties of TEGs, and thus the systems which can be described by TEGs, are limited. To enrich these properties, two main extensions for TEGs were introduced. First, Weighted Timed Event Graphs (WTEGs) which, in contrast to ordinary TEGs, exhibit event-variant behaviors. In WTEGs integer weights are considered on the arcs whereas TEGs are restricted to unitary weights. For instance, these integer weights make it straightforward to model a cutting process in a production line. Second, a new kind of synchronization called partial synchronization (PS) was introduced for TEGs. PS is useful to model systems where specific events can only occur in a particular time window. For example, consider a crossroad controlled by a traffic light: the green phase of the traffic light provides a time window in which a vehicle is allowed to cross. Clearly, PS leads to time-variant behavior. As a consequence, WTEGs and TEGs under PS are not (max,+)-linear anymore. In this thesis, WTEGs and TEGs under PS are studied in a dioid structure. Based on these dioid models for WTEGs a decomposition of the dynamic behavior into an event-variant and an event-invariant part is proposed. Under some assumptions, it is shown that the event-variant part is "invertible". Hence, based on this model, optimal control and model reference control, which are well known for ordinary TEGs, are generalized to WTEGs. Similarly, a decomposition model is introduced for TEGs under PS in which the dynamic behavior is decomposed into a time-variant and time-invariant part. Again, under some assumptions, it is shown that the time-variant part is invertible. Subsequently, optimal control, as well as model reference control for TEGs under PS is addressed.
Viele Produktions- und Fertigungsanlagen können mit Hilfe von Synchronisationsgraphen modelliert und analysiert werden. Diese Synchronisationsgraphen sind eine spezielle Klasse der zeitbehafteten Ereignisdiskreten Systemen, deren dynamisches Verhalten nur durch Synchronisations- und Sättigungsphänomene gekennzeichnet ist. Ein Vorteil dieser Synchronisationsgraphen gegenüber vielen anderen Modellen besteht darin, dass ihr schnellstes Verhalten durch lineare Gleichungen in einigen „tropischen“ Algebren, den sogenannten Dioiden, beschrieben werden kann. Dies hat zu der Entwicklung einer umfangreichen Theorie für lineare Systeme in Dioiden geführt, wobei viele Konzepte aus der Standard Systemtheorie auf Synchronisationsgraphen übertragen wurden. Zum Beispiel die (max,+) Algebra biete elegante Analyseverfahren und Reglerentwurfsverfahren für Synchronisationsgraphen. Allerdings ist die Systemklasse, die mit Hilfe von Synchronisationsgraphen beschrieben werden kann, eingeschränkt. Zum Beispiel lassen sich Fertigungsanlagen mit Gruppierungs- oder Vereinzelungsschritten nicht mit Synchronisationsgraphen modellieren. Daher wurden einige Erweiterungen für Synchronisationsgraphen eingeführt. Zum einen wurden die Kanten von Synchronisationsgraphen mit ganzzahligen Gewichten erweitert. Diese gewichteten Synchronisationsgraphen weisen im Gegensatz zu gewöhnlichen Synchronisationsgraphen ereignisvariantes Verhalten auf und ermöglichen es nun Gruppierungs oder Vereinzelungsschritte zu beschreiben. Des Weiteren wurde eine neue Art der Synchronisation namens partieller Synchronisation (PS) eingeführt. Diese PS ist nützlich für die Modellierung von zeitvarianten Systemen, bei denen bestimmte Ereignisse nur in einem bestimmten Zeitfenster auftreten können. Ein solches Verhalten tritt zum Beispiel an einer Kreuzung mit Ampelsteuerung auf, die Grünphase der Ampeln beschreibt das Zeitfenster, in dem ein Fahrzeug die Kreuzung überqueren darf. Aufgrund ihres ereignisvarianten bzw. zeitvarianten Verhalten können gewichteten Synchronisationsgraphen sowie Synchronisationsgraphen unter PS nicht mehr mit linearen Gleichungen in der (max,+) Algebra beschrieben werden. In dieser Arbeit werden gewichteten Synchronisationsgraphen und Synchronisationsgraphen unter PS in Dioiden modelliert. Basierend auf dieser Modellierung wird eine Zerlegung des dynamischen Verhaltens von gewichteten Synchronisationsgraphen in einen ereignisvarianten und einen ereignisinvarianten Teil vorgestellt. Analog wird für Synchronisationsgraphen unter PS gezeigt, dass ihr dynamisches Verhalten in einem zeitvarianten und zeitinvarianten Teil zerlegt werden kann. Unter speziellen Voraussetzungen wird gezeigt, dass dieser ereignisvarianten bzw. zeitvarianten Teile „invertierbar“ ist. Dies ermöglicht die Übertragung von etablierten Analyse- und Regelungsentwurfsverfahren von gewöhnlichen Synchronisationsgraphen auf die allgemeineren Klassen der gewichteten Synchronisationsgraphen und Synchronisationsgraphen unter PS.
De nombreux systèmes de production peuvent être modélisés et analysés à l’aide de graphes d’événements temporisés (GET). Les GET forment une classe de systèmes à événements discrets temporisés (SEDT), dont la dynamique est définie uniquement par des phénomènes de synchronisation et de saturation. Un avantage majeur des GET par rapport à d’autres classes de SEDT est qu’ils admettent, sous certaines conditions, un modèle linéaire dans des espaces algébriques particuliers : les dioïdes. Ceci a conduit au développement d’une théorie des systèmes linéaires dans les dioïdes, grâce à laquelle de nombreux concepts de l’automatique classique ont été adaptés aux GET. Par exemple, l’algèbre (max,+) (i.e., le dioïde basé sur les opérations (max,+)) offre des techniques élégantes pour l’analyse et le contrôle de GET. Cependant, les conditions nécessaires pour modéliser un système à événements discrets par un GET sont très restrictives. Pour élargir la classe de systèmes concernés, deux extensions principales ont été développées. D’une part, les GET valués ont été introduits pour décrire des phénomènes d’assemblage et de séparation dans les systèmes de production. Cette extension se traduit par l’association de coefficients entiers aux arrêtes d’un graphe d’événements. Contrairement aux GET, ces systèmes ne sont pas invariants par rapport aux événements et ne peuvent donc pas être décrits par des équations linéaires dans l’algèbre (max,+). D’autre part, la synchronisation partielle (PS) a été introduite pour modéliser des systèmes dans lesquels certains événements ne peuvent se produire que pendant des intervalles prédéfinis. Par exemple, dans une intersection réglée par un feu tricolore, une voiture peut traverser l’intersection lorsque le feu est vert. Contrairement aux GET, ces systèmes ne sont pas invariants dans le domaine temporel et ne peuvent donc pas être décrits par des équations linéaires dans l’algèbre (max,+). Dans cette thèse, une modélisation des GET valués et des GET avec PS dans des dioïdes adaptés est présentée. A l’aide de ces dioïdes, une décompostion pour les GET valués (resp. GET avec PS) en un GET et une partie non-invariante dans le domaine des événements (resp. dans le domaine temporel) est introduite. Sous certaines conditions, la partie invariante est "invertible". Dans ce cas, les modèles et contrôleurs pour le GET valué ou le GET sous PS peuvent être directement dérivés des modèles et contrôleurs obtenus pour le GET associé.
URI: https://depositonce.tu-berlin.de/handle/11303/10600
http://dx.doi.org/10.14279/depositonce-9526
Exam Date: 28-Oct-2019
Issue Date: 2020
Date Available: 27-Jan-2020
DDC Class: 620 Ingenieurwissenschaften und zugeordnete Tätigkeiten
Subject(s): timed event graphs
discrete event systems
synchronization
max-plus algebra
dioid
Synchronisationsgraphen
ereignisdiskrete Systeme
Synchronisation
License: http://rightsstatements.org/vocab/InC/1.0/
Appears in Collections:FG Regelungssysteme » Publications

Files in This Item:
trunk_johannes.pdf
Format: Adobe PDF | Size: 5.54 MB
DownloadShow Preview

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.