

A Lower Bound for Project Completion Time Attained by Detailing Project Tasks and Redistributing Workloads
Zohar LASLO KeywordsProject network, Directed Acyclic Graph (DAG), Maxcut, maximum matching, bipartite+graph AbstractWe 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 maxcut in the graph which separates the nodes 1 and n. It is also shown that for a complete nnode DAG, practitioners can quickly compute a lower bound for the project completion time. The maxcut 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 noncomplete 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 reallife cases. (top)
