Thèse Méthodes d'Ordonnancement d'Atelier pour la Résolution de Problèmes de Grande Taille avec Considération de Fonctions Objectif Réalistes H/F

Université Grenoble Alpes

Établissement : Université Grenoble Alpes
École doctorale : I-MEP² - Ingénierie - Matériaux, Mécanique, Environnement, Energétique, Procédés, Production
Laboratoire de recherche : Laboratoire des Sciences pour la Conception, l'Optimisation et la Production de Grenoble
Direction de la thèse : Marie-Laure ESPINOUSE ORCID 000000030120661X
Début de la thèse : 2026-10-01
Date limite de candidature : 2026-05-18T23:59:59

Les problèmes d'ordonnancement d'atelier constituent un enjeu majeur pour de nombreux secteurs industriels tels que l'automobile, l'aéronautique, les semi-conducteurs, la production pharmaceutique, les centres de tri ou la logistique hospitalière. Ils consistent à planifier l'exécution de tâches multi-opérations sous contraintes de ressources partagées, de précédence et de synchronisation. La combinatoire issue de ces contraintes rend ces problèmes particulièrement complexes, en particulier à l'échelle industrielle.
La littérature a largement étudié ces cadres (flow shop, job shop, open shop et leurs variantes flexibles, no-wait, no-idle ou blocking), mais demeure dominée par l'objectif de minimisation du makespan. Bien qu'utile pour les comparaisons méthodologiques, cet indicateur reflète imparfaitement les priorités industrielles, davantage orientées vers le flowtime, le retard (tardiness), la réduction des encours ou des formulations multi-objectifs. Les travaux portant sur ces critères réalistes sont peu nombreux et se limitent majoritairement à de petites instances, laissant ouverte la question essentielle du passage à l'échelle.
En parallèle, les méthodes de recherche arborescente heuristique (branch-and-bound avancé, guided search tree, beam search, hybridations) ont démontré leur efficacité sur de nombreux problèmes combinatoires de grande taille. Pourtant, leur utilisation systématique pour l'ordonnancement d'atelier avec objectifs non-makespan demeure encore marginale. Ce projet se situe précisément à cette convergence.
L'objectif principal est de développer des méthodes capables de résoudre efficacement des problèmes d'ordonnancement industriels de grande taille (nombre de tâches et nombre de machines) en se concentrant sur des objectifs réalistes : flowtime, retard, réduction des encours et approches multi-objectifs

La recherche en ordonnancement d'atelier s'est historiquement concentrée sur la minimisation du makespan, devenu l'objectif de référence pour l'évaluation des méthodes. Pourtant, dans les environnements industriels réels, les priorités opérationnelles portent davantage sur la réduction du flowtime, le respect des délais (tardiness), la limitation des encours (WIP) et des formulations multi-objectifs. Les travaux traitant explicitement ces critères restent peu nombreux et concernent majoritairement des instances de petite taille, souvent éloignées des structures industrielles actuelles. Les nouveaux jeux de données réalistes, comportant des centaines de tâches et des routages partiels, modifient profondément la structure des solutions et mettent en défaut les approches dominantes basées sur la recherche locale. La littérature actuelle fournit ainsi peu de cadres méthodologiques adaptés au passage à l'échelle pour ces objectifs. Parallèlement, les méthodes de recherche arborescentes heuristiques ont démontré leur efficacité sur divers problèmes combinatoires de grande dimension. Grâce à des mécanismes de bornes, de guidage et de sélection de noeuds, elles permettent une exploration structurée et sélective d'espaces de recherche très vastes. Malgré ce potentiel, leur utilisation pour l'ordonnancement d'atelier avec objectifs autres que le makespan demeure marginale. Le projet se situe précisément à cette convergence, en visant le développement d'approches arborescentes dédiées à des critères industriels réalistes. Il ambitionne ainsi de combler un manque méthodologique majeur pour la résolution de problèmes d'ordonnancement industriels de grande taille.
Le doctorant pourra bénéficier de l'expertise et de jeux de données d'un tout nouveau partenariat industriel.
Ce sujet de thèse fait suite à un stage soutenu en 2025 et qui donne lieu à la préparation d'un article et à un stage de master actuellement en cours.

L'objectif principal est de développer des méthodes capables de résoudre efficacement des problèmes d'ordonnancement industriels de grande taille (en nombre de tâches et de machines) en se concentrant sur des objectifs réalistes : flowtime, retard, réduction des encours et approches multi-objectifs. Il s'agira d'adapter et d'enrichir la recherche arborescente par la conception de stratégies de branchement dédiées, de bornes inférieures spécifiques, de mécanismes d'exploration sélective et de pruning efficaces, ainsi que par l'hybridation avec des heuristiques de guidage.
Le projet vise également une meilleure compréhension des mécanismes de performance de ces approches afin de dégager des principes méthodologiques transférables à d'autres contextes. Une validation approfondie sur des données industrielles réelles, fournies par un partenaire, assurera la pertinence opérationnelle des résultats.

Le coeur méthodologique du projet reposera sur le développement d'approches arborescentes adaptées aux objectifs étudiés. Des travaux seront menés sur la conception de bornes inférieures spécifiques aux indicateurs de flowtime et de retard, afin de mieux guider l'exploration de l'espace de recherche. Une analyse structurelle fine des arbres générés permettra d'identifier des stratégies de branchement et d'exploration plus efficaces dans un contexte de grande échelle. Ces méthodes seront complétées par l'intégration raisonnée d'heuristiques de tri, de mécanismes d'exploration contrôlée et, si nécessaire, d'outils d'apprentissage léger visant à améliorer les choix de décisions locales. Les performances obtenues seront comparées aux approches implémentées dans des solveurs existants et validées sur de larges jeux de données industriels, garantissant la robustesse et la pertinence des contributions.