A generalization of the least cost scheduling “time–cost trade-off” problem

Least cost scheduling techniques on critical path method network (CPM/cost problem) originates from James E. Kelly and Morgan Walker. It was developed in 1959. First algorithm based on network flows was published by Fulkerson in 1961. Classical form of time–cost trade-off originates in the minimum cost flow problem. In this paper a new construction management problem is presented that is an improvement of classical problem. Development deals with the system of contractual instalments. Events should occur at given times according to the contracts among building contractors. If events occur before those times they bring benefit; if they occur later they bring outcomes. It is shown that this model also originates in the minimum cost flow problem. An algorithm is presented that follows the main steps of algorithm of CPM/cost method published by Klafszky in 1969. Starting from an optimal initial solution, project duration time is decreased step by step until minimum project duration time is attained. In each step only a maximum flow problem must be solved although original problem is equivalent to a minimum cost flow problem.