idée d'algorithme d'affectation en c

Page 1 sur 2 1, 2  Suivant

Voir le sujet précédent Voir le sujet suivant Aller en bas

idée d'algorithme d'affectation en c

Message par Invité le Sam 22 Aoû - 12:08

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!
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é


Revenir en haut Aller en bas

Re: idée d'algorithme d'affectation en c

Message par Napoléon le Sam 22 Aoû - 14:09

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?

_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5283
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: idée d'algorithme d'affectation en c

Message par Invité le Sam 22 Aoû - 14:31

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.

Invité
Invité


Revenir en haut Aller en bas

Re: idée d'algorithme d'affectation en c

Message par Napoléon le Sam 22 Aoû - 14:44

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?

_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5283
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: idée d'algorithme d'affectation en c

Message par Invité le Sam 22 Aoû - 14:57

exactement!

Invité
Invité


Revenir en haut Aller en bas

Re: idée d'algorithme d'affectation en c

Message par Invité le Sam 22 Aoû - 15:05

excusez moi
date de début de tache souhaité est une donnée en fait, ol la connait.
Voilà!

Invité
Invité


Revenir en haut Aller en bas

Re: idée d'algorithme d'affectation en c

Message par Napoléon le Sam 22 Aoû - 15:51

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)

_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5283
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: idée d'algorithme d'affectation en c

Message par Invité le Sam 22 Aoû - 16:43

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 No

Invité
Invité


Revenir en haut Aller en bas

Re: idée d'algorithme d'affectation en c

Message par Invité le Dim 23 Aoû - 15:41

Salut,

Je ne vois pas quelle structure de données pour les machines? confused

Invité
Invité


Revenir en haut Aller en bas

Re: idée d'algorithme d'affectation en c

Message par Napoléon le Dim 23 Aoû - 15:46

On peut avoir comme structure de données d'une solution du problème:

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);

_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5283
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: idée d'algorithme d'affectation en c

Message par Invité le Dim 23 Aoû - 16:20

Merci pour votre réponse.
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é


Revenir en haut Aller en bas

Re: idée d'algorithme d'affectation en c

Message par Napoléon le Dim 23 Aoû - 16:24

Smile 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?
Code:
int tab_indices[6];/*liste des taches par priorité*/

_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5283
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: idée d'algorithme d'affectation en c

Message par Invité le Dim 23 Aoû - 16:30

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.

Invité
Invité


Revenir en haut Aller en bas

Re: idée d'algorithme d'affectation en c

Message par Napoléon le Dim 23 Aoû - 16:58

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:

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?

_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5283
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: idée d'algorithme d'affectation en c

Message par Invité le Dim 23 Aoû - 17:31

Je n'ai pas bien compris le prototype
Code:
AFFECTATION* affecter(int n,TACHE* taches, int m, MACHINE* machines)
?

Invité
Invité


Revenir en haut Aller en bas

Re: idée d'algorithme d'affectation en c

Message par Napoléon le Dim 23 Aoû - 17:38

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*".

_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5283
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: idée d'algorithme d'affectation en c

Message par Invité le Dim 23 Aoû - 18:22

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

Invité
Invité


Revenir en haut Aller en bas

Re: idée d'algorithme d'affectation en c

Message par Invité le Dim 23 Aoû - 18:48

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é


Revenir en haut Aller en bas

Re: idée d'algorithme d'affectation en c

Message par methodiX le Dim 23 Aoû - 19:13

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?

_________________
Sami - Methodix, tunis
Le génie de Newton a consisté à dire que la lune tombe alors que tout le monde voit bien qu'elle ne tombe pas.
(Paul Valéry)
_____
Cliquer ici: Voir les nouveaux messages depuis votre dernière visite
Cliquer ici: Astuce: Utiliser l'outil "Recherche" du forum
avatar
methodiX
Admin
Admin

Masculin
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 4665
Date d'inscription : 22/03/2007

Feuille de personnage
Capacité linguistique:
1000/1000  (1000/1000)

Revenir en haut Aller en bas

Re: idée d'algorithme d'affectation en c

Message par Invité le Dim 23 Aoû - 19:17

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?
Salut,
le d c'est la date de fin prévu de la tache. Elle sert à calculer le retard.

Invité
Invité


Revenir en haut Aller en bas

Re: idée d'algorithme d'affectation en c

Message par methodiX le Dim 23 Aoû - 19:31

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) ...

_________________
Sami - Methodix, tunis
Le génie de Newton a consisté à dire que la lune tombe alors que tout le monde voit bien qu'elle ne tombe pas.
(Paul Valéry)
_____
Cliquer ici: Voir les nouveaux messages depuis votre dernière visite
Cliquer ici: Astuce: Utiliser l'outil "Recherche" du forum
avatar
methodiX
Admin
Admin

Masculin
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 4665
Date d'inscription : 22/03/2007

Feuille de personnage
Capacité linguistique:
1000/1000  (1000/1000)

Revenir en haut Aller en bas

Re: idée d'algorithme d'affectation en c

Message par Invité le Lun 24 Aoû - 1:29

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é


Revenir en haut Aller en bas

Re: idée d'algorithme d'affectation en c

Message par methodiX le Lun 24 Aoû - 3:56

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 !

_________________
Sami - Methodix, tunis
Le génie de Newton a consisté à dire que la lune tombe alors que tout le monde voit bien qu'elle ne tombe pas.
(Paul Valéry)
_____
Cliquer ici: Voir les nouveaux messages depuis votre dernière visite
Cliquer ici: Astuce: Utiliser l'outil "Recherche" du forum
avatar
methodiX
Admin
Admin

Masculin
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 4665
Date d'inscription : 22/03/2007

Feuille de personnage
Capacité linguistique:
1000/1000  (1000/1000)

Revenir en haut Aller en bas

Re: idée d'algorithme d'affectation en c

Message par methodiX le Lun 24 Aoû - 4:04

Let's focus on the task number 2:


Durée = 5
Date début = 3
Date fin = 5

Comment ça se fait ?

_________________
Sami - Methodix, tunis
Le génie de Newton a consisté à dire que la lune tombe alors que tout le monde voit bien qu'elle ne tombe pas.
(Paul Valéry)
_____
Cliquer ici: Voir les nouveaux messages depuis votre dernière visite
Cliquer ici: Astuce: Utiliser l'outil "Recherche" du forum
avatar
methodiX
Admin
Admin

Masculin
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 4665
Date d'inscription : 22/03/2007

Feuille de personnage
Capacité linguistique:
1000/1000  (1000/1000)

Revenir en haut Aller en bas

Re: idée d'algorithme d'affectation en c

Message par methodiX le Lun 24 Aoû - 4:19



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?

_________________
Sami - Methodix, tunis
Le génie de Newton a consisté à dire que la lune tombe alors que tout le monde voit bien qu'elle ne tombe pas.
(Paul Valéry)
_____
Cliquer ici: Voir les nouveaux messages depuis votre dernière visite
Cliquer ici: Astuce: Utiliser l'outil "Recherche" du forum
avatar
methodiX
Admin
Admin

Masculin
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 4665
Date d'inscription : 22/03/2007

Feuille de personnage
Capacité linguistique:
1000/1000  (1000/1000)

Revenir en haut Aller en bas

Re: idée d'algorithme d'affectation en c

Message par Contenu sponsorisé


Contenu sponsorisé


Revenir en haut Aller en bas

Page 1 sur 2 1, 2  Suivant

Voir le sujet précédent Voir le sujet suivant Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum