Max-Plus linear system in control of data processing

• Autorzy: Raszka J. , Jamroż L.

Warianty tytułu

PL

Liniowy system max-plus w sterowaniu procesami przetwarzania danych

• Języki publikacji: EN

Abstrakty

EN

The increasing complexity of information processing in distributed computer systems and microprocessors requires the use of time-saving devices and extended capacities of transmission channels. Processes in computers systems need effective processing time. This article describes an application of the theory of the Max Plus Linear System (MPLS) to controlling digital information processing and transmission time in information systems. System processes are described by an MPLS state equation and an MPLS output equation. The MPLS model makes use of formal mathematical methods of max-plus algebra which include maximization and addition operations in the domain of non-negative real numbers with the addition of minus infinity. The input data and the structure of the processes under consideration are represented by the Timed Event Graph (TEG) formalism constituting a special case of Timed Petri Nets. The suggested MPLS methods are useful for investigating selected properties of network models. They may be applied, among others, to evaluate performance criteria, cycle time, predictive control etc. This article presents the theoretical considerations used to determine the input signals controlling discrete processes, which are then illustrated with examples of numerical computations.

PL

Zwiększająca się złożoność procesów przetwarzania informacji w rozproszonych systemach komputerowych i mikroprocesorowych wymaga oszczędnego wykorzystania czasu pracy urządzeń i zwiększonej pojemności kanałów transmisyjnych. Procesy w systemach komputerowych potrzebują efektywnego czasu przetwarzania W niniejszym opracowaniu przedstawiono zastosowanie teorii max-plus liniowego systemu (MPLS) w sterowaniu czasem przetwarzania informacji i czasem transmisji informacji cyfrowej w systemach informatycznych. System procesów opisany jest w przestrzeni MPLS równaniem stanu i równaniem wyjścia. Model MPLS jest oparty na formalnych matematycznych metodach max plus algebry, które są wyposażone w operacje maksymalizacji i dodawania w dziedzinie nieujemnych liczb rzeczywistych rozszerzonych o minus nieskończoność. Dane wejściowe i struktura rozważanych procesów są określone przez formalizm czasowych sieci zdarzeń jako szczególnego przypadku czasowych sieci Petri’ego. Zaproponowane metody MPLS są użyteczne w badania wybranych właściwości sieci. Miedzy innymi mogą być one zastosowane do oceny wydajności, czasu cyklu, sterowania predykcyjnego, itp. W artykule zastosowano teoretyczne rozważania określające wejściowe sygnały sterujące procesem dyskretnym oraz przedstawiono przykładowy wyniki z numerycznych obliczeń.

Słowa kluczowe

EN

max-plus algebra; Petri nets; data processing; discrete processes

PL

max-plus algebra; sieć Petriego; przetwarzanie danych; procesy dyskretne

• Wydawca: Wydawnictwo Politechniki Krakowskiej im. Tadeusza Kościuszki
• Czasopismo: Czasopismo Techniczne. Nauki Podstawowe
• Rocznik: 2014
• Tom: R. 111, z. 2-NP
• Strony: 113--127
• Opis fizyczny: Bibliogr. 15 poz., rys., wz., wykr.

Twórcy

autor

Raszka J.

• Institute of Computer Science, Cracow University of Technology

autor

Jamroż L.

• Institute of Computer Science, Cracow University of Technology

Bibliografia

• [1] Bacceli F., Cohen G., Olsder G., Quadrat J., Synchronization and Linearity. An Algebra for Discrete Event Systems, London, John Wiley & Sons Ltd, 1992.
• [2] Balduzzi F., Giua Has., Menga G., First-order hybrid Petri net: In model for optimisation and control, IEEE Trans. On Rob. And Aut. 1 6 (4), 2000 382—399.
• [3] Cassandras Ch., Lafortune St., Introduction to Discrete Event Systems, Springer, Kluwer Academic Publishers, 2008.
• [4] Elmahi I., Grunder O., Elmoudni A., A max plus algebra approach for modeling and control of lots delivery. Industrial Technology, IEEE ICIT ’04 Vol. 2, 8-10 Dec. 2004, 926—931.
• [5] Goverde Rob M.P., Railway timetable stability analysis using max-plus system theory, Elsevier, Transportation Research Part B 41, 2007, p. 179–201
• [6] Jamroż L., Raszka J., Simulation method for the performance evaluation of system of discrete cyclic processes. 16-th IASTED International Conference on Modelling, Identification and Control, Innsbruck, Austria, 17-19.02.1997, 190—193
• [7] Maia C.A., Andrade C.R., Hardouin L., On the control of max-plus linear system subject to state restriction, Automatica, Volume 47, Issue 5, May 2011, 988—992.
• [8] Murata T., Petri nets: properties, analysis and applications. Proceedings of the IEEE, vol. 77, no. 4, p.541-580, 1989.
• [9] Guţuleac E., Balmuş I. et alt., Descriptive Timed Membrane Petri Nets for Modelling of Parallel Computing, International Journal of Computers, Communications & Control, Vol. I No. 3, 2006, 33—39.
• [10] Nait-Sidi-Moh A., Manier M.-A., El Moudni A., Spectral analysis for performance evaluation in a bus network, European Journal of Operational Research Volume 193: Issue 1, 16 February 2009, 289—302.
• [11] De Schutter B., van den Boom T., Model predictive control for max-plus linear discrete event systems. Automatica 37(7), July 2001, 1049—1056.
• [12] Cordovilla M., Boniol F., et alt., Off-line Optimal Multiprocessor Scheduling of Dependent Periodic Tasks, Journées FAC’2011, Formalisation des Activités Concurrentes, 6 et 7 avril 2011- LAAS – CNRS, 2011.
• [13] Iwaniak M., Khadzhynov W., Usage of Petri nets for distributed transactions modeling Studia Informatica vol. 33, no 105, Silesian University of Technology, 2012.
• [14] Szpyrka M., Sieci Petriego w modelowaniu i analizie systemów współbieżnych, ISBN 9789788304333, WNT Warszawa, 2008.
• [15] Coolahan J.E.jr, Roussopoulos N., Timing Requirements for Time-Driven Systems Using Augmented Petri Nets, IEEE Trans. on Software Eng. v. SE-9, no. 5, 1983, 603—616.