Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Exercices fiche3 corrige RCP - MOCAB Fiche d ? exercices n Ordonnancements Corrigé Exercice ?? T? ches préemptives indépendantes ?? Algorithme de Mac Naughton On considère un ensemble de t? ches morcelables de durées Déterminer à l ? aide de l ? algorithm

RCP - MOCAB Fiche d ? exercices n Ordonnancements Corrigé Exercice ?? T? ches préemptives indépendantes ?? Algorithme de Mac Naughton On considère un ensemble de t? ches morcelables de durées Déterminer à l ? aide de l ? algorithme de Mac Naughton un ordonnancement optimal sur machines ?? ? max Un ordonnancement optimal de durée est Déterminer à l ? aide de l ? algorithme de Mac Naughton un ordonnancement optimal sur machines ?? ? max Un ordonnancement optimal de durée ?? est ?? CRCP - MOCAB Exercice ?? Flow-shop sur machines ?? Algorithme de Johnson On considère un ensemble de travaux constitués chacun de deux t? ches et La t? che de chaque travail s ? exécute sur une machine la t? che sur une machine La t? che de chaque travail précède la t? che On note la durée d ? exécution de la t? che du travail et la durée d ? exécution de la t? che du travail Les durées des t? ches sont les suivantes Déterminer à l ? aide de l ? algorithme de Johnson un ordonnancement de durée minimale pour ces travaux Avec l ? algorithme de Johnson- on obtient comme valeurs successives de ? ? d ? o? la liste et un ordonnancement optimal de durée est donc Avec l ? algorithme de Johnson- on obtient et et On obtient un autre ordonnancement également optimal de durée Remarque dans le déroulement des deux algorithmes des choix arbitraires ont été e ?ectués en cas d ? égalité de deux valeurs d ? autres listes étaient donc possibles Exercice ?? T? ches unitaires sur machine Soit ? un ensemble de t? ches unitaires devant s ? exécuter sur machine À chaque t? che sont associés une date d ? échéance et un poids Une t? che est dite en retard si sa date de ?n d ? exécution est supérieure à sa date d ? échéance Si une t? che est en retard un coût est à payer si est en avance aucun coût n ? est à payer L ? objectif est de déterminer un ordonnancement de coût minimal c ? est-à-dire minimiser la somme des coûts des t? ches en retard CRCP - MOCAB Montrer qu ? il existe un ordonnancement optimal tel que la machine n ? a pas de période d ? inactivité Considérons une période d ? inactivité de la machine Si l ? on décale d ? une unité vers le début du projet chaque t? che dont la date de début d ? exécution est alors on obtient un ordonnancement de coût moindre ou égal En e ?et avancer le début d ? une t? che ne peut occasionner de surcoût on ne met aucune t? che en retard Il est donc possible de supprimer ainsi toute période d ? inactivité de la machine puisque ces périodes sont en nombre ?ni En partant d ? un ordonnancement optimal on aboutit à un ordonnancement de même coût