Premium
On the computational complexity of the minimum‐dummy‐activities problem in a pert network
Author(s) -
Syslo Maciej M.
Publication year - 1984
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230140104
Subject(s) - event (particle physics) , computer science , scheduling (production processes) , time complexity , generalization , transitive relation , mathematics , theoretical computer science , mathematical optimization , algorithm , combinatorics , mathematical analysis , physics , quantum mechanics
The scheduling and planning of a project can be represented by two types of networks, namely, by the activity networks and the event networks. For each project, there exists a unique activity network without redundant (transitive) arcs but since there is an infinite number of different‐sized event networks, the problem is to find an event network with the minimum number of dummy activities. Krishnamoorthy and Deo proved that this problem is NP‐complete. In Sections III and IV we characterize those activity networks which have event networks without dummy activities and present a polynomial‐time algorithm which tests if a given activity network requires dummy activities in the event network. The same result is also proved for a generalization of the real‐world problem to arbitrary digraphs. Finally, we present an example which shows that the number of nodes and the number of arcs in event networks cannot be minimized simultaneously.