The International Association for Automation and Robotics in Construction
Publications / CCC 2025 - Zadar, Croatia
SIMPLIFICATION AND OPTIMIZATION OF PROJECT STRUCTURES BASED ON PRECEDENCE-CONSTRAINED KNAPSACK PROBLEM
The COVID-19 pandemic has highlighted the structural vulnerability of construction projects, especially in crises when the effectiveness of traditional scheduling approaches has significantly decreased. This paper presents a novel algorithmic approach that combines graph-based project structure simplification with cost-constrained profit maximization based on the mathematical model of the precedence-constrained knapsack problem. The method first reduces the size of the decision space by removing non-revenue-generating projects based on rules while preserving project logic dependencies and cost. After that, two optimization methods - integer linear programming and graph theory heuristics - are used to select the project. Based on practical examples, simplification significantly reduces the need for computation, making it possible to find optimal solutions that were not manageable on the original structures. The algorithm prioritizes project paths that provide the highest specific gains while also meeting precedent requirements. The analysis confirmed the model's flexibility and applicability in different project environments. The presented approach thus contributes to the development of crisis-resistant project management and, at the same time, offers a basis for the development of a generalizable decision support system.