Premium
Complexity of the minimum‐dummy‐activities problem in a pert network
Author(s) -
Krishnamoorthy M. S.,
Deo N.
Publication year - 1979
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.3230090302
Subject(s) - mathematical optimization , heuristic , computation , mathematics , node (physics) , transformation (genetics) , reduction (mathematics) , relation (database) , time complexity , network planning and design , computer science , algorithm , data mining , computer network , biochemistry , chemistry , geometry , structural engineering , engineering , gene
Abstract Any complex project consists of a number of activities which are carried out in some specified precedence order. One of the factors that is considered is in minimizing the project completior, time. The computation of the optimum project completion time is proportional to the number of edges, including dummy activities. In the past, many algorithms were proposed to yield minimum number of dummy activities required to satisfy the given precedence relation. In this paper we transform the node‐cover problem in graphs of degree at most 3 to the minimum‐dummy‐activities problem. Using this transformation we show that the minimum‐dummy‐activities problem in a PERT network is NP‐complete. The significance of this result is that it is worthwhile in developing a polynomial time heuristic algorithm for solving the dummy activities problem.