Remerciez-le!

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

Devoir Productique Exercice 1 Supposons qu’on a à réaliser les tâches suivantes

Devoir Productique Exercice 1 Supposons qu’on a à réaliser les tâches suivantes sur les machines A et B. Les temps opératoires sont repris au tableau suivant : Tâches à effectuer sur A puis B: Tâches 1 2 3 4 5 6 tiA 50 90 5 50 0 70 tiB 20 50 20 0 30 0 Tâches à effectuer sur B puis A : Tâches 7 8 9 10 11 tiA 100 0 15 40 15 tiB 70 90 110 0 0 1- Trouver l’ordonnancement qui minimise le temps total d’exécution des tâches sur les deux machines 2- Dessiner le diagramme de Gantt correspondant. Exercice 2 Supposons qu’on a à réaliser les tâches suivantes sur les machines A,B et C. Les temps opératoires sont repris au tableau suivant : taˆches 1 2 3 4 5 6 7 Assembla ge 7 1 1 4 1 8 1 8 3 6 Inspection 4 1 9 1 2 5 7 8 Expe ´dition 2 0 1 2 1 9 1 6 1 4 1 2 1 7 1- Trouver l’ordonnancement qui minimise le temps total d’exécution des tâches sur les deux machines 2- Dessiner le diagramme de Gantt correspondant. Exercice 3 Considérons un Ordonnancement de n taˆches sur m centres de production le proble`me combinatoire pose´ est formidable : il y a en effet (n!)m ordonnancements possibles. Le proble`me ge´ne´ral a e´te´ formalise´ en termes de programmation dynamique et en termes de programme line´aire en nombres entiers. La formulation permet d’inte´grer des contraintes supple´mentaires comme la date de livraison, une capacite´ de production, ... etc. Lorsque l’ordre de passage des taˆches est identique et que le nombre de centres de production ne de´passe pas quelques dizaines, une solution souvent proche de la solution optimale peut eˆtre trouve´e en utilisant l’algorithme de Johnson sur des groupements de centres de production successifs exactement a` la manie`re de ce que nous avons fait a` la section pre´ce´dente pour le cas de trois centres de production dont celui du milieu est domine´. Attention que, au contraire des cas pre´ce´dents il ne s’agit pas d’un algorithme donnant une solution optimale mais bien d’une me´thode heuristique donnant une solution approche´e. Prenons le cas de 5 centres de productions note´s A, B, C, D et E. Il faut re ´soudre les 4 proble`mes suivants par l’algorithme de Johnson (des parenthe`ses signiﬁent que l’on somme les temps des centres) : • avec la premie`re et la dernie`re machine : {A}− {E} • avec les deux premie`res et les deux dernie`res machines : {AB}− {DE} • avec les trois premie`res et les trois dernie`res machines : {A, B, C}− {C, D, E} • avec les quatre premie`res et les quatre dernie`res machines : {A, B, C, D}− {B, C, D, E} On prend alors le meilleur des temps totaux d’exe´cution des taˆches ainsi trouve´s. taˆc hes t i A t i B t i C ti D 1 5 0 4 3 1 5 4 2 8 9 9 9 9 5 7 7 3 7 4 7 2 0 9 8 4 8 6 4 1 2 9 4 5 6 1 1 9 6 5 1 4 6 1 8 0 6 6 7 8 Illustrons ceci sur un exemple a ` 4 centres de production. Tableau 2.8: Temps ope´ratoires avec quatre machines. Le premier proble`me ﬁctif consiste a` ne conside´rer que les machines A et D. Il conduit a` l’ordonnancement suivant par la me´thode de Johnson : 1 2 3 4 5 6 6 3 4 2 5 1 qui conduit a` un temps de 51,2 heures. Le deuxie`me proble`me ﬁctif consiste a` conside´rer les machines A+B et C+D comme illustre´ au tableau 2.9 . Il conduit a ` l’ordonnancement suivant par la taˆc hes tiA + tiB tiC + tiD 1 50+ 43 =93 15+4= 19 2 89+ 99= 188 95 + 77= 172 3 7+ 47= 54 20+ 98= 118 4 8+ 64= 72 12+ 94= 106 5 61+ 19= 80 65+ 14= 79 6 1+ 80= 81 66+ 78= 144 Tableau 2.9: Deuxie`me proble`me ﬁctif. me´thode de Johnson : 1 2 3 4 5 6 3 4 6 2 5 1 qui conduit a` un temps de 48,7 heures. Le troisie`me et dernier proble`me ﬁctif consiste a` conside´rer A+B+C et B+C+D. Il donne la meˆme solution que le proble`me ﬁctif 2. On a donc trouve´ une solution de temps e´gal a` 48,7 heures alors que la solution optimale (qui peut eˆtre calcule´e en faisant une e´nume´ration explicite de tous les ordonnancement possibles) conduit a ` un temps de 48,5 heures. Expliquer par un autre exemple de votre confection. uploads/Industriel/ devoir-2-productique.pdf