idée d'algorithme d'affectation en c
2 participants
Forum INFOMATH :: Enseignement de l'informatique :: INFO - Supérieur (Etudiants et Professionnels) :: C/C++
Page 1 sur 2
Page 1 sur 2 • 1, 2
idée d'algorithme d'affectation en c
Bonjour,
En fait, le problème consiste à placer n taches sur m machines pour minimiser les retards totaux.
La règle est la suivante : placer la tache dont la durée d'exécution est la plus petite à la machine disponible.
A chaque fois on doit calculer le retard "T" de chaque tache (formule
est la suivante : date de fin d'exécution de la tache déterminer après
affectation des taches sur les machines "c" -date de fin au plus tard
de la tache "d") : T= c - d.
Ce qui est demandé :
1) écrire un programme en c qui permet de trier les taches par durée d'exécution croissant: c'est fait!
2) écrire un programme en c qui permet de placer les taches sur les machines pour calculer les retards totaux selon la formule donnée ci-dessus.
Là, je me bloque . Je n'arrive pas à le faire
Pourriez vous me donner un coup d'aide?
Merci!
Voici un exemple pour mieux assimiler:
soit
Code : Autre
1)
séquence de tache (3,4,1,6,2,5)
2)
manuellement
sur m1 : les taches 3, 5
sur m2 : les taches 4, 2
sur m3 : les taches 1, 6
retards :
T1 :3-12<0->T1=0 (retard ne peut pas être négatif)
T2 : 10-5=5->T2=5
T3: 7-7=0
T4:5-10<0
T5:17-6=11
T6:7-8<0
T retards totaux: 5+11=16
En fait, le problème consiste à placer n taches sur m machines pour minimiser les retards totaux.
La règle est la suivante : placer la tache dont la durée d'exécution est la plus petite à la machine disponible.
A chaque fois on doit calculer le retard "T" de chaque tache (formule
est la suivante : date de fin d'exécution de la tache déterminer après
affectation des taches sur les machines "c" -date de fin au plus tard
de la tache "d") : T= c - d.
Ce qui est demandé :
1) écrire un programme en c qui permet de trier les taches par durée d'exécution croissant: c'est fait!
- Code:
#include
#include
typedef struct
{
int release_date;
int duree;
int due_date;
}tache;
void selection(tache job[], int *tab_indices, int nbrejob)
{
int i, min, j ;
tache x;
if (tab_indices)
for (i=0;i
tab_indices[i] = i;
for(i = 0 ; i < nbrejob-1 ; i++)
{
min = i;
for(j = i+1 ; j < nbrejob ; j++)
if(job[j].duree < job[min].duree)
min = j;
if(min != i)
{
x = job[i];
job[i] = job[min];
job[min] = x;
int indice = tab_indices[i];
tab_indices[i] = tab_indices[min];
tab_indices[min] = indice;
}
}
}
int main()
{
tache job[6]={{0,10,18},{3,6,15},{2,4,22},{4,9,23},{6,2,14},{5,6,12}};
int k;
int tab_indices[6];
selection(job,tab_indices, 6);
printf("voici les durees ordonnancees par ordre croissant :\n");
for (k=0;k<6;k++)
printf("%d",job[k].duree);
printf("\n");
printf("voici la sequence de job:\n");
for(k=0;k<6;k++)
{
printf("%d",tab_indices[k]);
}
for(k=3;k<5;k++)
{
c[k]=job[k].duree+job[k].release_date;
printf("%d\n",c[k]);
}
return 0;
}
2) écrire un programme en c qui permet de placer les taches sur les machines pour calculer les retards totaux selon la formule donnée ci-dessus.
Là, je me bloque . Je n'arrive pas à le faire
Pourriez vous me donner un coup d'aide?
Merci!
Voici un exemple pour mieux assimiler:
soit
Code : Autre
1 2 3 4 5 | 6 taches : j1, j2, j3, j4, j5, j6 3 machines : m1, m2, m3 durée d'exécution : 3, 6, 1, 2, 10, 4 d : 12, 5, 7, 8, 10, 6, 18 r(date de début de la tache, nécessaire pour placer les taches sur la machine) : 0, 1, 6, 3, 9, 12 |
1)
séquence de tache (3,4,1,6,2,5)
2)
manuellement
sur m1 : les taches 3, 5
sur m2 : les taches 4, 2
sur m3 : les taches 1, 6
retards :
T1 :3-12<0->T1=0 (retard ne peut pas être négatif)
T2 : 10-5=5->T2=5
T3: 7-7=0
T4:5-10<0
T5:17-6=11
T6:7-8<0
T retards totaux: 5+11=16
Invité- Invité
Re: idée d'algorithme d'affectation en c
Bienvenue au forum.
Il s'agit d'un problème d'affectation de tâches à des machines dont le but de minimiser le retard global.
D'abord, je dois te poser une question.
Quels sont les paramètres d'une tâche?
- durée de la tâche?
- ... compléter
Quels sont les paramètres d'une machine?
- état (disponible, occupée)
- ... compléter s'il y en a encore
Est-ce que tu dois appliquer un algorithme d'affectation bien connu dans la littérature (il y en a: voir wikipedia), ou bien tu dois inventer un nouvel algo?
Il s'agit d'un problème d'affectation de tâches à des machines dont le but de minimiser le retard global.
D'abord, je dois te poser une question.
Quels sont les paramètres d'une tâche?
- durée de la tâche?
- ... compléter
Quels sont les paramètres d'une machine?
- état (disponible, occupée)
- ... compléter s'il y en a encore
Est-ce que tu dois appliquer un algorithme d'affectation bien connu dans la littérature (il y en a: voir wikipedia), ou bien tu dois inventer un nouvel algo?
Napoléon- Admin
-
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 7673
Date d'inscription : 19/03/2007
Feuille de personnage
Capacité linguistique:
(999/1000)
Re: idée d'algorithme d'affectation en c
Merci pour votre réponse.
les paramètres d'une tache:
-durée
-date de début
paramètres d'une machine :
-date de disponibilité
En fait , la règle d'affectation est la suivante : chaque fois une tache est terminée placer la tache suivante sur la machine disponible.
A la date t= 0, disponibilité de machine =0
A la date t, disponibilité de machine = durée+date de début
voilà j'espère que vous pourriez me donner une idée pour faire cet algorithme!
Merci d'avance.
les paramètres d'une tache:
-durée
-date de début
paramètres d'une machine :
-date de disponibilité
En fait , la règle d'affectation est la suivante : chaque fois une tache est terminée placer la tache suivante sur la machine disponible.
A la date t= 0, disponibilité de machine =0
A la date t, disponibilité de machine = durée+date de début
voilà j'espère que vous pourriez me donner une idée pour faire cet algorithme!
Merci d'avance.
Invité- Invité
Re: idée d'algorithme d'affectation en c
il faut distinguer entre les paramètres et les variables de décision.
J'aurais du l'expliquer.
j'entends par "paramètres" tout ce qui possède déjà une valeur, comme par exemple, la durée d'une tâche. C'est très spécifique à la tâche. Par contre, la date de début d'une tâche n'est pas un paramètre, c'est une variable de décision, puisqu'on ne la connait pas d'avance. On doit la chercher. Et c'est ça l'objectif (entre autres) de l'algorithme d'affectation.
Alors, on reprend:
Pour une tâche, on connait:
- sa durée d'exécution
- son état: (en attente d'affectation, en cours d'exécution, terminée)
et on cherche:
- sa date début
- à quelle machine elle est affectée
Pour une machine, on connait:
- s'il est disponible ou non,
- si elle n'est pas disponible, à quel instant elle le sera,
et on cherche:
- suite de tâche à placer sur la machine
Tu confirmes?
J'aurais du l'expliquer.
j'entends par "paramètres" tout ce qui possède déjà une valeur, comme par exemple, la durée d'une tâche. C'est très spécifique à la tâche. Par contre, la date de début d'une tâche n'est pas un paramètre, c'est une variable de décision, puisqu'on ne la connait pas d'avance. On doit la chercher. Et c'est ça l'objectif (entre autres) de l'algorithme d'affectation.
Alors, on reprend:
Pour une tâche, on connait:
- sa durée d'exécution
- son état: (en attente d'affectation, en cours d'exécution, terminée)
et on cherche:
- sa date début
- à quelle machine elle est affectée
Pour une machine, on connait:
- s'il est disponible ou non,
- si elle n'est pas disponible, à quel instant elle le sera,
et on cherche:
- suite de tâche à placer sur la machine
Tu confirmes?
Napoléon- Admin
-
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 7673
Date d'inscription : 19/03/2007
Feuille de personnage
Capacité linguistique:
(999/1000)
Re: idée d'algorithme d'affectation en c
excusez moi
date de début de tache souhaité est une donnée en fait, ol la connait.
Voilà!
date de début de tache souhaité est une donnée en fait, ol la connait.
Voilà!
Invité- Invité
Re: idée d'algorithme d'affectation en c
OK. Donc comment tu vois la façon avec laquelle doit-se présenter une solution à ce problème ? (autrement dit: la structure de données du résultat)
Napoléon- Admin
-
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 7673
Date d'inscription : 19/03/2007
Feuille de personnage
Capacité linguistique:
(999/1000)
Re: idée d'algorithme d'affectation en c
nabiL a écrit:OK. Donc comment tu vois la façon avec laquelle doit-se présenter une solution à ce problème ? (autrement dit: la structure de données du résultat)
c'est une liste.
Je n'en suis pas sûr
Invité- Invité
Re: idée d'algorithme d'affectation en c
Salut,
Je ne vois pas quelle structure de données pour les machines?
Je ne vois pas quelle structure de données pour les machines?
Invité- Invité
Re: idée d'algorithme d'affectation en c
On peut avoir comme structure de données d'une solution du problème:
La solution finale est un tableau contenant "n" affectations où "n" est le nombre de tâches.
Statiquement:
ou dynamiquement:
- Code:
struct AFFECTATION
{
int num_tache;
int num_machine;
int date_debut;
}
La solution finale est un tableau contenant "n" affectations où "n" est le nombre de tâches.
Statiquement:
- Code:
AFFECTATION[n] solution;
ou dynamiquement:
- Code:
solution = (AFFECTATION*) malloc(sizeof(AFFECTATION) * n);
Napoléon- Admin
-
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 7673
Date d'inscription : 19/03/2007
Feuille de personnage
Capacité linguistique:
(999/1000)
Re: idée d'algorithme d'affectation en c
Merci pour votre réponse.
voici mon code. Il ne compile pas!Je ne vois pas où le problème!!
voici mon code. Il ne compile pas!Je ne vois pas où le problème!!
- Code:
#include
#include
typedef struct
{
int date_debut;
int duree;
}tache;
typedef struct
{
int tab_indices[6];/*liste des taches par priorité*/
int num_machine;
int datee_debut;
}affectation;
void selection(tache job[], int *tab_indices, int nbrejob)
{
int i, min, j ;
tache x;
if (tab_indices)
for (i=0;i
tab_indices[i] = i;
for(i = 0 ; i < nbrejob-1 ; i++)
{
min = i;
for(j = i+1 ; j < nbrejob ; j++)
if(job[j].duree < job[min].duree)
min = j;
if(min != i)
{
x = job[i];
job[i] = job[min];
job[min] = x;
int indice = tab_indices[i];
tab_indices[i] = tab_indices[min];
tab_indices[min] = indice;
}
}
}
void affectation_m( tache job[], affectation machine[],int num_machines)
{
int k ;
for(k=0;k<6;k++)
{
if(job[k].duree+job[k].date_debut
printf("%d",machine[k].num_machine);
printf("%d", machine[k].tab_indices);
}
int main()
{
tache job[6]={{0,10,18},{3,6,15},{2,4,22},{4,9,23},{6,2,14},{5,6,12}};
int k;int num_machine;
int tab_indices[6];
selection(job,tab_indices, 6);
printf("****voici les durees ordonnancees par ordre croissant :\n");
for (k=0;k<6;k++)
printf("%d",job[k].duree);
printf("\n");
printf("**** voici priority list:\n");
for(k=0;k<6;k++)
{
printf("%d",tab_indices[k]);
}
affectation_m(job, machine, 3);
return 0;
}
Invité- Invité
Re: idée d'algorithme d'affectation en c
Jusqu'à maintenant je ne t'ai pas donné une solution du problème.
Tout ce que j'essaie de faire c'est de comprendre d'une façon interactive de quoi il s'agit.
L'idéal c'est que tu arrives à résoudre le problème tout seul.
Pourquoi cet attribut?
Tout ce que j'essaie de faire c'est de comprendre d'une façon interactive de quoi il s'agit.
L'idéal c'est que tu arrives à résoudre le problème tout seul.
Pourquoi cet attribut?
- Code:
int tab_indices[6];/*liste des taches par priorité*/
Napoléon- Admin
-
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 7673
Date d'inscription : 19/03/2007
Feuille de personnage
Capacité linguistique:
(999/1000)
Re: idée d'algorithme d'affectation en c
Merci encore pour votre aide. Je suis débutant en la matière et j'ai essayé de résoudre le problème tout seul mais je ne parviens pas. C'est pour cela j'ai besoin de votre coup d'aide.
cet attribut donne l'ordre par priorité des taches (le bout de code que j'ai postulé au début permet de faire ca);
En attente de votre réponse, merci encore.
cet attribut donne l'ordre par priorité des taches (le bout de code que j'ai postulé au début permet de faire ca);
En attente de votre réponse, merci encore.
Invité- Invité
Re: idée d'algorithme d'affectation en c
D'abord, il faut comprendre l'exercice, et identifier ce qui est demandé, et comment va se passer l'interaction avec l'utilisateur: qu'est-ce qui est à saisir? qu'est-ce qui à calculer? etc...
Il faut saisir :
1) un tableau de "n" tâches. Une tâche = (id_tache, durée d'exécution)
2) un tableau de "m" machine. Une machine = (id_machine). id_machine peut être une chaine de caractère de taille 2 par exemple, puisque l'exercice mentionne déjà des noms de machines "m1", "m2" etc...
Il faut retourner :
1) un tableau de "n" affectations. Une affectation est équivalente au triplet suivant: (id_tache, id_machine, date_début)
La squelette du programme solution est plus au moins claire maintenant. Les fonctions suivantes doivent être développées:
Des commentaires?
Il faut saisir :
1) un tableau de "n" tâches. Une tâche = (id_tache, durée d'exécution)
2) un tableau de "m" machine. Une machine = (id_machine). id_machine peut être une chaine de caractère de taille 2 par exemple, puisque l'exercice mentionne déjà des noms de machines "m1", "m2" etc...
Il faut retourner :
1) un tableau de "n" affectations. Une affectation est équivalente au triplet suivant: (id_tache, id_machine, date_début)
La squelette du programme solution est plus au moins claire maintenant. Les fonctions suivantes doivent être développées:
- Code:
TACHE* saisir_taches(int* n)
MACHINE* saisir_machines(int* m)
AFFECTATION* affecter(int n,TACHE* taches, int m, MACHINE* machines)
int CALCULE_RETARD(int n, TACHE* taches, int m, MACHINE* machines, AFFECTATION* affect)
Des commentaires?
Napoléon- Admin
-
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 7673
Date d'inscription : 19/03/2007
Feuille de personnage
Capacité linguistique:
(999/1000)
Re: idée d'algorithme d'affectation en c
Je n'ai pas bien compris le prototype
- Code:
AFFECTATION* affecter(int n,TACHE* taches, int m, MACHINE* machines)
Invité- Invité
Re: idée d'algorithme d'affectation en c
assir a écrit:Je n'ai pas bien compris le prototype?
- Code:
AFFECTATION* affecter(int n,TACHE* taches, int m, MACHINE* machines)
La fonction "affecter" permet d'affecter les "n" tâches aux "m" machines. Elle doit retourner un tableau contenant les "n" affectations. Ce tableau est de type "AFFECTATION*".
Napoléon- Admin
-
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 7673
Date d'inscription : 19/03/2007
Feuille de personnage
Capacité linguistique:
(999/1000)
Re: idée d'algorithme d'affectation en c
Je pense qu'il faut calculer la date de disponibilité de la machine , non?
Peut-etre j'ai mal exprimé dans mes posts précedents, on résume :
D'où:
tache :
-durée
-date_debut
-id_taches
machine :
-indice_machine
-date_disponibilite
pour k=0,k=2 /*k compteur machine*/
printf("tache1 sur m1, tache 2 sur m2et tache3 sur m3%d %d",id_taches[k],id_machine[k]);
pour(k=0;k<2;k++)
{
pour(i=0;i<6;k++)
{
date_disponibilite[k]=tache[i].duree +tache[i].date_debut
si(date_disponibilite[k]<date_disponibilite[k+1])
alors
printf("%d %d",id_taches[i],id_machine[k]);
}
}
end
est ce que cet algo est faisable
Peut-etre j'ai mal exprimé dans mes posts précedents, on résume :
D'où:
tache :
-durée
-date_debut
-id_taches
machine :
-indice_machine
-date_disponibilite
pour k=0,k=2 /*k compteur machine*/
printf("tache1 sur m1, tache 2 sur m2et tache3 sur m3%d %d",id_taches[k],id_machine[k]);
pour(k=0;k<2;k++)
{
pour(i=0;i<6;k++)
{
date_disponibilite[k]=tache[i].duree +tache[i].date_debut
si(date_disponibilite[k]<date_disponibilite[k+1])
alors
printf("%d %d",id_taches[i],id_machine[k]);
}
}
end
est ce que cet algo est faisable
Invité- Invité
Re: idée d'algorithme d'affectation en c
- Code:
#include <stdio.h>
#include <stdlib.h>
typedef struct
{
int date_debut;
int duree;
}tache;
void selection(tache job[], int *id_taches, int nbrejob)
{
int i, min, j ;
tache x;
if (id_taches)
for (i=0;i<nbrejob;i++)
id_taches[i] = i;
for(i = 0 ; i < nbrejob-1 ; i++)
{
min = i;
for(j = i+1 ; j < nbrejob ; j++)
if(job[j].duree < job[min].duree)
min = j;
if(min != i)
{
x = job[i];
job[i] = job[min];
job[min] = x;
int indice = id_taches[i];
id_taches[i] = id_taches[min];
id_taches[min] = indice;
}
}
}
int main()
{
tache job[6]={{0,10,18},{3,6,15},{2,4,22},{4,9,23},{6,2,14},{5,6,12}};
int k, j;
int num_machine[3]={ 1,2,3};
int id_taches[6];
selection(job,id_taches, 6);
printf("voici les durees ordonnancees par ordre croissant :\n");
for (k=0;k<6;k++)
printf("%d",job[k].duree);
printf("\n");
printf(" voici priority list:\n");
for(k=0;k<6;k++)
{
printf("%d",id_taches[k]);
}
printf("\n");
for(j=0;j<2;j++)
printf("tache : %d -> machine : %d, ",id_taches[j],num_machine[j]);
return 0;
}
Invité- Invité
Re: idée d'algorithme d'affectation en c
Bonjour,
dans ton énoncé, il y a quelque chose que vous n'avez pas expliqué:
voir l'exemple de l'exercice:
Est-ce que c'est une donnée ou une variable à calculer?
Est-ce que tu peux donner un autre exemple si tu as bien compris le problème?
dans ton énoncé, il y a quelque chose que vous n'avez pas expliqué:
voir l'exemple de l'exercice:
d : 12, 5, 7, 8, 10, 6, 18
Est-ce que c'est une donnée ou une variable à calculer?
Est-ce que tu peux donner un autre exemple si tu as bien compris le problème?
methodiX- Admin
-
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 7055
Date d'inscription : 22/03/2007
Feuille de personnage
Capacité linguistique:
(1000/1000)
Re: idée d'algorithme d'affectation en c
Salut,methodiX a écrit:Bonjour,
dans ton énoncé, il y a quelque chose que vous n'avez pas expliqué:
voir l'exemple de l'exercice:d : 12, 5, 7, 8, 10, 6, 18
Est-ce que c'est une donnée ou une variable à calculer?
Est-ce que tu peux donner un autre exemple si tu as bien compris le problème?
le d c'est la date de fin prévu de la tache. Elle sert à calculer le retard.
Invité- Invité
Re: idée d'algorithme d'affectation en c
Salut,
le d c'est la date de fin prévu de la tache. Elle sert à calculer le retard.
donc ce n'est pas une donnée... c'est une valeur calculée, et qui sert à calculer, plutard, la durée du retard.
J'attends un autre exemple (disant: 5 tâches et 2 machines) ...
methodiX- Admin
-
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 7055
Date d'inscription : 22/03/2007
Feuille de personnage
Capacité linguistique:
(1000/1000)
Re: idée d'algorithme d'affectation en c
methodiX a écrit:Salut,
le d c'est la date de fin prévu de la tache. Elle sert à calculer le retard.
donc ce n'est pas une donnée... c'est une valeur calculée, et qui sert à calculer, plutard, la durée du retard.
J'attends un autre exemple (disant: 5 tâches et 2 machines) ...
d est une donnée.
Le voici un autre exemple :
soit 5 taches J1, J2, J3, J4, J5 et 3 machines:m1, m2 et m3
Liste de priorité des taches J: 3, 4, 1, 5, 2(par ordre de durée d'exécution croissant).
Après, il s'agit de placer la tache qui a la plus petite durée d'exécution sur
la machines la plus disponible tant que J <> 0 pour déterminer la séquence
d'ordonnancement optimale.
la solution est représentée par ce diagramme :
Calcul de retard :
Tache 3 :4-5=pas de retard
tache 4 :9-10 pas de retard
tache 1:3-4 pas de retard
tache 2
tache 5 :pas de retard
tache 2 :10-5=5
cette solution permet une somme de retard total =5
Invité- Invité
Re: idée d'algorithme d'affectation en c
D'accord. C'est plus clair maintenant... mais, il fallait que tu décrives tous les paramètres de ton problème avec précision dès le début...
Bref, j'espère que maintenant c'est plus clair dans ta tête...
à suivre !
Bref, j'espère que maintenant c'est plus clair dans ta tête...
à suivre !
methodiX- Admin
-
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 7055
Date d'inscription : 22/03/2007
Feuille de personnage
Capacité linguistique:
(1000/1000)
Re: idée d'algorithme d'affectation en c
Let's focus on the task number 2:
Comment ça se fait ?
Durée = 5
Date début = 3
Date fin = 5
Comment ça se fait ?
methodiX- Admin
-
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 7055
Date d'inscription : 22/03/2007
Feuille de personnage
Capacité linguistique:
(1000/1000)
Re: idée d'algorithme d'affectation en c
Tout ce qui en Orangé, c'est la durée réelle de la tâche en unités de temps.
Tout ce qui encadré avec un trait noir gras, c'est l'intervalle de temps maximal alloué à la tâche. C'est entre autres les contraintes temporelles de l'exécution d'une tâche.
J'essaie de comprendre @assir... explique plus la signification de "d" et "r" ... ex: est-ce qu'on peut exécuter une tâche au delà de son intervalle d'exécution [début (r), fin (d)] prévu?
methodiX- Admin
-
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 7055
Date d'inscription : 22/03/2007
Feuille de personnage
Capacité linguistique:
(1000/1000)
Page 1 sur 2 • 1, 2
Sujets similaires
» nouveau forum
» idée de PFE: Outil de visualisation de méthodes de recherche locale
» je suis besoin de votre idéé svp trés urgent .
» idée de PFE: Outil de visualisation de méthodes de recherche locale
» je suis besoin de votre idéé svp trés urgent .
Forum INFOMATH :: Enseignement de l'informatique :: INFO - Supérieur (Etudiants et Professionnels) :: C/C++
Page 1 sur 2
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum
|
|