A reduction tree approach for the discrete time/cost trade-off problem
Van Eynde, Rob Vanhoucke, Mario
Van Eynde, Rob
Vanhoucke, Mario
Citations
Altmetric:
Publication Type
Journal article with impact factor
Editor
Supervisor
Publication Year
2022
Journal
Computers & Operations Research
Book
Publication Volume
143
Publication Issue
July
Publication Begin page
Publication End page
Publication NUmber of pages
Collections
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.
Research Projects
Organizational Units
Journal Issue
Keywords
Discrete Time/Cost Trade-Off, Reduction Tree, Modular Decomposition