Répondre à la discussion
Affichage des résultats 1 à 8 sur 8

Explication d'un algo. de Gantt



  1. #1
    awaawa

    Explication d'un algo. de Gantt


    ------

    Bonjour,

    J'essaie de comprendre l'ago. (voir mon fichier joint ) et de l'appliquer pour retomber sur le le Gantt correspondant (dans le fichier joint).

    si vous le compreniez et que vous retomber sur le même résultat (Gantt) je serais ravi d'avoir une explication en français sur cette logique algorithmique car j'ai beaucoup perdu de temps dessus mais en vain.

    merci beaucoup!

    -----
    Fichiers attachés Fichiers attachés

  2. Publicité
  3. 📣 Nouveau projet éditorial de Futura
    🔥🧠 Le Mag Futura est lancé, découvrez notre 1er magazine papier

    Une belle revue de plus de 200 pages et 4 dossiers scientifiques pour tout comprendre à la science qui fera le futur. Nous avons besoin de vous 🙏 pour nous aider à le lancer...

    👉 Je découvre le projet

    Quatre questions à explorer en 2022 :
    → Quels mystères nous cache encore la Lune 🌙 ?
    → Pourra-t-on bientôt tout guérir grâce aux gènes 👩‍⚕️?
    → Comment nourrir le monde sans le détruire 🌍 ?
    → L’intelligence artificielle peut-elle devenir vraiment intelligente 🤖 ?
  4. #2
    Arzhur

    Re : Explication d'un algo. de Gantt

    C'est à partir d'ou que tu comprends pas ? Le calcul du temps d'attente ?

  5. #3
    awaawa

    Re : Explication d'un algo. de Gantt

    oui c'est au niveau des temps de présence que je suis perdu,
    comment savoir quel opération il faut affecter à quelle machine

  6. #4
    Arzhur

    Re : Explication d'un algo. de Gantt

    Pour la première c'est pas trop dur : O11 en M1 , O21 en M2 (c'est la phase d'initialisation)

    La machine qui s'arrête en premier est M1 : tu dois donc placer O12 ( le Oi,j+1)
    Là c'est facile y'a que M1 qui peut la faire -> O12 est assignée à M1

    t=10 M1 et M2 ont terminées: t'en choisis une au hasard (M1 par exemple)

    Il faut placer O13 (la suite de O12 de M1) :
    Temps d'attente de O13 pour M1 : 12 , pour M2 : 8 (t'es dans le cas où elles ne bossent pas)

    On assigne O13 à M2 (tu prends la machine la plus rapide)

    Il faut placer O22 (la suite de O21 de M2)

    Temps d'attente de O22 : pour M1:12 (elle bosse pas) pour M2:8+10=18 (elle bosse)

    On assigne O22 à M1.

    t=18 O13 est terminée

    Il faut placer O14...facile y'a que M1 ->O14 dans la file d'attente de M1 (puisque M1 bosse)

    M2 est au repos (elle ne peut rien faire)

    t=22 M1 a terminée
    Il faut placer O23....normalement tu peux faire la suite tout(e) seul(e)



    Arthur

  7. A voir en vidéo sur Futura
  8. #5
    awaawa

    Re : Explication d'un algo. de Gantt

    Merci Arzhur,

    Pour les premières opérations c'est facile dans notre cas car O11 est plus court sur la M1 et O21 ne peut se faire que sur la M2 (donc comme par magie tout est optimale )
    Mais supposons maintenant que O11 est plus court sur la M2 et que O21 ne peut se faire que sur la M2 , ce serait stupide de mettre les premières opérations des deux tâches sur la même machine (ce serait pas du tout optimale mais c'est pourtant comme ceci que je comprends l'algo.)

    Pouvez vous donc me dire comment faut il comprendre cette algorithme (je ne pense pas que mon interprétation soit correct).

    Deuxièmement à t=10 lorsque M1 et M2 ont terminées les opérations O12 et O21, on se focalise sur une machine au hasard (par exemple M1 comme vous avez dit), on remarque bien que O13 est plus courte sur la M2 donc on l'affecte a M2. A partir de là je suis bloqué, c'est quoi l'histoire des waiting list?

  9. #6
    Arzhur

    Re : Explication d'un algo. de Gantt

    Mais supposons maintenant que O11 est plus court sur la M2 et que O21 ne peut se faire que sur la M2 , ce serait stupide de mettre les premières opérations des deux tâches sur la même machine (ce serait pas du tout optimale mais c'est pourtant comme ceci que je comprends l'algo.)
    Oui je vois ce que tu veux dire et je le comprend de la même manière. De mémoire on a pas de solutions miracle pour ordonnancer des taches de manière optimale à chaque coup (dans le cas où on a plusieurs unités de calcul). Ainsi ça me choque pas que l’algorithme donne parfois des résultats "idiots". Tu remarqueras que l'algo ne prend pas en compte les opérations restantes avant de placer une opération...donc il a moins d'info que toi pour décider.

    Deuxièmement à t=10 lorsque M1 et M2 ont terminées les opérations O12 et O21, on se focalise sur une machine au hasard (par exemple M1 comme vous avez dit), on remarque bien que O13 est plus courte sur la M2 donc on l'affecte a M2. A partir de là je suis bloqué, c'est quoi l'histoire des waiting list?
    Oui parce que M1 et M2 ont terminé en même temps (tu peux me tutoyer aussi). A ce stade là, y'a pas d'histoire de waiting list...(ou alors je comprend pas ta question). Tu prends juste la machine la plus rapide en prenant en compte le fait que tu as affecté une tâche à M2.

    La waiting list c'est quand tu affectes une opération à une machine qui est entrain de bosser -> je mets cette tâche sur cette machine mais comme la machine bosse, je la met en la tâche attente.


    Imagine M1 et M2 ont terminés et il reste 4 en temps de calcul à M3 (je crée une M3 exprès pour l'exemple)

    tu dois placer operation12 (la suite de M1) et operation22 (la suite de M2)

    "operation12" prend 20 sur M1 et 10 sur M3 , M2 ne peut pas la faire
    "operation22" prend 20 sur M2 et 10 sur M3 , M1 ne peut pas la faire

    Tu choisis de t'occuper d'abord de operation12 (au hasard)

    l'algo te dit de la mettre sur M3. ( ok ?)
    MAIS M3 bosse donc ne peut faire l'opération tout de suite -> tu la mets dans sa liste d'attente ( waiting list si tu préfères)

    Du coup quand tu vas placer operation22 : il faut prendre en compte le fait de M3 à une tâche en attente (eh oui on a dit qu'on mettait operation12 sur M3....faut qu'elle le fasse) pour finalement placer operation22 sur M2. Si tu ne prends pas en compte les tâches en attente, tu vas donner toutes tes tâches à une machine rapide et rien du tout aux autres.

    Est-ce que ça répond à ton interrogation sur l'histoire de la wainting list ?


    Rmq : j'ai pris M1 au hasard et ça tombe bien diagramme de Gantt en solution a fait le même choix. Si tu prenais M2 le résultat était différent->O22 en M2 et O13 sur M1 ( et ainsi de suite)

  10. Publicité
  11. #7
    awaawa

    Re : Explication d'un algo. de Gantt

    Merci Arzhur,
    j'ai bien saisi maintenant,

    j'essaye désormais de coder en VBA l'ago. en pièce jointe (du même genre que le précédant mais avec de meilleurs résultats) que j'ai réalisé à la main sans problème mais étant débutant je bloque au niveau du code (cf fichier excel en pièce jointe) et j'ai aucune idée comment générer le gantt final

    si tu peux m'aider au niveau code au avec des conseils ce serait cool


    merci beaucoup!
    Images attachées Images attachées
    Fichiers attachés Fichiers attachés

  12. #8
    Arzhur

    Re : Explication d'un algo. de Gantt

    Aouch,


    Oui je veux bien t'aider...maintenant VBA j'ai jamais touché (mais bon je peux essayer d'apprendre un peu)...du coup je vais avoir un peu plus de mal. Faut espérer que quelqu'un qui connait le VBA a suivi le fil.

    Dans un premier temps, tu as la chance d'avoir l'algo de décrit, donc tu peux placer sa structure : les boucle for/if/else et met en commentaire ce que tu veux faire dedans. T'y gagneras en lisibilité et accessoirement ça va m'aider à lire le VBA.

    Ensuite tu pourras t'attaquer à implémenter ce que t'auras écrit en commentaire.

    Enlève aussi ton "code n'importe" quoi le copy-pasta c'est pas bon pour apprendre. (Mais ça sauve souvent la vie)

Discussions similaires

  1. Diagramme de Gantt
    Par Clint25 dans le forum Logiciel - Software - Open Source
    Réponses: 8
    Dernier message: 16/12/2011, 14h20
  2. gestion de projet/diagramme de GANTT de PERT SOS!!
    Par littlegirl dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 04/06/2011, 18h53
  3. Problème du plus court chemin ( Algo de dijkstra, algo A*)
    Par mathrider dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 12/06/2010, 11h25
  4. algo
    Par kanefa dans le forum Discussions scientifiques
    Réponses: 2
    Dernier message: 28/01/2009, 23h29