Beau petit problème de graph aujourd’hui. J’ai commencé par créer une class Step qui contient des références vers les autres étapes sur lesquelles elle dépend. La première partie a ensuite été résolue en bouclant et en annotant les étapes comme terminées jusqu’à ce que chaque étape soit complétée. Trouver la prochaine étape à compléter se traduit par un peu de LINQ pour déterminer la première étape incomplète (considérant une liste d’étape ordonnée alphabétiquement) pour laquelle toutes ses dépendances sont complètes:

var nextStep = steps.First(s => !s.IsCompleted && s.Requirements.All(r => r.IsCompleted));

Pour la seconde partie, j’ai pensé à plusieurs solutions possible et j’ai fini par utiliser une solution utilisant une simili-matrice comme l’exemple dans la description du problème. Ceci est fait en assignant une étape disponible à chaque travailleur au repos, augmenter le temps d’une seconde et recommencer jusqu’à ce que toutes les étapes soient complétées.

Une autre solution possible pourrait être d’utiliser une file de priorité pour déterminer la prochaine étape qui sera complétée, réduire le temps pour toutes les autres tâches en train de rouler et commencer la prochaine étape tant qu’il y a des travailleurs disponibles. Cette solution pourrait être implémentée sans créer une classe Worker comme j’ai fait.

Une autre approche pourrait avoir les travailleurs pousser des évènements lorsque leur tâche est complète et un handler d’évènement pour lui assigner la prochaine tâche disponible. Cette approche est similaire à ce qui est fait dans les programmes de scédulation de tâches, comme ceux utilisés sur des machines de calcul par exemple. Comme les étapes ici sont fictives, implémenter cette approche impliquerait créer des tâches fictives à compléter (tel que simplement attendre ou observer un compteur), donc ça demanderait plus de travail que les solutions plus simples.