A fast algorithm for time compression in project scheduling

An effective procedure for time–cost trade off in Critical Path Method (CPM) networks when discrete time–cost combinations are allowed on the project activities is developed. The particular problem confronted in this study is to select a time–cost combination for each activity which minimizes the project overall cost subject to a due-date. For this inherently difficult to solve problem, the heuristic algorithm constructs a feasible solution of minimal cost by compressing and increasing the duration of critical and noncritical activities. In order to improve the time efficiency of the algorithm, a subroutine is used that recalculates the critical paths by restricting the calculations to a partial network. The procedure, coded in Visual Basic and tested on a large set of randomly generated networks, has provided fairly good solutions at a small computational effort.