LIP6 2002/013

• Rapports de recherche «Ordonnancer une séquence de tâches au moindre coût»
• F. Sourd
• 14 pages - 27/05/2002 - document en - http://www.lip6.fr/lip6/reports/2002/lip6.2002.013.pdf 228 Ko
• Contact Francis.Sourd (at) nulllip6.fr
• Ancien Thème : SYSDEF
Ordonnancer une séquence de tâches, c'est-à-dire trouver les dates d'exécution, n'est pas un problème trivial quand le critère d'optimisation n'est pas régulier tels dans les problèmes avec coûts d'avance et de retard. Cet article présente un algorithme de programmation dynamique efficace pour résoudre le problème avec des coûts qui sont fonction des dates d'exécution, des coûts d'inactivité et des durées dépendant aussi des dates d'exécution des tâches. L'algorithme marche également lorsque le graphe de précédence est un arbre et il peut être adapté pour déterminer pour chaque tâches les fenêtres de temps d'exécution possibles lorsque le coût total est borné.