Key points are not available for this paper at this time.
Dans cet article, nous décrivons un algorithme de programmation entière pour allouer des ressources limitées à des activités concurrentes (jobs, tâches, etc.) d'un projet de manière à ce que le temps d'achèvement du projet soit minimal parmi tous les temps d'achèvement possibles. Typique de ces problèmes est la minimisation du temps d'achèvement des projets de type PERT/CPM où des limites sur la disponibilité des ressources obligent à retarder certaines activités pendant l'exécution du projet. Fait également partie de cette classe de problèmes pour laquelle notre procédure est applicable, l'affectation de travaux aux machines de manière à ce que le temps écoulé pour achever tous les travaux (makespan) soit un minimum sur toutes les affectations travaux-machine possibles. La procédure développée consiste en une évaluation systématique (énumération) de tous les temps de fin de travaux possibles pour chaque tâche du projet. Pour limiter le nombre d'affectations de tâches devant être explicitement évaluées, un artifice appelé coupe de réseau est développé, qui exclut de la considération l'évaluation des temps de fin de travaux qui ne peuvent pas conduire à un temps d'achèvement de projet réduit. Les résultats rapportés montrent que la procédure développée est une technique d'optimisation fiable pour des projets composés de 30 à 50 travaux et de trois types de ressources différents. La procédure est particulièrement applicable dans les cas où le stockage primaire sur ordinateur est limité. Beaucoup des mini-ordinateurs disponibles aujourd'hui sont capables de mettre en œuvre notre approche sans nécessiter de programmation étendue pour l'écriture sur un stockage auxiliaire, rendant ainsi la technique accessible au chef de projet dans les environnements où des ressources informatiques étendues pour la planification ne sont pas facilement disponibles.
Talbot et al. (Sat,) ont étudié cette question.