idée d'algorithme d'affectation en c

Page 2 sur 2 Précédent  1, 2

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

Rappel du premier message :

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 Invité le Lun 24 Aoû - 13:55

Merci pour ta réponse.

d c'est le date souhaité de fin de la tache (c'est une donnée)
r c'est la date souhaité de début de la tache(c'est une donnée)mais il faut à chaque fois le recalculer. le r recalculer sert à déterminer si la machine est disponible ou non.
Pour répondre à ta question oui on peut exécuter une tache au delà de son intervalle souhaité(prévu). Elle peut être exécutée avant ou après sa date de début souhaité si la machine est disponible avant cette date et elle peut être terminée après ou avant sa date de fin souhaité. Je devrais placer la tache sur la machine disponible le plus tôt.Puis calculer les retards totaux.


J'ai pensé à plusieurs idée mais aucune n'est satisfaite!
résumé étapes d'algorithme proposé(pardon pour l'énoncé algorithmique, ca fait longtemps que je n'ai pas pratiqué les conventions):
i:compteur tache
M =3: nombre de machine;
k:machine;
t(k): date de disponibilité de machine;
t(k)=0 quelque soit la machine k;
J : {j1, j2, j3, j4, j5...}ensemble de taches ordonnancées par ordre de priorité
tant que J<>0 faire
pour(i=0;i<2;i++) faire
placer les j1, j2 et j3 respectivement sur m1, m2 et m3;
corriger la date de disponibilité de la machine m1,m2 et m3;
enlever j1, j2 et j3 de J;
pour(i=3;i<5;i++)
chercher une machine m* disponible au plus tôt(min t(k));
placer j3 sur m*;
corriger la date de disponibilité de m*;
enlever j3 de J;
fait
Avez-vous une autre idée d'algorithme pour traiter ce problème?
J'espère que mon énoncé est compréhensible, sinon n'hésitez pas à me poser des questions pour éclaircissements !
Merci d'avance à vous tous, je suis vraiment en galère et ma tête explose (et je suis assez nul en algorithme aussi !)?

Invité
Invité


Revenir en haut Aller en bas

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

Message par Napoléon le Lun 24 Aoû - 19:48

Si tout ce que tu as dit est correct, que penses-tu de cette solution?
(2ème problème)


_________________
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 Lun 24 Aoû - 23:59

nabiL a écrit:Si tout ce que tu as dit est correct, que penses-tu de cette solution?
(2ème problème)

Merci pour ta réponse.
En fait, au début il s'agit de respecter la date de début des taches : tache 3 à débute t=4, tache 4 à t=7 et tache 1 à t=0 . Après, placer la tache sur la machine disponible plus tôt (indépendamment de la date de début de la tache)

Invité
Invité


Revenir en haut Aller en bas

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

Message par Napoléon le Mer 26 Aoû - 2:15

J'espère que tu es encore intéressée par la discussion...

Est-ce que tu peux calculer le retard causée par cette 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 Jeu 27 Aoû - 0:18

nabiL a écrit:J'espère que tu es encore intéressée par la discussion...

Est-ce que tu peux calculer le retard causée par cette affectation:



???
Merci à vous pour votre volonté de m'aider.
J'ai pu trouvé l'algorithme pour résoudre mon problème.
Merci encore.
Bonne continuation!

Invité
Invité


Revenir en haut Aller en bas

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

Message par Napoléon le Jeu 27 Aoû - 0:48

ça y est? ça a l'air d'être un algorithme très privé puisque tu n'a pas pensé à le publier sur le forum Very Happy

Un de mes collègues t'a préparé une solution algorithmique "très efficace" d'après lui... il est entrain de voir la complexité de cet algorithme avant de te le passer.

@+

_________________
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 Jeu 27 Aoû - 1:05

Merci cher frère Nabil.
en fait oui c'est un algorithme que je devrais proposer dans le cadre du mon mémoire de Master. Bien sur toute autre proposition me sera utile certainement Wink
Baraka allahou fik.
P.S. j'ai posé une question dans une autre rubrique du forum justement pour savoir exactement comment calculer la complexité algorithmique d'un algorithme quelconque.

Invité
Invité


Revenir en haut Aller en bas

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

Message par Napoléon le Jeu 27 Aoû - 1:14

P.S. j'ai posé une question dans une autre rubrique du forum justement
pour savoir exactement comment calculer la complexité algorithmique
d'un algorithme quelconque.

je ne suis pas au courant... je vais voir.

_________________
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 Contenu sponsorisé


Contenu sponsorisé


Revenir en haut Aller en bas

Page 2 sur 2 Précédent  1, 2

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