Chemin critique par la methode pert

0/5 (2 avis)

Vue 26 801 fois - Téléchargée 1 582 fois

Description

Ce programme resoud le probleme du chemin critique (ordonnancement)

Source / Exemple :


/******************************/
/*   El Antri Abdellah        */
/*   Sous licence GNU         */
/******************************/

/*****************************/
/* Tester sous linux         */
/* compilation: cc ro.c -o ro*/
/* Execution: ./ro           */
/*****************************/

#include<stdio.h>
#include<math.h>
#include<stdlib.h>

#define MAX_INT 65535

#define max(x,y) x>y?x:y
#define min(x,y) x<y?x:y

typedef struct {int date_plutot, date_plutard, marge, num_tache;}tache;

tache *projet;
int **matrice;

int main()
{
int chemin[100];
int associe [100];
int som_ch = 0;
int nbr_tache;
int i,j,k;
int num_succ;
int nbr_succ;
int duree;
int som = 0;
int *pile;

printf("\n Donner le nombre des taches: ");
scanf("%d",&nbr_tache);

projet = (tache *)malloc((nbr_tache + 2) * sizeof(tache));
if(projet == NULL)
  {
  printf(" \n Impossible d'allouer de l'espace pour projet");
  exit(1);
  }
  else printf("\n Espace allouer avec succe");

matrice = (int **)malloc((nbr_tache + 2) * sizeof(int *));

for(i = 0; i < nbr_tache + 2; i++)
   {
   matrice[i] = (int *)malloc((nbr_tache + 2) * sizeof(int));	   
   }

for(i = 0; i < nbr_tache + 2; i++)
    for(j = 0; j < nbr_tache + 2; j++)
       {
	matrice[i][j] = -1;
       }
matrice[0][1] = 0;

pile = (int *)malloc((nbr_tache +2) * sizeof(int));

for(i = 1; i < nbr_tache ; i++)
   {
   printf(" \n Donner le nombre des taches qui vient apres %d:",i);
   scanf("%d",&nbr_succ);
   for(j = 0; j < nbr_succ; j++)
     {
     printf(" Donner le numero du successeur N %d:", j+1);
     scanf("%d", &num_succ);
     printf(" Donner la duree entre %d et %d: ", i , num_succ);
     scanf("%d", &duree);	     
     matrice[i][num_succ] = duree; 
     }
   }
matrice[nbr_tache][nbr_tache+1] = 1;

// date au plutot
projet[0].date_plutot = 0;

for(j = 1; j < nbr_tache + 2; j++)
   {
   projet[j].date_plutot = 0;
   for(i = 0; i < j; i++)
      {
      if(matrice[i][j] != -1)
         {
	 projet[j].date_plutot = max(projet[j].date_plutot,
			             projet[i].date_plutot + matrice[i][j]);
	 }
      }	      
   printf(" \n date_plutot de %d: %d", j, projet[j].date_plutot);
   }

printf("\n Tapper une touche ...");
scanf("%d", &i);
projet[nbr_tache+1].date_plutard = projet[nbr_tache+1].date_plutot;

// date au plutard
for(i = nbr_tache ; i >= 0; i--)
   {
   projet[i].date_plutard = MAX_INT;	   
   for(j = i + 1; j <= nbr_tache + 1; j++)
      {
      if(matrice[i][j] != -1)
        projet[i].date_plutard  = min (projet[j].date_plutard  -  matrice[i][j],
			               projet[i].date_plutard); 
      }	      
   printf(" \n date_plutard de %d: %d", i, projet[i].date_plutot);
   }
printf("\n Tapper une touche ...");
scanf("%d", &i);

// marges
for(i=0; i < nbr_tache +2; i++)
   {
    projet[i].marge = projet[i].date_plutard - projet[i].date_plutot;
    printf("\n La marge de %d: %d", i, projet[i].marge);
   }

printf("\n Tapper une touche ...");
scanf("%d", &i);

associe[som_ch] = -1;
pile[som] = 1;
som ++;
som_ch ++;

while(som > 0)
	{
	som --;
	i = pile[som];
	chemin[som_ch] = i;
	som_ch ++;
	for(j = i+1; j < nbr_tache + 2; j++)
   	  if(matrice[i][j] != -1)	
      	   {
      	   if(projet[i].marge == 0 && projet[j].marge == 0 )
        	{
		if(j != nbr_tache + 1)	
		   {
		   pile[som] = j;
		   associe[som] = i;
		   som++; 
		   }
                  else 
	             {
		     printf("\n ==> ");	     
		     for (k = 1; k < som_ch; k++)
			 printf(" %d ", chemin[k]);
		     for (k = 0; k < som_ch; k++)
		          if(som > 0 && chemin[k] ==  associe[som - 1])
			  {
			  som_ch = k + 1;
			  break;
			  }	
		     }		     
     	        }	
	   }
	}	

printf("\n");
return 0;
}

Conclusion :


C'est l'inplementation de l'algorithme PERT, pour vos questions suggestions contacter moi

Codes Sources

A voir également

Ajouter un commentaire Commentaires
markarove Messages postés 2 Date d'inscription lundi 18 septembre 2006 Statut Membre Dernière intervention 19 septembre 2006
19 sept. 2006 à 12:26
Pas mal, sans option mais il marche tres bien.
deck_bsd Messages postés 1243 Date d'inscription jeudi 31 mars 2005 Statut Membre Dernière intervention 3 août 2016 2
10 juil. 2006 à 15:33
RRaaaa comment oses-tu poster ça ???? lol je rigole ;) mauvais souvenir :p . Bonne source .

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.