Pré-planification des tâches récurrentes

Question

Au travail, on nous donne un ensemble de contraintes de la forme (nom de tâche, fréquence), où fréquence est un nombre entier qui correspond au nombre de ticks entre chaque appel de la tâche "nom de tâche". Deux tâches ne peuvent pas être exécutées simultanément et chaque appel de tâche nécessite un tick pour se terminer. Notre objectif est de trouver le meilleur programme en termes de correspondance avec l'ensemble des contraintes.

Par exemple, si on nous donne les contraintes {(a, 2), (b, 2)}, le meilleur planning est "ab ab ab ...". Par contre, si on nous donne les contraintes ({a, 2}, {b, 5}, {c, 5}), le meilleur calendrier est probablement "abaca abaca abaca ..."

Actuellement, nous trouvons le meilleur programme en exécutant un algorithme génétique qui tente de minimiser la distance entre les fréquences réelles et les contraintes données. Cela fonctionne plutôt bien, mais je me demande s’il existe un algorithme qui convient mieux à ce genre de problème. J'ai essayé de chercher sur Google, mais les mots me manquent (la planification consiste généralement à effectuer des tâches :(). Pouvez-vous m'aider?

Answer 1

Tout d’abord, considérons le bien-fondé du commentaire de jldupont! :)

Deuxièmement, je pense que "période" est la description exacte du deuxième élément du tuple, par exemple. {Nom, point [icity]}.

Cela dit, regardez les algorithmes de mise en réseau. Une variante de la file d'attente pondérée est probablement applicable ici.

Par exemple, pour N tâches, créez N files d'attente correspondant aux tâches T0 ... Tn , et dans chaque cycle ("tick") en fonction de la période de la tâche, mettez un élément en file d'attente à la file d'attente correspondante.

L’algorithme du planificateur viserait alors à minimiser (en moyenne) le nombre total de serveurs dans les files d’attente. Un simple point de départ serait simplement de retirer de la file d'attente le quene Qx qui contient le plus grand nombre d'éléments. (Un paramètre sur l'élément en file d'attente indiquant "l'âge" faciliterait l'établissement des priorités.)