Scribd Logo
Importer

Bienvenue sur Scribd !

  • 22 vues

    Exercice 2

    Transféré par

    Karma Aycha

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme DOCX, PDF, TXT ou lisez en ligne sur Scribd

    Exercice 2

    Transféré par

    Karma Aycha
    22 vues2 pages

    Copyright

    © © All Rights Reserved

    Formats disponibles

    DOCX, PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme DOCX, PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format docx, pdf ou txt
    22 vues2 pages

    Exercice 2

    Transféré par

    Karma Aycha

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme DOCX, PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format docx, pdf ou txt
    Vous êtes sur la page 1sur 2

    Exercice 2 

    : Glouton dans le problème de l’ordonnancement


    Q1/
    Pseudo-code de Glouton dans le problème de l’ordonnancement :
    fonction ordonnancement glouton(travaux):
    travaux_triés <- trier(travaux) en ordre croissant selon les temps d'exécution
    temps_total <- 0
    ordonnancement <- une liste vide pour chaque travail dans travaux_triés: temps_total
    <- temps_total + temps_d_execution(travail)
    si temps_total <= date_limite(travail):
    ajouter travail à ordonnancement
    sinon:
    continuer
    renvoyer ordonnancement

    ** Trier les travaux en ordre croissant selon temps d’exécution


    **parcourir chaque travail dans l’ordre trié
    **si date limite n’est pas dépassé, le travail est ajouté à l’ordonnancement
    **sinon on ajoute le travail à l’ordonnancement
    **retourner l’ordonnancement obtenu
    Q2/
    L’utilité des différents paramètres dans glouton sur le problème de l’ordonnancement :
    Travaux : liste des travaux à ordonnancer, informations sur chaque travail (temps d’exécution,
    date limite)
    Travaux_triés : liste créée à partir de la liste des travaux et triée en ordre croissant selon temps
    d’exécution. Cette dernière est triée
    Temps_total : variable qui suit durée totale de l’ordonnancement en cours, elle est mise à jour a
    chaque fois qu’un travail est ajouté à l’ordonnancement
    Ordonnancement : liste qui contient les travaux ordonnés, initialement vide et remplie au fur et
    a mesure qu’on ajoute des travaux
    Temps_d_execution(travail) : prend un travail en entrée et renvoie son temps d’exécution
    Date_limite(travail) : fonction qui prend un travail en entrée et renvoie sa date limite

    Q3/
    Suppose-t-on a une entreprise qui a besoin d’ordonnancer la production des produits. La
    capacité de production est limitée et il y a des dates de livraison à respecter.

    On doit planifier la production de manière à maximiser le nombre de produits fabriqués tout en


    respectant les dates de livraison.

    Algorithme de Glouton :
    Liste de travaux à ordonnancer, chaque travail étant un produit spécifique avec un temps
    d’exécution et date limite de livraison, on trie la liste en ordre croissant selon temps d’exécution
    On parcourt la liste triée, vérifier date limitée, si oui on ajoute produit à l’ordonnancement sinon
    on passe au travail suivant

    A la fin, nous avons un ordonnancement des travaux qui respecte les dates de livraison

    Exemple : on a 3 produits a fabriqués


    Produit A : temps d'exécution = 4 jours, date limite = 10 jours
    Produit B : temps d'exécution = 2 jours, date limite = 8 jours
    Produit C : temps d'exécution = 3 jours, date limite = 12 jours
    1/trier dans l’ordre croissant, B, C, A
    3/ ordonnancer selon livraison
    Produit B : 2 jours de production, date limite respectée (livraison à Jour 2)
    Produit C : 3 jours de production, date limite respectée (livraison à Jour 5)
    Produit A : 4 jours de production, date limite respectée (livraison à Jour 9)
     On a un ordonnancement qui fabrique 3 produits dans les délais en respectant date
    livraison et maximisant le nombre de produits fabriqués

    Vous aimerez peut-être aussi