This PhD thesis studies how constraint programming (CP) scheduling solvers can make better decisions during search—specifically, which branches to explore and in what order. It focuses on how to define and measure heuristic quality in a principled way, and how learning methods can be used to improve these choices. The contributions are threefold.

The first contribution concerns the use of graph neural networks (GNNs) for scheduling heuristics. The thesis first develops a constructive GNN method for resource-constrained scheduling, achieving state-of-the-art results and supporting extensions under uncertainty. It then explores the use of a GNN as a value-selection heuristic inside a CP solver, where it uncovers important limitations.

The second contribution is a framework for analyzing value-selection heuristics. The thesis introduces the heuristic online accuracy by classifying branching decisions during search as correct or incorrect. It shows that more accurate heuristics make more expensive mistakes, and overall performance converges toward that of random choice when approaching the optimal solution. This explains why learning-based value selection can struggle when near-optimal solutions are required, though it may still help when good solutions are sufficient.

The third contribution concerns variable selection. Instead of inventing a new heuristic from scratch, the thesis proposes a measurable criterion for effectiveness based on refutation tree size for proving unsatisfiability. The thesis introduces an algorithm to compute minimum-sized refutation trees - providing lower bounds on search effort - and explores using refutation trees directly as a variable-selection heuristic, with promising improvements and clear directions for future learning-based work.