Planification de tâches avec fenêtre de disponibilité dans un contexte aléatoire

Contexte:
On s’intéresse à un problème dans lequel des tâches arrivent au cours du temps, de manière aléatoire et doivent être traitées. On doit décider du moment du traitement et de comment regrouper les tâches ensembles pour maximiser les gains. En effet, traiter plusieurs tâches ensembles coûte un seul traitement et rapporte les gains de toutes les tâches. Mais les tâches n’ont qu’une durée limitée de disponibilité. Pour trouver le meilleur planning global, on s’arrange pour résoudre plusieurs fois des petits plannings sans aucune part d’aléatoire afin d’approcher le résultat global [1].

Il existe de multiples manières de résoudre ces plannings déterministes, soit par de la Programmation Linéaire, soit par des heuristiques simples. Ajouter des méthodes de résolution à celles qui existent déjà et comparer les performances de ces nouvelles méthodes est la nouveauté. En effet, si la programmation linéaire donne le meilleur résultat en statique, il s’avère que son utilisation en pratique pose problème car son temps d’exécution est extrêmement long. On précise qu'ilexiste déjà un programme qui permet de planifier et d’estimer les performances des heuristiques pour le résultat global.

But :
Le but de ce projet serait d’ajouter deux heuristiques afin de comparer leurs performances statiques. Enfin après analyse du code existant du simulateur de les intégrer dans le simulateur et de comparer leurs performances dynamiques. Ces deux heuristiques sont basées sur des algorithmes de graphes: soit par un plus court chemin [2] soit par des cliques [3].

Ce projet est calibré pour 2 personnes

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

[3] V. Jost et al, « Batch processing with interval graph compatibilities between tasks », Discrete Applied Math 2008.
https://www.sciencedirect.com/science/article/pii/S0166218X0700114X