ordonnancement d’atelier :
une approche originale
Les statistiques de la qualité :
plan de contrôle de réception.
étude de capabilité d'un procédé
les plans d'expériences et méthode Taguchi pour
les cartes de contrôle pour le suivi d'un processus dans le temps.
une simulation d'usinage pour relier dessin de définition et les statistiques de la qualité.
Algorithme hongrois (Konig Egervary). Affectation de personnes à des tâches avec minimisation du coût total.
Les files d'attente
présentez moi
votre projet
sommaire
le problème de l’ordonnancement
la représentation de l’atelier suivant la méthode OPT
la prise en compte des contraintes pour déterminer l’ensemble des ordonnancements possibles
la modélisation pour utiliser un algorithme génétique
le choix d’une fonction coût
l’ordonnancement
les commandes arrivant dans un atelier doivent être fabriqués suivant un certain ordre. Des centaines d’algorithmes ont été créés dans le but de résoudre ce problème. Ce n’est pas facile : le nombre de possibilités croit de façon factorielle en fonction du nombre de tâches. A partir de 64 tâches une calculatrice normale affiche un dépassement de capacité.
on peut citer le PERT pour les projets,
dans l’ordre d’arrivée,
par la date de livraison,
dans l’ordre de la marge minimale,
l’algorithme de Jhonson…
on peut aussi suivre simplement les calculs concernant les files d'attente pour dimensionner le nombre de postes à mettre en oeuvre.
Exemples d’ordonnancements
le PERT :
ici a avant d, a et b avant c, c et d avant e :
chemin critique (a, d, e)
Jhonson sur deux machines
durées des tâches a(4,2) b(6,2) c(8,6) d(4,8) e(2,2)
rappel l’algorithme consiste à positionner
en premier la fabrication demandant le moins de temps sur la première machine
en dernier la fabrication demandant le moins de temps sur la seconde machine
cet algorithme minimise le temps qu’il faut pour effectuer l’ensemble des tâches
La méthode OPT
Elle est basée sur l’idée de faire passer un flux maximum à travers l’usine dans sa globalité. On s’attache pour cela à découvrir les postes formant un goulot d’étranglement. Une fois ces postes (G) démasqués on organise la production en fonction de ceux-ci.
si un poste précède un poste G le faire travailler au maximum ne va pas aider la production de l’usine. La conséquence unique sera un stock au pied de la machine G
un poste en aval de G ne pourra de toute façon travailler que si G fait des pièces
si un poste qui n’est pas dans la chaîne de G travaille trop le stock se retrouvera au montage.
veiller à faire une bonne maintenance sur G
visualisation de l’usine OPT
Un atelier simulé par la méthode OPT représente un flux
De ces quelques constatations on peut aussi tirer des leçons comme :
faire un contrôle préalable pour ne pas faire travailler G pour rien
faire attention aux pièces produites par G pour qu’il n’ait pas travaillé pour rien
La prise en compte des contraintes
Il existe principalement deux types de contraintes entre différentes tâches. Ce sont les contraintes ensemblistes et les contraintes potentielles.
- Les contraintes ensemblistes : (a, b, c) doivent être faites à la suite : six possibilités (abc, acb, bac, bca, cab, cba)
les contraintes ensemblistes peuvent recouvrir des choix du type- faire ensemble des pièces qui doivent subir le même traitement,
- faire ensemble des pièces qui sont destinées à la même commande
- les autres contraintes sont dites potentielles : a doit être réalisé avant b
les contraintes potentielles sont souvent dues à des gammes opératoires. Elles peuvent être imposées pour tenir compte d’une étape déjà effectuée.
la gestion des contraintes
l’exemple va porter sur 15 tâches ayant les contraintes suivantes :
a,b,c,d,e,f,g à effectuer ensemble
e, f, g, h, i, j à effectuer ensemble
ici les 10 tâches ne peuvent être exécutées que de gauche à droite ou de droite à gauche
c avant g : les 10 tâches ne peuvent plus être parcourues que de gauche à droite
a avant k et k avant i : trop de contraintes Pb
L'outil de modélisation de ces contraintes est le PQR arbre. Il permet de restreindre la liste des ordonnancements à tester aux ordonnancements vérifiant les contraintes.
L’algorithme génétique
Dans le cadre de l’ordonnancement l’utilisation de l’algorithme génétique est un bon exemple. La durée pour faire un ensemble de tâches n’est pas une fonction linéaire mais plutôt une fonction en escalier (racourcissement du délai si même outillage). D’autre part la prise en compte des contraintes par l’algorithme utilisé fabrique une structure que l’on peut coder efficacement sous forme de génome.
Les applications sur ce génome sont :
- le mariage (crossing over)
- la mutation
- la génération spontanée
Divers paramètres et variantes existent pour chaque application
La fonction d’évaluation
L’algorithme génétique choisit entre différents éléments d’une population lequel est le meilleur. Pour ce faire chaque ordonnancement correspondant doit être évalué.
J’ai parlé de la méthode OPT pour un autre avantage que ceux précédemment cités : en se focalisant sur le poste G on peut déterminer la date de fin d’une tâche. Après chacun peut évaluer un ordonnancement selon ces dates et ainsi choisir le meilleur selon ses critères.
comment valoriser un ordonnancement
une entreprise recherche un ordonnancement qui lui assurera le meilleur profit.
Cependant chaque entreprise est unique et les critères à prendre en compte sont votre choix.
Les seules caractériqtiques communes à tous les ordonnancements c’est que la fonction de valorisation est très complexe.
en effet l’inversion de deux tâches dans un ordonnancement peut allonger le délai final de manière non négligeable
on peut par exemple calculer :
le nombre de commandes fabriquées à temps
le chiffre d’affaire fabriqué à temps
le délai total pour effectuer toutes les tâches
les commandes en retard qu’il faudra livrer en service rapide
les commandes très en retard que l’on va perdre
la production très en avance qu’il va falloir stocker
le nombre de changement d’outils sur une presse…
Conclusion
La démarche proposée est efficace tout simplement parce qu’elle est le fruit de recherches sérieuses mais aussi parcequ’à chaque étape elle part de vous :
une modélisation spécifique de votre usine
la prise en compte de vos contraintes
la détermination d’ordonnancements suivant votre méthode d’évaluation
le choix de votre ordonnancement parmi une liste des meilleurs trouvés par un algorithme performant l’algorithme génétique.
la prestation
- Analyse des flux dans votre atelier afin de modéliser celui-ci.
- Réception des contraintes ensemblistes et potentielles et traitement de celles-ci pour établir la famille des ordonnancements possibles
- avec cette liste préparation des paramètres de l’algorithme génétique
- transmission sur un tableur de ces paramètres
- deux possibilités d’exploitation :
- à partir de vos indications je créée une fonction d’évaluation et vous transmets la liste des meilleurs ordonnancements trouvés
- je vous transmets le tableau et vous installez vous-même votre fonction (confidentialité... )
