A reduction tree approach for the discrete time/cost trade-off problem

Abstract

The Discrete Time/Cost Trade-Off Problem is a well studied problem in the project scheduling literature. Each activity has multiple execution modes, a solution is obtained by selecting a mode for each activity. In this manuscript we propose an exact algorithm to obtain the complete curve of non-dominated time/cost alternatives for the project. Our algorithm is based on the network reduction approach in which the project is reduced to a singular activity. We develop the reduction tree, a new datastructure that tracks the modular decomposition structure of an instance at each iteration of the reduction sequence. We show how it is related to the complexity graph of the instance. Several exact and heuristic algorithms to construct a good reduction tree are proposed. Our computational experiments show that the use of the reduction tree provides significant speedups when compared to the existing reduction plan approach. Although the new approach does not outperform the best performing branch-and-bound procedure from the literature, the experiments show that incorporating modular decomposition can provide significant performance improvements for solution algorithms, showing potential for developing improved hybridized procedures to solve this challenging problem type.