Programmation dynamique du makespan (ordonnancement à une machine)

[lecomte009]

L'algorithme suivant permet d'ordonnancer un ensemble des taches I : { 1, 2, 3,.., n} sur une machines de façon à minimiser le temps la date de fin de la dernière tache. On donne la durée de chaque tache pi avec i varie de 1 à n, et ri : date de disponibilité qui signifie que une tâche ne peut démarrer avant cette tâche. avec i variant de 1à n .
Si C*est la solution optimale pour S de I alors :
C*(∅)=0 et C*(S)=min{max⁡〖(C*(S-{i});ri)+pi 〗 } si S ≠0
La solution du problème est par conséquent C*(I)
C* (S-{i}) est la date de fin du passé précédent la décision i

Algorithme à implémenter dans un langage
Entrée : I : Ensemble contenant mes tâches à ordonnancés
n : nombre de tâches
ri, pi : respectivement date de disponibilité et durée de la tâche
Variables intermédiaires : S est un sous ensemble de I
k, i, Min, Max : entiers
Sorties : C*(I)
Début :
C*(∅)=0
Pour k=1 à n
Pour tout sous ensemble S de I contenant k éléments de I
C*(S)=∞
Pour tout élément i de S
Si C*(S-{i})<= ri alors Max=ri
Sinon Max = C*(S-{i})
Min=Max + pi
Si Min<C*(S)alors C*(S)=Min
Fin pour
Fin pour
Fin pour
Fin


Mon souci se situe au niveau de la création ses sous ensembles S de I en langage C !! Si vous pouvez me donnez de l'aide à ce niveau je vous en serai reconnaissant soit en langage C ou tout autre langage!!! merci