The minimum dummy task problem

✍ Scribed by Jeremy Spinrad

• Publisher: John Wiley and Sons
• Year: 1986
• Tongue: English
• Weight: 879 KB
• Volume: 16
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.3230160308

✦ Synopsis

The problem of minimizing the number of dummy tasks in a PERT network was shown to be NP-complete by Krishnamoorthy and Deo [9]. Previous methods of dealing with this problem have imposed extra restrictions on the solution [2,4] or have considered "good" exponential algorithms to solve the problem [l]. Recently, Syslo [13] has characterized the class of graphs that can be solved without using any dummy tasks. This paper takes a different approach to the problem; we propose a very simple heuristic, and find that it solves the problem exactly if the constraint graph does not contain certain forbidden subgraphs. We are able to show that this heuristic solves the problem exactly for several important classes of schedules, including series-parallel partial orders, interval orders, and two-dimensional partial orders.