Project scheduling in AND-OR graphs: A generalization of Dijkstra's algorithm

Project scheduling in AND-OR graphs: A generalization of Dijkstra's algorithm

0.00 Avg rating0 Votes
Article ID: iaor2004515
Country: United States
Volume: 27
Issue: 3
Start Page Number: 504
End Page Number: 517
Publication Date: Aug 2002
Journal: Mathematics of Operations Research
Authors: ,
Keywords: networks: path
Abstract:

The paper considers a project scheduling problem in weighted directed graphs in which arcs represent operations while nodes are identified with starting and finishing endpoints of the operations; arc lengths represent operation durations. The graphs have two types of nodes – AND-nodes and OR-nodes. The problem is to find the earliest starting times for all operations. This problem generalizes the shortest path problem and the critical path problem. The complexity of the suggested algorithm is O(p′p) where p′ is the number of acrcs entering the AND-nodes and p is the total number of arcs.

Reviews

Required fields are marked *. Your email address will not be published.