For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Parallel Degree of Well-Structured Workflow Nets
Nan QU Shingo YAMAGUCHI Qi-Wei GE
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2010/12/01
Online ISSN: 1745-1337
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)>>
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.