首页|Comparison of two problem transformation-based methods in detecting the best performing branch-and-bound procedures for the RCPSP

Comparison of two problem transformation-based methods in detecting the best performing branch-and-bound procedures for the RCPSP

扫码查看
原文链接
  • NETL
  • NSTL
  • Elsevier
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.

Project schedulingMachine learningProblem transformationClassificationPerformance detection

Weikang Guo、Mario Vanhoucke、Jose Coelho

展开 >

School of Management Science and Engineering, Southwestern University of Finance and Economics, Chengdu, China

Faculty of Economics and Business Administration, Ghent University, Tweekerkenstraat 2, 9000 Gent, Belgium||Technology and Operations Management, Vlerick Business School, Reep 1, 9000 Gent, Belgium||UCL School of Management, University College London, 1 Canada Square, London E14 5AA, United Kingdom

Faculty of Economics and Business Administration, Ghent University, Tweekerkenstraat 2, 9000 Gent, Belgium||INESC - Technology and Science, Porto (Portugal) and Universidade Aberta, Rua da Escola Politecnica, 147, 1269-001, Lisbon, Portugal

2025

10.1016/j.eswa.2025.127383

Expert systems with applications

Expert systems with applications

SCI
ISSN：0957-4174
年,卷(期)：2025.281(Jul.)
  • 84