计算机科学 ›› 2015, Vol. 42 ›› Issue (1): 12-18.doi: 10.11896/j.issn.1002-137X.2015.01.003

• 综述 • 上一篇    下一篇

时间Petri网的可调度分析及在FMS中的应用

翟正利,丁志军   

  1. 青岛理工大学计算机工程学院 青岛266520;同济大学电子与信息工程学院 上海201804,同济大学电子与信息工程学院 上海201804
  • 出版日期:2018-11-14 发布日期:2018-11-14
  • 基金资助:
    本文受国家重点基础研究发展计划(973计划)(2010CB328101),国家自然科学基金(61173042,61173181),上海市自然科学基金(13ZR1443100),山东省优秀中青年科学家科研奖励基金(BS2010DX009),青岛市科技计划项目(12-1-4-4-(7)-JCH)资助

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

摘要: 在实时系统中,检查任务执行的计划是否满足要求的时间约束称为可调度分析。通过把时间特性与其他行为特性分离,提出了一种 以时间Petri网建模的实时系统调度分析方法。如果特定任务的执行是可调度的,则可以计算任务执行的时间跨度,否则确定出不可调度的变迁以便于调整时间约束和纠正设计错误。提出了一种通过把复杂的任务序列分解成一些子序列来进行可调度性分析的综合时序分析技术,它不仅提高了效率,也有助于关于调度的可达性问题的讨论。讨论了柔性制造系统FMS中的车间装配子系统的可调度性。

关键词: 可调度分析,时间Petri网,实时系统,柔性制造系统

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!