@phdthesis{01HXC60A5P1F01448RJSW5YVE9,
  abstract     = {{The resource-constrained project scheduling problem (RCPSP) entails scheduling a series of non-preemptable, precedence-related activities, while also considering constraints on the resources needed for these activities' completion. Recognized as a widely studied NP-hard (Non-deterministic Polynomial-time Hard) optimization problem, the RCPSP has seen numerous solution methods proposed by researchers. Among these, priority rule-based heuristics are a popular approach, especially in real-world applications, due to their simplicity and speed.

However, priority rule-based heuristics are problem specific, therefore, no single rule consistently outperforms others across all scenarios. Researchers and project managers have to either randomly choose from the available priority rules or, to ensure solution quality, try these priority rules one by one. Therefore, an approach that employs a standardized process and can design new priority rules outperforming all traditional rules is highly worth exploring. 

Designing priority rule-based heuristics is a complex task. Typically, it requires problem experts to meticulously analyze instance characteristics to design new heuristics. This method is often time-consuming and is restricted by the scope of what experts can consider. Consequently, there's a growing trend among researchers to automate the construction of heuristics, a field commonly referred to as hyper-heuristics. Hyper-heuristics have found application in various combinatorial optimization areas, including job shop scheduling and the traveling salesman problem. However, their implementation in designing priority rule-based heuristics for project scheduling problems remains relatively nascent.

The research presented in this dissertation aims to bridge the identified gap in the literature. It encompasses five chapters, with \textbf{\Cref{chapter:introduction}} offering an overview of project scheduling problems and the automated design of priority rule-based heuristics. The subsequent three chapters delve into distinct research avenues. Finally, \textbf{\Cref{chapter:conclusions}} discusses the conclusions drawn and directions for future research.
Further explanations are given below for \textbf{Chapters} \textbf{2} to \textbf{4}.

\textbf{\Cref{chapter:GP1}} introduces a genetic programming hyper-heuristics (GPHH) algorithm for RCPSP priority rule design, featuring a duplicate removal technique for increased efficiency. This method significantly cuts down runtime without sacrificing search capability. Optimal training sets are found to support GPHH in generating effective priority rules. Analysis of various fitness evaluation functions indicates that while high-quality reference values are preferable, other criteria are also viable, attesting to GPHH's adaptability for new project scheduling problems. Employing these insights, GP-designed priority rules are tested across extensive datasets, including new projects with over 1,000 activities. These rules generally surpass traditional methods, notably in large parallel project scenarios. Additionally, a CHAID regression-based approach is developed, enhancing performance in smaller and large non-parallel projects by accurately predicting the most effective rule ensemble.

\textbf{\Cref{chapter:regression1}} tackles RCPSP priority rule design using supervised learning approach, a less explored contrast to the common unsupervised approaches like GPHH. This chapter focuses on regression-based methods for designing new heuristics for the RCPSP. Nine regression algorithms are evaluated, with the top three enhanced through ensemble techniques. These enhanced models demonstrate their ability to exceed traditional rules across all primary test datasets, and, in certain scenarios, they even outperform GP-designed rules. To validate these results, we conduct further tests on datasets with large-scale projects, affirming the broad applicability of the regression-based heuristics.

\textbf{\Cref{chapter:GP2}} addresses the high computational demand of GPHH in RCPSP priority rule design by introducing four RCPSP-specific surrogate models. These models prove efficient and effective, matching the original model's performance with equal evaluations and even outperforming the original model within the same runtime. Furthermore, the effectiveness of one of the best surrogate models proposed is validated across seven different population sizes. This demonstrates the model's capacity to produce results comparable to the original model when search spaces are explored extensively. An evaluation of the surrogate models' accuracy and the size of their generated rules reveals high precision, with some rules being more compact than those designed by the original model.}},
  author       = {{Luo, Jingyu}},
  language     = {{eng}},
  pages        = {{X, 134}},
  publisher    = {{Ghent University. Faculty of Economics and Business Administration}},
  school       = {{Ghent University}},
  title        = {{Towards automated design : priority rules for resource-constrained project scheduling}},
  year         = {{2024}},
}