Performance evaluation of marked graphs by linear programming
Authors:
- 1 September 1991
- journal article
- research article
- Published by Taylor & Francis in International Journal of Systems Science
- Vol. 22 (9) , 1541-1552
Abstract
Performance evaluation is an important issue for discrete event dynamic systems, which in many cases can be described in terms of the language of Petri nets. In particular, for marked graphs, a subclass of Petri nets, a formula for performance evaluation is widely known. That is, the ratio of the total execution time to the number of tokens in a cycle gives a lower bound for the cycle time of the system, and the maximum of these ratios over all cycles determines the overall system performance. However, we need to enumerate all directed cycles in a graph to apply this formula of performance evaluation. Carrying out this enumeration for an actual system is often impractical, since the number of cycles in a graph usually grows exponentially with the size of a system. We give a linear algebraic characterization for directed cycles, and based on this result, transform the problem of performance evaluation into a simple linear programming problem. A few explanatory examples are also given.Keywords
This publication has 5 references indexed in Scilit:
- Performance evaluation of job-shop systems using timed event-graphsIEEE Transactions on Automatic Control, 1989
- A linear-system-theoretic view of discrete-event processes and its use for performance evaluation in manufacturingIEEE Transactions on Automatic Control, 1985
- Performance Evaluation of Asynchronous Concurrent Systems Using Petri NetsIEEE Transactions on Software Engineering, 1980
- Enumeration of the Elementary Circuits of a Directed GraphSIAM Journal on Computing, 1973
- GRAPH THEORY1969