An application of randomized minimum cut to the project time/cost tradeoff problem

In this paper, we introduce a solution procedure for solving the project time/cost tradeoff problem, such that a project’s duration is reduced for a specified amount of time at minimum cost. In our solution procedure, we find the minimum cut in the acyclic graph representing the critical paths of the project, using the fast algorithm of randomized minimum cut. The minimum cut so obtained, is then utilized to identify the project activities that are to be reduced, in order to achieve a certain reduction in the project’s total duration. The applicability of the proposed solution procedure is demonstrated by some test problems.