Discussion :

[logo98]

Bonjour,

L'algorithme suivant permet d'ordonnancer un ensemble des taches j{ j1, j2, j3,.., jn} sur m machines{m1, m2} de façon à minimiser le temps la date de fin de la dernière tache. On donne la date début de chaque tache rj avec j varie de 1 à n, qj :dae de fin souhaitée avec j varie de 1 à n et pj : période d'éxécution de tache j avec j varie de 1 à n. J est l'ensemble des taches ordonnacées qui seront exécutées dans leur date. jR : l'ensemble de taches qui débutent l'ordonnancement. jQ: les taches qui seront placées en dernier. ù0 : la date sur la machine, j0 : la tache qui sera placé dans jR ou jQ selon la condition et σ: l'ordonnancement final optimal
Voici le pseudo-code de la première partie puis la deuxième partie en anglais




Je l'ai ré-écris ci-dessous en se basant sur son pseudo-code pour pouvoir l'implémenter en langage c.
Je suis débutant en matière d'algorithme.
J'aurais aimé savoir si mon algorithme est correcte? Y a t-il d'erreurs de forme ou autre?
Par avance, merci

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Entrées : pj,rj,qj, j0 appartient à {j1, .., jm}, u0
Sorties : s
 
début
  J = 0, jR= 0 et jQ=0
  Tant que | J | => m faire  
    Si rj0+ pj0  <= rj(n+1)   alors   J  =  J \{ j0} &&  jR= jR U j0
    Sinon  
      Si qj0+ pj0  <= qj(n+1)   alors   J  =  J \{j0} } && jQ= jQU j0
      Fin si
    Fin si
  Fin tant que
  u0 = min ui (  s  )
  Si  jQ #0
    Si pj0 + qj0 =max(pj + qj) alors
      jQ=j0
      u0 =max(u0,rj0)+pj0
      s=s-1
    Fin si
  Fin si
  u0 = min ui(    s   )
  Si jR#0
    Si pj0+rj0=max(pj +rj) alors
      jR=j0
      u0 =max(u0,qj0)+pj0
      s=s-1
    Fin si
  Fin si

[Furikawari]

Hem, il me semble que c'est à toi de faire cette vérification... Méthode : tu te crées un problème, tu appliques à la main l'algo de la publi, tu fais tourner ton code dessus et tu vérifies que les résultats correspondent (ou encore mieux tu le fais en TDD).

PS : il semble qu'il manque le step 3.