A Lower Bound for Project Completion Time Attained by Detailing Project Tasks and Redistributing Workloads

Keywords

Project network, Directed Acyclic Graph (DAG), Max-cut, maximum matching, bipartite+graph

Abstract

We evaluate the possible benefit from improving the workload distribution in a directed acyclic graph (DAG) (e.g. a project network), by determining a lower bound for the project completion time. It is shown that a lower bound can be obtained by equally distributing the workload over the max-cut in the graph which separates the nodes 1 and n. It is also shown that for a complete n-node DAG, practitioners can quickly compute a lower bound for the project completion time. The max-cut can be found by any linear programming algorithm or by reducing the problem to the problem of finding a maximum matching in a bipartite graph. Our results can help planners and project managers to characterize the "ideal case" in which the optimal workload distribution among the arc networks minimizes the project completion time. That can be done for a non-complete DAG as well as for a complete one. A lower bound can then be used to evaluate the maximum potential for reducing the project completion time in real-life cases.

(top)

(back to issue)