Membres du jury :
- Safia Kedad-Sidhoum, professeure au Conservatoire national des arts et métiers, rapporteure.
- Latéfa Ghomri, professeure à l’Université de Tlemcen, rapporteure.
- Fred-Maurice Ngolè Mboula, ingénieur docteur au CEA Paris-Saclay, examinateur.
- Pierre Lemaire, professeur à l’Université Grenoble Alpes, examinateur.
- Thibaud Monteiro, professeur à l’INSA Lyon, examinateur.
- Maria Di Mascolo, directrice de recherche au CNRS, directrice de thèse
Invité :
- Zakaria Yahouni, maître de conférences à Grenoble INP – UGA, co-encadrant de thèse.
Résumé
L’ordonnancement affecte des ressources limitées à des activités et organise leur exécution dans le temps. Cette thèse étudie trois problèmes : le flow shop de permutation, le job shop et le transport intra-hospitalier. Dans le premier, les tâches suivent la même succession de machines et gardent le même ordre sur toutes les machines. Dans le deuxième, chaque tâche suit son propre parcours. Dans le troisième, il faut affecter les demandes aux brancardiers et fixer leur ordre de service. La thèse étudie comment l’apprentissage automatique peut guider la recherche de solutions dans le temps de calcul disponible. Les méthodes de recherche opérationnelle conservent le modèle, les vérifications de faisabilité et l’évaluation des solutions. La thèse poursuit deux objectifs : l’objectif 1 est de trouver de meilleurs ordonnancements dans le temps disponible ; l’objectif 2 est de réduire l’effort nécessaire pour prouver qu’aucune meilleure solution n’existe. L’apprentissage par renforcement apprend à choisir des actions à partir de leurs effets sur la recherche. Selon l’étude, il règle une recherche locale itérée, choisit un voisinage ou ordonne l’exploration de sous-problèmes. Une recherche locale itérée alterne l’amélioration d’une solution et sa perturbation. Un voisinage définit les modifications que la recherche peut examiner. L’apprentissage supervisé apprend à partir d’exemples produits par le solveur. Il choisit comment diviser la recherche en sous-problèmes dans le job shop. Selon l’étude, l’apprentissage a lieu pendant chaque résolution ou avant l’utilisation du modèle. Une revue des méthodes de décomposition, qui coordonnent la résolution de plusieurs problèmes plus petits, élargit la réflexion au-delà de l’ordonnancement. Pour l’objectif 1, les expériences montrent une amélioration des ordonnancements obtenus dans le temps imparti par recherche locale et recherche locale itérée, ainsi que par une première méthode de séparation et évaluation. Cette dernière divise la recherche en sous-problèmes et écarte ceux qui ne peuvent pas améliorer la solution courante. Pour l’objectif 2, les résultats indiquent une réduction de l’effort de preuve dans un solveur exact. Les gains dépendent du problème, du solveur et du protocole ; certaines instances demandent davantage d’effort. Les expériences hospitalières résolvent séparément des situations de réordonnancement définies par les demandes et les ressources connues à un instant donné. Elles ne simulent pas une journée complète de service. Ces travaux montrent comment des décisions apprises peuvent améliorer des méthodes de recherche existantes. Ils précisent aussi ce que chaque évaluation permet de conclure. La réutilisation sur de nouvelles instances, la compréhension des choix du modèle et le coût total de l’apprentissage restent des questions importantes. La thèse fournit des méthodes et un cadre commun pour les étudier dans différents contextes de recherche.
Mots-clés : Ordonnancement, apprentissage automatique, apprentissage par renforcement, apprentissage supervisé, recherche locale, séparation et évaluation, apprentissage du branchement, méthodes de décomposition.
Abstract :
Scheduling assigns activities to limited resources over time. This thesis studies three scheduling problems: the permutation flow shop, the job shop and intra-hospital transport. In a permutation flow shop, jobs follow the same machine sequence and keep the same order on all machines. In a job shop, each job follows its own machine route. In hospital transport, requests must be assigned to porters and ordered for service. The thesis examines how machine learning can guide search decisions within a time limit. Operations research methods retain the scheduling model, feasibility checks and objective evaluation. The thesis pursues two goals: Objective 1, finding better schedules within a computation budget, and Objective 2, reducing the effort needed to prove optimality. Reinforcement learning configures an iterated local search, selects neighbourhoods and orders search branches. Supervised learning selects branching decisions in an exact job-shop solver. Across these studies, learning either takes place during each solve or before deployment, through solver interaction or collected solver data. A literature review of learning within mathematical decomposition extends the discussion beyond scheduling. For Objective 1, the experiments show improvements in schedules found by local search, iterated local search and a preliminary branch-and-bound under a time limit. For Objective 2, they provide evidence of reduced proof effort in an exact solver. The benefits depend on the problem, solver and evaluation protocol, and some instances require more effort. The hospital experiments concern static instances built from the information available at individual rescheduling times. Together, the studies show how learned decisions can help established search methods. They also clarify which benefits each evaluation supports. Reuse on new instances, the explanation of policy choices and the total cost of learning remain central questions for further work. The thesis provides implemented methods and a common basis for examining these questions across different search settings.
Keywords : Scheduling, machine learning, reinforcement learning, supervised learning, local search, branch-and-bound, learning to branch, decomposition methods.