COMPLEXITY OF THE MINIMUM-DUMMY-ACTIVITIES PROBLEM IN A PERT NETWORK

被引：26

作者：

KRISHNAMOORTHY, MS

DEO, N

机构：

来源：

NETWORKS | 1979年 / 9卷 / 03期

关键词：

D O I：

10.1002/net.3230090302

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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. Copyright © 1979 Wiley Periodicals, Inc., A Wiley Company

引用

页码：189 / 194

页数：6

共 8 条

[1]

Aho A.V., Hopcroft J.E., Ullman J.D., The design and analysis of computer algorithms, (1974)

[2]

Corneil D.G., Gotlieb C.C., Lee Y.M., Minimal eventnode network of project precedence relations, Comm. ACM, 16, pp. 296-298, (1973)

[3]

Deo N., Graph Theory with Applications to Computer Science and Engineering, (1974)

[4]

Dimsdale D., Computer construction of minimal project network, IBM Systems Journal, 2, pp. 24-36, (1963)

[5]

Fisher A.C., Liebman D.S., Nemhauser G.L., Computer construction of project networks, Communications of the ACM, 11, pp. 493-497, (1968)

[6]

Garey M.R., Johnson D.S., Stockmeyer L., pp. 47-64, (1974)

[7]

Harary F., Graph Theory, (1969)

[8]

Karp R.M., On the computational complexity of combinatorial problems, Networks, 5, pp. 45-68, (1975)

← 1 →