TD2 - Ordonnancement [PDF]

Zitiervorschau

Module Ordonnancement TD n°2 Dorsaf Daldoul

GIND2

Exercice 1 On considère le problème d’ordonnancement dans un atelier comportant 3 machines identiques. 11 pièces sont à réaliser : Pièce i 1 pi 9

2 9

3 8

4 8

5 7

6 7

7 6

8 6

9 5

10 5

11 5

Donner la séquence optimale qui minimise le makespan.

Exercice 2 Résoudre le problème de flow shop à 4 machines suivant (F4||Cmax) : pièce M1 M2 M3 M4

1 6 4 3 8

2 8 4 8 2

3 2 6 7 5

4 2 6 2 8

5 3 7 3 7

6 4 8 7 4

Exercice 3 Un atelier comporte deux machines M1 et M2. La fabrication de toutes les pièces nécessite une opération 1 sur la machine M1 et une opération 2 sur la machine M2. Les deux opérations peuvent être réalisées dans n’importe quel ordre. L’objectif ici est de minimiser le makespan. Laquelle de ces deux organisations est à choisir : -

toutes les pièces sont réalisées en exécutant l’opération 1 puis l’opération 2 ; les 3 premières pièces sont réalisées en exécutant l’opération 1 puis l’opération 2 et les 3 dernières pièces sont réalisées en exécutant l’opération 2 puis l’opération 1. pièce M1 M2

1 4 6

2 5 2

3 2 4

4 2 1

5 8 7

6 7 6

Exercice 4 Un responsable d’entrepôt reçoit une commande de chargement pour 10 palettes bien spécifique. Chaque palette doit être assemblée (Atelier A), emballée (Atelier B) puis inspectée et chargée (Atelier C) dans le camion (chaque Atelier comprend une seule machine). Les temps en heures des différentes opérations sont reportés dans le tableau suivant : Palette i TiA TiB TiC

1 1h10 0h25 0h45

2 0h45 0h30 0h55

3 0h45 0h35 1h10

4 0h20 0h25 1h05

5 1h15 0h40 0h50

6 1h25 0h35 1h15

7 0h55 0h40 0h45

8 0h40 0h25 0h50

9 1h05 0h20 1h15

10 1h00 0h30 1h20

L’objectif est de donner l’ordre de traitement des palettes permettant de minimiser le temps total nécessaire à la réalisation de la commande. 1. Caractériser le problème d’ordonnancement et donner sa codification. 2. Donner le nom de la méthode de résolution de ce problème, la séquence optimale et calculer sa fonction objectif, en donnant le diagramme de Gantt.

Exercice 5 Dans un atelier d’assemblage des cartes électroniques d’automobile, on distingue trois centres de charge : le premier comporte deux postes parallèles identiques d’insertion des composants électroniques (M1 et M’1). Le deuxième (M2) permet le brassage à la vague des cartes. Le troisième poste comprend trois postes de contrôle identiques (M3, M’3 et M’’3). Cartes i pi1 (M1 ou M’1) en mn pi2 (M2) en mn pi3 (M3, M’3, M’’3) en mn

A 15 10 10

B 20 5 10

C 35 30 10

D 45 15 10

E 50 7 10

Partie 1 : L’objectif est de minimiser le temps total d’assemblage des cartes électroniques. Dans cette question on ne s’intéresse qu’au premier centre de charge a. Caractériser le problème d’ordonnancement et donner sa codification. b. On propose deux méthodes pour sa résolution. Donner pour chaque méthode, la séquence optimale et calculer sa fonction objectif, en donnant le diagramme de Gantt. i. Quand un poste d’insertion est libre, affecter le travail le plus long parmi les travaux restants dans ce centre de charge. ii. Quand un poste est libre, affecter le travail le plus petit parmi les travaux restants dans ce centre de charge. c. Que peut-on conclure ? Partie 2 : On s’intéresse maintenant aux deux centres de charge « Insertion » suivi du « Brassage à la vague ». La première carte quittant les postes d’insertion sera affectée à la vague. a. A partir des résultats de la question (1/b/ i), tracer le diagramme de Gantt et calculer la fonction objectif. b. A partir des résultats de la question (1/b/ii), tracer le diagramme de Gantt et calculer la fonction objectif. c. Que peut-on conclure. Partie 3 : On s’intéresse maintenant aux trois postes de charge à la fois. Le premier article quittant la vague sera affecté au premier poste de contrôle libre. a. En se basant sur le résultat qui a minimisé la fonction objectif pour l’ensemble {Insertion-Brassage}, tracer le diagramme de Gantt des trois postes à la fois. Calculer la fonction objectif. b. L’optimisation de l’utilisation des ressources du troisième centre de charge aura-telle un effet sur la fonction objectif obtenue au (3/a). Justifier. Partie 4 : L’objectif est de minimiser la durée de séjour pour tout l’atelier (Les 3 centres de charge). a. Proposer une heuristique pour résoudre ce problème. b. Calculer la fonction objectif.