Automated design of heuristics for resource-constrained project scheduling problem via regression algorithms

Le résumé fourni par la source

Abstract The resource-constrained project scheduling problem (RCPSP) is a complex optimization problem aiming to construct feasible schedules that minimize the project makespan while satisfying the precedence and renewable resource constraints. Priority rule heuristics are prevalent approaches for solving the RCPSP, particularly in practical applications. However, these rules are problem-specific, and no rule can consistently outperform others across different projects. Designing priority rules through manual methods requires substantial expertise, time, and computational effort. This has led researchers to propose automated techniques for this purpose. Most existing research in this area focuses on unsupervised learning techniques like genetic programming hyper-heuristics (GPHH), while the investigation of supervised learning algorithms remains limited. To address this gap, this research explores the potential of supervised learning algorithms, specifically regression-based methods, for the automated design of new priority rule heuristics for RCPSP. Nine widely used regression algorithms were evaluated, and the top-performing three were further enhanced using ensemble techniques to augment their effectiveness. Computational experiments show that regression-based heuristics can outperform traditional priority rules across all primary test datasets and, in some cases, even surpass priority rules designed through GPHH. To further validate the reliability of our results, we also tested the regression-based heuristics on various supplementary datasets, including project instances with more than 1,000 activities and empirical projects. Their performance highlights the robust generalization of regression-based heuristics.

Ce résumé expose les affirmations des auteurs. BNTIC ne l’interprète pas comme une validation indépendante des résultats.