The minimum dummy task problem. (English) Zbl 0644.90054

Spinrad, Jeremy

Networks 16, No. 3, 331-348 (1986).

Summary: The minimum dummy task problem for PERT networks is NP-complete on arbitrary graphs. This paper presents a very simple heuristic algorithm for the minimum dummy task problem and proves that this algorithm finds an optimal PERT network for various classes of graphs, including interval orders, two-dimensional partial orders, and series-parallel partial orders.

MSC:

90B35	Deterministic scheduling theory in operations research
90C35	Programming involving graphs or networks
65K05	Numerical mathematical programming methods
68Q25	Analysis of algorithms and problem complexity

Keywords:

management of large projects; The minimum dummy task problem; PERT networks; NP-complete; heuristic algorithm; interval orders; series- parallel partial orders

References:

[1]	Corneil, Comm. ACM 16 pp 296– (1973)
[2]	Dimsdale, IBM Systems Journal 2 pp 24– (1963)
[3]	Duschnik, Am. J. Math. 63 pp 600– (1941)
[4]	Fischer, Comm. ACM 11 pp 493– (1968)
[5]	and , Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, San Francisco, 1979. · Zbl 0411.68039
[6]	Ghouila-Houri, CR Acad. Sci. Paris 254 (1962)
[7]	Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980. · Zbl 0541.05054
[8]	and , Operations Research, Holden-Day Inc., San Francisco, 1967.
[9]	Krishnamoorthy, Networks 9 pp 189– (1979)
[10]	Papadimitriou, SIAM J. Comput. 18 pp 405– (1979)
[11]	Two dimensional partial orders. Ph. D. thesis, Princeton University, 1982.
[12]	Single machine scheduling with precedence constraints of dimension 2. McMaster Univ. Faculyty of Business Working Paper Series 188. · Zbl 0541.90054
[13]	Syslo, R. A. I. R. O Recherche operationnelle/Operations Research 15 pp 241– (1981)
[14]	Operations Research, an Introduction, McMillan, New York, 1976, pp. 360–388.
[15]	Valdes, SIAM J. Comput. 11 pp 298– (1982)