Computer Science ›› 2015, Vol. 42 ›› Issue (1): 12-18.doi: 10.11896/j.issn.1002-137X.2015.01.003

Previous Articles     Next Articles

Schedulability Analysis of Time Petri Net and its Application in FMS

ZHAI Zheng-li and DING Zhi-jun   

  • Online:2018-11-14 Published:2018-11-14

Abstract: In a real-time system,the process of verifying whether a schedule of task execution meets the imposed timing constraints is referred to as scheduling analysis.This paper presented an approach to analyze the scheduling of real time systems modeled in time Petri nets by separating timing properties from other behavioral properties.If a specific task execution is schedulable,we could calculate the time span of the task execution,otherwise pinpointed out non-schedulable transitions to help adjust timing constraints and correct design error.A technique for compositional timing analysis was also proposed to deal with complex task sequences by decomposing it into some simple sub-task sequences,which not only improves efficiency but also facilitates the discussion of reachability issue with regard to scheduling.Finally,sche-duling analysis of an assembly system in flexible manufacturing systems (FMS) was discussed.

Key words: Schedulability analysis,Time Petri nets,Real-time systems,Flexible manufacturing system

[1] Felder M,Mandrioli D,Morzenti A.Proving properties of real-time systems through logical specifications and Petri net models[J].IEEE Transactions on Software Engineering,1994,20(2):127-141
[2] Haban D,Shin K G.Application of real-time monitoring toscheduling tasks with random execution times[J].IEEE Tran-sactions on Software Engineering,1990,16(12):1374-1389
[3] Tsai J J P,Jennhwa Yang S,Chang Y H.Timing constraint Petri nets and their application to schedulability analysis of real-time system specifications[J].IEEE Transactions on Software Engineering,1995,21(1):32-49
[4] Merlin P M,Farber D J.Recoverability of communication protocols --implications of a theoretical study[J].IEEE Transaction on Communications,1976,24(9):1036-1049
[5] Wang Jia-cun,Deng Yi,Xu Gang.Reachability analysis of real-time systems using time Petri nets[J].IEEE Transactions on Systems,Man,and Cybernetics,Part B:Cybernetics,2000,30(5):725-736
[6] Berthomieu B,Lime D,Roux O H,et al.Reachability problems and abstract state spaces for time Petri nets with stopwatches[J].Discrete Event Dynamic Systems,2007,17(2):133-158
[7] Stoyenko A D,Hamacher C,Holt R C.Analyzing hard-real-time programs for guaranteed schedulability[J].IEEE Transaction on Software Engineering,1991,17(8):737-750
[8] Jahanian F,Mok A K-L.Safety analysis of timing properties in real-time systems[J].IEEE Transaction on Software Enginee-ring,1986,12(12):890-904
[9] Berthomieu B,Diaz M.Modeling and verification of time depen-dent systems using time Petri nets[J].IEEE Transaction on Software Engineering,1991,17(3):259-273
[10] Bucci G,Vicario E.Compositional validation of time-critical systems using communicating time Petri nets[J].IEEE Transaction on Software Engineering,1995,21(12):969-992
[11] Furfaro A,Nigro L.Modelling and schedulability analysis of real-time sequence patterns using time Petri nets and Uppaal[C]∥Proceedings of 2007 International Workshop on Real Time Software.2007,16:821-835
[12] http://www.uppaal.org/
[13] Gu Z,Shin K G.Analysis of event-driven real-time systems with time Petri nets:a translation-based approach[C]∥Design and Analysis of Distributed Embedded Systems DAPES ’02 .2002:31-40
[14] 蒋昌俊.Petri网的行为理论及其应用[M].北京:高等教育出版社,2003
[15] 袁崇义.Petri网原理及应用[M].北京:电子工业出版社,2005
[16] 吴哲辉.Petri网导论[M].北京:机械工业出版社,2006
[17] Popova-Zeugmann L.On time Petri nets[J].Elektronische In-formationsverarbeitung und Kybernetik,1991,27(4):227-244
[18] Wang Jia-cun,Deng Yi.Incremental modeling and verification of flexible manufacturing systems[J].Journal of Intelligent Manufacturing,1999,10(6):485-502

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!