idée d'algorithme d'affectation en c

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

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 !)?

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

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)

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

ç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

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.

@+

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

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.