Modelling of economic systems with Petri nets
Автор: Skorodumov Pavel Valeryevich
Журнал: Economic and Social Changes: Facts, Trends, Forecast @volnc-esc-en
Рубрика: Modelling and informatics
Статья в выпуске: 4 (34) т.7, 2014 года.
Бесплатный доступ
Modelling is one of the most important tools to study complex systems. Components of both continuous and discrete nature are present in the behavior of contemporary economic systems. The article uses formalism of nested hybrid Petri nets as a tool to study complex economic systems. The author describes basic approaches of simulation modelling, concepts of classical Petri nets, modified means of nested hybrid Petri nets, benefits of their use for systems modelling. The article presents the concept of a universal system of simulation modelling. On the basis of considered approaches the article proposes to develop a universal system of simulation modelling on the basis of the modified machine Petri nets.
Complex system, model, simulation modelling, petri nets, universal system of simulation modelling
Короткий адрес: https://sciup.org/147223626
IDR: 147223626 | DOI: 10.15838/esc/2014.4.34.22
Текст научной статьи Modelling of economic systems with Petri nets
Modern economic systems have both structural and behavioral complexity. The existing concept of a complexity level is determined by the number of points of a particular type, their relationships and interactions, and “relations order” between them [2]. Behavioral complexity can be associated with the system behavior in time and the existence of management processes in economic systems. The system management is considered to be a process stimulating some system to achieve a certain goal [2]. In general, the system behavior is continuous in time, while the control processes are of a discrete nature. The complex system that combines components of continuous and discrete natures is referred to as hybrid.
One way to study the surrounding systems is modelling. Modelling is the process that reflects real (or planned) activities of the enterprise by means of a special methodology [8]. The model represents a real or abstract object, which replaces a research object in the study due to the existing analogy. The most natural and important field to use modelling is the analysis of complex systems, including social engineering (production, financing, etc.) [11].
Nowadays, the most effective method to study economic systems is simulation modelling [4].
There are three main approaches: discrete event simulation, system dynamics and agent based modelling [11].
System dynamics usually operates with continuous-time processes, discrete-event and agent based models are used for discretetime processes.
System dynamics implies a maximum level of model abstraction; discrete-event simulation reflects abstraction of low and intermediate levels. Agent-based modelling can be applied at any level with a model of any size [11].
J. Gordon was the first to study discrete event simulation. In the early 1960’s he designed the GPSS system and implemented it on the IBM mainframe. The main object in this system is a passive transact (service request), which can specifically represent workers, parts, raw materials, documents, signals, etc. Shifting down the model, transacts stand in line for single-channel and multi-channel devices, capture and release them, split and become destroyed, etc. [11].
In 1961 J. Forrester proposed a system dynamics methodology as a research tool to study information feedback loops in production and economic activity. The processes, taking place in the real world, are represented in terms of stocks and flows between them in system dynamics. The system-dynamic model describes system behavior and its structure as a set of positive and negative feedbacks and time delays. Mathematically, this model looks like a system of differential equations [11].
Agent-based simulation involves a decentralized model. In this model, there is no single point, which determines system behavior as a whole. The agent model consists of many individual objects (agents) and their environment. System behavior is described at the individual level; global behavior is seen as the result of the agents’ total activity, each of them exists in a shared environment, interacts with it and other agents due to their own “charter” [11].
If you match an abstract submission system with certain graphics primitives and link them with lines that have certain logic, you get a net, a graphics image of the process. The net methods to describe and analyze the processes are preferential as their abstraction is close to the intuitive idea of the processes [5].
One of the popular graphical tools to study systems is Petri nets (P/T net). They help to describe and analyze the length of performance and interaction of the operations in the processes of various levels in order to identify the bottlenecks of production and economic systems, and to determine the magnitude and potential for cost reduction of human, financial and other resources to perform these processes. The main advantages of using a P/T net in simulation are the following: 1) the process, defined in P/T net terms, has a clear and precise representation; 2) the visible graphics of net construction simplifies perception of its definitions and algorithms; 3) the possibility to use different methods of analysis [7].
At the same time, the P/T net popularity is caused by a good representation of different types of objects, present in many of the simulated systems, and by an “event-driven” approach to modelling. Petri nets describe linkages and interactions of parallel processes [5].
The P/T net is a powerful tool to study systems due to the possibility to describe many classes of discrete asynchronous, parallel, distributed, non-deterministic systems, visualized presentation of its work, developed mathematical and software tools of analysis. It was specifically designed to simulate the systems that contain parallel interacting components, such as hardware and software, flexible production systems, social and biological systems [5].
In general, the Petri net [3] is a directed bipartite graph:
N = (P n ,T n ,F n ) , (1)
where P N is a final set of places,
T N is a final set of transitions, such as that P n П T n = 0 ,
F N is a function of incidence, specifying the multiplicity of arcs,
F n :(P n X T n ) u (T n x P n ) ^ Nat
( Nat is a set of natural numbers, supplemented by zero).
In Petri nets places comply with conditions and transitions – with events. The dynamics of simulated system behavior is reflected in the net functioning as a set of actions, called as transition firings. The transition rules reveal logical relationship between conditions and events in the system being simulated.
The change of the net status is associated with the mechanism of the change of a marking. The initial state of a P/T net is set by the initial marking of its place. The net marking is to assign places to numeric values (tokens). Tokens are a set of attributes (numbers, variables). The condition is represented by marking of the relevant place, namely transition of a number of n-tokens (markers) in this place. The transition can only actuate if all conditions to realize the given event are satisfied. There are special rules or transition procedures for it [3, 6].
The ordinary Petri net, despite the breadth of its use, does not help to study complex systems including both discrete and conti-nuous components. The work [9] offers a tool of nested hybrid Petri nets (NHPN), uniting formalisms of hybrid and nested Petri nets.
The hybrid nested Petri net is defined by means of the following set [10]:
NHPN = {Atom,Lab,SN(HPN),
(EN1, ... , ENk) , Λ}. (2)
Atom = Var и Con is a multiset of atoms, consisting of variables names and constants names;
Lab = Lab v U Lab h is a variety of tokens for both vertical and horizontal transition synchronization;
(EN1, ... , ENk) (k ≥ 1) is a final set of ordinary P/T nets;
Л is a function of marketing transitions by means of elements from the set Lab.
SN(HPN) is a system net in the structure of the NHPN representing a hybrid Petri net (HPN):
HPN = (P, T, Pre, Post, D, C,). (3)
P = P и P is a multiset of discrete and con-dc tinuous places;
T = T d и T c и T K и T E is a multiset of discrete, continuous, transitions of quantization and extrapolation;
Pre , Post are incidence matrices describing the set of arcs;
D : Tt ^ R + is a function determining the delay period for the discrete time transitions;
C:T ^ R + X R + is a function revealing the c 0 ^
bandwidth of continuous transitions.
The interesting question that arises when studying systems using P/T nets is to introduce the concept of time in the system. The concepts of global and local times can be used.
The first one is external time for the system, with which the latter is connected by means of the simulation step concept, thus estimating the temporary status of the system, relative to external systems.
The second one is used to identify the delay of discrete transitions and the bandwidth of continuous transitions of the NHPN. All discrete transitions are divided into instant capture, deterministic time and exponential deterministic. The division is connected with the identification of the delay interval for transition. Continuous transitions are defined by the concept of bandwidth that reflects the speed of the token running through the transition.
Marking assigns the whole number of tokens, consistent with their potential, for each discrete place. For each continuous place it shows where it has a signal or not.
Nested hybrid Petri nets include the concepts of the arc weight and inhibitor arc, characteristic for high-level Petri nets.
The significant addition to the device is the possibility of using fractional and negative values for the weight of the arc running from the transition. When using the negative weight of the arc, we should take into account the potential of the tokens that are in this position. Regardless of the interpretation of marking, the equation for the net dynamics does not change.
The dynamics of the NHPN conduct describes the following types of steps:
-
1. The system-autonomous step is activation of the transition of the net system in accordance with the rules for hybrid Petri nets, with the elementary nets being considered as tokens that do not have their own structure.
-
2. The elementary-autonomous step only changes the internal state (marking) of the elementary net without changing its location in the system net.
-
3. The step of horizontal synchronization is used to synchronize transitions in two elementary nets that are in the same place of the system net.
-
4. The step of vertical synchronization is used to synchronize the transition in the system network with some transitions of elementary nets.
To describe the dynamics of the NHPN conduct we use the following equation:
M, = M + C(p,t)U . (4) k k-1 k
M is a matrix of the net;
Uk – the control vector determines the set of transitions, ready for operation at the moment;
С(p,t) is a NHPN incidence matrix. The incidence matrix element, located at the intersection of the series indicated by the place p i and the column indicated by the transition t j , assigns the value NumM, NumM or 0 when the transition t j has an incoming arc from the place p i , an outgoing arc to the place p i or has no connection with the place p i (where the value NumM is a number of deleted/ added tokens). The value NumM is determined on the basis of types of the place and transition, as well as the weight of the arc connecting them.
The modified tool of nested hybrid Petri nets extends the application of classical Petri nets and existing extensions and helps to explore hybrid systems with a complex structure as a whole.
The representation of individual parts of the system in the form of nested Petri nets helps to simplify the perception of the huge and lengthy P/T net, to make the model of the system more transparent and understandable and simulate multicomponent structures of varying complexity, including systems with the elements of service.
The introduction of new transitions of quantization and extrapolation, the concepts of arc weight, permitting and prohibiting arcs, modified rules of working with them makes the proposed formalism more powerful and expressive means of describing not only hybrid systems, but various mathematical functions and algorithms.
Economic-mathematical models have physical, financial and social factors requiring the use of various tools at the corresponding model level. So, the production-technological model (traditionally viewed as a system of mass service) is well simulated with discrete event tools like GPSS; the financial model fits well into the framework of system dynamics; the agent-based approach can be useful for simulation of labor resources [11].
Today simulation of systems that integrate all notes and high computer technologies is the most promising and rapidly developing sphere where business and corporations can apply simulation modelling [4].
The concept of a universal modelling system gives an opportunity to save time necessary for design and implementation of a simulation model, to make the model more simple and accessible. This reduces the probability of errors in the course of models development due to insufficient knowledge of the language means, negligence in the work with large volumes of information, etc. [1].
The concept of the universal system of simulation modelling is based on the principles of simplicity, modularity and adaptability [1].
The first principle involves the user’s minimum knowledge of the modelling system and, as a result, low labor costs.
The second one involves the existence of model systems that are common for different classes – developed modules.
The third reflects the ability to cover complex unstructured multi-level objects, the elements of which are dynamic systems in a broad sense.
Existing simulation systems can be divided into two groups: systems using classical modelling languages (GPSS, iThink Analyst, Arena) and specialized systems, oriented to solve the tasks of simulation modelling of a particular narrow subject area. The advantages of one group of modelling systems are disadvantages of the other. Creation of the system covering the largest range of real objects, and, first of all, the systems, the product of which is management, is of considerable interest [1].
All the stated above shows that it is worthwhile constructing universal simulation systems on the basis of the modified tool of nested hybrid Petri nets. There are certain advantages of the new system:
-
1. Its implementation on the basis of simulation modelling.
-
2. Integration of all positive features of Petri nets.
-
3. Possibility to develop models on the basis of various extensions of Petri nets.
-
4. Integration of all notes of simulation modelling.
-
5. Its implementation on the basis of the concept of the universal system of simulation modelling.
-
6. Possibility of application in various researches.
Cited works
-
1. Dukhanov A. V., Medvedeva O. N. Simulation Modeling of Complex Systems: a Course of Lectures . Vladimir: VGU, 2010. 118 p.
-
2. Kobelev N. B. Bases for Simulation Modeling of Complex Economic Systems . Moscow: Delo, 2003. 336 p.
-
3. Kotov V. E. Petri Nets. Moscow: Nauka, 1984. 160 p.
-
4. Lychkina N. N. Dynamic Simulation Modeling of Socio-Economic Systems and its Application in Information-Analytical Solutions for Strategic Management . Available at: http://strategybusiness.ru/dinamika-soczialno-ekonomicheskix-sistem/dinamicheskoe-imitaczionnoe-modelirovanie-razvitiya-soczialno-ekonomicheskix-sistem-i-ego-primenenie-v-informaczionno-analiticheskix-resheniyax-dlya-strategicheskogo-upravleniya.html .
-
5. Mal’kov M. V., Malygina S. N. Petri Nets and Modeling . Available at: http://cyberleninka.ru/article/n/seti-petri-i-modelirovanie .
-
6. Peterson J. Petri Net Theory and the Modelling of Systems . Moscow: Mir, 1984. 264 p.
-
7. Poleshchuk N. A. Cost Modelling in Economic Systems Using Petri Nets . Available at: http://www.marketing-mba . ru/article/v4_11/Paliashchuk.pdf.
-
8. Repin V. V., Eliferov V. G. Process Approach to Management. Modeling of Business Processes. Moscow: Mann, Ivanov i Ferber, 2013. 544 p.
-
9. Skorodumov P. V. Modeling of Complex Dynamic Systems on the Basis of Nested Hybrid Petri Nets. Management Systems and Information Technologies: Research and Technology Journal . Moskow; Voronezh: Nauchnaya kniga, 2008, pp. 182-187.
-
10. Skorodumov P. V. Modeling of Technological Processes in Terms of Petri Nets. Scientific Aspects of Innovation Research: Materials of the First International Research-to-Practice Conference . Samara: OOO “Insoma-press”, 2013, pp. 30-34.
-
11. Chernyshova N.N. Simulation Modeling of Business Processes: Study Guide . Nizhnii Novgorod: NGU im. Lobachevskogo, 2010. 28 p.
Список литературы Modelling of economic systems with Petri nets
- Dukhanov A. V., Medvedeva O. N. Imitatsionnoe modelirovanie slozhnykh sistem: kurs lektsii . Vladimir: VGU, 2010. 118 p.
- Kobelev N. B. Osnovy imitatsionnogo modelirovaniya slozhnykh ekonomicheskikh system . Moscow: Delo, 2003. 336 p.
- Kotov V. E. Seti Petri. Moscow: Nauka, 1984. 160 p.
- Lychkina N. N. Dinamicheskoe imitatsionnoe modelirovanie razvitiya sotsial'no-ekonomicheskikh sistem i ego primenenie v informatsionno-analiticheskikh resheniyakh dlya strategicheskogo upravleniya [Dynamic Simulation Modeling of Socio-Economic Systems and its Application in Information-Analytical Solutions for Strategic Management]. Available at: http://strategybusiness.ru/dinamika-soczialno-ekonomicheskix-sistem/dinamicheskoe-imitaczionnoe-modelirovanie-razvitiya-soczialno-ekonomicheskix-sistem-i-ego-primenenie-v-informaczionno-analiticheskix-resheniyax-dlya-strategicheskogo-upravleniya.html.
- Mal'kov M. V., Malygina S. N. Seti Petri i modelirovanie . Available at: http://cyberleninka.ru/article/n/seti-petri-i-modelirovanie.
- Peterson J. Teoriya setei Petri i modelirovanie system . Moscow: Mir, 1984. 264 p.
- Poleshchuk N. A. Modelirovanie zatrat v ekonomicheskikh sistemakh s pomoshch'yu setei Petri . Available at: http://www.marketing-mba.ru/article/v4_11/Paliashchuk.pdf.
- Repin V. V., Eliferov V. G. Protsessnyi podkhod k upravleniyu. Modelirovanie biznes-protsessov . Moscow: Mann, Ivanov i Ferber, 2013. 544 p.
- Skorodumov P. V. Modelirovanie slozhnykh dinamicheskikh sistem na baze vlozhennykh gibridnykh setei Petri . Sistemy upravleniya i informatsionnye tekhnologii: nauchno-tekhnicheskii zhurnal . Moskow; Voronezh: Nauchnaya kniga, 2008, pp. 182-187.
- Skorodumov P. V. Modelirovanie tekhnologicheskikh protsessov v terminakh setei Petri . Nauchnye aspekty innovatsionnykh issledovanii: materialy I Mezhdunar. nauch.-prakt. konf. . Samara: OOO “Insoma-press”, 2013, pp. 30-34.
- Chernyshova N.N. Imitatsionnoe modelirovanie biznes-protsessov: ucheb.-metod. posobie . Nizhnii Novgorod: NGU im. Lobachevskogo, 2010. 28 p.