Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-3967
Main Title: Modeling and control of complex systems in a dioid framework
Translated Title: Modellierung und Regelung komplexer Systeme in Dioid Strukturen
Author(s): Brunsch, Thomas
Advisor(s): Raisch, Jörg
Hardouin, Laurent
Referee(s): Brock, Oliver
Demongodin, Isabel
Moor, Thomas
Lesage, Jean-Jacques
Raisch, Jörg
Hardouin, Laurent
Granting Institution: Technische Universität Berlin, Fakultät IV - Elektrotechnik und Informatik
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: Viele Systeme in der Produktions- und Fertigungsindustrie können mit Hilfe von Synchronisationsgraphen, einer Klasse von Petri Netzen, modelliert werden. Vorteil solcher Synchronisationsgraphen ist die Möglichkeit, sie als lineares System in Dioidalgebren (auch idempotente Halbringe genannt) abzubilden. Für solche linearen Systeme in Dioidalgebren existiert wiederum eine etablierte Theorie zur Bestimmung von Steuerungen und Regelungen. Es ist allerdings nicht möglich Systeme mit einem verschachtelten Ablaufplan mit Hilfe von Synchronisationsgraphen zu modellieren. Ein verschachtelter Ablaufplan zeichnet sich dadurch aus, dass mehrere Teilprozesse eines Produkts ein und dieselbe Ressource belegen und diese Ressource in der Zwischenzeit Produktionsschritte anderer Teile durchführt. Desweiteren beziehen sich Zeitinformationen in Petri Netzen immer auf die minimale Zeiten, die Marken in einer Stelle bleiben müssen. Häufig werden in Produktionssystemen jedoch Zeitfenster angegeben, wo neben der minimalen Zeit auch eine maximale Zeit festgelegt wird, zu der der Produktionsschritt abgeschlossen sein muss. Solche Zeitfenster können nicht in (standard) Synchronisationsgraphen modelliert werden. Ähnlich verhält es sich mit Kapazitäten von Teilprozessen. Während maximale Kapazitäten relativ einfach durch Marken in Synchronisationsgraphen modelliert werden können, ist es nicht möglich eine Mindestanzahl von Marken in einer Stelle zu garantieren. Eine Erweiterung von Synchronisationsgraphen im Hinblick auf Zeitfenster ist bereits in mehreren Publikationen untersucht worden. Es gibt jedoch noch keine Studien darüber, wie man verschachtelte Ablaufpläne oder Mindestkapazitäten in Fertigungsanlagen bei der Modellierung berücksichtigen kann. In dieser Arbeit stellen wir einen Ansatz vor, mit dem man Prozesse mit verschachtelten Ablaufplänen durch eine Erweiterung von Synchronisationsgraphen modellieren kann. Das Modell eines solchen Prozesses resultiert jedoch in einer akausalen Systembeschreibung in Dioidalgebren. Da die modellierten Systeme jedoch kausal sind, wird der Kausalitätsbegriff näher untersucht und erweitert. Mit Hilfe der Regelungstheorie für lineare Systeme in Dioiden ist es dann möglich, geeignete Regler zu entwerfen. Im zweiten Teil dieser Arbeit untersuchen wir Synchronisationsgraphen mit zusätzlichen Nebenbedingungen wie maximalen Bearbeitungszeiten und Mindestkapazitäten. Durch Nutzung der Residuentheorie ist es möglich, ein lineares Dioidsystem für Synchronisationsgraphen mit Nebenbedingungen zu bestimmen. Schließlich wird ein Algorithmus zum Entwerfen geeigneter Regler vorgestellt. Die Anwendbarkeit unserer Ergebnisse wird anhand realer Systeme aus dem Bereich des Hochdurchsatz-Screenings demonstriert.
Many different kinds of manufacturing systems can be modeled by timed event graphs (TEG), a sub-class of Petri nets. The main advantage of timed event graphs is their linear representation in specific mathematical structures named dioids or idempotent semirings. For linear systems in dioids, in turn, exists an established control theory, which can be used to determine feedback and feedforward controllers. However, if the considered system shall be operated with a re-entrant workflow, resulting in a nested schedule, i.e., a resource may be occupied by the same part more than once and in between these resource allocations another part is processed on this very resource, it is not possible to determine a TEG modeling the system’s behavior. Furthermore, in standard Petri nets, and consequently in standard timed event graphs, timing information is always considered to be the minimal time of a (sub-) process. Nevertheless, often manufacturing systems are operated with time windows, i.e., a minimal time is necessary to complete a (sub-) process but, at the same time, a maximal time is given, at which the (sub-) process needs to be finished. Such time windows cannot easily be included in timed event graphs. Similarly, it is rather straightforward to include maximum capacities of (sub-) processes or resources, but not possible to include minimum capacities in timed event graphs. While the issue of time windows has been addressed in various publications, an extension of timed event graphs to model systems with nested schedules or minimum capacities has not been studied. In this work, we propose an approach to model manufacturing systems with nested schedules. This approach is based on an extension for timed event graphs which, in turn, results in non-causal dioid representations with respect to the standard definition of causality for linear systems in dioids. Consequently, the causality issue for systems with nested schedules is addressed. Eventually, the control theory developed for systems in a dioid framework can be applied to determine suitable controllers. In the second part of this thesis, timed event graphs with constraints are investigated. The constraints include time windows, i.e., minimal and maximal time bounds for some (sub-) processes as well as minimum and maximum capacities. Using results from residuation theory, an algorithm to determine linear systems for extended timed event graphs is developed. Finally, a method is introduced to compute suitable controllers for timed event graphs with the mentioned additional constraints. Using a real world example from high-throughput screening, the applicability of our approach is demonstrated.
De nombreux systèmes, notamment manufacturiers, peuvent être modélisés par des graphes d’événements temporisés, une classe particulière de réseaux de Petri. Un avantage majeur de cette approche est l’existence d’une représentation linéaire dans certains dioïdes (ou semi-anneaux idempotents). Cette caractéristique a permis le développement d’une théorie du contrôle dédiée aux graphes d’événements temporisés. Il n’est cependant pas possible de représenter certains modes de fonctionnement, dits imbriqués, par des graphes d’événemts temporisés. Par imbriqué, nous entendons qu’une ressource effectue plusieurs tâches sur un même produit, mais, qu’entre certaines de ces tâches, elle peut être affectée à la réalisation de tâches sur d’autres produits. De plus, alors qu’il est facile de spécifier dans les graphes d’événements temporisés un temps minimal pour une tâche, il n’est pas possible de définir un temps maximal. Pourtant, dans de nombreuses applications, la durée d’une tâche doit être comprise dans un intervalle. Ce type de spécifications ne peut donc pas être inclus dans les graphes d’événements temporisés classiques. Il en va de même pour le nombre de marques dans une place : le nombre maximal de marques dans une place peut être modélisé, mais pas le nombre minimal de marques. Contrairement au problème relatif au temps maximal pour une tâche, le problème relatif au mode de fonctionnement imbriqué et au nombre minimal de marques dans une place n’a pas encore été traité. Dans ce mémoire, la modélisation de systèmes avec un mode de fonctionnement imbriqué est abordée. Notre approche repose sur la présence dans le modèle d’éléments non causaux selon la définition classique de la causalité pour les systèmes linéaires dans les dioïdes. De fait, le problème de la causalité est traité pour les modes de fonctionnement imbriqués. L’automatique dédiée aux graphes d’événements temporisés est étendue aux systèmes avec un mode de fonctionnement imbriqué. Dans la deuxième partie de ce mémoire, la modélisation de graphes d’événements temporisés avec contraintes (temps mininal et maximal et nombre minimal et maximal de marques pour chaque place) est abordée. En utilisant la théorie de la résiduation, une représentation linéaire est obtenue et une méthode est présentée pour étendre certaines commandes aux graphes d’événements temporisés avec contraintes. Pour finir, l’intérêt de ce travail est illustré au moyen d’un exemple industriellement pertinent : un système de test à haut débit de produits pharmacologiques provenant de notre partenaire industriel.
URI: urn:nbn:de:kobv:83-opus4-47807
http://depositonce.tu-berlin.de/handle/11303/4264
http://dx.doi.org/10.14279/depositonce-3967
Exam Date: 30-Jan-2014
Issue Date: 7-Apr-2014
Date Available: 7-Apr-2014
DDC Class: 500 Naturwissenschaften und Mathematik
600 Technik, Medizin, angewandte Wissenschaften
Subject(s): Idempotente Halbringe
Modellierung
Regelung
ereignisdiskrete Systeme
Fabrikautomatisierung
Dioids
manufacturing
modeling
control
residuation
Usage rights: Terms of German Copyright Law
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 4 Elektrotechnik und Informatik » Institut für Energie- und Automatisierungstechnik » Publications

Files in This Item:
File Description SizeFormat 
brunsch_thomas.pdf1.54 MBAdobe PDFThumbnail
View/Open


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