logo IMB
Retour

Séminaire Optimisation Mathématique Modèle Aléatoire et Statistique

An Efficient Constraint Programming Approach to Preemptive Job Shop Scheduling

Emmanuel Hebrard

( LAAS-CNRS-Toulouse )

Online

le 21 mars 2024 à 11:00

Constraint Programming (CP) has been widely, and very successfully, applied to scheduling problems. However, the focus has been on uninterruptible tasks, and preemptive scheduling problems are typically harder for existing constraint solvers. Indeed, one usually needs to represent all potential task interruptions thus introducing many variables and symmetrical or dominated choices.
I will talk about CP approaches to both non-preemptive and preemptive job shop scheduling, and then I will show how methods for the former can be applied with very little change to the latter. The resulting approach does not require an explicit model of task interruptions and as a result significantly outperforms state-of-the-art dedicated approaches in our experimental results.