Title Sprječavanje potpunog zastoja u sustavima s diskretnim događajima primjenom Petrijevih mreža
Title (english) Petri nets Based Deadlock Prevention in Discrete Event Systems
Author Danko Kezić
Mentor Nedjeljko Perić (mentor)
Committee member Leo Budin (predsjednik povjerenstva)
Committee member Nedjeljko Perić (član povjerenstva)
Committee member Ante Munitić (član povjerenstva)
Committee member Ivan Petrović (član povjerenstva)
Committee member Stjepan Bogdan (član povjerenstva)
Granter University of Zagreb Faculty of Electrical Engineering and Computing (Department of Control and Computer Engineering) Zagreb
Defense date and country 2003, Croatia
Scientific / art field, discipline and subdiscipline TECHNICAL SCIENCES Electrical Engineering Automation and Robotics
Universal decimal classification (UDC ) 621.3 - Electrical engineering
Abstract U ovom se radu sustavno obrađuje problematika nastanka i sprječavanja potpunog zastoja u sustavima s diskretnim događajima. Potpuni zastoj je stanje sustava iz kojeg nije moguće poduzeti nikakvu akciju. Istražena je metoda projektiranja nadzornika za sprječavanje potpunog zastoja u sustavima automatskog upravljanja modeliranih pomoću općih Petrijevih mreža i Petrijevih mreža s pridruženim simbolima. U radu je dan usporedni prikaz projektiranja nadzornika za sprječavanje potpunog zastoja pomoću teorije automata i Petrijevih mreža. Analizom su ustanovljene prednosti Petrijevih mreža, kao što su manji broj diskretnih stanja modela sustava s diskretnim događajima i jednostavniji način proračuna nadzornika za sprječavanje potpunog zastoja. Predložena je metoda za pojednostavljivanje složene Petrijeve mreže sustava s diskretnim događajima koji se sastoji od neupravljivih i upravljivih prijelaza u jednostavniju Petrijevu mrežu od isključivo upravljivih prijelaza, a koja je pogodna za projektiranje nadzornika za sprječavanje potpunog zastoja. Pojednostavljivanje složene Petrijeve mreže procesa obavlja se metodom sinteze Petrijeve mreže «od dna ka vrhu» koja je kombinirana s metodama redukcije i dekompozicije složene Petrijeve mreže. Nadalje se u radu definiraju uvjeti za postizanje živosti i potpunog zastoja u Petrijevoj mreži. Predložen je algoritam za projektiranje nadzornika za sprječavanje potpunog zastoja. Algoritam kombinira metodu uzastopne kontrole minimalnih sifona koja traži minimalne sifone koristeći matričnu metodu traženja svih sifona Petrijeve mreže te postupno iz skupa pronađenih sifona izbacuje sve one koji nisu minimalni, i metodu analize grafa dostupnih stanja mreže. Rezultat algoritma za sprječavanje potpunog zastoja je skup ograničenja na dostupna stanja mreže i/ili na početna stanja mreže u vidu linearnih nejednadžbi. Ograničenja na dostupna stanja mreže definiraju broj kontrolnih mjesta koji sačinjavaju nadzornik stanja za sprječavanje potpunog zastoja i koji su povezani sa Petrijevom mrežom procesa. Predloženi algoritam omogućava proračun jednostavnijeg nadzornika koji ima manji broj kontrolnih mjesta nego što to omogućavaju dosada objavljeni algoritmi. Verifikacija algoritma pokazana je na dva procesa. Prvi je zamišljeni fleksibilni šaržni proces koji se koristi u farmaceutskoj industriji, a drugi je pomorski prometni sustav. Fleksibilni šaržni proces razmatran u ovom radu se sastoji od više različitih dijeljenih resursa istog tipa, kod kojeg se u slučaju kvara jednog resursa poslovi usmjeravaju na drugi resurs istog tipa. Potpuni zastoj može nastati u slučaju otkaza jednog dijeljenog resursa ukoliko se u postrojenju istovremeno proizvodi više proizvoda različitog tipa. Primjenom nadzornika za sprječavanje potpunog zastoja koji se dobije po metodi predloženoj u ovom radu, omogućava se nastavak istovremene proizvodnje više različitih proizvoda bez potpunog zastoja i u slučaju otkaza pojedinih dijeljenih resursa postrojenja. Drugi sustav je pomorski prometni sustav kanala i bazena u kojem do potpunog zastoja može doći neodgovarajućim zauzimanjem kanala i/ili bazena od strane brodova koji prolaze iz suprotnih smjerova. U radu je prikazana metoda projektiranja nadzornika koji upravlja prometnom signalizacijom sustava kanala i bazena na način da sprječava moguću pojavu potpunog zastoja, a da u isto vrijeme što manje ometa promet brodova.
Abstract (english) This doctoral thesis systematically considers the problem of deadlock occurrence and prevention in the discrete event systems. The deadlock is a state of the system which does not allow any action. The subject of research has been the method of synthesising deadlock prevention supervisory controller in automated systems which are modelled by Generalized Petri nets and Labelled Petri nets. The thesis presents and compares the method of synthesising deadlock prevention supervisory controller by automata and Petri net theories. The analysis shows Petri net advantages i.e. a smaller number of discrete states in the discrete event model and an easier method of calculating deadlock prevention supervisory controller. The thesis proposes the method of simplification from the complex Petri net of discrete event system which consists of controllable and uncontrollable transitions to the simple Petri net which consists solely of controllable transitions, and which is suitable for synthesising deadlock prevention supervisory controller. The simplification of complex process Petri net is done by the bottom-up synthesis method in combination with methods of reduction and the decomposition of complex Petri net. Further, conditions for achieving liveness and a deadlock in the Petri net are being defined. The thesis proposes an algorithm for the design of deadlock prevention supervisory controller. This algorithm combines both the method of iterative minimal siphon control which searches for minimal siphons using the matrix method of searching for all siphons in the net and gradually from the set of all siphons extracts those which are not minimal, and the method of analyzing reachability graph. The result of the deadlock prevention algorithm is the set of constraints on the reachable and initial marking of Petri net by means of linear inequalities. Constrains on the reachable markings determine the number of control places which are included in the state deadlock prevention supervisory controller, and which are connected to the process Petri net. The proposed algorithm enables the calculation of a more simple deadlock prevention supervisory controller that has a fewer control places than the algorithms that have been proposed so far. The verification of algorithms is shown on two processes. The first is a flexible batch process in the pharmaceutical industry and the second is a maritime traffic system. Flexible batch process which is considered in the thesis consists of several different shared resources belonging to the same type in which, in case of resource breakdown, the jobs are allocated to the other resource of the same type. The deadlock situation can occur in case of resource breakdown if several different products are being produced at the same time. By application of deadlock prevention supervisory controller, which can be obtained by the method proposed in the thesis, it is possible to continue production of several different products at the same time without the deadlock, even in the situation of the resource breakdown. Regarding the other process, maritime traffic system, the deadlock situations can occur when channel and pool systems which accommodate vessels sailing in opposite directions are improperly used. The thesis illustrates the formal method for design of the deadlock supervisory controller which controls traffic signalisation in the channel and pool systems in a way to prevent a possible deadlock, and with the least possible disturbance of the on-going traffic.
Keywords
Petrijeve mreže
sustav s diskretnim događajima
sprječavanje potpunog zastoja
izbjegavanje potpunog zastoja
nadzorno upravljanje
fleksibilni šaržni proces
sifoni i zamke
pomorski prometni sustav
Keywords (english)
Petri net
discrete event systems
deadlock prevention
deadlock avoidance
supervisory control systems
flexible batch process
siphons and traps
maritime traffic system
Language croatian
URN:NBN urn:nbn:hr:168:217782
Study programme Title: Doctoral study programme "Electrical Engineering and Computing" Study programme type: university Study level: postgraduate Academic / professional title: doktor/doktorica znanosti, po-dručje tehničkih znanosti (doktor/doktorica znanosti, po-dručje tehničkih znanosti)
Catalog URL https://lib.fer.hr:8443/cgi-bin/koha/catalogue/detail.pl?biblionumber=29231
Type of resource Text
Extent 206 str. ; 30 cm
File origin Born digital
Access conditions Closed access
Terms of use
Created on 2019-09-16 11:45:33