DocumentCode
746462
Title
New NP-Complete Problems in Performance Evaluation of Concurrent Systems Using Petri Nets
Author
Magott, Jan
Author_Institution
Institute of Engineering Cybernetics, Technical University of Wroclaw
Issue
5
fYear
1987
fDate
5/1/1987 12:00:00 AM
Firstpage
578
Lastpage
581
Abstract
Timed Petri nets are useful in performance evaluation of concurrent systems. The maximum computation rate is achieved for minimal cycle time of timed Petri net. It is known that minimal cycle time problem for P-invariant Petri nets is NP-complete. In this paper we prove that the minimal cycle time problem, for non-P-invariant Petri nets and for a small subclass of P-invariant Petri nets called free-choice nets having live and safe marking, is NP-complete.
Keywords
Computational complexity; free-choice net; minimal cycle time; non-P-invariant Petri net; performance evaluation; timed Petri net; Cybernetics; Data analysis; Data flow computing; Fires; Petri nets; Random variables; Time factors; Time measurement; Computational complexity; free-choice net; minimal cycle time; non-P-invariant Petri net; performance evaluation; timed Petri net;
fLanguage
English
Journal_Title
Software Engineering, IEEE Transactions on
Publisher
ieee
ISSN
0098-5589
Type
jour
DOI
10.1109/TSE.1987.233462
Filename
1702257
Link To Document