Master Class on Constraint Programming for Scheduling

Monday 13 April, 2026, Salle Europe, LAAS-CNRS

(for PhD students registered to the Workshop only)

Basics of Constraint Programming for Scheduling and Application to Space

Cédric Pralet,
ONERA, Toulouse, France

Constraint Programming (CP) is a powerful tool to tackle scheduling problems. All along this talk, we will use a concrete application, namely planning for Earth observation satellites, in order to illustrate some features of CP both in terms of scheduling models and scheduling algorithms. In this application, the satellites can be seen as machines and the candidate observations can be seen as candidate jobs. We will start from a very basic configuration involving a single satellite and progressively complexify the problem to illustrate so-called interval-based techniques used in CP solvers. In a last part, we will discuss scalability issues together with the combination between CP and Large Neighborhood Search.

Global scheduling constraints 

Margaux Nattaf,
G-SCOP, Grenoble, France 

The strength of CP comes partly from global constraints, which model key structures like machines and resources. These constraints use dedicated filtering algorithms to remove impossible values early. For scheduling problems, two important global constraints are the disjunctive (machine) and the cumulative (resource) constraints. The talk will present the main filtering algorithms used for these constraints, such as edge-finding, time-table, and energetic reasoning. We show how these algorithms reduce domains and detect conflicts early and highlight how they exploit the structure of scheduling problems.

PMS Hackathon: Box Packing with Constraint Programming

Emmanuel Hébrard		Titouan Seraud		Tim Luchterhand
LAAS-CNRS, Toulouse, France		LAAS-CNRS, Toulouse, France		LAAS-CNRS, Toulouse, France

Find the best solution to a complex problem with constraint programming...

Rectangle and 3D-packing problems can be seen as scheduling problems, and in constraint programming they are solved using the same concepts (intervals, precedences and resources). In this hackathon, you will model and solve some problems related to packing game boxes. The goal is to showcase advanced use of a constraint solver: although modeling this problem with constraint toolkits is not difficult, efficiently solving it might require greedy initial solutions, large neighborhood policies, and other such strategies. We will see how to do that in the solver Tempo (https://gitlab.laas.fr/roc/emmanuel-hebrard/tempo), however, you are free to use other tools.