GPA750 – Ordonnancement des systèmes de production

aéronautique

Professeur Pontien Mbaraga, Ph.D

Cours 2

• Caractéristiques des environnements de production et des modèles – Survol des modèles– Caractéristiques et contraintes – Objectifs et mesures de performances– Mesure de performance régulière– Caractéristiques des calendriers– Relations entre les mesures de performances

2.1. Définitions et Modèles• Définitions:

– Ressource, Machine; Commande (job); Opérations (tâches)• Modèles

– Gestion de Projet• Min temps de finition du projet• A&D

– Atelier multigamme (job shop)• Min temps de finition ou nombre de commandes en retard• Atelier de fabrication ou de réparation (réfection)

– Atelier avec système de Manutention automatisée • Atelier monogamme, Atelier de fabrication flexible, ligne d’assemblage• Max le débit ou le flux de production (throughput)• Automobile, microélectronique, etc

– Ordonnancement par lots (lots scheduling)• Planification à moyen et long terme• Demande et/ou production continue• Temps de changement • Min l’inventaire et les temps de changements• Domaine d’applications: plastique, papier, chimique, vente au détail

– Système de réservation et planification d’horaire

Notation générale pour un problème d’atelier

• Données statiques:– Nbre de commandes : n;– Nbre de machines : m;– Indices j & k dénotent les commandes j & k;– Indices h & i dénotent les machines h & i;– Pij :Temps de l’opération de la commande j sur la

machine i; L’indice i est omis si machines identiques.– rj : Date de mise en disponibilité (release date) de la

commande j;– dj: Date due (due date) de la commande j;– wj: Poids ou priorité de la commande j;– aj : allocation pour le traitement de la commande j;

• aj = dj – rj

Notation générale pour un problème d’atelier

• Données dynamiques– Cij : Date de finition de la commande j sur la machine i;– W j(x) : Temps d’attente (waiting time) précédant

immédiatement la xième opération de la commande j – Wj :Temps d’attente total

xm W j(x)

– Cj :Date de finition de la commande j ;• Cj = rj + m

x (Wj(x) + Cj(x))

– Fj : Temps de passage (flowtime) de la commande j• Fj = Cj - rj

– Ih : Temps mort sur la machine h• Ih = Cmax – i Pih

Types de problèmes d’ateliers

• Il y a 3 types selon la nature des contraintes de précédence entre opérations d ’une même job : - Problème d’«open-shop» : les opérations d’une même

commande sont indépendantes. (Pas d ’ordre!)- Problème d ’atelier général (job-shop) : les opérations

d’une commande sont liées par un ordre total, non nécessairement identique pour toutes les commandes (re-circulation).

- Problème d ’atelier séquentiel (flow-shop) : les opérations des commandes sont liées par un ordre total; Flow-shop Flexible (nombre d ’étapes en séries avec machines parallèles à chaque étape).

Configuration des machines et routage des opérations

• Modèle à une machine;• Modèle avec machines parallèles ;• Ateliers monogammes (flow shop)

– Contraintes de routage identiques pour toutes les commandes, c.à.d. visitent les machines ou centre d’usinage dans le même ordre.

• Ateliers multigammes– Note: les machines dans les derniers modèles

peuvent être des centres d’usinage avec plusieurs machines en parallèles.

2.2. Caractéristiques et contraintes

• Contrainte de préséance– Spécifie qu’une commande i doit être précédée par une commande j;

• Contrainte de routage– Spécifie le routage de la commande dans le système;

• Contraintes de manutention– Dépendent du degré d’automatisation

• Si poste de travail automatisé alors la manutention peut être automatisée.• Affecte l’inventaire et le temps de début de l’opération subséquente.

• Temps de changements (setup)– Dépend ou non de la séquence

• Sijk – temps de changement si j est suivi de k sur la machine i• Cijk – Coût associé au temps de changement

• Préemption (pour les tâches morcelables)– Interrompre le traitement d’une commande sur une machine afin de

passer une commande prioritaire;• Preemptive resume (continue à partir là où était rendu)• Preemptive repeat (recommence)

2.2. Caractéristiques et contraintes

• Contrainte d’espace et de temps d’attente– Limite la quantité en attente devant une machine– Peut entraîner le blocage de la machine en amont

• Production pour stockage vs. production sur commande– Taux de demande relativement constante vs

demande très variable– Traitement des options

• Admissibilité des machines ou ressources• Contraintes du personnel

Hypothèses usuelles : Cas déterministe

1. Chaque commande est une entité distincte qui consiste en un ensemble d’opérations

• Deux opérations d’une même commande ne peuvent être traitées simultanément

2. Pas de pré-emption3. Chaque commande a m opérations

• Pas de re-circulation4. Pas d’annulation des commandes5. Les temps d’opérations sont indépendants de l’ordonnancement6. Encours permis7. Il existe seulement un type de chaque machine

• Pas de choix possible8. Les machines peuvent être inactives9. Une machine ne peut faire deux opérations en même temps10. Les machines ne brisent pas11. Les routages sont connus et fixés d’avance12. Toutes les données sont déterministes – pas d’aléas

2.3 Objectifs et mesures de performances

• Débit (Throughput) et Temps de finition– Le débit est équivalent au flux de production

• Déterminer par la machine goulot• Donc, Max débit du système = Max débit machines goulots

– S’assurer que les machines goulots n’ont pas de temps mort

– Temps de Finition (makespan)• Cmax = max(C1,…,Cn)• Est souvent utilisé quand le nombre de commandes est fini

– e.g. dans le cas des machines parallèles avec des temps de changements qui dépendent de la séquence

• Min Cmax est équivalent à maximiser le débit quand:– N est fini;– Le flux des commandes est constant dans le temps

• Temps de finition moyen

– Flow time Fj – temps de passage de la commande dans le système• Fj = Cj – rj

• Fmax = max (F1,…, Fn)• Flowtime moyen ( ) /J

j

F F n

( ) /Jj

C C n

2.3. Objectifs et mesures de performances

• Min Fmax revient à dire que le coût de l’ordonnancement est proportionnel à la plus longue commande;

• Min Cmax – coût proportionnel au temps alloué à l’ensemble des n commandes;

• Note si rj = 0 pour tout j alors: – Cmax = Fmax

• Min Fmoy = Min Cmoy

– Minimiser le temps moyen d’une commande

2.3. Objectifs et mesures de performances

• Objectifs reliés à la date due– Retard maximal Lmax

• Retard associé à la commande j: Lj = Cj – dj

• Retard maximal: Lmax = max (L1,…, Ln)• On veut minimiser Lmax

– Quand et pourquoi utilise-t-on ce critère?

– Minimiser le nbre de tâches en retard• Donne souvent des calendriers où certaines commandes sont très en retard

– Minimiser la somme des retards positifs (tardy)• Retard peut être + (retard : tardiness) ou – (avance : earliness)• Retard positif de la commande j: Tj = max(Cj – dj, 0)• La fonction à minimiser est:

• Où wj est le poids de la commande j• Note: la partie négative du retard est l’avance (earliness) associée à une

commande:– Ej = max(-Lj,0)

1

n

j jj

w T

2.3. Objectifs et mesures de performances

• Coûts de changement (setup)– N’est pas proportionnel au temps de setup

• Exemple – production continue où la machine fonctionne pendant le temps de changement

• Coût de l’encours (WIP)– On veut minimiser le WIP car ce dernier immobilise le capital, cause des

goulots, augmente les coûts de manutention et d’accidents ou de pertes– Min débit revient à minimiser l’encours:

• Min Cj

• Si on veut minimiser la valeur total de l’encours: Min wjCj

• Coût de l’inventaire final (hj)– Production sur commande: Min ‘earliness’– Production pour l’inventaire: Lots économique de production

• Coût associé au personnel– Quart de travail, temps supplémentaire

• Peut-on évaluer le coût d’un ordonnancement?

2.4. Mesure de performance régulière

• Une mesure de performance R est dite régulière si elle est non décroissante en fonction des temps de finition (C1,…,Cn).

• Supposons que – C1< C’1, C1<C’2,… ,Cn < =C’n– Alors R(C1, C2, …Cn) <= R(C’1, C’2,… C’n)

• Exemples de mesures de performance régulière:– Cmoy, Cmax, Fmoy, Fmax, Lmoy, Lmax, Tmoy, Tmax

C1,…Cn

R

2.5. Caractéristiques des Calendriers

• Calendrier sans-délais– Une machine n’est jamais inactive s’il y a des

commandes à traiter.

• Exemple :

2.5. Caractéristiques des Calendriers

• Calendrier actif– Impossible de générer un

autre calendrier en changeant la séquence sur les machines de sorte qu’une opération commence plus tôt et aucune opération commence plus tard

• Calendrier semi-actif– Un calendrier où toutes les

commandes débutent à leurs temps le plus tôt sur les machines étant donné la séquence actuelle

Exemple de Calendrier Actifmais qui n’est pas sans-délais:

Exemple de Calendrier Semi Actifqui n’est pas Actif:

2.5. Caractéristiques des Calendriers

• Théorème:– Afin de minimiser une

mesure de performance régulière on doit seulement considérer des calendriers semi-actifs

Classes de Calendrier pour lesAteliers Multigammes

2.6. Relations entre les mesures de performances

• Les mesures suivantes sont équivalentes– Cmoy ; Fmoy ; et Lmoy

• Un ordonnancement optimal par rapport à Lmax l’est aussi par rapport à Tmax

– Attention : Le contraire n’est pas vrai!

Exemple avec 4 jobs et 4 machines

Données de Base: Une solution possible

Comment déterminer si la solution est réalisable?

2.7. Observations• Comment déterminer si un ordonnancement est réalisable?

– Diagramme de Gantt– Méthode réseau

• Combien de solutions possibles pour un problème de n commandes et m machines?– (n!)m – (4!)4 = 331,776.

• Temps de résolution– Supposons qu’on peut vérifier 1000 solutions par secondes:

• Temps de résolution: 5.5 minutes• Supposons qu’on ajoute une nouvelle commande

– Nbre de solutions: (5!)4 = 2.1 x 108 – Temps de résolution: plus de 57 heures!...

• Quel est le temps minimal de finition - Min Cmax?– Ordonnacement actuel: 11:51– La machine S est inutilisé de 11:05 à 11:11

2ième solution

Interchanger B et D dans la séquence sur la machine FT

3ième Solution:C avant D et A

Est-ce que ce calendrier est optimal?

Solution à la 2ièmeitération

Insérer un délais sur FT

Exemple du logiciel LENKIN