Information Technology Reference
In-Depth Information
Proof: Supposethat thereisafeasiblesolution x .Then, x mustbeasubnet
of N S because N S contains all the data relations in this service portfolio.
Our decomposition algorithm finds all ASWP and conflict-free subnets
of N S by iterating on all possible selection tuples, and we denote the
derived subnets set as
N S Þ
. Because
x
is also ASWP and conflict-free,
x 2 Vð
and that is, if there is a feasible solution, our decomposition
algorithm can find it.
N S Þ
3.4.2 Complexity Analysis
The complexity of each run of the decomposition algorithm equals the
complexity of traversing the reduced service net, that is, O(
)
where V and E are the vertex and edge sets of the reduced service net,
respectively. If RSN contains n OR-split places, each with m branches,
we have m n selection tuples. In the worst case, from each tuple, we
run the decomposition algorithm and obtain one distinctive subnet.
Thus, we can have m n subnets altogether. In the worst case, the
computational complexity is O((
j
V
jþ j
E
j
m n ), that is, O( m n ).
In practice, m and n are usually not large. Moreover, it is observed
that some selection tuples may derive nonfeasible subnets, and
some different tuples derive identical subnets. By detecting these cir-
cumstances, many selection tuples can be simply ignored. One
circumstance is dead path elimination , that is, to detect whether
different selection tuples lead to the same decomposition.
As shown in Figure 3.9a, if h
j
V
jþj
E
j
)
stands for arbitrary
value), when we apply the decomposition algorithm on the net, p c 3 is
removed. We can conclude that once p c 1 selects t 1 , the selection value of
¼ð
t 1 ; ; Þ
(
p c 3 , that is, Q h ð
, does not make a difference in terms of the result.
Thus, many different selection tuples will lead to the same decomposi-
tion result, and by using this fact, we do not have to run the decompo-
sition algorithm for each selection tuple.
The other circumstance is lack-of-synchronization detection , that
is, to detect whether one valuation will derive nonfeasible subnets.
When we run the decomposition algorithm, if
p c 3 Þ
t
t , p is
9
t ,
j
j >
1
^
(
9
p
2
t such that any path from i to p does not
contain any conflict place), then this subnet must be the one with lack-
of-synchronization. At this point, the algorithm can stop and we
conclude that no feasible solution can be derived from this selection
a dead source place)
^
(
9
p
2
tuple. In Figure 3.9b, t d
1, p 1 2 t d and p 1 is a dead source place;
>
Search WWH ::




Custom Search