Discrete event systems (DES) are a special class of dynamical systems with discrete-valued state space and event-driven transitions. DES are ubiquitous in today's world and are used in different sectors such as manufacturing systems, transport networks and computer networks. They offer unique capabilities, such as flexibility and adaptability; at the same time, they can be challenging to model and analyze. Moreover, the complexity of DES is scaled up when disturbances are present. Many different kinds of real life DES can be modeled using dioid algebra which is a powerful tool for describing nonlinear behaviors using linear system models. Dioid algebra is an exotic algebra of formal series which can be understood as a set of only positive numbers without negatives. This special algebraic structure is useful in modeling DES because such systems feature variables that cannot be inverted with respect to some variables. Nonlinear behaviors of DES are able to be modeled as linear systems in terms of dioid algebra in order to use classical control techniques in scheduling and control of DES.This dissertation presents the scheduling and control of DES using a special dioid called max-plus algebra, which is a set of real numbers with the operation of maximum and addition replacing the usual classical operations of addition and multiplication, respectively. This dissertation also studies the behavior of DES when disturbances are present. Two different paths to the scheduling of DES are presented: using dioid algebra and using linear programming methods. The control of DES with disturbances and uncertainties is also explored, particularly, the solutions of the disturbance decoupling problem and the modified disturbance decoupling problem using various controller structures are presented. Disturbance decoupling in this dissertation means the scheduling of the DES will not not be affected by the presence of the disturbances. On the other hand, modified disturbance decoupling means the scheduling will not be worse than the delays caused by the disturbances in industrial just-in-time (JIT) standards. JIT means that the operations start with just enough time to be completed by the desired schedule in order to minimize waste and costs in work in progress and material storage.The applicability of the approach presented in this dissertation is demonstrated in real-world processes including a large-scale high throughput screening (HTS) system in drug discovery and an optimal scheduler for an airport's runways. The main contributions of this dissertation are max-plus and mathematical programming solutions for scheduling and control of discrete event systems with disturbances. The results present a theoretical scheduling prior to exhaustive scheduling algorithms in large-scaled industrial systems.

De nombreux systèmes de transport peuvent être modélisées par des synchronisations ordinaires (pour tout k>=l, l'occurrence k de l'événement B se produit au moins t unités de temps après l'occurrence k-l de l'événement A). Ces systèmes sont linéaires dans l'algèbre (max,+). Pour certaines applications, il est primordial de modéliser la simultanéité entre événements. Comme la synchronisation ordinaire ne suffit pas à exprimer ce phénomène, nous introduisons la synchronisation partielle (l'événement B ne peut se produire que quand l'événement A se produit). Dans ce mémoire, des méthodes développées pour la modélisation et le contrôle de systèmes linéaires dans l'algèbre (max,+) sont étendues à des systèmes régis par des synchronisations ordinaires et partielles. Nous considérons uniquement des systèmes divisés en un système principal et un système secondaire et gouvernés par des synchronisations ordinaires entre événements dans le même système et des synchronisations partielles d'événements dans le système secondaire par des événements dans le système principal. Nous introduisons une commande optimale et une commande prédictive pour cette classe de systèmes par analogie avec les résultats disponibles pour les systèmes linéaires dans l'algèbre (max,+). En considérant un comportement donné pour le système principal, il est aussi possible de représenter le système secondaire par une fonction de transfert et de modifier sa dynamique pour suivre un modèle de référence. / Many transportation networks can be modeled by (max,+)-linear systems, i.e., discrete event systems ruled by standard synchronizations (conditions of the form: "for all k>=l, occurrence k of event B is at least t units of time after occurrence k-l of event A"). In some applications, it is also necessary to model simultaneity between events (e.g., for a road equipped with traffic lights, a vehicle can cross an intersection only when the associated traffic light is green). Such conditions cannot be expressed using standard synchronizations. Hence, we introduce the partial synchronization (condition of the form: "event B can only occur when event A occurs"). In this thesis, we consider a class of discrete event systems ruled by standard and partial synchronizations, called (max,+)-systems with partial synchronization. Such systems are split into a main system and a secondary system such that there exist only standard synchronizations between events in the same system and partial synchronizations of events in the secondary system by events in the main system. We adapt some modeling and control approaches developed for (max,+)-linear systems to (max,+)-systems with partial synchronization. Optimal feedforward control and model predictive control for (max,+)-linear systems are extended to (max,+)-systems with partial synchronization. Furthermore, transfer relation and model reference control are provided for the secondary system under a predefined behavior of the main system.

Orientador: Rafael Santos Mendes / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-10T17:09:25Z (GMT). No. of bitstreams: 1 Cavalcante_MabiaDaniel_D.pdf: 2715835 bytes, checksum: c50d435fedfc8844d3524aff040c39f0 (MD5) Previous issue date: 2008 / Resumo: Network Calculus (NC) é um conjunto de regras e resultados para calcular parâmetros de desempenho de redes de comunicações. As redes de comunicações são exemplos de Sistemas Dinâmicos a Eventos Discretos (DEDS), ou seja, sistemas cujas mudanças de estado são comandadas por eventos que ocorrem em instantes discretos. As restrições matemáticas de alguns DEDS podem ser descritas mais adequadamente usando a álgebra de dióides. Existe, portanto, uma relação entre NC e álgebra de dióides. No entanto, trabalhar em uma plataforma completamente baseada na álgebra de dióides é uma abordagem nova para o NC. Nesse contexto, as contribuições deste trabalho podem ser consideradas sob dois aspectos. Por um lado, no uso sistemático da álgebra de dióides e na definição de métodos, baseados nessa álgebra, para a modelagem e análise de desempenho de redes de comunicações. Por outro lado, nas análises desenvolvidas e resultados alcançados para alguns sistemas específicos. Como uma forma de ilustrar os métodos propostos, analisam-se componentes comuns a modelo~ de redes de comunicações, tais como: enlaces conservativos, reguladores de tráfegos, buffers de recepção e multiplexadores. Alguns resultados alcançados para esses sistemas são inovadores e menos conservativos do ql1e os encontrados na literatura / Abstract: Network Calculus (NC) is a set of rules and results regarding performance parameters of communication networks. Communication networks are examples of Discrete Event Dynamic Systems (DEDS), i.e., systems whose state transitions are triggered by events that occur at discrete instants. The mathematical constraints of some DEDS can be described more adequately using the dioid algebra. Therefore, there is a relationship between NC and the dioid algebra. However, working on a framework completely based on the dioid algebra is a new approach to the NC. ln this context, the contributions of this work can be considered under two aspects. On one hand, in the systematic use of the dioid algebra and the definition of methods based on this algebra to model and analyze performance of communication networks. On the other hand, in the analysis developed and results achieved for some specific systems. To illustrate the introduced methods, some systems that are commonly faund in models af communication networks were analyzed. Among them: conservative links, traffic regulators, receive buffers (or packetizers) and multiplexers. Some of the results obtained for these systems are new and less conservative than those in the literature / Doutorado / Automação / Doutor em Engenharia Elétrica

No description available.