Le 12/12/2023 par Claire Hanen :

Contexte :
Le problème considéré est un problème générique relatif à l’ordonnancement de tâches (c’est à dire
au calcul et à la fixation des dates de traitements des tâches) en contexte incertain. Chaque tâche, a
une fenêtre de temps caractérisée par une date de disponibilité, et une date d’échéance durant
laquelle elle peut être traitée. Si la tâche n’est pas traitée durant cette fenêtre elle est alors perdue
engendre un coût. L’autre spécificité est que les tâches ne sont pas connues en avance mais qu’elles
arrivent au cours du temps de manière aléatoire et que leur date de disponibilité est également
aléatoire. On cherche donc à définir un algorithme d’ordonnancement pour minimiser le coût
moyen.
La prise en compte de l’aléatoire dans des contextes d’ordonnancement est une thématique de plus
en plus présente aussi bien dans le monde académique qu’économique. Ainsi, la résolution de ce
problème présente un intérêt théorique notable car il n’existe pas, à ce jour, d’approche qui puisse
calculer l’optimum global.
Par ailleurs, ce type de problème trouve de nombreuses applications pratiques dans des domaines
variés. En santé (pour le planning de salle d’opération), en transport (pour l’acheminement des
données périssables), dans l’industrie (avec des échéances de production en réponse à des contrats),
par exemple.
Cadre et travail demandé :
Pour trouver le meilleur planning global, on résout à chaque pas de temps des sous-problèmes
déterministes sur un court intervalle de temps afin d’approcher le résultat [1]. On appelle cela
l’horizon roulant. L’enjeu est donc de trouver des algorithmes de résolution des problèmes
d’ordonnancement sous-jacents déterministes qui soient rapides et efficaces et ensuite de les évaluer
(en les simulant) pour connaître leurs performances en moyenne afin de déterminer le meilleur. Le
but de ce stage est de travailler sur des heuristiques déterministes pour résoudre les plannings et
d’inclure les algorithmes dans un logiciel de simulation existant développé en JAVA.
Les actions à réaliser seront :

• prise en main du problème et du simulateur ;
• recherche théorique sur les heuristiques, en s’inspirant de [2] et [3] ;
• implémentation des heuristiques ;
• évaluation des performances des heuristiques par rapport à une estimation du minimum
• global obtenu avec des techniques issues de l’IA comme les Monte Carlo Tree Search.

Conditions du stage et candidatures
Durée 5 à 6 mois
Gratification environ 580 euros par mois.
Lieu LIP6, Paris
Encadrants (et contacts) claire.hanen@lip6.fr et emmanuel.hyon@lip6.fr
Les candidats auront des compétences avérées en JAVA et en Recherche Opérationnelle
Envoyer CV et relevé de notes aux deux encadrants.
Bibliographie
[1] N. Benammar, Ph. Chrétienne, E. Hyon, A. Jean-Marie : “Approches par horizon roulant pour
un problème de planification stochastique”, ROADEF 2020.
https://hal.archives-ouvertes.fr/hal-02967919/document.
[2] Q. Liu et al, « Algorithms for the variable-sized bin packing problem with time windows ».
Computers & Industrial Engineering Volume 155, May 2021
https://www.sciencedirect.com/science/article/abs/pii/S0360835221000796?via%3Dihub
[3] V. Jost et al, « Batch processing with interval graph compatibilities between tasks », Discrete
Applied Math 2008.
[4] Philippe Baptiste, Philippe Chrétienne, Jie Meng-Gerard, Francis Sourd. On maximizing the
profit of a satellite launcher: selecting and scheduling tasks with time windows and setups. Discrete
Applied Mathematics, 2009, 157 (17), pp.3656-3664.