A network flow procedure for project crashing with penalty nodes

In this paper a procedure is developed to obtain the project-cost curve when there are linear penalty costs for delays of certain key events in a project in addition to crashing costs for activities. A linear programming formulation is given. From primal dual considerations, the optimality conditions are derived and a network flow interpretation to the problem on a modified network is developed. The treatment is similar to that of Fulkerson 7] except that provision for flow drainage from penalty nodes is made, and the notion of auxiliary sources is introduced to satisfy the modified optimality conditions. The solution procedure based on network flow arguments proceeds in two phases. In phase 1, the global minimum of the project-cost is obtained, whereas in phase 2, the entire project cost-duration efficient frontier is generated. An example problem illustrating the procedure is also presented.