NEH heuristique programmé en c
cocc_12
Messages postés
3
Statut
Membre
-
cocc_12 Messages postés 3 Statut Membre -
cocc_12 Messages postés 3 Statut Membre -
bonsoir tous le monde,
si c est possible de m aider a traduir l algorithme de Nawaz, Enscort et ham en C . voila une definition de l algorithme .
NEH est une heuristique "générique" qui peut s'adapter à de nombreux problème : la meilleure insertion. Lorsque l'on cherche une séquence (un cycle dans le cas du voyageur de commerce), on classe les objets à trier selon un critère donné, puis on les prend les uns après les autres et on les insère à la meilleure place possible dans la séquence en construction.
La complexité de cet algorithme est en O(n2) puisque à chaque insertion k(il y en a n) il y a de l'ordre de kinsertions à essayer.
Pour le Flow shop, l'algorithme est le suivant:
*Classer les jobs par ordre de mj=1pijdécroissants.
* Considérer une séquence initiale avec le premier.
* Tant qu'il reste des jobs, prendre le premier et le placer à la meilleure place possible dans la séquence courante.
*fin
si c est possible de m aider a traduir l algorithme de Nawaz, Enscort et ham en C . voila une definition de l algorithme .
NEH est une heuristique "générique" qui peut s'adapter à de nombreux problème : la meilleure insertion. Lorsque l'on cherche une séquence (un cycle dans le cas du voyageur de commerce), on classe les objets à trier selon un critère donné, puis on les prend les uns après les autres et on les insère à la meilleure place possible dans la séquence en construction.
La complexité de cet algorithme est en O(n2) puisque à chaque insertion k(il y en a n) il y a de l'ordre de kinsertions à essayer.
Pour le Flow shop, l'algorithme est le suivant:
*Classer les jobs par ordre de mj=1pijdécroissants.
* Considérer une séquence initiale avec le premier.
* Tant qu'il reste des jobs, prendre le premier et le placer à la meilleure place possible dans la séquence courante.
*fin
2 réponses
-
Bonjour,
En quoi pouvons-nous t'aider ?
Quelles sont tes questions ?
Qu'as-tu commencé à faire ?
Où bloques-tu ? -
bonsoir,
voila une definition de NEH houristic d apres le site de wikipedia https://fr.wikipedia.org/wiki/Flow-shop et j'aimerais avoir cette algorithme en C si c possible merci fiddy pour votre soutien . je veux implementer cette fonction dans un autre proogramme.-
-
merci fiddy.
voila mon code.:
travail.c
void travail(int tn,int trav[tn])
{
int i;
for(i=0;i<tn;i++)
{
trav[i]=selection(2);
//remplacer par trav[i]=selection(1)
//printf("%d",trav[i]);
}
}
selection.c
int random = 0 ;
int selection(int valeur)
{
int resultat;
srand(random += time(NULL));
resultat=((rand()+1)%(valeur));
return resultat;
}
main.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "selection.c"
#include "travail.c"
const n=5;
const machine=4;
int main ()
{
int i,j,pij[n],job=0,stock;
int trav[n];
int travaux[machine][n];
//Matrice
for(j=0;j<machine;j++)
{
job=0;
travail(n,&trav);
for(i=0;i<n;i++)
{
travaux[j][i]=trav[i];
if(travaux[j][i]==1) job++;;
printf("%d",travaux[j][i]);
}
pij[j]=job;
printf("pij=%d\n",pij[j]);
}
//tri
if(pij[0]<=pij[1])
{
stock=pij[0];
pij[0]=pij[1];
pij[1]=stock;
}
printf("pij[0]=%d et pij[1]=%d",pij[0],pij[1]);
return 0;
}
voila Mr fiddi jusqu' ici c bon ,si vous permettez me reste la derniere ligne de l algorithme :
inserer le travail i dans la position k.......(voir le lien de wikipedea) merci d 'vance
-
