Ordonnancement d’atelier :
Les PQR arbres
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é.
Un nouvel ordonnancement utilisant la méthode OPT les PQR arbres et les algorithmes génétiques
Algorithme hongrois (Konig Egervary). Affectation de personnes à des tâches avec minimisation du coût total.
présentez moi
votre projet
Origine
Les PQR arbres ont eu pour première utilisation l'informatique. En particulier le stockage des données sur bandes. Le problème étant qu'une bande étant lue de manière séquentielle il est utile (pour minimiser les temps d'accès) de stocker les unes à la suite des autres les informations utiles à une requête.
Exemple
Soit la base de données suivante :
| prénom | âge |
| Pierre | 15 |
| Sylvain | 20 |
| Eliane | 12 |
| Stéphanie | 32 |
| Marie | 21 |
Et les requêtes suivantes
Personnes de moins de 20 ans : Pierre et Eliane
| prénom | âge |
| Pierre | 15 |
| Eliane | 12 |
| Sylvain | 20 |
| Stéphanie | 32 |
| Marie | 21 |
Personnes ayant un nom commençant par S : Sylvain et Stéphanie
pas de changement.
Filles triées par âge : Eliane Marie et Stéphanie.
| prénom | âge |
| Pierre | 15 |
| Eliane | 12 |
| Marie | 21 |
| Stéphanie | 32 |
| Sylvain | 20 |
On voit qu'en rangeant les enregistrement dans cet ordre on peut sortir les enregistrements relatifs à une requête en un seul passage. Cet ordre répond à 4 contraintes : trois contraintes ensemblistes et une contrainte d'ordre (potentielle). Pour trouver cet ordre qui n'est pas évident Les PQR arbres ont été trouvés comme étant un outil très puissant. Ils permettent de vérifier s'il existe des possibilités de ranger les données en respectant les contraintes. Ils permettent de présenter ces solutions sous forme d'arbre.
La transposition dans l'atelier est simple puisqu'il suffit d'utiliser la correspondance
enregistrement<--> tâche
enregistrements triés <--->contrainte de gamme
requête <---->contrainte de grouppe (ensemblistes)
Les différentes sortes de noeuds
Un PQR arbre est constitué de trois types de noeuds : P, Q, R
Le noeud P symbolisé par un point : tous ses fils peuvent être mis dans n'importe quel ordre, tout en respectant les contraintes.
Le noeud Q symbolisé par un rectangle : il peut être parcourru soit dans un sens soit dans l'autre, tout en respectant les contraintes.
Le noeud R symbolisé par un rectangle orienté par une flèche : il peut être parcourru dans un seul sens, c'est une relation d'ordre total.
Utilisation sur l'exemple précédent
Au départ il n'y a pas de contrainte on peut mettre les enregistrements dans n'importe quel ordre (5! =120 solutions):
Première contrainte personnes ayant moins de 20 ans Pierre et Eliane :
nb possibilités 4!*2!=48.
Contrainte suivante : Personnes ayant un nom commençant par S : Sylvain et Stéphanie
nb solutions 3!*2!*2!=24.
Contrainte suivante : les filles Stéphanie, Marie, Eliane.
deux possibilités
Dernière contrainte : trier les filles par âge croissant Eliane<Marie<Stéphanie
Une seule solution.
Conclusion
On voit que la prise en compte de contraites permet de diminuer le nombre d'ordres possibles. Dans le cadre de la planification cela permet de ramener un problème à une dimension calculable. De plus cet abre est modélisables plus facilement pour l'utilisation des algorithmes génétiques.
La prise en compte d'une nouvelle contrainte se fait selon des règles précises.
