Can every precedence table be represented as an "activity on arc" activity network

202 Views Asked by At

I have the precedence table

Activity | depends on    
A        | -
B        | - 
C        | -
D        | A,B
E        | B,C    
F        | A,C

And I want to write it as an activity on arc network

So far I have:

    1--D--4
   /|
  A ^
 /  |
0-B-2
 \  |
  C v 
   \|
    3--E--5

Where the events are numbered, and the vertical arcs represent dummy activities, directed by the arrows.

I can't see how I can now attach activity F to this network. I can't attach F directly or indirectly to any of the existing events. Is this possible? And in general is there an algorithmic approach to forming the activity on arc network from the precedence table?

1

There are 1 best solutions below

0
On BEST ANSWER

I found a possible solution, with 6 dummies, I'm not certain it is the most efficient solution, but I believe it points to an answer to my questions. Activity network

Based on this it seems likely that any precedence tree can be represented in an activity-on-arc network, if you allow for lots of dummies, simply join each new activity to the tree by dummies, one for each dependency.

It also suggests a possible algorithm for producing such a network could be to build it with lots of dummies, and then manipulate the tree to reduce the number of dummies. It has also given me some insight into what an "Event" is: Each of the unique lists of dependencies in the precedence table is an Event.