Parallel Degree of Well-Structured Workflow Nets

Nan QU  Shingo YAMAGUCHI  Qi-Wei GE  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E93-A   No.12   pp.2730-2739
Publication Date: 2010/12/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E93.A.2730
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Theory of Concurrent Systems and its Applications)
WF-nets,  well-structured,  PARAdeg,  heuristic algorithm,  longest path,  nest structure,  

Full Text: PDF(566.3KB)>>
Buy this Article

In this paper, we discuss the parallel degree of well-structured workflow nets, WF-nets, for short. First, we give the definition of parallel degree, PARAdeg, for WF-nets. Second, we show it is intractable to compute the value of PARAdeg for acyclic well-structured WF-nets. Next we construct two heuristic algorithms to compute the value. The first algorithm is focused on nest structure and the second one is focused on the longest path. Finally, we perform an experiment to compare the two algorithms and the result is that the accuracy of the first algorithm based on nest structure was higher than that of the second one based on the longest path for most well-structured WF-nets and the accuracy of the second one is better than that of first one only when the well-structured workflow nets are mainly composed by the parallel structures.