The minimum dummy task problem. (English) Zbl 0644.90054

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.


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
Full Text: DOI


[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)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.