因應物聯網、機器人和雲端計算等系統快速的科技創新，我們需要更有效之方法來模型化由上述系統所架構出來愈趨複雜的動態資源配置系統，以解決類似瓶頸、死結等潛藏的系統控制相關問題。為了解決以派翠網路模型化大型系統一直存在的指數倍數成長之複雜性問題，一個即使運用MIP（混合整數規劃）方法於可達性分析也是完全NP（非確定性多項式時間）的問題，趙玉教授率先以開發k階和k網系統的控制相關狀態(CRSs)數量之封閉形式解決方案(簡稱封閉解)，來突破此一指數倍數成長複雜性的障礙。然而，對稱網路結構的屬性，限縮了此兩系統在模型化系統中可應用的範圍;同時由於不可避免的死結的狀況，也阻礙了兩個系統的並行處理能力。為了延伸派翠網路封閉解的研究領域至非對稱系統，及強化對大型即時動態資源分配非對稱系統的模型化能力，本論文擴展派翠網路封閉解的研究領域至所謂的「左邊一般化k階系統」、「左邊一般化k網系統」和「A網系統」等三種不同類型的基本非對稱系統。「左邊一般化k階（相對於k網）系統」是在k階（相對於k網）之控製行程的任意位置，使用一非共享資源的網路模型，為模型化具有客製化製程系統之基本網路架構; 「A網系統」是在一k階系統中，連接一頂層非共享圈子網（TNCS）的網路模型，在實際應用中，為模型化具共享相同製程系統的基本網路架構。本論文透過非共用資源在等價網路(k階（相對於k網）)的影響性分析，及其等價網路之封閉解為基礎，建構「左邊一般化k階（相對於k網）系統」之封閉解;在「A網系統」中，由於TNCS和連接的缺陷 k階系統兩個子系統的獨立性，首先我們可以從其相關之k階系統的封閉解中，排除不可能狀態的數量，推導出缺陷k階系統的封閉解，然後以累計加總缺陷k階系統及TNCS兩個子系統在各種TNCS中存在不同權杖個數狀況下的封閉解乘積，構建出「A網系統」的封閉解。在實際應用中，我們可透過由封閉解所產生之即時CRS信息，強化對大型動態即時資源分配系統的模型化能力。例如，採用本論文所提出的避免死結演算法，可以在不用附加控制器之狀況下，實現k階和k網系統之並行處理的功能;並且可以在k-網系統中，在不用暫停所有系統的工作流程狀況下，實現動態行程配置的功能。除了應用虹吸計算方法構建非對稱系統的基礎封閉解外，本論文還提出了依據其反向網路被驗證的有效信息為基準，新的由模型驗證之以知識基礎的理論分析方法，加速派翠網路封閉解的建構。在此，本論文開啟了以變型k階系統為啟端，建構派翠網路封閉解新的研究時代。 / In the light of the rapid innovation of the Internet of Things (IoT), robot systems, and cloud computing systems, we need an efficient methodology to model gradually more and more complicated, real-time resource allocation systems (RAS), constructed using the systems mentioned above, for solving issues such as bottlenecks, deadlocks, and other embedded system-control-related problems. To solve the exponentially increasing complexity in the persistent problem of modeling large systems using Petri nets, which is an NP (nondeterministic polynomial time)-complete problem even when MIP (mixed integer programming) is employed for reachability analysis, Chao broke this barrier by developing the first closed-form solution (CFS) for the number of Control Related States (CRSs) for k-th order and k-net systems. However, the properties of symmetric net structures limit their application range in modeling systems; the inevitable deadlock obstructs the capability of concurrent processing in both systems. To enhance the capability of modeling large dynamic, real-time resource allocation in asymmetric systems, this dissertation extends the research on the CFS of PNs to the so-called Gen-Left k-th order system, the Gen-Left k-net system, and the A-net system, which comprise the three different types of fundamental asymmetric systems. A Gen-Left k-th order (resp. k-net) system is a k-th order (resp. k-net) system containing a non-sharing resource (NSR) at arbitrary locations in the control process, which is the fundamental net structure for modeling contained customized manufacturing processes inside a system. An A-net system is a k-th order system connected to a Top Non-sharing Circle Subnet (TNCS), which is the fundamental net structure to model a shared common manufacturing processing system in real applications. Based upon analyzing the effects of one NSR in the equivalent, the corresponding k-th order (resp. k-net) system, and an equivalent CFS, this dissertation derives the CFS for the Gen-Left k-th order (resp. k-net) system. Due to the independence of the TNCS and the connected Deficient k-th order system, we can first derive the CFS for a Deficient k-th order system just by excluding the number of impossible states from the CFS for its corresponding k-th order system. Then, the CFS of an A-net is constructed by summing the products of the CFS for the two sub-systems in each different case under the condition of the number of tokens inside TNCS. Based on real-time CRS information derived, we can enhance the capability for modeling a large dynamic, real-time resource allocation system in real applications. Employing the proposed deadlock-avoidance algorithm, for instance, we can realize concurrent processing in both k-th order and k-net systems without additional controllers being implemented; and the function of dynamic process allocation in a k-net system without suspending the system’s working flows. In addition to applying siphon computation to construct the fundamental CFS for asymmetric systems, this dissertation pioneers and proposes a new knowledge-based, analysis methodology, called proof by model, to accelerate the construction of the CFS for a PN based upon the validation information from its reverse net. This dissertation opens a new research era for constructing the CFS for PNs beginning from the Variant k-th order system.

Les rapports d’activité de l’Établissement Français du Sang (EFS) font état d’une demande croissante de produits sanguins labiles (PSL) tels les concentrés globules rouges (CGR), les plaquettes, et le plasma. Afin d’assurer la demande vitale en PSL, il est primordial d’optimiser la logistique liée aux activités de collecte du sang et de ses composants. Pour faire face à cette situation, l’EFS Auvergne-Loire mène une réflexion dans le but d’utiliser de manière plus efficiente les dispositifs de collecte en sites fixes et mobiles pour améliorer (i) la qualité de service rendue au donneur, et (ii) l’efficience de l’utilisation des ressources humaines. Dans ce contexte nous avons développé dans cette thèse des outils opérationnels pour (i) la modélisation des dispositifs de collecte, (ii) la régulation des flux de donneurs, et (iii) la planification de collectes mobiles.La méthode d'analyse des dispositifs de collecte est basée sur des techniques de simulation à événements discrets. Une modélisation préalable des flux de donneurs dans les systèmes de collecte en sites fixes et mobiles à l’aide de réseaux de Petri a été proposée. Pour la régulation de flux de donneurs, notamment pour la planification optimale des rendez-vous des donneurs et la planification de la capacité dans les systèmes de collecte au site fixe, deux approches ont été abordées: (a) Construction d'un algorithme basée sur techniques d'optimisation stochastique via simulation ; (b) Programmation mathématique: Modèle de programmation en nombres entiers non-linéaire (MINLP) basée sur réseaux de files d'attente et représentation et évaluation des systèmes à événements discrets à travers de programmation mathématique. Pour la planification de collectes mobiles. Deux types de modèles ont été développés : (a) Au niveau tactique : Modèles de programmation en nombres entiers linéaire (MIP) pour planifier les semaines de collectes pour chaque ensemble disponible sur un horizon de temps pour garantir l'autosuffisance à niveau régional des CGR. (b) Au niveau opérationnel : Modèle de programmation en nombres entiers linéaire (MIP) pour l’organisation du travail des équipes en charge de la collecte. / Activity reports of the French Blood Establishment (EFS) indicate a growing demand for Labile Blood Products (LBP) as red blood cells (RBC), platelets and plasma. To ensure the vital demand of labile blood products (LBP), it’s essential to optimize the logistics related with the collection of blood components. To deal with this situation, the EFS Auvergne-Loire carry out a reflection in order to use more efficiently the collection devices in fixed and mobile sites, to improve the quality of service offered to the donor and the efficiency of human resources. In this context we have developed in this thesis operational tools for (i) modeling of blood collection devices (ii) The regulation of flows donors (iii) Planning of bloodmobile collections.The method analysis of collection devices is based on techniques of discrete event simulation. A preliminary modeling of donors’ flow in fixed and mobile collection systems using Petri nets was conducted. For the regulation of flow of donors, i.e. the optimal capacity planning and appointment scheduling of blood collections, two approaches were considered: (a) Simulation based-optimization.(b) Mathematical Programming: Mixed integer nonlinear programming (MINLP) based on queuing networks and mathematical programming representation of discrete event systems. For planning of bloodmobile collections. Two models have been developed: (a) At the tactical level: Mixed integer linear programming (MIP) to determine the weeks in which the mobile collection must be organized in order to ensure the regional self-sufficiency of RBC. (b) At the operational level: Mixed integer linear programming (MIP) for the planning of human resources in charge of blood collections.

Made available in DSpace on 2016-12-12T17:38:32Z (GMT). No. of bitstreams: 1 Alexandre Pinotti.pdf: 2613359 bytes, checksum: 2102dc273398a9bfa8e51bb28b5fded1 (MD5) Previous issue date: 2012-12-11 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This work presents a method for embedded systems design based on the Supervisory Control Theory for Discrete-Event Systems. The method is composed of steps comprising the specification phase until the approval of the control system. The conception phase is based on the local modular approach for the synthesis of minimally restrictive supervisors that constrains the plant behavior by disabling controllable events and are nonblocking with respect to the set of marked states. The method also includes an implementation architecture for the supervisory control applied to microcontrollers to solve problems such as causality, choice and inexact synchronization. An interface concentrates all controllable and uncontrollable events generation. It deals with the choice problem when reduced supervisors are implemented, randomly choosing one controllable event among the possible ones. This dissertation also presents a tool developed for the automatic code generation of the proposed implementation structure. The main module code is generated to be independent of the number of supervisors and plant models, that is, is the same for any control application. The tool is used to obtain the control applied to a case study and also for the temperature control of a commercial refrigerator. The control system has been validated using the same tools applied for the validation of household appliances at Whirlpool Corporation / Neste trabalho é proposto um método de projeto para sistemas embarcados concebido com base na Teoria de Controle Supervisório de Sistemas a Eventos Discretos. O método é composto por etapas que vão desde a especificação até a aprovação do sistema de controle. A etapa de concepção do método utiliza da abordagem modular local para síntese de supervisores minimamente restritivos que limitam o comportamento da planta através da desabilitação de eventos controláveis e são não bloqueantes em relação ao conjunto de estados marcados. O método ainda inclui uma arquitetura de implementação do controle supervisório direcionada para microcontroladores, visando solucionar os problemas da causalidade, escolha e sincronização inexata. Uma interface é concebida para concentrar a geração de eventos controláveis e não controláveis. Apresenta-se uma solução para o problema da escolha quando são implementados supervisores reduzidos sendo tal escolha realizada de modo online definindo um evento controlável, entre os possíveis, de forma aleatória. Apresenta-se uma ferramenta desenvolvida para a geração de código baseada na estrutura de implementação proposta. O código do módulo principal é gerado de forma a ser independente do número de supervisores e modelos de planta envolvidos, sendo o mesmo para qualquer aplicação de controle. Utiliza-se a ferramenta para obtenção do código da lógica de controle em um estudo de caso e para a regulação de temperatura em um refrigerador comercial. A validação do controle é realizada utilizando-se de ferramentas aplicadas à validação de eletrodomésticos da linha branca na Whirlpool Eletrodomésticos.

Indiana University-Purdue University Indianapolis (IUPUI) / Yan, Jiaxiang. M.S.E.C.E., Purdue University, May 2013. Modeling, Monitoring and Optimization of Discrete Event Systems Using Petri Nets. Major Professor: Lingxi Li. In last decades, the research of discrete event systems (DESs) has attracts more and more attention because of the fast development of intelligent control strategies. Such control measures combine the conventional control strategies with discrete decision-making processes which simulate human decision-making processes. Due to the scale and complexity of common DESs, the dedicated models, monitoring methods and optimal control strategies for them are necessary. Among various DES models, Petri nets are famous for the advantage in dealing with asynchronous processes. They have been widely applied in intelligent transportation systems (ITS) and communication technology in recent years. With encoding of the Petri net state, we can also enable fault detection and identification capability in DESs and mitigate potential human errors. This thesis studies various problems in the context of DESs that can be modeled by Petri nets. In particular, we focus on systematic modeling, asynchronous monitoring and optimal control strategies design of Petri nets. This thesis starts by looking at the systematic modeling of ITS. A microscopic model of signalized intersection and its two-layer timed Petri net representation is proposed in this thesis, where the first layer is the representation of the intersection and the second layer is the representation of the traffic light system. Deterministic and stochastic transitions are both involved in such Petri net representation. The detailed operation process of such Petri net representation is stated. The improvement of such Petri net representation is also provided with comparison to previous models. Then we study the asynchronous monitoring of sensor networks. An event sequence reconstruction algorithm for a given sensor network based on asynchronous observations of its state changes is proposed in this thesis. We assume that the sensor network is modeled as a Petri net and the asynchronous observations are in the form of state (token) changes at different places in the Petri net. More specifically, the observed sequences of state changes are provided by local sensors and are asynchronous, i.e., they only contain partial information about the ordering of the state changes that occur. We propose an approach that is able to partition the given net into several subnets and reconstruct the event sequence for each subnet. Then we develop an algorithm that is able to reconstruct the event sequences for the entire net that are consistent with: 1) the asynchronous observations of state changes; 2) the event sequences of each subnet; and 3) the structure of the given Petri net. We discuss the algorithmic complexity. The final problem studied in this thesis is the optimal design method of Petri net controllers with fault-tolerant ability. In particular, we consider multiple faults detection and identification in Petri nets that have state machine structures (i.e., every transition in the net has only one input place and one output place). We develop the approximation algorithms to design the fault-tolerant Petri net controller which achieves the minimal number of connections with the original controller. A design example for an automated guided vehicle (AGV) system is also provided to illustrate our approaches.