Academic Bibliography

 Search 200 years of publications by Ghent University researchers.
Advanced search
2 files | 3.55 MB
Add to list
  1. Search results
  2. A reduction tree approach for the dis...

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

Rob Van Eynde and Mario Vanhoucke (UGent)
(2022) COMPUTERS & OPERATIONS RESEARCH. 143.
Author
Organization
Project
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.
Keywords
Discrete time/cost trade-off, Reduction tree, Modular decomposition, CASH FLOW, TABU SEARCH, OPTIMIZATION, COMPLEXITY, APPROXIMATION, ALGORITHMS, METAHEURISTICS

Downloads

  • Download
    (...).pdf
    • full text (Published version)
    • |
    • UGent only
    • |
    • PDF
    • |
    • 2.31 MB
  • Download
    Van Eynde and Vanhoucke COR 2022 accepted version .pdf
    • full text (Accepted manuscript)
    • |
    • open access
    • |
    • PDF
    • |
    • 1.23 MB

Citation

Please use this url to cite or link to this publication:

MLA
Van Eynde, Rob, and Mario Vanhoucke. “A Reduction Tree Approach for the Discrete Time/Cost Trade-off Problem.” COMPUTERS & OPERATIONS RESEARCH, vol. 143, 2022, doi:10.1016/j.cor.2022.105750.
APA
Van Eynde, R., & Vanhoucke, M. (2022). A reduction tree approach for the discrete time/cost trade-off problem. COMPUTERS & OPERATIONS RESEARCH, 143. https://doi.org/10.1016/j.cor.2022.105750
Chicago author-date
Van Eynde, Rob, and Mario Vanhoucke. 2022. “A Reduction Tree Approach for the Discrete Time/Cost Trade-off Problem.” COMPUTERS & OPERATIONS RESEARCH 143. https://doi.org/10.1016/j.cor.2022.105750.
Chicago author-date (all authors)
Van Eynde, Rob, and Mario Vanhoucke. 2022. “A Reduction Tree Approach for the Discrete Time/Cost Trade-off Problem.” COMPUTERS & OPERATIONS RESEARCH 143. doi:10.1016/j.cor.2022.105750.
Vancouver
1.
Van Eynde R, Vanhoucke M. A reduction tree approach for the discrete time/cost trade-off problem. COMPUTERS & OPERATIONS RESEARCH. 2022;143.
IEEE
[1]
R. Van Eynde and M. Vanhoucke, “A reduction tree approach for the discrete time/cost trade-off problem,” COMPUTERS & OPERATIONS RESEARCH, vol. 143, 2022.
@article{8744630,
  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.}},
  articleno    = {{105750}},
  author       = {{Van Eynde, Rob and Vanhoucke, Mario}},
  issn         = {{0305-0548}},
  journal      = {{COMPUTERS & OPERATIONS RESEARCH}},
  keywords     = {{Discrete time/cost trade-off,Reduction tree,Modular decomposition,CASH FLOW,TABU SEARCH,OPTIMIZATION,COMPLEXITY,APPROXIMATION,ALGORITHMS,METAHEURISTICS}},
  language     = {{eng}},
  pages        = {{20}},
  title        = {{A reduction tree approach for the discrete time/cost trade-off problem}},
  url          = {{http://doi.org/10.1016/j.cor.2022.105750}},
  volume       = {{143}},
  year         = {{2022}},
}
Altmetric
View in Altmetric
Web of Science
Times cited: