Julien Moncel

Qlio2

Ordonnancement lancement et pilotage

Le contexte de l’ordonnancement
- Production industrielle
o Plusieurs ressources (machines / Personnes)
o Plusieurs produits / Flux/ clients
o Commandes client à satisfaire au mieux
Le but de l’ordonnancement
- L’ordonnancement permet de savoir qui fait quoi, quand
- But de l’ordo = placer des OF « intelligemment » dans le planning
o Priorités, deadlines, adéquation charge/capacité, etc.
o Application de méthodes
- Séquencement = ordre dans lequel réaliser les OF (classement : OF1, OF2, etc)
- Ordonnancement=
o Séquencement
o Dattes/horaires précis
o Ressources utilisées
o Planning réaliste
o Optimiser les critères de performance choisis
Exemple d’ordonnancement : atelier pose accessoires maroquinerie
- 3 postes accessoires
o Poignée
o Bandoulière
o Chaînette décorative
- Différents sacs, différents accessoires à poser
- Ordre de pose des accessoires indifférent

1) MTO= Make To Order sa traduction est travail à la commande

2) Il s’agit d’un atelier a cheminement libre = free workshop en anglais
3)

- Temps de travail total du poste Bandoulière = 350

- Donc : fin du travail pas avant =350
- Or : Planning trouvé termine en 350
- Donc : planning trouvé= planning optimal !
- En général, montrer qu’un planning
Julien Moncel
Qlio2

Exercice 2 :
Question 1 : il s’agit d’un jobshop
Question 2 :

Autre ordo
Julien Moncel
Qlio2

Autre ordo
Julien Moncel
Qlio2

Données nécessaires pour faire un ordo

- Toute la base de données techniques
- OF :
o Gamme
o Date de disponibilité (au plus tôt)
o Date de besoin (au plus tard)
- Ressources :
o Disponibilité ( horaires congés pannes etc)
o Caractéristiques ( vitesse, temps de préparation, etc)
- Atelier
o Implantation, temps de transfert
Représentation de l’ordonnancement
- Diagramme de gantt
o Abscisse = axe du temps
o Ordonnée : 2 possibilités
▪ Ressources → Gantt Ressource ou Gantt Machine
▪ Les OF → Gannt par OF
L’ordonnancement est un casse-tête
- Satisfaire des objectifs multiples et parfois contradictoires
o Respect des délais client
Julien Moncel
Qlio2
o Minimisation des stocks/encours
o Maximisation rendement
o Minimisation des coûts de fabrication
- Tout en prenant compte des contraintes liées à :
o Organisation de l’atelier
o Anticipation des aléas (marges)
o Contraintes de production diverses
- Atelier = espace contenant plusieurs machines ayant des fonctionnalités différentes
- En général : pour obtenir un produit fini, il faut que celui-ci passe sur plusieurs machines
- Plusieurs types d’ateliers
Open shop
- Cas le plus général
- Chaque produit doit passer sur des machines qui sont propres à ce produit
- L’ordre n’a pas d’importance
- « Atelier à cheminement libre »
- Exemple ; usinage, garage automobile, centre de soins médicaux, maintenance avions lors
d’escales, tests d’équipements sur bancs de test, etc
Job shop :
- Idem à open shop, mais il y’a un ordre imposé de passage sur les machines pour chaque
produit
- « Atelier à cheminement multiples »
Flow shop
- Flow-shop = cas particulier du job shop où
o Toutes les pièces passent sur les mêmes machines, dans le même ordre
o Les temps opératoires peuvent cependant varier d’une pièce à l’autre
- « Atelier à cheminement unique »
Contraintes de production : exemples
- Plusieurs machines aux fonctionnalités identiques mais n’ayant pas la même vitesse
- Certains OF qui sont impératifs/ prioritaires par rapport à d’autres
- Temps de préparation variables
- Opérateurs n’ayant pas tous les mêmes qualifications sur les machines
- ETC
Exemple de contraintes de production complexes (exo3)
- 3 machines M1 M2 M3
- Aussi dispo : machine M1 bis identique à M1 mais 2 fois plus lente
- 4 opérateurs dispo
o OP1 qualifié sur M1 M2
o OP2 qualifié sur M1 M2
o OP3 qualifié sur M1 M3
o OP4 qualifié sur M1 M2 M3
- OF1 OF2 OF3 OF4 OF5 à réaliser sans préemption
- Objectif : minimiser la durée totale (date fin dernier OF)
- Gammes : Machine (durée u.T.)
o OF1 : M1 (10) > M2 (5)
Julien Moncel
Qlio2
o OF2 : M1 (15) >M3 (10)
o OF3 : M1 (20) >M2 (15)>M3 (5)
o OF4 : M2 (15) >M3 (10)
o OF5 : M2 (5) >M1 (5) M3 (10)
- Temps de transfert nuls
- Questions
o De quel type d’atelier s’agit-il ?
job-shop
o Quelles sont les ressources critiques ?
La Machine M3 et M1 qui a une charge élevée
o Proposer un ordonnancement (Gantt machine) et discuter de son optimalité

-
- Dans les bons logiciels d’ordo
o Algos « prêt à l’emploi »
▪ Certains de ces algos vus en cours
o Pour des problèmes classiques
- Mais pour certains pbs d’ordo
o Aucune méthode satisfaisante n’est connue, même avec l’aide de l’ordi
L’ordo dans la vraie vie de l’entreprise
- L’ordo dans l’entreprise industrielle, comment ça marche ?
o On essaye de ne pas avoir de pb d’ordo
▪ Simplification des flux et des contraintes
• Temps de changement de série, polyvalence des opérateurs,
surcapacité de ressources peu onéreuses,etc)
▪ MTS plutôt que MTO
• Mts plus facile à planifier
▪ Planif amont + PDP mieux faite :
Julien Moncel
Qlio2

• Capacité de travail + réaliste (coeff d’éfficacité)

- Souvent, même après simplification, il reste toujours un travail d’ordonnancement à faire
- On essaye de voir si le pb que l’on a à traiter se rapporte à un pb classique connu par la science
o Si ce pb admet des méthodes de résolution efficaces connues, on applique ces
méthodes
▪ Logiciel/ a la main etc
- Et si le pb d’ordo que l’on a à résoudre est différent des pb connus par la science/ vus en cours
- On essaye de se dépatouiller pour trouver un bon ordo
o En développant sa propre méthodo
o En essayant plusieurs critères
o En s’inspirant de méthodes connues
o Etc
EXO 4
- Les machines goulot sont la machine M1 et M2

-
- Ordo optimal = meilleur parmi tous les ordos possibles ( vis-à-vis du critère de performance
considéré)
- Démontrer l’optimalité ?
o Argument « ad hoc » ( adapté aux contraintes du pb )
▪ Etude des possibilités arguments sur poste goulot ressources critique, etc)
o Argument scientifique
▪ « le cours » cad la science dit que telle méthode donne un ordo optimal sur
ce pb or j’ai appliqué ladite méthode donc mon ordo est optimal
Critères de performance
- Plusieurs possibilités
o Retards
▪ Plus grand retard
▪ Retard moyen
▪ Nb d’of en retard
o Dates de fin
▪ La plus grande (makes pan)
- Résoudre un cas particulier = trouver un ordo optimal pour ce cas particulier
o Déjà à notre portée dans certains cas
Julien Moncel
Qlio2
- Résoudre un pb général = trouver une méthode de résolution générale qui donne tjrs un ordo
optimal
o En qlio : on va apprendre certaines de ces méthodes et les appliquer
Typologie des méthodes de résolution
- Méthodes exactes : méthode générale qui fournit tjrs un ordo optimal
o Rares
o Existent parfois pour de pb « simples »
- Heuristiques : méthodes générales qui fournissent un ordo pas forcément optimal
o Parfois on obtient un ordo optimal
o Parfois non
o L’ordo n’est assez souvent « pas trop mal »
▪ Pas optimal mais pas loin
- Un panorama de quelques pb d’ordo « classiques »
- But de l’ordo : placer des of intelligemment
o Critères de performances (dates de fin , retards ,etc)
- Ordo = planification opérationnelle (court terme)
o Ordo = outil de planification de prod le plus précis
▪ Besoin d’infos détaillées( gamme, calendrier des ressources disponibles etc)
- L’ordo peut être soumis à des contraintes multiples et contradictoires
- La prise en compte des différentes contraintes peut se révéler un véritable casse-tête
o Heureusement on va voir des méthodes

CHAPITRE II QUELQUES METHODES D’ORDONNANCEMENT

Jalonnement VS ordo à capacité finie
- Ordo à capacité finie
o Planning de travail réaliste
▪ Arbitrage, priorisation entre les OF
• Jamais 2 of en mm temps sur les ressources
- Ordo à capacité infinie
o Of placés en s’autorisant à en placer plusieurs en mm temps sur les ressources
o Peut être qu’il va y avoir :
▪ Ressources en surcharge
▪ Planning non réalisable
Julien Moncel
Qlio2

- Positionnement des of à capacité finie

o Au plus tôt
o Au plus tard
- En tenant compte de
o Durées opératoires
o Temps de réglages
o Temps de transferts
o Précédences
PAS DE NOTION D’ORDRE ENTRE LES OF ( ON FAIT COMME SI ON POUVAIT LES FAIRE TOUS EN MEME
TEMPS )

EXO 4 JALONNEMENT
Julien Moncel
Qlio2

Après lissage fin au plus tôt

Jalonnement au plus tard

Machines parellèles
- Plusieurs machines disponibles
- Chaque OF passe sur une et une seule machine au choix
Julien Moncel
Qlio2
o Machines toutes équivalentes
- Exemples :
o Stations de lavages
o Flux de production divergent/ convergent
▪ 1 poste de charge constitué de plusieurs postes de travail
Ordo 1 machine : facile ?
- 1 seule machine dispo n OF à ordonnancer
- Facile ? Tout dépend du critère considéré
- Exo 6 Ordonnancer les 6 OF ci-dessus sur 1 machine (hypothèse : temps de transfert nul) de
sorte à minimiser
o Le délai total de réalisation des OF (makespan)
o Le délai moyen de réalisation d’un OF
o Le retard max d’un OF (retard=0 si OF pas en retard)
- OF - A - B - C - D - E - F
Durée - 4 - 2 - 6 - 5 - 9 8
- Date - 12 15 20 10 24 35
de besoin
A B C D E F

0 2 4 6 8 10 12
M1

- Makespan : pas possible de faire mieux, tout ordo sans temps mort est optimal (l’ordre n’a
aucune importance)
- Délai moyen, retard max : optimal ? l’ordre a-t-il une importance ? D’autres idées ?
Minimiser le délai moyen sur 1 machine
- Algorithme SPT (shortest processing time)
o Classer les tâches dans l’ordre de durée croissante
▪ Les tâches les plus courtes d’abord, les plus longues à la fin
o Ordonnancer les tâches dans cet ordre
o SPT est une méthode exacte pour minimiser le délai moyen sur 1 machine
- Algorithme EDD (earliest due date)
o Classer les tâches dans l’ordre de date de besoin croissante
▪ Les tâches les plus urgentes d’abord, les moins urgentes à la fin
o Ordonnancer les tâches dans cet ordre
o EDD est une méthode exacte pour minimiser le retard max sur 1 machine
Attention aux critères multiples
- Optimiser un seul critère (délai, délai moyen, retard, etc) est parfois déjà bien assez compliqué
- Trouver un ordo optimisant plusieurs critères à la fois est souvent impossible
o Critères parfois concurrents / incompatibles
- En général on choisit un critère unique, et on essaye de l’optimiser
Attention au contexte
- Exo 7 : 1 machine indisponible pour maintenance planifiée (maintenance préventive) entre
les temps 10 et 15)
o Of planifiés avant 10 ou après 15, pas de préemption)
Julien Moncel
Qlio2
- SPT Et EDD restent-elles des méthodes exactes ?
- Quid du makespan ? Est-ce aussi facile de trouver un ordo minimisant le makespan ?
- Ordo SPT makespan = 43 delai moyen 131/6= 21,83
- Retard max= 19
- Le délai moyen est-il optimal ?
o Attention le cours ne dit rien à ce sujet :
▪ Sans période d’indispo : spt optimal pour délai moyen
▪ Avec période d’indispo : ???
- Observation : 4 unités de temps mort avant l’indispo
Ordo non-spt meilleur que spt
- Makespan= 39, délai moyen= 122/6 = 20,33, retard max= 15
- Délai moyen en baisse
- Makespan et retard en baisse également
o Makespan optimal ( 0 temps mort)
o Autres critères : pas clair
o Ce qui est clair : spt non optimal pour délai moyen
Et sur 2 machines ou plus ?
- Peu de méthodes exactes à 2 machines ou plus
- Même la minimisation du makespan est compliquée
o Equilibrage de charge
- Exo8 : trouver un ordo des 6 OF ci-dessous sur 2 machines minimisant le makespan
- Même question sur 3 machines
- Makespan=17
- Makespan optimal car la charge est parfaitement répartie
o Autant de charge sur les deux machines
- Equilibrage de charge 3 machines
- Makespan optimal car la charge est répartie au mieux
o Remarque : makespan = 11 impossible ( 3*11=33<34)
- Equilibrage de charge 2 machines
o Charge totale = 60 : répartition idéale 30/30
o 31 = meilleur makespan trouvé ; est-ce optimal ?
- Equilibrage de charge 3 machines
o Charge totale = 60 répartition idéale 20/20/20
o 23= meilleur makespan trouvé ; est-ce optimal ?
Que dit la science ?
- Aucune méthode exacte et efficace n’est connue pour minimiser le makespan sur 2 machines
ou plus
- Efficace ? Méthode prenant un temps de calcul « raisonnable »
- Méthode exacte triviale ( mais très couteuse en temps de calcul) : essayer tous les ordos
possibles, garder le meilleur (méthode « force brute »)
o 2n-2 ordos à tester, à partir de n=100 ça devient n’imp même pour un ordi surpuissant
▪ 2100=1030, ordi le plus puissant au monde : 1018 opérations/ seconde, soit
30000 de calculs
Et pour le délai moyen ?
- SPT adaptée est une méthode exacte pour optimiser le délai moyen sur 2 machines ou plus
- Adaptation de SPT
Julien Moncel
Qlio2
o Trier les tâches par durée croissante et les mettre dans une liste L (= liste des tâches à
ordonnancer)
o Construire l’ordo en partant d’un planning vide
o Tant que L n’est pas vide
▪ Prendre la première tâche de L
▪ Positionner cette tâche sur la première machine disponible
▪ Supprimer cette tâche de L
Flow-shop
- Flux linéaire
o Atelier à cheminement unique
o Tous les OF passent sur les mêmes postes, dans le même ordre
o Temps opératoires différents selon les OF
- Flow-shop à 2,3,4,…,m machines
- Différents critères à optimiser
Algorithme de johnson
Julien Moncel
Qlio2

Extension de l’algorithme de johnson à 3 machines

- Flow-shop à 3 machines ( M1,M2,M3)
- Adaptation de johnson possible si une condition de dominance est remplie : durées sur M2
« petites » par rapport aux durées sur M1 ou sur M3
o Plus grande durée sur Mé inférieure ou égale à la plus petite durée sur M1 ou sur M3
Adaptation de l’algorithme de johnson si la condition de dominance est remplie
- On définit deux machines fictives M1’ et M2’
o On définit des durées opératoires fictives :
▪ Pi,M1’ =PiM1+ Pi,M2 et pi,M2’= Pi,M2+pi,M3
- On applique la règle de johnson avec ces durées et machines fictives pour obtenir une
séquence
- On ordonnance les vraies tâches sur les 3 vraies machines avec la séquence obtenue par
Johnson avec durées et machines fictives
- →Méthode exacte si la condition de dominance est remplie
Julien Moncel
Qlio2

Ordonnancement à base de règles

- Principe : application d’une règle de priorité
o EX : SPT,EDD, etc
- Intérêt
o Facile à appliquer
o Parfois : méthode exacte
- Méthodes centralisées :
o Un agent « central » réalise l’ordo
- Méthodes décentralisées :
o Application de règles « locales » ( au niveau du poste de travail)
Ordonnancement centralisé par placement d’OF
- On choisit une règle de priorité (SPT,EDD,etc)
- On part d’un planning vierge et on place les OF 1 par 1
- Tant qu’il reste des OF non placés
o Choisir l’OF le plus prioritaire non encore placé
o Placer toutes les phases de cet OF sur les machines dans les « trous » laissés par les OF
placés précédemment
▪ On ne touche pas aux OF placés aux étapes précédentes
Julien Moncel
Qlio2
- Deux alternatives pour le placement : chargement au plus tôt ou au plus tard (avantages/
inconvénients : déjà vu)
Exercice 14 ordonnancement centralisé par placement d’OF dans un site de menuiserie industrielle
Un site de fabrication de menuiserie industrielle vient de recevoir 3 commandes comme suit :

Référence produit P1 P2 P3
Quantité commandée 100 100 100
Délai de livraison 9 JOURS 8 JOURS 11 JOURS
Les clients ne souhaitent pas stocker la marchandise, et le site de fabrication non plus. Les délais de
livraison sont donc à considérer dans une perspective « juste-à-temps » : idéalement on cherche à
déterminer un ordonnancement de production de ces trois commandes permettant de livrer chaque
commande à sa date de livraison (ni avant ni après)
Les gammes de fabrication de chacun de ces produits sont décrites ci-dessous

P1 P2 P3
POSTE DUREE POSTE DUREE POSTE DUREE
UNITAIRE UNITAIRE UNITAIRE
A 0,16H B 0,24H B 0,40H
B 0,08H A 0,16H C 0,08H
C 0,16H C 0,08 A 0,08H
Les lots de transfert et de fabrication sont de 100 pcs les temps de transfert sont négligés. La capacitté
journalière de chaque poste de travail est de 8 heures par jour
Question 1
Calculer la charge de travail pour chaque commande et pour chaque poste, et exprimer celle-ci en
heures puis en jours. Quel est le poste goulot ?
P1 (100 pièces)
Poste A : 100 × 0,16H = 16H
Poste B : 100 × 0,08H = 8H
Poste C : 100 × 0,16H = 16H
P2 (100 pièces)
Poste B : 100 × 0,24H = 24H
Poste A : 100 × 0,16H = 16H
Poste C : 100 × 0,08H = 8H
P3 (100 pièces)
Poste B : 100 × 0,40H = 40H
Poste C : 100 × 0,08H = 8H
Poste A : 100 × 0,08H = 8H
2. Charge totale par poste
Julien Moncel
Qlio2
Poste A:16H+16H+8H= 40H
Poste B=:8H+24H+40H= 72H
Poste C : 16H+ 8H+ 8H= 32H
3. Conversion en jours de travail
Poste A : 40H/ 8H = 5 jours
Poste B : 72H/8h = 9 jours
Poste C : 32H/8H = 4 jours
4. poste goulot
Le poste B a la charge la plus élevée avec 72 heures (9 jours) de travail, ce qui est nettement supérieur
aux autres postes.
Question 2 Donner le diagramme de gantt de l’ordonnancement obtenu par application d’une
méthode centralisée par placement d’OF avec la règle EDD, avec chargement des OF au plus tôt

Correction

Question 4
Julien Moncel
Qlio2

Méthodes décentralisées
- L’ordonnancement est réalisé en temps réel
- Chaque poste de travail applique une règle locale d’ordonnancement et traite les OF qui lui
arrivent dans cet ordre au fil de l’eau
o Chaque poste de travail peut avoir sa propre règle
- Aucuun planning global détaillé n’est produit à l’avance
o Difficile de prévoir quand un produit en particulier sera terminé
- Plus simple à mettre en œuvre, plus robuste aux aléas, mais pas sûr du tout d’arriver à
l’optimal…
Ordo décentralisé : quel rôle pour le responsable d’ordonnancement
- Le responsable d’ordonnancement :
o Réalise le jalonnement
o Identifie les postes goulot
o Fixe les règles de priorité
▪ Veille à déterminer des règles judicieuses pour les goulots
o Lance les OF et prépare les fiches suiveuses
o Suit les OF par retour de fiches suiveuses
▪ Analyse et évalue la performance
▪ Amélioration continue : bonnes règles ?
Comparaison ordonnancement centralisé / décentralisé
Julien Moncel
Qlio2