Comparison of two problem transformation-based methods in detecting the best performing branch-and-bound procedures for the RCPSP
Guo, Weikang Coelho, José
Guo, Weikang
Coelho, José
Publication Type
Journal article with impact factor
Editor
Supervisor
Publication Year
2025-07
Journal
Expert Systems with Applications
Book
Publication Volume
281
Publication Issue
Publication Begin page
127383
Publication End page
127383
Publication Number of pages
Collections
Abstract
The branch-and-bound (B&B) procedure is one of the most frequently used methods for solving the resource-constrained project scheduling problem (RCPSP) to obtain optimal solutions and has a rich history in the academic literature. Over the past decades, various variants of this procedure have been proposed, each using slightly different configurations to search for the optimal solution. While most of the configurations perform relatively well for many problem instances, there is, however, no known universal best B&B configuration that works well for all problem instances. In this work, we propose two problem transformation-based machine learning classification methods (binary relevance and classifier chains) to automatically detect the best-performing branch-and-bound configuration for the resource-constrained project scheduling problem. The proposed novel learning models aim to find the relationship between the project characteristics and the performance of a specific B&B configuration. With this obtained knowledge, the best-performing B&B configurations can be predicted, resulting in a better solution. A comprehensive computational experiment is conducted to demonstrate the effectiveness of the proposed classification models and the performance improvements over three categories of methods from the literature, including the latest branch-and-bound configurations, the state-of-the-art classification models in project scheduling, and commonly used clustering algorithms in machine learning. The results show that the proposed classification models can enhance solution quality for the RCPSP without changing the core components of existing algorithms. More specifically, the classifier chains method, when combined with the Back-Propagation Neural Network algorithm, achieves the best performance, outperforming binary relevance, which demonstrates the impact of label correlation on the performance. The experiments also demonstrate the merits of the proposed model in improving the robustness of the solutions. Furthermore, these findings not only highlight the potential of the classification models in detecting best-performing B&B configurations, but also emphasize the need for future work and development to further improve the performance and applicability of these models.
Research Projects
Organizational Units
Journal Issue
Keywords
33 Built Environment and Design, 3302 Building, Networking and Information Technology R&D (NITRD), Bioengineering, Machine Learning and Artificial Intelligence