Condition nécessaire utilisant le raisonnement énergétique pour un problème d'ordonnancement à contraintes énergétiques
Résumé
Le problème que nous avons étudié est un problème d'ordonnancement avec une ressource continue et des contraintes énergétiques, le CECSP. Dans ce problème, étant donné une ressource de capacité limitée et un ensemble de tâches, nous voulons trouver un ordonnancement tel que chaque tâche utilise une quantité de la ressource comprise entre une valeur minimale et une valeur maximale et soit exécutée dans sa fenêtre de temps. De plus, chaque tâche possède une demande en énergie et nous voulons apporter à chacune d'entre elles une énergie au moins égale à celle demandée. Dans notre cas, l'énergie fournie à une tâche est une fonction de la quantité de la ressource allouée à celle-ci.
Ce problème est en fait une généralisation d'un problème préexistant : le problème d'ordonnancement cumulatif (CuSP). CECSP est donc NP-difficile. Pour CuSP, une condition nécessaire et calculable en temps polynomial a été développé. Cette condition utilise une technique appelée raisonnement énergétique. Pour notre problème, le cas où la fonction permettant le calcul de l'énergie est la fonction identité ayant déjà été traitée, nous avons adapté ce test pour le cas où celle-ci est soit linéaire soit linéaire par morceaux.
La continuité de la ressource pour CECSP ne permettant pas l'application des techniques de propagation préexistantes, la mise en œuvre d'une condition nécessaire pour ce problème est donc un résultat intéressant.