Contexte du sujet de stage

Les problèmes d’ordonnancement qui consistent à organiser dans le temps l’exécution de tâches nécessitant des ressources à disponibilité limitée sont présents dans tous les secteurs de l’industrie et des services. Il s’agit de problèmes complexes, très difficiles à résoudre en pratique. Toutefois, lorsque les ressources correspondent exactement aux modèles classiques de la littérature scientifique en ordonnancement, comme les ressources dites disjonctives ou cumulatives, les problèmes d’ordonnancement sont bien résolus, y compris de manière exacte, par les méthodes hybrides de programmation par contraintes et de satisfiabilité booléenne [1,2]. Les choses se gâtent lorsqu’on souhaite intégrer des contraintes de ressources complexes issues des applications pratiques, comme des buffers intermédiaires à capacité limitée [4], des temps de réglage des machines ou des ressources multi-compétences [5]. Pour ces problèmes, les approches exactes perdent grandement de leur efficacité et les problèmes sont généralement résolus par des heuristiques.

Dans ce contexte, ce sujet de stage propose de concevoir des méthodes exactes hybridant la programmation linéaire en nombres entiers et la programmation par contraintes aidées par des techniques de décomposition, plus précisément la décomposition de Benders logique [3,4] permettant d’élaborer des coupes combinatoires. Les méthodes proposées seront comparées aux méthodes de la littérature.

Objectifs du stage

Le contenu du stage a pour objectifs de (tout ou partie des points suivants en fonction des possibilités) :

• modéliser un ou plusieurs des problèmes présentés dans [4,5] en programmation par contraintes ;
• concevoir, développer et tester une méthode hybride et par décomposition de Benders logique pour la résolution efficace du problème ;
• tester la méthode proposée sur des jeux de données.

Lieu du stage : LAAS-CNRS, 7 avenue du Colonel Roche, 31400 Toulouse – www.laas.fr

Profil recherché : M2 ou Ecole d’Ingénieurs Informatique et/ou Recherche Opérationnelle

Poursuite en thèse : possible sous réserve d’obtenir un financement

Encadrement et contacts

Christian Artigues, LAAS-CNRS (artigues@laas.fr)

Carla Juvin, Toulouse Business School (c.juvin@tbs-education.fr)

Pierre Lopez, LAAS-CNRS (lopez@laas.fr)

Références bibliographiques

[1] Hebrard, E. (2025). Disjunctive Scheduling in Tempo. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025), pp. 13-1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik.

[2] Heinz, V., Vilím, P., & Hanzálek, Z. (2025). Reinforcement learning for search tree size minimization in constraint programming: New results on scheduling benchmarks. Computers & Industrial Engineering, 111413.

[3] Hooker, J. N. (2007). Planning and scheduling by logic-based Benders decomposition. Operations research, 55(3), 588-602.

[4] Juvin, C., Houssin, L., & Lopez, P. (2023). Logic-based Benders decomposition for the preemptive flexible job-shop scheduling problem. Computers & Operations Research, 152, 106156.

[4] Kasapidis, G. A., Paraskevopoulos, D. C., Mourtos, I., & Repoussis, P. P. (2025). A unified solution framework for flexible job shop scheduling problems with multiple resource constraints. European Journal of Operational Research, 320(3), 479-495.

[5] Wang, C., Fan, D., Liu, Y., Ren, S., & Wang, J. (2025). Dual-resource flexible job shop scheduling considering worker proficiency differences. Computers & Operations Research, 107216.