Page 127 -

114 M. Wynn et al.
some detail, we use one last example taken from the Order Fulfillment example
described in Appendix A. Figure 3.6 represents the Carrier Appointment process
with an OR-join task, Create Bill of Lading together with its input conditions c1, c3,
and c4 (the task and its input conditions have been shaded grey in the figure). Please
note that there is also another OR-join task in the figure, Complete PickUp/Delivery,
but as it is part of a structured OR-split and OR-join combination, we focus our
attention on a more interesting scenario involving the Create Bill of Lading task.
We know that to invoke the OR-join enabling algorithm, at least one of the input
conditions for Create Bill of Lading task must have one token. Now, we will observe
the results of the algorithm for different markings of the YAWL net.
First, let us assume that we are at a state in the workflow, where the quote for
transportation has been prepared and one token each has been placed in condi-
tions c1 and c2. At marking c1Cc2, the algorithm evaluates to FALSE, indicating
the OR-join task should not be enabled. This is because it is possible to reach a
marking c1 C c4, which marks two input conditions of the OR-join by executing
the Arrange Pickup Appointment task
Similarly, at marking c2Cc3, it is possible to reach marking c3Cc4 in the future
and the algorithm returns FALSE
At marking c1 C c4, the algorithm detects that the only reachable marking from
c1 C c4 is c3 C c4. Therefore, it is not possible to cover the larger marking
c1 C c3 C c4 where all initially marked input conditions (c1; c4) remain marked
and a previously unmarked input condition (c3) becomes marked. Hence, the
algorithm returns TRUE
Similarly, at marking c3 C c4, the algorithm detects that it is not possible to
have any more tokens arriving at c1, so it returns TRUE and the OR-join task is
enabled at this marking

Let us now more closely examine the effect of the two optimization techniques on
the example in Fig. 3.6. Figure 3.7 shows a rough indication of what the application
of structural restriction and active projection would result in for the Carrier Appoint-
ment process when evaluating the Create Bill of Lading task. Please note that the
actual restrictions are applied to the underlying reset net and not to the YAWL net.
For this example, the structural restriction technique removes approximately half of
the tasks under consideration (the bottom half and the left side of Fig. 3.6) as these
tasks are not on the path to the OR-join task in question. This is fairly significant
as the backwards coverability algorithm needs to consider firing all the transitions
in the reset net if there are no restrictions. The active projection technique is then
applied depending on the current marking. The figure shows an active projection
region for the marking c1 C c2. Because of the nature of the AND-split before
conditions c1 and c2, c1 C c2 is the first reachable marking where the OR-join
evaluation will be performed. So, all active projection regions for other markings
will even be smaller than this one. This example clearly demonstrates the efficiency
gained from applying these two restriction techniques. Of course, for other nets
where most tasks are on the path to the OR-join, the structural restriction technique
might not be as effective. Similarly, for nets where there are many reachable states