Planification de tâches aléatoires avec fenêtres de disponibilité

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 des problème d'affectation de tâches à des ressources dans un cadre aléatoire 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.

Plus précisément, 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 durant laquelle elle peut être traitée. 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. On cherche donc à définir un algorithme d’ordonnancement pour minimiser le coût moyen.

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. 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.

Lieu: 
LIP6
Encadrant: 
emmanuel.hyon@lip6.fr
Co-Encadrant: 
claire.hanen.lip6.fr
Référent Universitaire: 
n/a
Attribué: 
No
Année: 
2 024

User login