Computer Science ›› 2016, Vol. 43 ›› Issue (11): 121-125.doi: 10.11896/j.issn.1002-137X.2016.11.023

Previous Articles     Next Articles

Method for Finding Critical Paths Based on Concurrent Reachable Marking Graph with Tags

HAN Yao-jun   

  • Online:2018-12-01 Published:2018-12-01

Abstract: The color timed Petri net model was gotten by transforming AOE network in this paper.The earliest event start time was calculated while constructing Petri net model.The algorithm of constructing concurrent reachable mar-king graph with tags for color timed Petri net modeling AOE network was given.The critical paths were gotten and the shortest time of completing all activities was calculated from tags of concurrent reachable marking graph.The example and simulation show that the execution efficiency of the algorithm is better than traditional algorithm for finding critical paths when there are more than three concurrent activities in AOE network.The more the concurrent activities are,the higher the efficiency is.

Key words: Color timed Petri net,Concurrent reachable marking graph,AOE network,Critical paths

[1] 严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,2008:183-185
[2] East W.Critical Path Method(CPM) Tutor for Construction Planning and Scheduling [M].McGraw-Hill,2015
[3] He Li-hua,Zhang Lian-ying.An improved fuzzy network critical path method[J].Systems Engineering-Theory & Practice,2014,4(1):190-196(in Chinese) 何立华,张连营.改进的模糊网络关键路径法[J].系统工程理论与实践,2014,34(1):190-196
[4] Cao Han,Liu Da-xin,Fu Rui.Workflow critical path algorithm based on activities[J].Journal of Harbin Engineering University,2006,27(4):551-555(in Chinese) 曹瀚,刘大昕,富锐.基于活动的工作流关键路径算法[J].哈尔滨工程大学学报,2006,7(4):551-555
[5] Hu Mei-qun,Xia Yin-shui,Wang Lun-yao.Critical Path Algorithm Based on Branch-and-bound[J].Journal of Ningbo University(NSEE),2011,24(2):37-41(in Chinese) 胡美群,夏银水,王伦耀.基于分支限界的关键路径求解算法[J].宁波大学学报(理工版),2011,24(2):37-41
[6] Liu Xiao-jing.The improvement and application of the key path algorithm to AOE-net[J].Computer Systems & Applications,2006(9):47-53(in Chinese) 刘小晶.AOE网的关键路径求解算法改进及其应用[J].计算机系统应用,2006(9):47-53
[7] Wu Zhe-hui,Wang Mei-qin.A kind of Peri nets involving time factors and their applications in ngineering[J].Acta Mathematicae Applicatae Sinica,1987,10(3):289-299(in Chinese) 吴哲辉,王美琴.一类含时间因素的Petri网及其在工程上的应用[J].应用数学学报,1987,0(3):289-299
[8] Ye Shuang,Ye Jian-hong,Liu Chuan-cai.Algorithm for finding the Critical Paths Based on Petri Net[J].Computer Science,2012,9(6):201-203(in Chinese) 叶双,叶剑虹,刘传才.基于Petri网的关键路径求解算法[J].计算机科学,2012,9(6):201-203
[9] Zheng Wen-Yan.A New Method for Finding the Critical Paths Based on Colored Petri Nets[J].Computer Systems & Applications,2013,22(8):9-13(in Chinese) 郑文艳.基于CPN的求解关键路径的新方法[J].计算机系统应用,2013,2(8):9-13
[10] 吴哲辉.Petri网导论[M].北京:机械工业出版社,2006
[11] Jensen K.Coloured Petri nets:basic concepts,analysis methods,and practical use[M].Berlin:Springer Verlag,1992
[12] Zuberek W M.Timed Petri nets:definitions,properties and applications[J].Microelectronics and Reliability,1991,1(4):627-644

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!