Approximate algorithm for reducing dummy-activities in a pert network

Abstract

A project is an enterprise consisting of several activities which are to be carried out in some specific order. The activities and the order in which they need to be carried out can be represented by a pert network. Two types of networks are commonly used: activity-On-Node (AON) and Activity-On-Arrow (AOA) networks. When networks are used, it often becomes necessary to draw dummy activities. Since the computation of project completion time is proportional to the number of arcs, including dummy, it is desirable to draw a network with as few dummy activities as possible. It has been earlier shown that the minimum-dummy-activities problem is NP-complete. In this paper we propose an approximate algorithm for solving the dummy activities problem. The algorithm is explained by an example.