Zastosowanie programowania liniowego do badania sieci Petriego

• Autorzy: Dylewski R. , Adamski M. , Jabłoński J.

Warianty tytułu

EN

Application of Linear Programming for Analysis of Petri Net

• Języki publikacji: PL

Abstrakty

PL

W literaturze przedmiotu, proponuje się wykorzystywanie metod algebry liniowej (LA) do badania strukturalnych i dynamicznych własności sieci Petriego, zwracając uwagę na zalety techniki ILP (Integer Linear Programming). Bezkrytyczne stosowanie ogólnych, uniwersalnych procedur matematycznych o stosunkowo dużej sprawności obliczeniowej prowadzi jednak do niepotrzebnego wygenerowania dużej liczby zbytecznych rezultatów. Projektant rekonfigurowalnego sterownika logicznego (RLC) zmuszany jest do pracochłonnej selekcji trudnych do intuicyjnego zinterpretowania wyników analizy, nieprzydatnych w trakcie projektowania matrycowego układu cyfrowego. W artykule dokonano krótkiego, krytycznego przeglądu dotychczas stosowanych metod analizy sieci Petriego z wykorzystaniem technik ILP. Pokazano sposób racjonalnego wykorzystania ILP do wyznaczania i efektywnej selekcji inwariantów bezpiecznej sterującej sieci Petriego, z pominięciem jej znakowań pozornych umiejscowionych wśród potencjalnie osiągalnych stanów globalnych i przemieszanych razem z rzeczywistymi stanami globalnymi.

EN

The paper presents a novel part of well known design methodology for Reconfigurable Logic Controllers implementation, which starts from a suitable cover of the control interpreted Petri net by means of the minimal number of its proper state machine (SM) components. The proposed analysis procedure is based both on Integer Linear Programming (ILP) and structural theory of Petri nets. The number of generated P-invariants, treated as candidates for covering all places of the net, is usually too surplus and contains subsets which do not define State Machine components. Some of P-invariants do not properly define state machine components because they have no intersection or they have more then one intersection with real distributed global states of the control interpreted net. Another well known drawback of the known ILP methods is the generation of several spurious global states of Petri net, whih are mixed in potential reachability graph with real global ststes, taken from dynamic reachability graph. The spurious global states shoud be eliminated during matrix calculations and P-invariants that do not define proper state machine components of the net rejected as soon as possible. The paper proposes a noell ILP-based method for finding a minimal number of P-invariants covering the net. The results of the new method can be used for decomposition of the control interpreted Peri net into linked parallel modules or its local state encoding before its direct structured mapping to Hardware Description Languages.

Słowa kluczowe

PL

sieć Petriego; sterownik rekonfigurowalny; sterownik logiczny; proramowanie liniowe; programowanie całkowitoliczbowe; P-inwariant; elektrotechnika; elektroenergetyka

EN

Peri net; Reconfigurable logic Controllers; Integer Linear Programming; P-invariants; SM-components; electrical technology; electrical power engineering

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2011
• Tom: R. 87, nr 11
• Strony: 159--163
• Opis fizyczny: Bibliogr. 19 poz., il., tabl., wykr.

Twórcy

autor

Dylewski R.

autor

Adamski M.

autor

Jabłoński J.

• Uniwersytet Zielonogórski, ul. Licealna 9, 65-417 Zielona Góra,

Bibliografia

• [1] Petri C. A., Kommunikation mit Automaten, Institut fur Instrumentelle Mathematik, Schriften des IIM, n. 3, (1962)
• [2] Adamski M., Węgrzyn M., Petri nets mapping into reconfigurable logic controllers, Electronics and Telecommunications Quarterly, 55 (2009), n.2,157-182
• [3] Jabłoński J., Zdalnie rekonfigurowalny system rozproszony z FPSLIC, Pomiary, Automatyka, Konlrola, S (2006), 59-61
• [4] Murata T., Petri Nets: Properties, Analysis and Applications, Proceedings of the IEEE. 77 (1989), 541-580
• [5] Silva M., Introducing Petri nets, in Practice of Petri Nets in Manufacturing. London, U.K.: Chapman & Hall, (1993), 1-62
• [6] David R.. Alia H.. Petri Nets and Grafcet. Tools lor modeling discrete event systems. London: Prentice Hall, (1992)
• [7] Datta A., Ghosh S., Synthesis of a Class of Deadlock-Frsee Petri Nets, Journal of the Association for Computing Machinery, 31 (1984), 486-506
• [8] Carmona J., Cortadella J., ILP models for the synthesis of asynchronous control circuits, In Proc. International Conf. Computer-Aided Design (ICCAD), (2003), 818-826
• [9] Carmona J.. Cortadella J., State encoding of large asynchronous controllers, In Proc. ACM/IEEE Des. Autom. Conf., (2006). 939-944
• [10] Carmona J., Cortadella J., Encoding Large Asynchronous Controllers With ILP Techniques, IEEE Trans. on Computer-Aided Design of Integrated- Circuits and-Systems, 27 (2008), 20-33
• [11] Dylewski R., Projection method with residual selection For linear feasibility problems, Discussiones MafbemaUcae. Differential Inclusions, Control and Optimization, 27 (2007), 43-50
• [12] Bilinski K., Adamski M., Saul, J.M.. Dagless E.L, Petri-net-based algorithms for parallel-controller synthesis. Computers and Digital Techniques, IEE Proceedings, 141 (1994), n.6, 405-412
• [13] Vanderbei R. J., Linear Programming, Foundation and Extensions. Boston; Kluver, (1997)
• [14] Walukiewicz S., Programowanie dyskretne, Warszawa: PWN,(1986)
• [15] Karmarkar N., A new polynomial-time algorithm for linear programming, Combinatorics. 4 (1984), 373-395
• [16] Cegielski A., Programowanie liniowe. Zielona Góra: Of. Wyd. Uniwersytetu Zielonogorskiego, (2002)
• [17] Valette R.: Elude comparative de deux outils de representation: Grafcet et reseau de Petri, Le Nouvel Automatisme, (1978)
• [18] Wiśniewska M., Adamski M., Zastosowanie dualizmu hipergrafów w dekompozycji równoległej automatów współbieżnych, Przegląd Telekomunikacyjny i Wiadomości Telekomunikacyine, 6 (2008). 731-733
• [19] Węgrzyn M.. Wolański, P., Adamski M., Monteiro J.L, Coloured Petri net model of application specific logic controller programs, ISIE'97, Proceedings of the IEEE International Symposium on Industrial Electronics, 1(1997), 7-11