Algorithme de planification

Question

J'ai un problème de planification où les nouveaux travaux (ensembles de tâches dont l'exécution est séquentiellement connectée) arrivent toutes les quelques secondes environ.
Chaque travail nécessite l'allocation de ressources à des intervalles connus.
Par exemple:
Job j1 est un ensemble de tâches pour lesquelles nous réserver des ressources {r1, r2, r3} sur un modèle de planification connu:

r1:[t0 .. t1=t0+td1], 
r2:[t2=t1+td2+i2 .. t3=t2+td3] 

• t0 étant l'heure de début de l'exécution
• TD1 est la longueur de l'allocation de ressources pour r1
• t1 étant l'heure de fin de l'allocation de ressources pour r1
• i1 est la longueur de le péritoide en attente entre r1, r2 et ainsi de suite.

Dans l'exemple, est prévue juste après l'exécution de j1 a commencé une nouvelle j2 d'emploi. L'heure de début la plus précoce pour j2 est t1. Un travail peut prendre quelques minutes d'exécution dont la plupart consiste à attendre. J'ai un planificateur qui regarde la table de réservation actuelle et décide quel est le moment de départ le plus tôt possible pour un nouveau travail avec des temps d'allocation et des périodes d'attente fixes et effectue les réservations en conséquence. (En réalité, la période d'attente n'a pas vraiment besoin d'être corrigée - mais dans un certain pourcentage (peut-être 5%) et il peut y avoir des alternatives à l'utilisation des ressources, par exemple, si la ressource r3.1 est réservée, Cependant, si le planificateur est nécessaire (oui, il a été suggéré) de pouvoir ajuster dynamiquement toutes les allocations de planification lorsqu'un nouveau travail arrive pour maximiser le travail total fait (en un jour) en profitant du fait que les temps d'attente ne doivent pas être exactement comme donnés et la possibilité d'exécution parallèle avec quelques doublons de resrouce (3.1/3.2), alors je regarderais un complètement différent schéma d'ordonnancement (que mon approche actuelle du début-comme-possible-possible).

1. Quel schéma de programmation appelleriez-vous alors?
2. Des suggestions sur l'approche du (nouveau) problème?

Answer 1

Quant à votre question concernant les « alternatives à une utilisation des ressources »:

Le modèle le plus couramment mis en œuvre pour lutter contre ce genre de problème est le Object Pool Pattern
L'exemple le plus largement connu pour ce qui est probablement le ThreadPool

Je vous suggère de mettre en œuvre une classe ResourcePool avec une méthode int GetResource(ResourceType type, int durationInSeconds). La valeur de retour indique quand la ressource suivante de ResourceType sera disponible

Answer 2

Vous pourriez avoir affaire au RCPSP (Resource Contrained Project Scheduling Problem). Les techniques de la solution vont de la programmation d'entiers et de la programmation de contraintes à diverses heuristiques.La technique dépend des détails tels que l'horizon de planification, comment les tâches/emplois utilisent/partager des ressources, la façon dont vous avez besoin rapidement un calendrier de solution, etc.

voir:

https://developers.google.com/optimization/scheduling/job_shop

http://www.laas.fr/files/ROC/2014-Presentations/MILP-RCPSP-PMS2014.pdf