Information Technology Reference
In-Depth Information
R
i
represents the reachability relations between any two operations
in
W
i
, and by aggregating them we can examine the reachability
relations among operations in a global, cross-workflow perspective,
that is, in
S
0
.
Given the workflow set
W
¼f
W
1
;
W
2
; ...;
W
n
g
and the operation set
O
¼f
o
1
;
o
2
; ...;
o
m
g
, we now combine
f
R
1
;
R
2
; ...;
R
n
g
into an aggre-
gated relation
R
¼½
r
ij
mm
:
r
ij
¼
P
k
f
, that is,
r
ij
equals the number of workflows in
which
o
i
can reach
o
j
, and
r
ii
¼
R
kij
¼
1
g
0.
We then calculate the
n
th power of
R
:
R
n
r
i
hi
mm
and
r
ij
¼
P
n
r
n
1
ik
r
kj
Therefore,
r
ij
equals the number of times for which
o
i
can reach
o
j
by traversing
n
workflows, that is, transferring
n
¼
k
¼
1
1 times. Now we
know for each given operation pair, the existence of a directed chain
that crosses a certain number of workflows and connects these two
operations.
Step 3: Calculate a Transfer Matrix.
At the beginning of Section 8.3.4, we emphasize that we want a service
chain
crossing the least workflows
, the way passengers want an
itinerary crossing the least routes (i.e., with the least transfers). To
achieve that goal, we need to introduce another transfer matrix
T
.
Given
m
operations and
n
workflows:
T
r
ij
>
¼½
t
ij
mm
:
t
ij
¼f
min
k
2f
1
;
2
; ...;
n
g
s
:
t
:
0
g
if such
k
exists,
and 0 otherwise.
T
reveals the least transfer distance between two given operations.
By definition,
t
ij
1 is the number of transfers through which
o
i
can
reach
o
j
.If
t
ij
¼
0, there is no path between them crossing the available
workflows.
Step 4: Calculate Transfer Paths.
If
t
ij
2, at least
k
- 1 transfer is needed for any path from
o
i
to
o
j
. The least transfer path spans over
k
workflows that can be
denoted
¼
k
f
w
1
;
w
2
; ...;
w
k
g
. Then
this
path
can
be
denoted
w
1
o
q
1
!
w
2
w
k
1
o
q
k
1
!
w
k
o
i
!
!
o
j
in which two adjacent operations