Planification avec des ressources variables

Question

(Tout d'abord, désolé pour mon anglais, ce n'est pas ma langue maternelle)

J'ai une liste de tâches/emplois, chaque tâche doit commencer après une heure de début, a besoin de fonctionner pour un certain temps et doit être terminé après une certaine heure de fin.

Je peux dynamiquement ajouter et supprimer des travailleurs, il est donc possible d'exécuter 2 tâches ou plus en même temps si nécessaire. Mon objectif est de trouver un plan de planification qui exécute chaque travail avec succès et utilise le minimum de travailleurs possible. J'utilise actuellement un algorithme EDF (http://en.wikipedia.org/wiki/Earliest_deadline_first_scheduling) et j'appelle récursivement la fonction avec une limite de travail plus élevée si elle ne peut pas planifier tous les travaux correctement, mais je pense que cela ne fonctionne pas correctement parce que je n'ai pas un vrai moyen de mesurer quand je peux à nouveau réduire la limite de ressources.

Y a-t-il des algorithmes qui fonctionnent pour mon problème, ou d'autres idées intelligentes?

Merci pour votre aide.

Answer 1

Un problème de planification peut souvent être résolus de façon très efficace en formulant soit comme programme entier mixte (MIP)

http://en.wikipedia.org/wiki/Mixed_integer_programming#Integer_unknowns

ou d'exprimer à l'aide de la programmation par contraintes (CP)

http://en.wikipedia.org/wiki/Constraint_programming

Pour MIP ou CP, vous trouverez des solveurs gratuits et commerciaux qui peuvent résoudre votre problème.

Dans ces deux approches, vous vous efforcez d'indiquer les propriétés que la solution doit posséder, et le travail ardu d'application d'un algorithme approprié est laissé à un solveur spécialisé.