Chemin critique par la methode pert

Soyez le premier à donner votre avis sur cette source.

Vue 23 754 fois - Téléchargée 1 348 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

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

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.