School of Information and Communication Engineering, Hu’nan Institute of Science and Technology, Yueyang 414006, China; Department of Computer Science and Technology, Tongji University, Shanghai 200092, China 在期刊界中查找 在百度中查找 在本站中查找
Department of Computer Science and Technology, Tongji University, Shanghai 200092, China; State Key Laboratory of Software Engineering, Wuhan University, Wuhan 430072, China 在期刊界中查找 在百度中查找 在本站中查找
This paper presents a time Petri net (TPN) model with mixed semantics that efficiently addresses the schedulability analysis problem of the existing semantics models. The proposed model associates each firable transition with a mandatory firing point that is set to the least upper bound of the transition and its non-conflicting transitions. This treatment not only eliminates the effect of conflicting transitions on the transition friability and extends the scheduling scope of the TPN model, but also ensures the time limit of the task scheduling. To determine the expressiveness of the mixed model, the study proves that the mixed semantics model has the power of Turing machines and its marking reachability problem is undecidable. The timed expressiveness of three semantics models with respect to timed language acceptance is also compared. A state class approach is then proposed for the scheduling analysis of the mixed model. Finally, a flexible manufacturing system is used as an example to compare the scheduling ability of three semantics models.
[1] Merlin PM, Farber DJ. Recoverability of communication protocols implications of a theoretical study. IEEE Trans. on Communications, 1976,24(9):1036?1043. [doi: 10.1109/TCOM.1976.1093424]
[2] Berthomieu B, Diaz M. Modeling and verification of time dependent systems using time Petri nets. IEEE Trans. on Software Engineering, 1991,17(3):259?273. [doi: 10.1109/32.75415]
[3] Cerone A, Maggiolo-Schettini A. Time-Based expressivity of time Petri nets for system specification. Theoretical Computer Science, 1999,216(1-2):1?53. [doi: 10.1016/S0304-3975(98)00008-5]
[4] Boyer M, Roux OH. Comparison of the expressiveness of arc, place and transition time Petri nets. In: Proc. of the 28th Int’l Conf. on Application and Theory of Petri Nets and other Models of Concurrency. LNCS 4546, Berlin: Springer-Verlag, 2007. 63?82. [doi: 10.1007/978-3-540-73094-1_7]
[5] Felder M, Mandrioli D, Morzenti A. Proving properties of real-time systems through logical specifications and Petri net models. IEEE Trans. on Software Engineering, 1994,20(2):127?141. [doi: 10.1109/32.265634]
[6] Koutny M. A compositional model of time Petri nets. In: Proc. of the 21st Int’l Conf. on Application and Theory of Petri Nets. LNCS 1825, Berlin: Springer-Verlag, 2000. 303?322. [doi: 10.1007/3-540-44988-4_18]
[7] Esparza J. Decidability and complexity of Petri net problems—An introduction. In: Proc. of the Lectures on Petri Nets I: Basic Models. LNCS 1491, 1998. 374?428. [doi: 10.1007/3-540-65306-6_20]
[8] Berthomieu B, Lime D, Roux OH, Vernadat F. Reachability problems and abstract state spaces for time Petri nets with stopwatches. Discrete Event Dynamic System, 2007,17(2):133?158. [doi: 10.1007/s10626-006-0011-y]
[9] Alain RP, Arnaud S. Weak time Petri nets strike back. In: Proc. of the 20th Int’l Conf. on Concurrency Theory. LNCS 5710, Berlin: Springer-Verlag, 2009. 557?571. [doi: 10.1007/978-3-642-04081-8_37]
[10] Wang JC, Deng Y, Xu G. Reachability analysis of real-time systems using time Petri nets. IEEE Trans. on Systems, Man, and Cybernetics, Part B: Cybernetics, 2000,30(5):725?736. [doi: 10.1109/3477.875448]
[11] Vicario E. Static analysis and dynamic steering of time dependent systems using time Petri nets. IEEE Trans. on Software Engineering, 2001,27(8):728?748. [doi: 10.1109/32.940727]
[12] Peterson JL, Wrote; Wu ZH, Trans. Petri Net Theory and the Modeling of Systems. Xuzhou: China University of Mining and Technology Press, 1989 (in Chinese).