Publication

A prediction model for ranking branch-and-bound procedures for the resource-constrained project scheduling problem

Guo, Weikang
Vanhoucke, Mario
Coelho, José
Citations
Altmetric:
Publication Type
Journal article with impact factor
Editor
Supervisor
Publication Year
2023
Journal
European Journal of Operational Research
Book
Publication Volume
306
Publication Issue
2
Publication Begin page
579
Publication End page
595
Publication NUmber of pages
Collections
Abstract
The branch-and-bound (B&B) procedure is one of the most widely used techniques to get optimal solutions for the resource-constrained project scheduling problem (RCPSP). Recently, various components from the literature have been assembled by Coelho and Vanhoucke (2018) into a unified search algorithm using the best performing lower bounds, branching schemes, search strategies, and dominance rules. However, due to the high computational time, this procedure is only suitable to solve small to medium-sized problems. Moreover, despite its relatively good performance, not much is known about which components perform best, and how these components should be combined into a procedure to maximize chances to solve the problem. This paper introduces a structured prediction approach to rank various combinations of components (configurations) of the integrated B&B procedure. More specifically, two regression methods are used to map project indicators to a full ranking of configurations. The objective is to provide preference information about the quality of different configurations to obtain the best possible solution. Using such models, the ranking of all configurations can be predicted, and these predictions are then used to get the best possible solution for a new project with known network and resource values. A computational experiment is conducted to verify the performance of this novel approach. Furthermore, the models are tested for 48 different configurations, and their robustness is investigated on datasets with different numbers of activities. The results show that the two models are very competitive, and both can generate significantly better results than any single-best configuration.
Research Projects
Organizational Units
Journal Issue
Keywords
Project Scheduling, RCPSP, Preference Learning, Label Ranking, Performance Prediction
Citation
Knowledge Domain/Industry
Other links
Embedded videos