A new algorithm for preparing PERT networks

Activity on node (AON) and activity on arrow (AOA) network are widely used for planning and scheduling of projects. In the AOA network we have the problem of preparing the network with least number of dummy activities. Krishnamoorty and Deo have shown this problem to be NP-complete. For a given project, if the immediate preceding activities of all activities are given, then a linear time algorithm due to Syslo can be used to check if an AOA network with zero dummy activity can be constructed. Spinrad has given an O(n³) algorithm to prepare the AOA network which requires information about immediate preceding activities of all activities in a network. We present here a new algorithm to prepare the PERT network which runs in O(n² log(n)) steps if the effort to prepare the input is not counted. The complexity of the algorithm presented here is dominated by the O(n³) time required to prepare the immediate preceding activities of all activities in a network, which is an input to our algorithm, see Aho et al.