Schedulability Analysis Algorithm of Timing Constraint Petri Nets

Abstract:

A novel approach to the schedulability analysis is presented in this paper for timing constraint Petri nets, which have wide applications in the workflow management, software engineering, reliability engineering, and so on. The analysis can be conducted in two phases: finding firing sequences and timing constraint analysis, among which the first one is to find the transition sequences that transform the initial marking to a certain marking by using incidence matrix in the underlying Petri net, and the second one is to verify whether the reachable marking found in the first step is reachable with the timing constraints. The proposed method is able to pinpoint out non-schedulable transitions and adjust the timing constraints to make all the transitions schedulable within complex task sequences, while meeting the needs of the managers to schedule the tasks.

• Periodical: Advanced Materials Research (Volumes 532-533)
• Pages: 1810-1814
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.532-533.1810
• Online since: June 2012
• Authors: Hui Fang Li, Fu Jian Feng
• Keywords: Reachability, Schedulability, Timing Constraint Petri Nets

References

[1] A.D. Stoyenko, C. Hamacher and R. C. Holt, Analyzing Hard-Real-Time Programs for Guaranteed Schedulability, IEEE Trans. on Software Engineering, 1991, 17(8): 737-750.

DOI: 10.1109/32.83911

[2] Dian-xiang Xu, Xu-dong He and Yi Deng, Compositional shedulability analysis of real-time systems using time Petri nets, IEEE Trans. on Software Engineering, 2002, 29(10): 984-996.

DOI: 10.1109/tse.2002.1041054

[3] Jeffrey J.P. Tsai, Steve Jennhwa Yang and Yap-Hsiung Chang, Timing constraint Petri nets and their applications to schedulability analysis of real-time system specifications, IEEE Trans. on Software Engineering, 1995, 21(1): 32-49.

DOI: 10.1109/32.341845

[4] Wei SONG, Wanchun DOU and Xiping Liu, Timing Constraint Petri Nets and Their Schedulability Analysis and Verification, Journal of Software, 2007, 18(1): 11-21.

DOI: 10.1360/jos180011

[5] Jianqiang Li, Yushun Fan and Mengchu Zhou, Timing constraint workflow nets for workflow analysis, IEEE Trans. on Systems, Man, and Cybernetics, 2003, 33(2): 179-193.

DOI: 10.1109/tsmca.2003.811771

[6] Huifang Li and Yushun Fan, Schedulability Analysis Algorithm for Timing Constraint Workflow Models, Computer Integrated Maufacturing Systems, 2002, 8(7): 527-532.

[7] Erwin R. Boer and Tadao Murata, Generating basis siphons and traps of Petri nets using the sign incidence matrix, IEEE Trans. on Circuits and Systems I: Fundamental Theory and Applications, 1994, 41(4): 266-271.

DOI: 10.1109/81.285680